[][src]Crate rpds

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:

[dependencies]
rpds = "<version>"

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

List documentation

Your classic functional list.

Example

use rpds::List;

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

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

let a_list = list.push_front("a");

assert_eq!(a_list.first(), Some(&"a"));

let list_dropped = a_list.drop_first().unwrap();

assert_eq!(list_dropped, list);

Vector

Vector documentation

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

Example

use rpds::Vector;

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

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

let screaming_vector = vector
    .drop_last().unwrap()
    .push_back("VECTOR!!!");

assert_eq!(screaming_vector[2], "VECTOR!!!");

Stack

Stack documentation

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

Example

use rpds::Stack;

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

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

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

assert_eq!(a_stack.peek(), Some(&"a"));

let stack_popped = a_stack.pop().unwrap();

assert_eq!(stack_popped, stack);

Queue

Queue documentation

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

Example

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();

assert_eq!(queue_dequeued.peek(), Some(&"dois"));

HashTrieMap

HashTrieMap documentation

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

Example

use rpds::HashTrieMap;

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

assert_eq!(map_en.get(&1), Some(&"one"));

let map_pt = map_en
    .insert(1, "um")
    .insert(2, "dois");

assert_eq!(map_pt.get(&2), Some(&"dois"));

let map_pt_binary = map_pt.remove(&2);

assert_eq!(map_pt_binary.get(&2), None);

HashTrieSet

HashTrieSet documentation

A set implemented with a HashTrieMap.

Example

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 set_positive = set_extended.remove(&"zero");

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

RedBlackTreeMap

RedBlackTreeMap documentation

A map implemented with a red-black tree.

Example

use rpds::RedBlackTreeMap;

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

assert_eq!(map_en.get(&1), Some(&"one"));

let map_pt = map_en
    .insert(1, "um")
    .insert(2, "dois");

assert_eq!(map_pt.get(&2), Some(&"dois"));

let map_pt_binary = map_pt.remove(&2);

assert_eq!(map_pt_binary.get(&2), None);

assert_eq!(map_pt_binary.first(), Some((&0, &"zero")));

RedBlackTreeSet

RedBlackTreeSet documentation

A set implemented with a RedBlackTreeMap.

Example

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 set_positive = set_extended.remove(&"zero");

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

assert_eq!(set_positive.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:

use rpds::HashTrieSet;

let mut set = HashTrieSet::new();

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

let set_0_1 = set.clone();
let set_0_1_2 = set.insert("two");

Initialization Macros

There are convenient initialization macros for all data structures:

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

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

Re-exports

pub use crate::list::List;
pub use crate::map::hash_trie_map::HashTrieMap;
pub use crate::map::red_black_tree_map::RedBlackTreeMap;
pub use crate::queue::Queue;
pub use crate::set::hash_trie_set::HashTrieSet;
pub use crate::set::red_black_tree_set::RedBlackTreeSet;
pub use crate::stack::Stack;
pub use crate::vector::Vector;

Modules

list
map
queue
set
stack
vector

Macros

ht_map

Creates a HashTrieMap containing the given arguments:

ht_set

Creates a HashTrieSet containing the given arguments:

list

Creates a List containing the given arguments:

queue

Creates a Queue containing the given arguments:

rbt_map

Creates a RedBlackTreeMap containing the given arguments:

rbt_set

Creates a RedBlackTreeSet containing the given arguments:

stack

Creates a Stack containing the given arguments:

vector

Creates a Vector containing the given arguments: