skew_forest/
lib.rs

1//! An implementation of skew-binary random access lists.
2//! 
3//! Skew-binary random access lists are a persistent list data structure. They allow logarithmic
4//! time random access. Most notably, online lowest common ancestors can be implemented in
5//! logarithmic time in the length of the path.
6//! 
7//! These lists are *persistent*, i.e. they allow preserving the old version of itself when mutated
8//! Eg. consider a simple list like this:
9//! 
10//! ```text
11//! A - B - C - D    List: ABCD
12//! ```
13//! 
14//! If, after B, we clone the list and append `E` and `F`, we will get the resulting structure:
15//! 
16//! ```text
17//! A - B - C - D    First list: ABCD
18//!       \ 
19//!         E - F    Second list: ABEF
20//! ```
21//! 
22//! Here we can see how `A` and `B` will be shared among the two lists. Thus the "lists" in skew-
23//! binary random access lists can really be seen as paths in a tree instead. To emphasize this,
24//! this implmentations refers to skew-binary random access lists as paths, or more specifically
25//! as the `SkewPath` type.
26//! 
27//! Since we want to be able to share nodes, the paths themselves do not own the nodes. Instead, the
28//! paths are indexes into a structure that *does* own the nodes. This structure, the `SkewForest`,
29//! encapsulates the shared graph of the paths.
30//! 
31//! # Topology
32//! 
33//! An additional wrinkle is that the `SkewForest` and `SkewPath` in this implementation does not
34//! store any actual values. They *only* store the path topology, i.e. the sequence of node indexes
35//! that forms the nodes of a path. When `push` operation is called on a `SkewPath` the index of the
36//! node is returned.
37//! 
38//! To actually associate a value with a node, a `SkewMap` can be constructed to map these indices
39//! to values.
40//! 
41//! # Example
42//! 
43//! The example below demonstrates creating two lists as shown above.
44//! 
45//! ```
46//! use skew_forest::{SkewForest, SkewPath, SkewPathNode, SkewMap};
47//!
48//! let mut forest = SkewForest::default();
49//! let mut path_a = SkewPath::<[SkewPathNode; 8]>::default();
50//! 
51//! // Push A and B onto `path_a`
52//! let node_a = forest.push(&mut path_a);
53//! let node_b = forest.push(&mut path_a);
54//! 
55//! // Clone A to B
56//! let mut path_b = path_a.clone();
57//! 
58//! // Push C and D onto `path_a`
59//! let node_c = forest.push(&mut path_a);
60//! let node_d = forest.push(&mut path_a);
61//! 
62//! // Push E and F onto `path_b`
63//! let node_e = forest.push(&mut path_b);
64//! let node_f = forest.push(&mut path_b);
65//! 
66//! // Check that `path_a` matches ABCD
67//! assert_eq!(
68//!     forest.iter(&path_a).collect::<Vec<_>>(),
69//!     vec![node_a, node_b, node_c, node_d],
70//! );
71//! 
72//! // Check that `path_b` matches ABCD
73//! assert_eq!(
74//!     forest.iter(&path_b).collect::<Vec<_>>(),
75//!     vec![node_a, node_b, node_e, node_f],
76//! );
77//! ```
78
79mod bits;
80mod forest;
81mod map;
82
83pub use forest::*;
84pub use map::*;
skew_forest/lib.rs

skew_forest/
lib.rs
