Crate rpds [−] [src]
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>"
Additionally, add this to your crate root:
#[macro_use] 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
[dependencies]
rpds = { version = "<version>", features = ["serde"] }
Data Structures
This crate implements the following data structures:
List
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
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
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
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
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
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
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
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"));
Re-exports
pub use sequence::list::List; |
pub use sequence::vector::Vector; |
pub use stack::Stack; |
pub use queue::Queue; |
pub use map::hash_trie_map::HashTrieMap; |
pub use set::hash_trie_set::HashTrieSet; |
pub use map::red_black_tree_map::RedBlackTreeMap; |
pub use set::red_black_tree_set::RedBlackTreeSet; |
Modules
map | |
queue | |
sequence | |
set | |
stack |
Macros
ht_map |
Creates a |
ht_set |
Creates a |
list |
Creates a |
queue |
Creates a |
rbt_map |
Creates a |
rbt_set |
Creates a |
stack |
Creates a |
vector |
Creates a |