1 | use super::node::{ForceResult::*, Root}; |
2 | use super::search::SearchResult::*; |
3 | use core::alloc::Allocator; |
4 | use core::borrow::Borrow; |
5 | |
6 | impl<K, V> Root<K, V> { |
7 | /// Calculates the length of both trees that result from splitting up |
8 | /// a given number of distinct key-value pairs. |
9 | pub fn calc_split_length( |
10 | total_num: usize, |
11 | root_a: &Root<K, V>, |
12 | root_b: &Root<K, V>, |
13 | ) -> (usize, usize) { |
14 | let (length_a, length_b); |
15 | if root_a.height() < root_b.height() { |
16 | length_a = root_a.reborrow().calc_length(); |
17 | length_b = total_num - length_a; |
18 | debug_assert_eq!(length_b, root_b.reborrow().calc_length()); |
19 | } else { |
20 | length_b = root_b.reborrow().calc_length(); |
21 | length_a = total_num - length_b; |
22 | debug_assert_eq!(length_a, root_a.reborrow().calc_length()); |
23 | } |
24 | (length_a, length_b) |
25 | } |
26 | |
27 | /// Split off a tree with key-value pairs at and after the given key. |
28 | /// The result is meaningful only if the tree is ordered by key, |
29 | /// and if the ordering of `Q` corresponds to that of `K`. |
30 | /// If `self` respects all `BTreeMap` tree invariants, then both |
31 | /// `self` and the returned tree will respect those invariants. |
32 | pub fn split_off<Q: ?Sized + Ord, A: Allocator + Clone>(&mut self, key: &Q, alloc: A) -> Self |
33 | where |
34 | K: Borrow<Q>, |
35 | { |
36 | let left_root = self; |
37 | let mut right_root = Root::new_pillar(left_root.height(), alloc.clone()); |
38 | let mut left_node = left_root.borrow_mut(); |
39 | let mut right_node = right_root.borrow_mut(); |
40 | |
41 | loop { |
42 | let mut split_edge = match left_node.search_node(key) { |
43 | // key is going to the right tree |
44 | Found(kv) => kv.left_edge(), |
45 | GoDown(edge) => edge, |
46 | }; |
47 | |
48 | split_edge.move_suffix(&mut right_node); |
49 | |
50 | match (split_edge.force(), right_node.force()) { |
51 | (Internal(edge), Internal(node)) => { |
52 | left_node = edge.descend(); |
53 | right_node = node.first_edge().descend(); |
54 | } |
55 | (Leaf(_), Leaf(_)) => break, |
56 | _ => unreachable!(), |
57 | } |
58 | } |
59 | |
60 | left_root.fix_right_border(alloc.clone()); |
61 | right_root.fix_left_border(alloc); |
62 | right_root |
63 | } |
64 | |
65 | /// Creates a tree consisting of empty nodes. |
66 | fn new_pillar<A: Allocator + Clone>(height: usize, alloc: A) -> Self { |
67 | let mut root = Root::new(alloc.clone()); |
68 | for _ in 0..height { |
69 | root.push_internal_level(alloc.clone()); |
70 | } |
71 | root |
72 | } |
73 | } |
74 | |