1 use super::merge_iter::MergeIterInner; 2 use super::node::{self, Root}; 3 use core::alloc::Allocator; 4 use core::iter::FusedIterator; 5 6 impl<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. append_from_sorted_iters<I, A: Allocator + Clone>( &mut self, left: I, right: I, length: &mut usize, alloc: A, ) where K: Ord, I: Iterator<Item = (K, V)> + FusedIterator,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. bulk_push<I, A: Allocator + Clone>(&mut self, iter: I, length: &mut usize, alloc: A) where I: Iterator<Item = (K, V)>,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 94 struct MergeIter<K, V, I: Iterator<Item = (K, V)>>(MergeIterInner<I>); 95 96 impl<K: Ord, V, I> Iterator for MergeIter<K, V, I> 97 where 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. next(&mut self) -> Option<(K, V)>103 fn next(&mut self) -> Option<(K, V)> { 104 let (a_next, b_next) = self.0.nexts(|a: &(K, V), b: &(K, V)| K::cmp(&a.0, &b.0)); 105 b_next.or(a_next) 106 } 107 } 108