1use super::merge_iter::MergeIterInner;
2use super::node::{self, Root};
3use core::alloc::Allocator;
4use core::iter::FusedIterator;
5
6impl<K, V> Root<K, V> {
7 /// Appends all key-value pairs from the union of two ascending iterators,
8 /// incrementing a `length` variable along the way. The latter makes it
9 /// easier for the caller to avoid a leak when a drop handler panicks.
10 ///
11 /// If both iterators produce the same key, this method drops the pair from
12 /// the left iterator and appends the pair from the right iterator.
13 ///
14 /// If you want the tree to end up in a strictly ascending order, like for
15 /// a `BTreeMap`, both iterators should produce keys in strictly ascending
16 /// order, each greater than all keys in the tree, including any keys
17 /// already in the tree upon entry.
18 pub fn append_from_sorted_iters<I, A: Allocator + Clone>(
19 &mut self,
20 left: I,
21 right: I,
22 length: &mut usize,
23 alloc: A,
24 ) where
25 K: Ord,
26 I: Iterator<Item = (K, V)> + FusedIterator,
27 {
28 // We prepare to merge `left` and `right` into a sorted sequence in linear time.
29 let iter = MergeIter(MergeIterInner::new(left, right));
30
31 // Meanwhile, we build a tree from the sorted sequence in linear time.
32 self.bulk_push(iter, length, alloc)
33 }
34
35 /// Pushes all key-value pairs to the end of the tree, incrementing a
36 /// `length` variable along the way. The latter makes it easier for the
37 /// caller to avoid a leak when the iterator panicks.
38 pub fn bulk_push<I, A: Allocator + Clone>(&mut self, iter: I, length: &mut usize, alloc: A)
39 where
40 I: Iterator<Item = (K, V)>,
41 {
42 let mut cur_node = self.borrow_mut().last_leaf_edge().into_node();
43 // Iterate through all key-value pairs, pushing them into nodes at the right level.
44 for (key, value) in iter {
45 // Try to push key-value pair into the current leaf node.
46 if cur_node.len() < node::CAPACITY {
47 cur_node.push(key, value);
48 } else {
49 // No space left, go up and push there.
50 let mut open_node;
51 let mut test_node = cur_node.forget_type();
52 loop {
53 match test_node.ascend() {
54 Ok(parent) => {
55 let parent = parent.into_node();
56 if parent.len() < node::CAPACITY {
57 // Found a node with space left, push here.
58 open_node = parent;
59 break;
60 } else {
61 // Go up again.
62 test_node = parent.forget_type();
63 }
64 }
65 Err(_) => {
66 // We are at the top, create a new root node and push there.
67 open_node = self.push_internal_level(alloc.clone());
68 break;
69 }
70 }
71 }
72
73 // Push key-value pair and new right subtree.
74 let tree_height = open_node.height() - 1;
75 let mut right_tree = Root::new(alloc.clone());
76 for _ in 0..tree_height {
77 right_tree.push_internal_level(alloc.clone());
78 }
79 open_node.push(key, value, right_tree);
80
81 // Go down to the right-most leaf again.
82 cur_node = open_node.forget_type().last_leaf_edge().into_node();
83 }
84
85 // Increment length every iteration, to make sure the map drops
86 // the appended elements even if advancing the iterator panicks.
87 *length += 1;
88 }
89 self.fix_right_border_of_plentiful();
90 }
91}
92
93// An iterator for merging two sorted sequences into one
94struct MergeIter<K, V, I: Iterator<Item = (K, V)>>(MergeIterInner<I>);
95
96impl<K: Ord, V, I> Iterator for MergeIter<K, V, I>
97where
98 I: Iterator<Item = (K, V)> + FusedIterator,
99{
100 type Item = (K, V);
101
102 /// If two keys are equal, returns the key-value pair from the right source.
103 fn next(&mut self) -> Option<(K, V)> {
104 let (a_next: Option<(K, V)>, b_next: Option<(K, V)>) = self.0.nexts(|a: &(K, V), b: &(K, V)| K::cmp(&a.0, &b.0));
105 b_next.or(optb:a_next)
106 }
107}
108