Rust Persistent Data Structures provides fully persistent data structures with structural sharing.
To use rpds add the following to your Cargo.toml:
[dependencies]
rpds = "<version>"Additionally, add this to your crate root:
#[macro_use]
extern crate rpds;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
[dependencies]
rpds = { version = "<version>", features = ["serde"] }This crate implements the following data structures:
Your classic functional list.
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);A sequence that can be indexed. The implementation is described in Understanding Persistent Vector Part 1 and Understanding Persistent Vector Part 2.
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!!!");A LIFO (last in, first out) data structure. This is just a List in disguise.
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);A FIFO (first in, first out) data structure.
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"));A map implemented with a hash array mapped trie. See Ideal Hash Trees for details.
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);A set implemented with a HashTrieMap.
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"));A map implemented with a red-black tree.
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")));A set implemented with a RedBlackTreeMap.
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"));