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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
use alloc::vec::Vec;
use super::traits::{BalancedLeaf, Leaf};
use super::{Arc, Inode, Lnode, Node, Tree};
/// An incremental [`Tree`] builder.
#[derive(Clone)]
pub struct TreeBuilder<const ARITY: usize, L: Leaf> {
/// A stack of internal nodes.
///
/// # Invariants
///
/// - all the nodes at every stack level are internal nodes;
///
/// - all the inodes within a stack level have the same depth;
///
/// - all the vectors at every stack level have a length strictly less than
/// `ARITY` (but it could also be zero, i.e. all levels except the first
/// one can be empty);
///
/// - the inodes are grouped in order of descending depth, with each stack
/// level containing inodes of depth one less than the previous level;
///
/// - every inode at every stack level is completely full, i.e. for every
/// inode it holds `inode.leaf_count() == max_children ^ inode.depth()`;
///
/// - all the inodes in the last stack level (assuming there are any) have
/// a depth of 1.
stack: Vec<Vec<Arc<Node<ARITY, L>>>>,
/// A bunch of leaves waiting to be grouped into an internal node.
leaves: Vec<Arc<Node<ARITY, L>>>,
}
impl<const ARITY: usize, L: Leaf> Default for TreeBuilder<ARITY, L> {
#[inline]
fn default() -> Self {
Self { stack: Vec::new(), leaves: Vec::with_capacity(ARITY) }
}
}
impl<const ARITY: usize, L: Leaf> TreeBuilder<ARITY, L> {
#[inline]
pub fn append(&mut self, leaf: L) {
debug_assert!(self.leaves.len() < ARITY);
self.leaves.push(Arc::new(Node::Leaf(Lnode::from(leaf))));
if self.leaves.len() < ARITY {
return;
}
let mut inode = Arc::new(Node::Internal(Inode::from_children(
self.leaves.drain(..),
)));
let mut stack_idx = match self.stack.len() {
0 => {
let mut first_level = Vec::with_capacity(ARITY);
first_level.push(inode);
self.stack.push(first_level);
return;
},
n => n - 1,
};
loop {
let stack_level = &mut self.stack[stack_idx];
debug_assert!(
stack_level.is_empty()
|| stack_level[0].depth() == inode.depth()
);
debug_assert!(stack_level.len() < ARITY);
stack_level.push(inode);
if stack_level.len() < ARITY {
return;
}
inode = Arc::new(Node::Internal(Inode::from_children(
stack_level.drain(..),
)));
if stack_idx == 0 {
stack_level.push(inode);
self.stack.push(Vec::with_capacity(ARITY));
#[cfg(debug_assertions)]
for level in &self.stack[1..] {
debug_assert!(level.is_empty());
}
return;
} else {
stack_idx -= 1;
}
}
}
/// Completes the build and outputs the final `Tree`, consuming `self`.
#[inline]
pub fn build(mut self) -> Tree<ARITY, L>
where
L: Default + BalancedLeaf + Clone,
{
if self.stack.is_empty() {
if self.leaves.is_empty() {
// No internal nodes on the stack and no leaves, this means
// that `append` has never been called and we're building an
// empty Tree. This is why we need the `Default` bound on `L`.
return Tree::default();
} else if self.leaves.len() == 1 {
return Tree { root: self.leaves.into_iter().next().unwrap() };
}
}
let mut root = if !self.leaves.is_empty() {
debug_assert!(self.leaves.len() < ARITY);
Arc::new(Node::Internal(Inode::from_children(self.leaves)))
} else {
loop {
let stack_level = self.stack.pop().unwrap();
match stack_level.len() {
0 => continue,
1 if self.stack.is_empty() => {
// The stack is now empty and there was a single node
// in its first level. That node is the root.
break stack_level.into_iter().next().unwrap();
},
_ => {
break Arc::new(Node::Internal(Inode::from_children(
stack_level,
)));
},
}
}
};
while let Some(mut stack_level) = self.stack.pop() {
debug_assert!(
stack_level.is_empty()
|| stack_level[0].depth() == root.depth()
);
debug_assert!(stack_level.len() < ARITY);
stack_level.push(root);
root = Arc::new(Node::Internal(Inode::from_children(stack_level)));
}
{
// The only way the root can be a leaf node is if the stack is
// empty and `self.leaves` contains a single leaf, and that case
// was handled at the start of this function.
let root = Arc::get_mut(&mut root).unwrap().get_internal_mut();
root.balance_right_side();
}
Node::replace_with_single_child(&mut root);
Tree { root }
}
#[allow(dead_code)]
#[inline]
pub fn new() -> Self {
Self::default()
}
}