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;
Data Structures
This crate offers 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"));
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 list::List; |
pub use map::hash_trie_map::HashTrieMap; |
pub use map::red_black_tree_map::RedBlackTreeMap; |
pub use queue::Queue; |
pub use set::hash_trie_set::HashTrieSet; |
pub use set::red_black_tree_set::RedBlackTreeSet; |
pub use stack::Stack; |
pub use vector::Vector; |
Modules
list | |
map | |
queue | |
set | |
stack | |
vector |
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 |