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
:
[]
= "<version>"
Additionally, add this to your crate root:
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
[]
= { = "<version>", = ["serde"] }
Data Structures
This crate implements the following data structures:
List
Your classic functional list.
Example
use List;
let list = new.push_front;
assert_eq!;
let a_list = list.push_front;
assert_eq!;
let list_dropped = a_list.drop_first.unwrap;
assert_eq!;
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 Vector;
let vector = new
.push_back
.push_back
.push_back;
assert_eq!;
let screaming_vector = vector
.drop_last.unwrap
.push_back;
assert_eq!;
Stack
A LIFO (last in, first out) data structure. This is just a List
in disguise.
Example
use Stack;
let stack = new.push;
assert_eq!;
let a_stack = stack.push;
assert_eq!;
let stack_popped = a_stack.pop.unwrap;
assert_eq!;
Queue
A FIFO (first in, first out) data structure.
Example
use Queue;
let queue = new
.enqueue
.enqueue
.enqueue;
assert_eq!;
let queue_dequeued = queue.dequeue.unwrap;
assert_eq!;
HashTrieMap
A map implemented with a hash array mapped trie. See Ideal Hash Trees for details.
Example
use HashTrieMap;
let map_en = new
.insert
.insert;
assert_eq!;
let map_pt = map_en
.insert
.insert;
assert_eq!;
let map_pt_binary = map_pt.remove;
assert_eq!;
HashTrieSet
A set implemented with a HashTrieMap
.
Example
use HashTrieSet;
let set = new
.insert
.insert;
assert!;
let set_extended = set.insert;
assert!;
let set_positive = set_extended.remove;
assert!;
RedBlackTreeMap
A map implemented with a red-black tree.
Example
use RedBlackTreeMap;
let map_en = new
.insert
.insert;
assert_eq!;
let map_pt = map_en
.insert
.insert;
assert_eq!;
let map_pt_binary = map_pt.remove;
assert_eq!;
assert_eq!;
RedBlackTreeSet
A set implemented with a RedBlackTreeMap
.
Example
use RedBlackTreeSet;
let set = new
.insert
.insert;
assert!;
let set_extended = set.insert;
assert!;
let set_positive = set_extended.remove;
assert!;
assert_eq!;