vers_vecs/trees/mod.rs
1//! Tree data structures. Currently only the [BP][bp] tree is exposed.
2//! The trees are succinct, approaching the information-theoretic lower bound for the space complexity:
3//! They need O(n) bits to store a tree with n nodes, and theoretically o(n) extra bits to support queries.
4//! However, this is relaxed to O(n) with a factor smaller than 1 in practice.
5//!
6//! For details, see the submodules.
7
8pub mod bp;
9
10pub(crate) mod mmt;
11
12/// A trait for succinct tree data structures defining the most basic tree navigation operations.
13pub trait Tree {
14 /// A type that represents a node during tree navigation. Note that the handle is not necessarily
15 /// a contiguous index.
16 type NodeHandle;
17
18 /// Returns the root node of the tree, if the tree isn't empty.
19 /// If the tree is unbalanced, the result is meaningless.
20 fn root(&self) -> Option<Self::NodeHandle>;
21
22 /// Returns the parent of a node, if it exists.
23 /// If `node` is not a valid node handle, the result is meaningless.
24 fn parent(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;
25
26 /// Returns the left child of a node, if it exists.
27 /// If `node` is not a valid node handle, the result is meaningless.
28 fn first_child(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;
29
30 /// Returns the left sibling of a node, if it exists.
31 /// If `node` is not a valid node handle, the result is meaningless.
32 fn next_sibling(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;
33
34 /// Returns the right sibling of a node, if it exists.
35 /// If `node` is not a valid node handle, the result is meaningless.
36 fn previous_sibling(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;
37
38 /// Returns the rightmost child of a node, if it exists.
39 /// If `node` is not a valid node handle, the result is meaningless.
40 fn last_child(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;
41
42 /// Convert a node handle into a contiguous index, allowing associated data to be stored in a vector.
43 /// If `node` is not a valid node handle, the result is meaningless.
44 fn node_index(&self, node: Self::NodeHandle) -> usize;
45
46 /// Convert a contiguous index that enumerates all nodes into a node handle.
47 /// This operation is the inverse of `node_index`.
48 /// The index must be in the range `0..self.size()`.
49 ///
50 /// If the index is out of bounds, the behavior is unspecified.
51 fn node_handle(&self, index: usize) -> Self::NodeHandle;
52
53 /// Returns true if the node is a leaf.
54 /// If `node` is not a valid node handle, the result is meaningless.
55 fn is_leaf(&self, node: Self::NodeHandle) -> bool;
56
57 /// Returns the depth of the node in the tree.
58 /// The root node has depth 0.
59 /// If `node` is not a valid node handle, the result is meaningless.
60 ///
61 /// If the tree is unbalanced, the result is zero for nodes that are preceded by too many closing
62 /// parenthesis.
63 fn depth(&self, node: Self::NodeHandle) -> u64;
64
65 /// Returns the number of nodes in the tree.
66 fn size(&self) -> usize;
67
68 /// Returns true, if the tree has no nodes.
69 fn is_empty(&self) -> bool {
70 self.size() == 0
71 }
72}
73
74/// A trait for succinct tree data structures that support [`subtree_size`] queries.
75///
76/// [`subtree_size`]: SubtreeSize::subtree_size
77pub trait SubtreeSize: Tree {
78 /// Returns the number of nodes in the subtree rooted at the given node.
79 /// This includes the node itself, meaning the minimum subtree size is 1.
80 /// If the function is called on an invalid node handle, the result is meaningless.
81 ///
82 /// Returns `None` if the `node` has no closing parenthesis (in an unbalanced parenthesis
83 /// expression).
84 fn subtree_size(&self, node: Self::NodeHandle) -> Option<usize>;
85}
86
87/// A trait for succinct tree data structures that support [`is_ancestor`] queries.
88///
89/// [`is_ancestor`]: IsAncestor::is_ancestor
90pub trait IsAncestor: Tree {
91 /// Returns true if `ancestor` is an ancestor of the `descendant` node.
92 /// Note that a node is considered an ancestor of itself.
93 ///
94 /// Returns `None` if the parenthesis expression is unbalanced and `ancestor` does not have a
95 /// closing parenthesis.
96 fn is_ancestor(&self, ancestor: Self::NodeHandle, descendant: Self::NodeHandle)
97 -> Option<bool>;
98}
99
100/// A trait for succinct tree data structures that support level-order traversal.
101pub trait LevelTree: Tree {
102 /// Returns the `level`'th ancestor of the given node, if it exists. If the level is 0, `node`
103 /// is returned. If `node` is not a valid node handle, the result is meaningless.
104 fn level_ancestor(&self, node: Self::NodeHandle, level: u64) -> Option<Self::NodeHandle>;
105
106 /// Returns the next node in the level order traversal of the tree, if it exists.
107 fn level_next(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;
108
109 /// Returns the previous node in the level order traversal of the tree, if it exists.
110 fn level_prev(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;
111
112 /// Returns the leftmost node at the given level, if it exists.
113 fn level_leftmost(&self, level: u64) -> Option<Self::NodeHandle>;
114
115 /// Returns the rightmost node at the given level, if it exists.
116 fn level_rightmost(&self, level: u64) -> Option<Self::NodeHandle>;
117}
118
119/// This trait provides the functionality to build a tree by visiting its nodes in depth first
120/// search order. The caller should call [`enter_node`] for each node visited in pre-order depth-first
121/// traversal, and [`leave_node`] once the node's subtree was visited (i.e. post-order).
122///
123/// Once the full tree has been visited, the caller must call [`build`] to create an instance of the
124/// implementing tree type.
125///
126/// [`enter_node`]: TreeBuilder::enter_node
127/// [`leave_node`]: TreeBuilder::leave_node
128/// [`build`]: TreeBuilder::build
129pub trait TreeBuilder {
130 /// The tree type constructed with this interface
131 type Tree;
132
133 /// Called to create a new node in the tree builder
134 fn enter_node(&mut self);
135
136 /// Called after the subtree of a node in the tree has already been visited.
137 fn leave_node(&mut self);
138
139 /// Finalize the tree instance.
140 ///
141 /// # Errors
142 /// Returns `Err(excess)` if the constructed tree is invalid
143 /// (i.e. there are nodes for which [`leave_node`] has not been called,
144 /// or there are more calls to `leave_node` than to [`enter_node`];
145 /// the number of extraneous calls to `enter_node` is returned in the error).
146 ///
147 /// [`leave_node`]: Self::leave_node
148 /// [`enter_node`]: Self::enter_node
149 fn build(self) -> Result<Self::Tree, i64>;
150}