Rust Persistent Data Structures

Rust Persistent Data Structures provides fully persistent data structures with structural sharing.

Setup

To use rpds add the following to your Cargo.toml:

toml [dependencies] rpds = "<version>"

Additionally, add this to your crate root:

```rust,ignore

[macro_use]

extern crate rpds; ```

Data Structures

This crate offers the following data structures:

1. List
2. Vector
3. Stack
4. Queue
5. HashTrieMap
6. HashTrieSet
7. RedBlackTreeMap
8. RedBlackTreeSet

List

Your classic functional list.

Example

```rust use rpds::List;

let list = List::new().push_front("list");

assert_eq!(list.first(), Some(&"list"));

let alist = list.pushfront("a");

asserteq!(alist.first(), Some(&"a"));

let listdropped = alist.drop_first().unwrap();

asserteq!(listdropped, list); ```

Vector

A sequence that can be indexed. The implementation is described in Understanding Persistent Vector Part 1 and Understanding Persistent Vector Part 2.

Example

```rust use rpds::Vector;

let vector = Vector::new() .pushback("I’m") .pushback("a") .push_back("vector");

assert_eq!(vector[1], "a");

let screamingvector = vector .droplast().unwrap() .push_back("VECTOR!!!");

asserteq!(screamingvector[2], "VECTOR!!!"); ```

Stack

A LIFO (last in, first out) data structure. This is just a List in disguise.

Example

```rust use rpds::Stack;

let stack = Stack::new().push("stack");

assert_eq!(stack.peek(), Some(&"stack"));

let a_stack = stack.push("a");

asserteq!(astack.peek(), Some(&"a"));

let stackpopped = astack.pop().unwrap();

asserteq!(stackpopped, stack); ```

Queue

A FIFO (first in, first out) data structure.

Example

```rust use rpds::Queue;

let queue = Queue::new() .enqueue("um") .enqueue("dois") .enqueue("tres");

assert_eq!(queue.peek(), Some(&"um"));

let queue_dequeued = queue.dequeue().unwrap();

asserteq!(queuedequeued.peek(), Some(&"dois")); ```

HashTrieMap

A map implemented with a hash array mapped trie. See Ideal Hash Trees for details.

Example

```rust use rpds::HashTrieMap;

let map_en = HashTrieMap::new() .insert(0, "zero") .insert(1, "one");

asserteq!(mapen.get(&1), Some(&"one"));

let mappt = mapen .insert(1, "um") .insert(2, "dois");

asserteq!(mappt.get(&2), Some(&"dois"));

let mapptbinary = map_pt.remove(&2);

asserteq!(mappt_binary.get(&2), None); ```

HashTrieSet

A set implemented with a HashTrieMap.

Example

```rust use rpds::HashTrieSet;

let set = HashTrieSet::new() .insert("zero") .insert("one");

assert!(set.contains(&"one"));

let set_extended = set.insert("two");

assert!(set_extended.contains(&"two"));

let setpositive = setextended.remove(&"zero");

assert!(!set_positive.contains(&"zero")); ```

RedBlackTreeMap

A map implemented with a red-black tree.

Example

```rust use rpds::RedBlackTreeMap;

let map_en = RedBlackTreeMap::new() .insert(0, "zero") .insert(1, "one");

asserteq!(mapen.get(&1), Some(&"one"));

let mappt = mapen .insert(1, "um") .insert(2, "dois");

asserteq!(mappt.get(&2), Some(&"dois"));

let mapptbinary = map_pt.remove(&2);

asserteq!(mappt_binary.get(&2), None);

asserteq!(mappt_binary.first(), Some((&0, &"zero"))); ```

RedBlackTreeSet

A set implemented with a RedBlackTreeMap.

Example

```rust use rpds::RedBlackTreeSet;

let set = RedBlackTreeSet::new() .insert("zero") .insert("one");

assert!(set.contains(&"one"));

let set_extended = set.insert("two");

assert!(set_extended.contains(&"two"));

let setpositive = setextended.remove(&"zero");

assert!(!set_positive.contains(&"zero"));

asserteq!(setpositive.first(), Some(&"one")); ```

Other Features

Mutable Methods

When you change a data structure you often do not need its previous versions. For those cases rpds offers you mutable methods which are generally faster:

```rust use rpds::HashTrieSet;

let mut set = HashTrieSet::new();

set.insertmut("zero"); set.insertmut("one");

let set01 = set.clone(); let set01_2 = set.insert("two"); ```

Initialization Macros

There are convenient initialization macros for all data structures:

```rust use rpds::*;

let vector = vector![3, 1, 4, 1, 5]; let map = ht_map!["orange" => "orange", "banana" => "yellow"]; ```

Check the documentation for initialization macros of other data structures.

Serialization

We support serialization through serde. To use it enable the serde feature. To do so change the rpds dependency in your Cargo.toml to

toml [dependencies] rpds = { version = "<version>", features = ["serde"] }