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