Mercurial > lbo > hg > btreex
changeset 11:b3cd822e1983 default tip
Better deletion but still with crucial bug
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sat, 09 Jul 2022 15:40:10 -0700 |
parents | eec91e90ede7 |
children | |
files | src/lib.rs |
diffstat | 1 files changed, 167 insertions(+), 19 deletions(-) [+] |
line wrap: on
line diff
--- a/src/lib.rs Fri Jul 08 22:54:56 2022 -0700 +++ b/src/lib.rs Sat Jul 09 15:40:10 2022 -0700 @@ -2,7 +2,7 @@ use std::cmp::Ordering; // Min. order: 3 -const ORDER: usize = 5; +const ORDER: usize = 4; #[derive(Debug)] struct Node<T> { @@ -359,7 +359,172 @@ pub fn delete(&mut self, entry: &T) -> Option<T> { match self.find_from(self.root, entry) { None => None, - Some((_, node, nodeentry)) => self.delete_recursive(self.root, Some(entry), None), + Some((_, node, nodeentry)) => { + let d = self.yank(self.root, entry); + d + } + } + } + + // Yank-Refill-Rebalance strategy: + // 1. find element and remove it, leaving a hole in a node. + // 2. Fill hole by removing an element from one of the children, creating a new hole below. + // Recursively bubble down the whole until a leaf is reached. + // 3. Rebalance: check if either child is below half capacity and rotate or merge nodes. + + fn yank(&mut self, node: usize, entry: &T) -> Option<T> { + println!("yank {}", node); + for i in 0..ORDER-1 { + if let Some(val) = self.get(node, i) { + match Cmp::cmp(entry, val) { + Ordering::Less => { + let d = self.yank(self.get_child(node, i).unwrap(), entry); + self.rebalance(node, i); + return d; + }, + Ordering::Equal => { + let d = self.pop(node, i); + self.rebalance(node, i); + return d; + }, + Ordering::Greater => { + // Last element or no more entries + if i == ORDER-2 || self.get(node, i+1).is_none() { + let d = self.yank(self.get_child(node, i+1).unwrap(), entry); + self.rebalance(node, i); + return d; + } else { + continue + } + } + } + } + } + None + } + + // Fill hole in node at entryix by rotating or merging children's elements. + fn pop(&mut self, node: usize, entryix: usize) -> Option<T> { + println!("pop {}/{}", node, entryix); + if self.is_leaf(node) { + let d = self.get_mut(node, entryix).take(); + for i in entryix..ORDER-2 { + *self.get_mut(node, i) = self.get_mut(node, i+1).take(); + } + return d; + } + // Invariant: every entry has two children unless in leaf node. + let (left, right) = (self.get_child(node, entryix).unwrap(), self.get_child(node, entryix+1).unwrap()); + let (leftcount, rightcount) = (self.count_in(left), self.count_in(right)); + // Replace with element from fuller child. + let d = self.get_mut(node, entryix).take(); + if leftcount > rightcount { + *self.get_mut(node, entryix) = self.pop(left, leftcount-1); + } else { + *self.get_mut(node, entryix) = self.pop(right, 0); + } + // TODO: illegal "crossing"! + d + } + + fn rebalance(&mut self, node: usize, entryix: usize) { + if self.is_leaf(node) { + return; + } + println!("rebalance {}/{}", node, entryix); + let (left, right) = (self.get_child(node, entryix).unwrap(), self.get_child(node, entryix+1).unwrap()); + let (leftcount, rightcount) = (self.count_in(left), self.count_in(right)); + if leftcount >= ORDER/2 && rightcount >= ORDER/2 { + return; + } + assert!(leftcount < ORDER-1 || rightcount < ORDER-1); + // Merge or rotate? + if leftcount + rightcount + 1 > ORDER-1 { + assert!(leftcount >= ORDER/2 || rightcount >= ORDER/2); + // Rotate + let piv = self.get_mut(node, entryix).take(); + if leftcount > rightcount { + // Move one element from left to right child. + println!("before {:?}", self.v[right]); + + *self.get_child_mut(right, ORDER-1) = self.get_child_mut(right, ORDER-2).take(); + for i in (1..ORDER-1).rev() { + // Shuffle right node. + *self.get_child_mut(right, i) = self.get_child_mut(right, i-1).take(); + *self.get_mut(right, i) = self.get_mut(right, i-1).take(); + } + *self.get_mut(right, 0) = piv; + + + *self.get_child_mut(right, 0) = self.get_child_mut(left, leftcount).take(); + *self.get_mut(node, entryix) = self.get_mut(left, leftcount-1).take(); + println!("after {:?}", self.v[right]); + } else { + println!("before {:?}", self.v[left]); + *self.get_mut(left, leftcount) = piv; + *self.get_child_mut(left, leftcount+1) = self.get_child_mut(right, 0).take(); + //*self.get_child_mut(node, entryix) = self.get_child_mut(right, 0).take(); + *self.get_mut(node, entryix) = self.get_mut(right, 0).take(); + + for i in 0..ORDER-2 { + // Shuffle right node. + *self.get_child_mut(right, i) = self.get_child_mut(right, i+1).take(); + *self.get_mut(right, i) = self.get_mut(right, i+1).take(); + } + println!("after: {:?}", self.v[left]); + *self.get_child_mut(right, ORDER-2) = self.get_child_mut(right, ORDER-1).take(); + } + } else { + // Merge + let piv = self.get_mut(node, entryix).take(); + + let mut newnode = Node::new(); + let mut count = 0; + for i in 0..ORDER-1 { + newnode.entries[i] = self.get_mut(left, i).take(); + newnode.children[i] = self.get_child_mut(left, i).take(); + if newnode.entries[i].is_none() { + break + } + count += 1; + } + // Copy right-most child + if count == ORDER-1 { + panic!("Encountered full left node in merge!"); + // newnode.children[ORDER-1] = self.get_child_mut(left, ORDER-1).take(); + } + newnode.entries[count] = piv; + count += 1; + let off = count; + for i in off..ORDER-1 { + newnode.entries[i] = self.get_mut(right, i-off).take(); + newnode.children[i] = self.get_child_mut(right, i-off).take(); + if newnode.entries[i].is_none() { + break; + } + count += 1; + } + // Copy right-most child. + newnode.children[count] = self.get_child_mut(right, count-off).take(); + + // TODO: recycle nodes. + let newnodeix = self.v.len(); + self.v.push(newnode); + + // Replace lchild-piv-rchild in `node`. + *self.get_child_mut(node, entryix) = Some(newnodeix); + for i in entryix..ORDER-2 { + *self.get_mut(node, i) = self.get_mut(node, i+1).take(); + if i > entryix { // Discard former right node. + *self.get_child_mut(node, i) = self.get_child_mut(node, i+1).take(); + } + } + *self.get_child_mut(node, ORDER-2) = self.get_child_mut(node, ORDER-1).take(); + + // Replace root if there is no active entry left. + if node == self.root && self.count_in(node) == 0 { + self.root = newnodeix; + } } } } @@ -496,21 +661,4 @@ } } } - - #[test] - fn test_binary_node_search() { - let mut bt = BTree::new(10); - for i in 0..super::ORDER/2 { - bt.insert(i); - } - - println!("{}", bt.debug_print()); - assert_eq!(bt.binary_node_search(bt.root, &19), 15); - for i in 0..super::ORDER - 1 { - assert_eq!( - bt.binary_node_search(bt.root, &i), - std::cmp::min(i, super::ORDER/2) - ); - } - } }