Mercurial > lbo > hg > btreex
changeset 8:b796dab2d3ed
First part of deletion code. Still need recursion up the tree
| author | Lewin Bormann <lbo@spheniscida.de> |
|---|---|
| date | Fri, 08 Jul 2022 18:19:38 -0700 |
| parents | bc8b8baa6d8c |
| children | 1a2cc00f6836 |
| files | src/lib.rs |
| diffstat | 1 files changed, 134 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- a/src/lib.rs Tue Jul 05 13:56:44 2022 -0700 +++ b/src/lib.rs Fri Jul 08 18:19:38 2022 -0700 @@ -79,6 +79,9 @@ fn count(&self) -> usize { self.count_from(self.root) } + fn count_in(&self, node: usize) -> usize { + self.v[node].entries.iter().filter(|e| e.is_some()).count() + } fn count_from(&self, node: usize) -> usize { let mut s = self.occupied(node); for i in 0..ORDER { @@ -90,9 +93,10 @@ } pub fn find<'a>(&'a self, value: &T) -> Option<&'a T> { - self.find_from(self.root, value) + self.find_from(self.root, value).map(|e| e.0) } - fn find_from<'a>(&'a self, node: usize, value: &T) -> Option<&'a T> { + // Returns reference to value if found, and node/entry indices. + fn find_from<'a>(&'a self, node: usize, value: &T) -> Option<(&'a T, usize, usize)> { let mut j = 0; // Break once we arrived at the entry right of the correct child, if we don't return // earlier. @@ -103,7 +107,7 @@ if j < ORDER - 1 { if let Some(el) = self.get(node, j) { if Cmp::cmp(value, el) == Ordering::Equal { - return Some(el); + return Some((el, node, j)); } } } @@ -116,7 +120,7 @@ j = i; break; } - Ordering::Equal => return Some(el), + Ordering::Equal => return Some((el, node, i)), Ordering::Greater => continue, } } else { @@ -351,6 +355,110 @@ } } } + + + pub fn delete(&mut self, entry: &T) -> Option<T> { + match self.find_from(self.root, entry) { + None => None, + Some((_, node, nodeentry)) => Some(self.delete_entry(node, nodeentry)) + } + } + + fn delete_entry(&mut self, node: usize, entry: usize) -> T { + // Entry must exist!! + if self.is_leaf(node) { + // Shift, and return. + let d = self.get_mut(node, entry).take(); + for i in entry..ORDER-1 { + *self.get_mut(node, i) = self.get_mut(node, i+1).take(); + assert!(self.get_child(node, i).is_none()); + if self.get(node, i).is_none() { + break; + } + } + // TO DO: rotate or merge. Need access to parent! + assert!(self.get_child(node, self.count_in(node)).is_none()); + return d.unwrap(); + } else { + // Non-leaf. + // Remove entry; + // rotate left or right subtree element into place by removing it from there as well. + let d = self.get_mut(node, entry).take(); + let (left, right) = (self.v[node].children[entry], self.v[node].children[entry+1]); + let (candidate, ix, need_restructure) = match (left, right) { + (Some(l), Some(r)) => { + let (leftcount, rightcount) = (self.count_in(l), self.count_in(r)); + if leftcount <= rightcount { + (r, 0, rightcount < ORDER/2) + } else { + (l, leftcount-1, leftcount < ORDER/2) + } + }, + (Some(l), None) => (l, self.count_in(l)-1, self.count_in(l) < ORDER/2), + (None, Some(r)) => panic!("Tree architecture fault: no left subchild but right subchild"), + (None, None) => panic!("delete_entry in leaf node, but expected internal node"), + }; + + // Recurse into subtree. + *self.get_mut(node, entry) = Some(self.delete_entry(candidate, ix)); + + // Merge nodes if either node is too small. + if need_restructure { + // Can we rotate into place? + if let (Some(l), Some(r)) = (left, right) { + let (leftcount, rightcount) = (self.count_in(l), self.count_in(r)); + if leftcount+rightcount > ORDER { + // Yes! + let to_move = self.get_mut(node, entry).take().unwrap(); + if leftcount < rightcount { + self.insert_into(l, to_move); + *self.get_mut(node, entry) = Some(self.delete_entry(r, 0)); + } else { + self.insert_into(r, to_move); + *self.get_mut(node, entry) = Some(self.delete_entry(l, leftcount-1)); + } + } + } else { + // Need to merge two nodes. + // Remove current entry and add it to a new node, together with left and right + // nodes' entries. + let mut newnode = Node::new(); + let mut count = 0; + + // Move elements. + let left = self.get_child(node, entry).unwrap(); + // Move left elements first. + for i in 0..ORDER-1 { + newnode.entries[i] = self.get_mut(left, i).take(); + count += 1; + } + // Move old pivot eleement. + newnode.entries[count] = self.get_mut(node, entry).take(); + count += 1; + // Move right elements. + let right = *self.get_child(node, entry+1); + if let Some(right) = right { + for i in count..ORDER-1 { + newnode.entries[i] = self.get_mut(right, i-count).take(); + count += 1; + } + } + + let newnodeix = self.v.len(); + self.v.push(newnode); + *self.get_child_mut(node, entry) = Some(newnodeix); + + // TODO!! Recycle nodes!! + for i in entry..ORDER-2 { + *self.get_mut(node, i) = self.get_mut(node, i+1).take(); + *self.get_child_mut(node, i+1) = self.get_child_mut(node, i+2).take(); + } + } + } + + return d.unwrap(); + } + } } impl<T: std::fmt::Debug, Cmp: Compare<T>> BTree<T, Cmp> { fn debug_print(&self) -> String { @@ -397,11 +505,31 @@ } #[test] + fn test_delete() { + let mut bt = BTree::new(16); + + let ns = &[ + 15, 2, 21, 35, 4, 62, 31, 27, 88, 1, 12, 45, 11, 16, 23, 20, 22, 24, 25, 26, 28, 29, + 30, 31, 32, + ]; + + for n in ns { + bt.insert(*n); + } + println!("{}", bt.debug_print()); + for e in ns { + println!("deleting {}", e); + println!("{}", bt.debug_print()); + bt.delete(e); + } + } + + #[test] fn randomized_all_reachable() { time_test::time_test!("10 x 1000 inserts"); for seed in &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] { let mut rng = StdRng::seed_from_u64(*seed); - let N = 1000; + let N = 100; let mut bt = BTree::new(N / 2); for i in 0..N { let rn = rng.next_u32(); @@ -457,7 +585,7 @@ time_test::time_test!("10 x 1000 inserts"); for seed in &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] { let mut rng = StdRng::seed_from_u64(*seed); - let N = 1000; + let N = 100; let mut bt = std::collections::BTreeSet::new(); for i in 0..N { let rn = rng.next_u32();