An implementation of skew-binary random access lists.
Skew-binary random access lists are a persistent list data structure. They allow logarithmic time random access. Most notably, online lowest common ancestors can be implemented in logarithmic time in the length of the path.
These lists are persistent, i.e. they allow preserving the old version of itself when mutated Eg. consider a simple list like this:
A - B - C - D List: ABCD
If, after B, we clone the list and append E
and F
, we will get the resulting structure:
A - B - C - D First list: ABCD
\
E - F Second list: ABEF
Here we can see how A
and B
will be shared among the two lists. Thus the "lists" in skew-
binary random access lists can really be seen as paths in a tree instead. To emphasize this,
this implmentations refers to skew-binary random access lists as paths, or more specifically
as the SkewPath
type.
Since we want to be able to share nodes, the paths themselves do not own the nodes. Instead, the
paths are indexes into a structure that does own the nodes. This structure, the SkewForest
,
encapsulates the shared graph of the paths.
An additional wrinkle is that the SkewForest
and SkewPath
in this implementation does not
store any actual values. They only store the path topology, i.e. the sequence of node indexes
that forms the nodes of a path. When push
operation is called on a SkewPath
the index of the
node is returned.
To actually associate a value with a node, a SkewMap
can be constructed to map these indices
to values.
The example below demonstrates creating two lists as shown above.
```rust use skew_forest::{SkewForest, SkewPath, SkewPathNode, SkewMap};
let mut forest = SkewForest::default(); let mut path_a = SkewPath::<[SkewPathNode; 8]>::default();
// Push A and B onto path_a
let nodea = forest.push(&mut patha);
let nodeb = forest.push(&mut patha);
// Clone A to B let mut pathb = patha.clone();
// Push C and D onto path_a
let nodec = forest.push(&mut patha);
let noded = forest.push(&mut patha);
// Push E and F onto path_b
let nodee = forest.push(&mut pathb);
let nodef = forest.push(&mut pathb);
// Check that path_a
matches ABCD
asserteq!(
forest.iter(&patha).collect::
// Check that path_b
matches ABCD
asserteq!(
forest.iter(&pathb).collect::
License: MIT