vers-vecs 1.9.1

A collection of succinct data structures supported by fast implementations of rank and select queries.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

//! Tree data structures. Currently only the [BP][bp] tree is exposed.
//! The trees are succinct, approaching the information-theoretic lower bound for the space complexity:
//! They need O(n) bits to store a tree with n nodes, and theoretically o(n) extra bits to support queries.
//! However, this is relaxed to O(n) with a factor smaller than 1 in practice.
//!
//! For details, see the submodules.

pub mod bp;

pub(crate) mod mmt;

/// A trait for succinct tree data structures defining the most basic tree navigation operations.
pub trait Tree {
    /// A type that represents a node during tree navigation. Note that the handle is not necessarily
    /// a contiguous index.
    type NodeHandle;

    /// Returns the root node of the tree, if the tree isn't empty.
    /// If the tree is unbalanced, the result is meaningless.
    fn root(&self) -> Option<Self::NodeHandle>;

    /// Returns the parent of a node, if it exists.
    /// If `node` is not a valid node handle, the result is meaningless.
    fn parent(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;

    /// Returns the left child of a node, if it exists.
    /// If `node` is not a valid node handle, the result is meaningless.
    fn first_child(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;

    /// Returns the left sibling of a node, if it exists.
    /// If `node` is not a valid node handle, the result is meaningless.
    fn next_sibling(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;

    /// Returns the right sibling of a node, if it exists.
    /// If `node` is not a valid node handle, the result is meaningless.
    fn previous_sibling(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;

    /// Returns the rightmost child of a node, if it exists.
    /// If `node` is not a valid node handle, the result is meaningless.
    fn last_child(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;

    /// Convert a node handle into a contiguous index, allowing associated data to be stored in a vector.
    /// If `node` is not a valid node handle, the result is meaningless.
    fn node_index(&self, node: Self::NodeHandle) -> usize;

    /// Convert a contiguous index that enumerates all nodes into a node handle.
    /// This operation is the inverse of `node_index`.
    /// The index must be in the range `0..self.size()`.
    ///
    /// If the index is out of bounds, the behavior is unspecified.
    fn node_handle(&self, index: usize) -> Self::NodeHandle;

    /// Returns true if the node is a leaf.
    /// If `node` is not a valid node handle, the result is meaningless.
    fn is_leaf(&self, node: Self::NodeHandle) -> bool;

    /// Returns the depth of the node in the tree.
    /// The root node has depth 0.
    /// If `node` is not a valid node handle, the result is meaningless.
    ///
    /// If the tree is unbalanced, the result is zero for nodes that are preceded by too many closing
    /// parenthesis.
    fn depth(&self, node: Self::NodeHandle) -> u64;

    /// Returns the number of nodes in the tree.
    fn size(&self) -> usize;

    /// Returns true, if the tree has no nodes.
    fn is_empty(&self) -> bool {
        self.size() == 0
    }
}

/// A trait for succinct tree data structures that support [`subtree_size`] queries.
///
/// [`subtree_size`]: SubtreeSize::subtree_size
pub trait SubtreeSize: Tree {
    /// Returns the number of nodes in the subtree rooted at the given node.
    /// This includes the node itself, meaning the minimum subtree size is 1.
    /// If the function is called on an invalid node handle, the result is meaningless.
    ///
    /// Returns `None` if the `node` has no closing parenthesis (in an unbalanced parenthesis
    /// expression).
    fn subtree_size(&self, node: Self::NodeHandle) -> Option<usize>;
}

/// A trait for succinct tree data structures that support [`is_ancestor`] queries.
///
/// [`is_ancestor`]: IsAncestor::is_ancestor
pub trait IsAncestor: Tree {
    /// Returns true if `ancestor` is an ancestor of the `descendant` node.
    /// Note that a node is considered an ancestor of itself.
    ///
    /// Returns `None` if the parenthesis expression is unbalanced and `ancestor` does not have a
    /// closing parenthesis.
    fn is_ancestor(&self, ancestor: Self::NodeHandle, descendant: Self::NodeHandle)
        -> Option<bool>;
}

/// A trait for succinct tree data structures that support level-order traversal.
pub trait LevelTree: Tree {
    /// Returns the `level`'th ancestor of the given node, if it exists. If the level is 0, `node`
    /// is returned. If `node` is not a valid node handle, the result is meaningless.
    fn level_ancestor(&self, node: Self::NodeHandle, level: u64) -> Option<Self::NodeHandle>;

    /// Returns the next node in the level order traversal of the tree, if it exists.
    fn level_next(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;

    /// Returns the previous node in the level order traversal of the tree, if it exists.
    fn level_prev(&self, node: Self::NodeHandle) -> Option<Self::NodeHandle>;

    /// Returns the leftmost node at the given level, if it exists.
    fn level_leftmost(&self, level: u64) -> Option<Self::NodeHandle>;

    /// Returns the rightmost node at the given level, if it exists.
    fn level_rightmost(&self, level: u64) -> Option<Self::NodeHandle>;
}

/// This trait provides the functionality to build a tree by visiting its nodes in depth first
/// search order. The caller should call [`enter_node`] for each node visited in pre-order depth-first
/// traversal, and [`leave_node`] once the node's subtree was visited (i.e. post-order).
///
/// Once the full tree has been visited, the caller must call [`build`] to create an instance of the
/// implementing tree type.
///
/// [`enter_node`]: TreeBuilder::enter_node
/// [`leave_node`]: TreeBuilder::leave_node
/// [`build`]: TreeBuilder::build
pub trait TreeBuilder {
    /// The tree type constructed with this interface
    type Tree;

    /// Called to create a new node in the tree builder
    fn enter_node(&mut self);

    /// Called after the subtree of a node in the tree has already been visited.
    fn leave_node(&mut self);

    /// Finalize the tree instance.
    ///
    /// # Errors
    /// Returns `Err(excess)` if the constructed tree is invalid
    /// (i.e. there are nodes for which [`leave_node`] has not been called,
    /// or there are more calls to `leave_node` than to [`enter_node`];
    /// the number of extraneous calls to `enter_node` is returned in the error).
    ///
    /// [`leave_node`]: Self::leave_node
    /// [`enter_node`]: Self::enter_node
    fn build(self) -> Result<Self::Tree, i64>;
}