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
use super::map::MIN_LEN;
use super::merge_iter::MergeIterInner;
use super::node::{self, ForceResult::*, Root};
use core::iter::FusedIterator;
impl<K, V> Root<K, V> {
pub fn append_from_sorted_iters<I>(&mut self, left: I, right: I, length: &mut usize)
where
K: Ord,
I: Iterator<Item = (K, V)> + FusedIterator,
{
let iter = MergeIter(MergeIterInner::new(left, right));
self.bulk_push(iter, length)
}
fn bulk_push<I>(&mut self, iter: I, length: &mut usize)
where
I: Iterator<Item = (K, V)>,
{
let mut cur_node = self.borrow_mut().last_leaf_edge().into_node();
for (key, value) in iter {
if cur_node.len() < node::CAPACITY {
cur_node.push(key, value);
} else {
let mut open_node;
let mut test_node = cur_node.forget_type();
loop {
match test_node.ascend() {
Ok(parent) => {
let parent = parent.into_node();
if parent.len() < node::CAPACITY {
open_node = parent;
break;
} else {
test_node = parent.forget_type();
}
}
Err(_) => {
open_node = self.push_internal_level();
break;
}
}
}
let tree_height = open_node.height() - 1;
let mut right_tree = Root::new();
for _ in 0..tree_height {
right_tree.push_internal_level();
}
open_node.push(key, value, right_tree);
cur_node = open_node.forget_type().last_leaf_edge().into_node();
}
*length += 1;
}
self.fix_right_edge();
}
fn fix_right_edge(&mut self) {
let mut cur_node = self.borrow_mut();
while let Internal(internal) = cur_node.force() {
let mut last_kv = internal.last_kv().consider_for_balancing();
let right_child_len = last_kv.right_child_len();
if right_child_len < MIN_LEN {
last_kv.bulk_steal_left(MIN_LEN - right_child_len);
}
cur_node = last_kv.into_right_child();
}
}
}
struct MergeIter<K, V, I: Iterator<Item = (K, V)>>(MergeIterInner<I>);
impl<K: Ord, V, I> Iterator for MergeIter<K, V, I>
where
I: Iterator<Item = (K, V)> + FusedIterator,
{
type Item = (K, V);
fn next(&mut self) -> Option<(K, V)> {
let (a_next, b_next) = self.0.nexts(|a: &(K, V), b: &(K, V)| K::cmp(&a.0, &b.0));
b_next.or(a_next)
}
}