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 extern crate rpds;

Enable serialization

To enable serialization (using serde) you need to enable the serde feature in rpds. To do so change the rpds dependency in Cargo.toml to

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

Data Structures

This crate implements 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")); ```