vendor/im-rc/src/nodes/btree.rs

   1 // This Source Code Form is subject to the terms of the Mozilla Public
   2 // License, v. 2.0. If a copy of the MPL was not distributed with this
   3 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
   4
   5 use std::borrow::Borrow;
   6 use std::cmp::Ordering;
   7 use std::mem;
   8 use std::ops::{Bound, RangeBounds};
   9
  10 use typenum::{Add1, Unsigned};
  11
  12 use config::OrdChunkSize as NodeSize;
  13 use nodes::sized_chunk::Chunk;
  14 use util::{clone_ref, Ref};
  15
  16 use self::Insert::*;
  17 use self::InsertAction::*;
  18
  19 const NODE_SIZE: usize = NodeSize::USIZE;
  20 const MEDIAN: usize = (NODE_SIZE + 1) >> 1;
  21
  22 pub trait BTreeValue: Clone {
  23     type Key;
  24     fn ptr_eq(&self, other: &Self) -> bool;
  25     fn search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize>
  26     where
  27         BK: Ord + ?Sized,
  28         Self::Key: Borrow<BK>;
  29     fn search_value(slice: &[Self], value: &Self) -> Result<usize, usize>;
  30     fn cmp_keys<BK>(&self, other: &BK) -> Ordering
  31     where
  32         BK: Ord + ?Sized,
  33         Self::Key: Borrow<BK>;
  34     fn cmp_values(&self, other: &Self) -> Ordering;
  35 }
  36
  37 pub struct Node<A> {
  38     keys: Chunk<A, NodeSize>,
  39     children: Chunk<Option<Ref<Node<A>>>, Add1<NodeSize>>,
  40 }
  41
  42 pub enum Insert<A> {
  43     Added,
  44     Replaced(A),
  45     Update(Node<A>),
  46     Split(Node<A>, A, Node<A>),
  47 }
  48
  49 enum InsertAction<A> {
  50     AddedAction,
  51     ReplacedAction(A),
  52     InsertAt,
  53     InsertSplit(Node<A>, A, Node<A>),
  54 }
  55
  56 pub enum Remove<A> {
  57     NoChange,
  58     Removed(A),
  59     Update(A, Node<A>),
  60 }
  61
  62 enum RemoveAction {
  63     DeleteAt(usize),
  64     PullUp(usize, usize, usize),
  65     Merge(usize),
  66     StealFromLeft(usize),
  67     StealFromRight(usize),
  68     MergeFirst(usize),
  69     ContinueDown(usize),
  70 }
  71
  72 impl<A> Clone for Node<A>
  73 where
  74     A: Clone,
  75 {
  76     fn clone(&self) -> Self {
  77         Node {
  78             keys: self.keys.clone(),
  79             children: self.children.clone(),
  80         }
  81     }
  82 }
  83
  84 impl<A> Default for Node<A> {
  85     fn default() -> Self {
  86         Node {
  87             keys: Chunk::new(),
  88             children: Chunk::unit(None),
  89         }
  90     }
  91 }
  92
  93 impl<A> Node<A>
  94 where
  95     A: Clone,
  96 {
  97     #[inline]
  98     fn has_room(&self) -> bool {
  99         self.keys.len() < NODE_SIZE
 100     }
 101
 102     #[inline]
 103     fn too_small(&self) -> bool {
 104         self.keys.len() < MEDIAN
 105     }
 106
 107     #[inline]
 108     fn is_leaf(&self) -> bool {
 109         self.children[0].is_none()
 110     }
 111
 112     #[inline]
 113     pub fn new() -> Self {
 114         Self::default()
 115     }
 116
 117     #[inline]
 118     pub fn unit(value: A) -> Self {
 119         Node {
 120             keys: Chunk::unit(value),
 121             children: Chunk::pair(None, None),
 122         }
 123     }
 124
 125     #[inline]
 126     pub fn from_split(left: Node<A>, median: A, right: Node<A>) -> Self {
 127         Node {
 128             keys: Chunk::unit(median),
 129             children: Chunk::pair(Some(Ref::from(left)), Some(Ref::from(right))),
 130         }
 131     }
 132
 133     pub fn min(&self) -> Option<&A> {
 134         match self.children.first().unwrap() {
 135             None => self.keys.first(),
 136             Some(ref child) => child.min(),
 137         }
 138     }
 139
 140     pub fn max(&self) -> Option<&A> {
 141         match self.children.last().unwrap() {
 142             None => self.keys.last(),
 143             Some(ref child) => child.max(),
 144         }
 145     }
 146 }
 147
 148 impl<A: BTreeValue> Node<A> {
 149     fn child_contains<BK>(&self, index: usize, key: &BK) -> bool
 150     where
 151         BK: Ord + ?Sized,
 152         A::Key: Borrow<BK>,
 153     {
 154         if let Some(Some(ref child)) = self.children.get(index) {
 155             child.lookup(key).is_some()
 156         } else {
 157             false
 158         }
 159     }
 160
 161     pub fn lookup<BK>(&self, key: &BK) -> Option<&A>
 162     where
 163         BK: Ord + ?Sized,
 164         A::Key: Borrow<BK>,
 165     {
 166         if self.keys.is_empty() {
 167             return None;
 168         }
 169         // Perform a binary search, resulting in either a match or
 170         // the index of the first higher key, meaning we search the
 171         // child to the left of it.
 172         match A::search_key(&self.keys, key) {
 173             Ok(index) => Some(&self.keys[index]),
 174             Err(index) => match self.children[index] {
 175                 None => None,
 176                 Some(ref node) => node.lookup(key),
 177             },
 178         }
 179     }
 180
 181     pub fn lookup_mut<BK>(&mut self, key: &BK) -> Option<&mut A>
 182     where
 183         BK: Ord + ?Sized,
 184         A::Key: Borrow<BK>,
 185     {
 186         if self.keys.is_empty() {
 187             return None;
 188         }
 189         // Perform a binary search, resulting in either a match or
 190         // the index of the first higher key, meaning we search the
 191         // child to the left of it.
 192         match A::search_key(&self.keys, key) {
 193             Ok(index) => Some(&mut self.keys[index]),
 194             Err(index) => match self.children[index] {
 195                 None => None,
 196                 Some(ref mut child_ref) => {
 197                     let child = Ref::make_mut(child_ref);
 198                     child.lookup_mut(key)
 199                 }
 200             },
 201         }
 202     }
 203
 204     pub fn path_first<'a, BK>(
 205         &'a self,
 206         mut path: Vec<(&'a Node<A>, usize)>,
 207     ) -> Vec<(&'a Node<A>, usize)>
 208     where
 209         A: 'a,
 210         BK: Ord + ?Sized,
 211         A::Key: Borrow<BK>,
 212     {
 213         if self.keys.is_empty() {
 214             return Vec::new();
 215         }
 216         match self.children[0] {
 217             None => {
 218                 path.push((self, 0));
 219                 path
 220             }
 221             Some(ref node) => {
 222                 path.push((self, 0));
 223                 node.path_first(path)
 224             }
 225         }
 226     }
 227
 228     pub fn path_last<'a, BK>(
 229         &'a self,
 230         mut path: Vec<(&'a Node<A>, usize)>,
 231     ) -> Vec<(&'a Node<A>, usize)>
 232     where
 233         A: 'a,
 234         BK: Ord + ?Sized,
 235         A::Key: Borrow<BK>,
 236     {
 237         if self.keys.is_empty() {
 238             return Vec::new();
 239         }
 240         let end = self.children.len() - 1;
 241         match self.children[end] {
 242             None => {
 243                 path.push((self, end - 1));
 244                 path
 245             }
 246             Some(ref node) => {
 247                 path.push((self, end));
 248                 node.path_last(path)
 249             }
 250         }
 251     }
 252
 253     pub fn path_next<'a, BK>(
 254         &'a self,
 255         key: &BK,
 256         mut path: Vec<(&'a Node<A>, usize)>,
 257     ) -> Vec<(&'a Node<A>, usize)>
 258     where
 259         A: 'a,
 260         BK: Ord + ?Sized,
 261         A::Key: Borrow<BK>,
 262     {
 263         if self.keys.is_empty() {
 264             return Vec::new();
 265         }
 266         match A::search_key(&self.keys, key) {
 267             Ok(index) => {
 268                 path.push((self, index));
 269                 path
 270             }
 271             Err(index) => match self.children[index] {
 272                 None => match self.keys.get(index) {
 273                     Some(_) => {
 274                         path.push((self, index));
 275                         path
 276                     }
 277                     None => Vec::new(),
 278                 },
 279                 Some(ref node) => {
 280                     path.push((self, index));
 281                     node.path_next(key, path)
 282                 }
 283             },
 284         }
 285     }
 286
 287     pub fn path_prev<'a, BK>(
 288         &'a self,
 289         key: &BK,
 290         mut path: Vec<(&'a Node<A>, usize)>,
 291     ) -> Vec<(&'a Node<A>, usize)>
 292     where
 293         A: 'a,
 294         BK: Ord + ?Sized,
 295         A::Key: Borrow<BK>,
 296     {
 297         if self.keys.is_empty() {
 298             return Vec::new();
 299         }
 300         match A::search_key(&self.keys, key) {
 301             Ok(index) => {
 302                 path.push((self, index));
 303                 path
 304             }
 305             Err(index) => match self.children[index] {
 306                 None if index == 0 => Vec::new(),
 307                 None => match self.keys.get(index - 1) {
 308                     Some(_) => {
 309                         path.push((self, index));
 310                         path
 311                     }
 312                     None => Vec::new(),
 313                 },
 314                 Some(ref node) => {
 315                     path.push((self, index));
 316                     node.path_prev(key, path)
 317                 }
 318             },
 319         }
 320     }
 321
 322     fn split(
 323         &mut self,
 324         value: A,
 325         ins_left: Option<Node<A>>,
 326         ins_right: Option<Node<A>>,
 327     ) -> Insert<A> {
 328         let left_child = ins_left.map(Ref::from);
 329         let right_child = ins_right.map(Ref::from);
 330         let index = A::search_value(&self.keys, &value).unwrap_err();
 331         let mut left_keys;
 332         let mut left_children;
 333         let mut right_keys;
 334         let mut right_children;
 335         let median;
 336         if index < MEDIAN {
 337             self.children[index] = left_child;
 338
 339             left_keys = Chunk::from_front(&mut self.keys, index);
 340             left_keys.push_back(value);
 341             left_keys.drain_from_front(&mut self.keys, MEDIAN - index - 1);
 342
 343             left_children = Chunk::from_front(&mut self.children, index + 1);
 344             left_children.push_back(right_child);
 345             left_children.drain_from_front(&mut self.children, MEDIAN - index - 1);
 346
 347             median = self.keys.pop_front();
 348
 349             right_keys = Chunk::drain_from(&mut self.keys);
 350             right_children = Chunk::drain_from(&mut self.children);
 351         } else if index > MEDIAN {
 352             self.children[index] = left_child;
 353
 354             left_keys = Chunk::from_front(&mut self.keys, MEDIAN);
 355             left_children = Chunk::from_front(&mut self.children, MEDIAN + 1);
 356
 357             median = self.keys.pop_front();
 358
 359             right_keys = Chunk::from_front(&mut self.keys, index - MEDIAN - 1);
 360             right_keys.push_back(value);
 361             right_keys.append(&mut self.keys);
 362
 363             right_children = Chunk::from_front(&mut self.children, index - MEDIAN);
 364             right_children.push_back(right_child);
 365             right_children.append(&mut self.children);
 366         } else {
 367             left_keys = Chunk::from_front(&mut self.keys, MEDIAN);
 368             left_children = Chunk::from_front(&mut self.children, MEDIAN);
 369             left_children.push_back(left_child);
 370
 371             median = value;
 372
 373             right_keys = Chunk::drain_from(&mut self.keys);
 374             right_children = Chunk::drain_from(&mut self.children);
 375             right_children[0] = right_child;
 376         }
 377
 378         debug_assert!(left_keys.len() == MEDIAN);
 379         debug_assert!(left_children.len() == MEDIAN + 1);
 380         debug_assert!(right_keys.len() == MEDIAN);
 381         debug_assert!(right_children.len() == MEDIAN + 1);
 382
 383         Split(
 384             Node {
 385                 keys: left_keys,
 386                 children: left_children,
 387             },
 388             median,
 389             Node {
 390                 keys: right_keys,
 391                 children: right_children,
 392             },
 393         )
 394     }
 395
 396     fn merge(middle: A, left: Node<A>, mut right: Node<A>) -> Node<A> {
 397         let mut keys = left.keys;
 398         keys.push_back(middle);
 399         keys.append(&mut right.keys);
 400         let mut children = left.children;
 401         children.append(&mut right.children);
 402         Node { keys, children }
 403     }
 404
 405     fn pop_min(&mut self) -> (A, Option<Ref<Node<A>>>) {
 406         let value = self.keys.pop_front();
 407         let child = self.children.pop_front();
 408         (value, child)
 409     }
 410
 411     fn pop_max(&mut self) -> (A, Option<Ref<Node<A>>>) {
 412         let value = self.keys.pop_back();
 413         let child = self.children.pop_back();
 414         (value, child)
 415     }
 416
 417     fn push_min(&mut self, child: Option<Ref<Node<A>>>, value: A) {
 418         self.keys.push_front(value);
 419         self.children.push_front(child);
 420     }
 421
 422     fn push_max(&mut self, child: Option<Ref<Node<A>>>, value: A) {
 423         self.keys.push_back(value);
 424         self.children.push_back(child);
 425     }
 426
 427     pub fn insert(&mut self, value: A) -> Insert<A> {
 428         if self.keys.is_empty() {
 429             self.keys.push_back(value);
 430             self.children.push_back(None);
 431             return Insert::Added;
 432         }
 433         let (median, left, right) = match A::search_value(&self.keys, &value) {
 434             // Key exists in node
 435             Ok(index) => {
 436                 return Insert::Replaced(mem::replace(&mut self.keys[index], value));
 437             }
 438             // Key is adjacent to some key in node
 439             Err(index) => {
 440                 let mut has_room = self.has_room();
 441                 let action = match self.children[index] {
 442                     // No child at location, this is the target node.
 443                     None => InsertAt,
 444                     // Child at location, pass it on.
 445                     Some(ref mut child_ref) => {
 446                         let child = Ref::make_mut(child_ref);
 447                         match child.insert(value.clone()) {
 448                             Insert::Added => AddedAction,
 449                             Insert::Replaced(value) => ReplacedAction(value),
 450                             Insert::Update(_) => unreachable!(),
 451                             Insert::Split(left, median, right) => InsertSplit(left, median, right),
 452                         }
 453                     }
 454                 };
 455                 match action {
 456                     ReplacedAction(value) => return Insert::Replaced(value),
 457                     AddedAction => {
 458                         return Insert::Added;
 459                     }
 460                     InsertAt => {
 461                         if has_room {
 462                             self.keys.insert(index, value);
 463                             self.children.insert(index + 1, None);
 464                             return Insert::Added;
 465                         } else {
 466                             (value, None, None)
 467                         }
 468                     }
 469                     InsertSplit(left, median, right) => {
 470                         if has_room {
 471                             self.children[index] = Some(Ref::from(left));
 472                             self.keys.insert(index, median);
 473                             self.children.insert(index + 1, Some(Ref::from(right)));
 474                             return Insert::Added;
 475                         } else {
 476                             (median, Some(left), Some(right))
 477                         }
 478                     }
 479                 }
 480             }
 481         };
 482         self.split(median, left, right)
 483     }
 484
 485     pub fn remove<BK>(&mut self, key: &BK) -> Remove<A>
 486     where
 487         BK: Ord + ?Sized,
 488         A::Key: Borrow<BK>,
 489     {
 490         let index = A::search_key(&self.keys, key);
 491         self.remove_index(index, key)
 492     }
 493
 494     fn remove_index<BK>(&mut self, index: Result<usize, usize>, key: &BK) -> Remove<A>
 495     where
 496         BK: Ord + ?Sized,
 497         A::Key: Borrow<BK>,
 498     {
 499         let action = match index {
 500             // Key exists in node, remove it.
 501             Ok(index) => {
 502                 match (&self.children[index], &self.children[index + 1]) {
 503                     // If we're a leaf, just delete the entry.
 504                     (&None, &None) => RemoveAction::DeleteAt(index),
 505                     // If the left hand child has capacity, pull the predecessor up.
 506                     (&Some(ref left), _) if !left.too_small() => {
 507                         if left.is_leaf() {
 508                             RemoveAction::PullUp(left.keys.len() - 1, index, index)
 509                         } else {
 510                             RemoveAction::StealFromLeft(index + 1)
 511                         }
 512                     }
 513                     // If the right hand child has capacity, pull the successor up.
 514                     (_, &Some(ref right)) if !right.too_small() => {
 515                         if right.is_leaf() {
 516                             RemoveAction::PullUp(0, index, index + 1)
 517                         } else {
 518                             RemoveAction::StealFromRight(index)
 519                         }
 520                     }
 521                     // If neither child has capacity, we'll have to merge them.
 522                     (&Some(_), &Some(_)) => RemoveAction::Merge(index),
 523                     // If one child exists and the other doesn't, we're in a bad state.
 524                     _ => unreachable!(),
 525                 }
 526             }
 527             // Key is adjacent to some key in node
 528             Err(index) => match self.children[index] {
 529                 // No child at location means key isn't in map.
 530                 None => return Remove::NoChange,
 531                 // Child at location, but it's at minimum capacity.
 532                 Some(ref child) if child.too_small() => {
 533                     let left = if index > 0 {
 534                         self.children.get(index - 1)
 535                     } else {
 536                         None
 537                     }; // index is usize and can't be negative, best make sure it never is.
 538                     match (left, self.children.get(index + 1)) {
 539                         // If it has a left sibling with capacity, steal a key from it.
 540                         (Some(&Some(ref old_left)), _) if !old_left.too_small() => {
 541                             RemoveAction::StealFromLeft(index)
 542                         }
 543                         // If it has a right sibling with capacity, same as above.
 544                         (_, Some(&Some(ref old_right))) if !old_right.too_small() => {
 545                             RemoveAction::StealFromRight(index)
 546                         }
 547                         // If it has neither, we'll have to merge it with a sibling.
 548                         // If we have a right sibling, we'll merge with that.
 549                         (_, Some(&Some(_))) => RemoveAction::MergeFirst(index),
 550                         // If we have a left sibling, we'll merge with that.
 551                         (Some(&Some(_)), _) => RemoveAction::MergeFirst(index - 1),
 552                         // If none of the above, we're in a bad state.
 553                         _ => unreachable!(),
 554                     }
 555                 }
 556                 // Child at location, and it's big enough, we can recurse down.
 557                 Some(_) => RemoveAction::ContinueDown(index),
 558             },
 559         };
 560         match action {
 561             RemoveAction::DeleteAt(index) => {
 562                 let pair = self.keys.remove(index);
 563                 self.children.remove(index);
 564                 Remove::Removed(pair)
 565             }
 566             RemoveAction::PullUp(target_index, pull_to, child_index) => {
 567                 let mut children = &mut self.children;
 568                 let mut update = None;
 569                 let mut value;
 570                 if let Some(&mut Some(ref mut child_ref)) = children.get_mut(child_index) {
 571                     let child = Ref::make_mut(child_ref);
 572                     match child.remove_index(Ok(target_index), key) {
 573                         Remove::NoChange => unreachable!(),
 574                         Remove::Removed(pulled_value) => {
 575                             value = self.keys.set(pull_to, pulled_value);
 576                         }
 577                         Remove::Update(pulled_value, new_child) => {
 578                             value = self.keys.set(pull_to, pulled_value);
 579                             update = Some(new_child);
 580                         }
 581                     }
 582                 } else {
 583                     unreachable!()
 584                 }
 585                 if let Some(new_child) = update {
 586                     children[child_index] = Some(Ref::from(new_child));
 587                 }
 588                 Remove::Removed(value)
 589             }
 590             RemoveAction::Merge(index) => {
 591                 let left = self.children.remove(index).unwrap();
 592                 let right = mem::replace(&mut self.children[index], None).unwrap();
 593                 let value = self.keys.remove(index);
 594                 let mut merged_child = Node::merge(value, clone_ref(left), clone_ref(right));
 595                 let (removed, new_child) = match merged_child.remove(key) {
 596                     Remove::NoChange => unreachable!(),
 597                     Remove::Removed(removed) => (removed, merged_child),
 598                     Remove::Update(removed, updated_child) => (removed, updated_child),
 599                 };
 600                 if self.keys.is_empty() {
 601                     // If we've depleted the root node, the merged child becomes the root.
 602                     Remove::Update(removed, new_child)
 603                 } else {
 604                     self.children[index] = Some(Ref::from(new_child));
 605                     Remove::Removed(removed)
 606                 }
 607             }
 608             RemoveAction::StealFromLeft(index) => {
 609                 let mut update = None;
 610                 let mut out_value;
 611                 {
 612                     let mut children = self.children.as_mut_slice()[index - 1..=index]
 613                         .iter_mut()
 614                         .map(|n| {
 615                             if let Some(ref mut o) = *n {
 616                                 o
 617                             } else {
 618                                 unreachable!()
 619                             }
 620                         });
 621                     let mut left = Ref::make_mut(children.next().unwrap());
 622                     let mut child = Ref::make_mut(children.next().unwrap());
 623                     // Prepare the rebalanced node.
 624                     child.push_min(
 625                         left.children.last().unwrap().clone(),
 626                         self.keys[index - 1].clone(),
 627                     );
 628                     match child.remove(key) {
 629                         Remove::NoChange => {
 630                             // Key wasn't there, we need to revert the steal.
 631                             child.pop_min();
 632                             return Remove::NoChange;
 633                         }
 634                         Remove::Removed(value) => {
 635                             // If we did remove something, we complete the rebalancing.
 636                             let (left_value, _) = left.pop_max();
 637                             self.keys[index - 1] = left_value;
 638                             out_value = value;
 639                         }
 640                         Remove::Update(value, new_child) => {
 641                             // If we did remove something, we complete the rebalancing.
 642                             let (left_value, _) = left.pop_max();
 643                             self.keys[index - 1] = left_value;
 644                             update = Some(new_child);
 645                             out_value = value;
 646                         }
 647                     }
 648                 }
 649                 if let Some(new_child) = update {
 650                     self.children[index] = Some(Ref::from(new_child));
 651                 }
 652                 Remove::Removed(out_value)
 653             }
 654             RemoveAction::StealFromRight(index) => {
 655                 let mut update = None;
 656                 let mut out_value;
 657                 {
 658                     let mut children = self.children.as_mut_slice()[index..index + 2]
 659                         .iter_mut()
 660                         .map(|n| {
 661                             if let Some(ref mut o) = *n {
 662                                 o
 663                             } else {
 664                                 unreachable!()
 665                             }
 666                         });
 667                     let mut child = Ref::make_mut(children.next().unwrap());
 668                     let mut right = Ref::make_mut(children.next().unwrap());
 669                     // Prepare the rebalanced node.
 670                     child.push_max(right.children[0].clone(), self.keys[index].clone());
 671                     match child.remove(key) {
 672                         Remove::NoChange => {
 673                             // Key wasn't there, we need to revert the steal.
 674                             child.pop_max();
 675                             return Remove::NoChange;
 676                         }
 677                         Remove::Removed(value) => {
 678                             // If we did remove something, we complete the rebalancing.
 679                             let (right_value, _) = right.pop_min();
 680                             self.keys[index] = right_value;
 681                             out_value = value;
 682                         }
 683                         Remove::Update(value, new_child) => {
 684                             // If we did remove something, we complete the rebalancing.
 685                             let (right_value, _) = right.pop_min();
 686                             self.keys[index] = right_value;
 687                             update = Some(new_child);
 688                             out_value = value;
 689                         }
 690                     }
 691                 }
 692                 if let Some(new_child) = update {
 693                     self.children[index] = Some(Ref::from(new_child));
 694                 }
 695                 Remove::Removed(out_value)
 696             }
 697             RemoveAction::MergeFirst(index) => {
 698                 if self.keys[index].cmp_keys(key) != Ordering::Equal
 699                     && !self.child_contains(index, key)
 700                     && !self.child_contains(index + 1, key)
 701                 {
 702                     return Remove::NoChange;
 703                 }
 704                 let left = self.children.remove(index).unwrap();
 705                 let right = mem::replace(&mut self.children[index], None).unwrap();
 706                 let middle = self.keys.remove(index);
 707                 let mut merged = Node::merge(middle, clone_ref(left), clone_ref(right));
 708                 let mut update;
 709                 let mut out_value;
 710                 match merged.remove(key) {
 711                     Remove::NoChange => {
 712                         panic!("nodes::btree::Node::remove: caught an absent key too late while merging");
 713                     }
 714                     Remove::Removed(value) => {
 715                         if self.keys.is_empty() {
 716                             return Remove::Update(value, merged);
 717                         }
 718                         update = merged;
 719                         out_value = value;
 720                     }
 721                     Remove::Update(value, new_child) => {
 722                         if self.keys.is_empty() {
 723                             return Remove::Update(value, new_child);
 724                         }
 725                         update = new_child;
 726                         out_value = value;
 727                     }
 728                 }
 729                 self.children[index] = Some(Ref::from(update));
 730                 Remove::Removed(out_value)
 731             }
 732             RemoveAction::ContinueDown(index) => {
 733                 let mut update = None;
 734                 let mut out_value;
 735                 if let Some(&mut Some(ref mut child_ref)) = self.children.get_mut(index) {
 736                     let child = Ref::make_mut(child_ref);
 737                     match child.remove(key) {
 738                         Remove::NoChange => return Remove::NoChange,
 739                         Remove::Removed(value) => {
 740                             out_value = value;
 741                         }
 742                         Remove::Update(value, new_child) => {
 743                             update = Some(new_child);
 744                             out_value = value;
 745                         }
 746                     }
 747                 } else {
 748                     unreachable!()
 749                 }
 750                 if let Some(new_child) = update {
 751                     self.children[index] = Some(Ref::from(new_child));
 752                 }
 753                 Remove::Removed(out_value)
 754             }
 755         }
 756     }
 757 }
 758
 759 // Iterator
 760
 761 pub struct Iter<'a, A: 'a> {
 762     fwd_path: Vec<(&'a Node<A>, usize)>,
 763     back_path: Vec<(&'a Node<A>, usize)>,
 764     pub(crate) remaining: usize,
 765 }
 766
 767 impl<'a, A: 'a + BTreeValue> Iter<'a, A> {
 768     pub fn new<R, BK>(root: &'a Node<A>, size: usize, range: R) -> Self
 769     where
 770         R: RangeBounds<BK>,
 771         A::Key: Borrow<BK>,
 772         BK: Ord + ?Sized,
 773     {
 774         let fwd_path = match range.start_bound() {
 775             Bound::Included(key) => root.path_next(key, Vec::new()),
 776             Bound::Excluded(key) => {
 777                 let mut path = root.path_next(key, Vec::new());
 778                 if let Some(value) = Self::get(&path) {
 779                     if value.cmp_keys(key) == Ordering::Equal {
 780                         Self::step_forward(&mut path);
 781                     }
 782                 }
 783                 path
 784             }
 785             Bound::Unbounded => root.path_first(Vec::new()),
 786         };
 787         let back_path = match range.end_bound() {
 788             Bound::Included(key) => root.path_prev(key, Vec::new()),
 789             Bound::Excluded(key) => {
 790                 let mut path = root.path_prev(key, Vec::new());
 791                 if let Some(value) = Self::get(&path) {
 792                     if value.cmp_keys(key) == Ordering::Equal {
 793                         Self::step_back(&mut path);
 794                     }
 795                 }
 796                 path
 797             }
 798             Bound::Unbounded => root.path_last(Vec::new()),
 799         };
 800         Iter {
 801             fwd_path,
 802             back_path,
 803             remaining: size,
 804         }
 805     }
 806
 807     fn get(path: &[(&'a Node<A>, usize)]) -> Option<&'a A> {
 808         match path.last() {
 809             Some((node, index)) => Some(&node.keys[*index]),
 810             None => None,
 811         }
 812     }
 813
 814     fn step_forward(path: &mut Vec<(&'a Node<A>, usize)>) -> Option<&'a A> {
 815         match path.pop() {
 816             Some((node, index)) => {
 817                 let index = index + 1;
 818                 match node.children[index] {
 819                     // Child between current and next key -> step down
 820                     Some(ref child) => {
 821                         path.push((node, index));
 822                         path.push((child, 0));
 823                         let mut node = child;
 824                         while let Some(ref left_child) = node.children[0] {
 825                             path.push((left_child, 0));
 826                             node = left_child;
 827                         }
 828                         Some(&node.keys[0])
 829                     }
 830                     None => match node.keys.get(index) {
 831                         // Yield next key
 832                         value @ Some(_) => {
 833                             path.push((node, index));
 834                             value
 835                         }
 836                         // No more keys -> exhausted level, step up and yield
 837                         None => loop {
 838                             match path.pop() {
 839                                 None => {
 840                                     return None;
 841                                 }
 842                                 Some((node, index)) => {
 843                                     if let value @ Some(_) = node.keys.get(index) {
 844                                         path.push((node, index));
 845                                         return value;
 846                                     }
 847                                 }
 848                             }
 849                         },
 850                     },
 851                 }
 852             }
 853             None => None,
 854         }
 855     }
 856
 857     fn step_back(path: &mut Vec<(&'a Node<A>, usize)>) -> Option<&'a A> {
 858         match path.pop() {
 859             Some((node, index)) => match node.children[index] {
 860                 Some(ref child) => {
 861                     path.push((node, index));
 862                     let mut end = child.keys.len() - 1;
 863                     path.push((child, end));
 864                     let mut node = child;
 865                     while let Some(ref right_child) = node.children[end + 1] {
 866                         end = right_child.keys.len() - 1;
 867                         path.push((right_child, end));
 868                         node = right_child;
 869                     }
 870                     Some(&node.keys[end])
 871                 }
 872                 None => {
 873                     if index == 0 {
 874                         loop {
 875                             match path.pop() {
 876                                 None => {
 877                                     return None;
 878                                 }
 879                                 Some((node, index)) => {
 880                                     if index > 0 {
 881                                         let index = index - 1;
 882                                         path.push((node, index));
 883                                         return Some(&node.keys[index]);
 884                                     }
 885                                 }
 886                             }
 887                         }
 888                     } else {
 889                         let index = index - 1;
 890                         path.push((node, index));
 891                         Some(&node.keys[index])
 892                     }
 893                 }
 894             },
 895             None => None,
 896         }
 897     }
 898 }
 899
 900 impl<'a, A: 'a + BTreeValue> Iterator for Iter<'a, A> {
 901     type Item = &'a A;
 902
 903     fn next(&mut self) -> Option<Self::Item> {
 904         match Iter::get(&self.fwd_path) {
 905             None => None,
 906             Some(value) => match Iter::get(&self.back_path) {
 907                 Some(last_value) if value.cmp_values(last_value) == Ordering::Greater => None,
 908                 None => None,
 909                 Some(_) => {
 910                     Iter::step_forward(&mut self.fwd_path);
 911                     self.remaining -= 1;
 912                     Some(value)
 913                 }
 914             },
 915         }
 916     }
 917
 918     fn size_hint(&self) -> (usize, Option<usize>) {
 919         // (0, Some(self.remaining))
 920         (0, None)
 921     }
 922 }
 923
 924 impl<'a, A: 'a + BTreeValue> DoubleEndedIterator for Iter<'a, A> {
 925     fn next_back(&mut self) -> Option<Self::Item> {
 926         match Iter::get(&self.back_path) {
 927             None => None,
 928             Some(value) => match Iter::get(&self.fwd_path) {
 929                 Some(last_value) if value.cmp_values(last_value) == Ordering::Less => None,
 930                 None => None,
 931                 Some(_) => {
 932                     Iter::step_back(&mut self.back_path);
 933                     self.remaining -= 1;
 934                     Some(value)
 935                 }
 936             },
 937         }
 938     }
 939 }
 940
 941 // Consuming iterator
 942
 943 enum ConsumingIterItem<A> {
 944     Consider(Node<A>),
 945     Yield(A),
 946 }
 947
 948 pub struct ConsumingIter<A> {
 949     fwd_last: Option<A>,
 950     fwd_stack: Vec<ConsumingIterItem<A>>,
 951     back_last: Option<A>,
 952     back_stack: Vec<ConsumingIterItem<A>>,
 953     remaining: usize,
 954 }
 955
 956 impl<A: Clone> ConsumingIter<A> {
 957     pub fn new(root: &Node<A>, total: usize) -> Self {
 958         ConsumingIter {
 959             fwd_last: None,
 960             fwd_stack: vec![ConsumingIterItem::Consider(root.clone())],
 961             back_last: None,
 962             back_stack: vec![ConsumingIterItem::Consider(root.clone())],
 963             remaining: total,
 964         }
 965     }
 966
 967     fn push_node(stack: &mut Vec<ConsumingIterItem<A>>, maybe_node: Option<Ref<Node<A>>>) {
 968         if let Some(node) = maybe_node {
 969             stack.push(ConsumingIterItem::Consider(clone_ref(node)))
 970         }
 971     }
 972
 973     fn push(stack: &mut Vec<ConsumingIterItem<A>>, mut node: Node<A>) {
 974         for _n in 0..node.keys.len() {
 975             ConsumingIter::push_node(stack, node.children.pop_back());
 976             stack.push(ConsumingIterItem::Yield(node.keys.pop_back()));
 977         }
 978         ConsumingIter::push_node(stack, node.children.pop_back());
 979     }
 980
 981     fn push_fwd(&mut self, node: Node<A>) {
 982         ConsumingIter::push(&mut self.fwd_stack, node)
 983     }
 984
 985     fn push_node_back(&mut self, maybe_node: Option<Ref<Node<A>>>) {
 986         if let Some(node) = maybe_node {
 987             self.back_stack
 988                 .push(ConsumingIterItem::Consider(clone_ref(node)))
 989         }
 990     }
 991
 992     fn push_back(&mut self, mut node: Node<A>) {
 993         for _i in 0..node.keys.len() {
 994             self.push_node_back(node.children.pop_front());
 995             self.back_stack
 996                 .push(ConsumingIterItem::Yield(node.keys.pop_front()));
 997         }
 998         self.push_node_back(node.children.pop_back());
 999     }
1000 }
1001
1002 impl<A> Iterator for ConsumingIter<A>
1003 where
1004     A: BTreeValue,
1005 {
1006     type Item = A;
1007
1008     fn next(&mut self) -> Option<Self::Item> {
1009         loop {
1010             match self.fwd_stack.pop() {
1011                 None => {
1012                     self.remaining = 0;
1013                     return None;
1014                 }
1015                 Some(ConsumingIterItem::Consider(node)) => self.push_fwd(node),
1016                 Some(ConsumingIterItem::Yield(value)) => {
1017                     if let Some(ref last) = self.back_last {
1018                         if value.cmp_values(last) != Ordering::Less {
1019                             self.fwd_stack.clear();
1020                             self.back_stack.clear();
1021                             self.remaining = 0;
1022                             return None;
1023                         }
1024                     }
1025                     self.remaining -= 1;
1026                     self.fwd_last = Some(value.clone());
1027                     return Some(value);
1028                 }
1029             }
1030         }
1031     }
1032
1033     fn size_hint(&self) -> (usize, Option<usize>) {
1034         (self.remaining, Some(self.remaining))
1035     }
1036 }
1037
1038 impl<A> DoubleEndedIterator for ConsumingIter<A>
1039 where
1040     A: BTreeValue,
1041 {
1042     fn next_back(&mut self) -> Option<Self::Item> {
1043         loop {
1044             match self.back_stack.pop() {
1045                 None => {
1046                     self.remaining = 0;
1047                     return None;
1048                 }
1049                 Some(ConsumingIterItem::Consider(node)) => self.push_back(node),
1050                 Some(ConsumingIterItem::Yield(value)) => {
1051                     if let Some(ref last) = self.fwd_last {
1052                         if value.cmp_values(last) != Ordering::Greater {
1053                             self.fwd_stack.clear();
1054                             self.back_stack.clear();
1055                             self.remaining = 0;
1056                             return None;
1057                         }
1058                     }
1059                     self.remaining -= 1;
1060                     self.back_last = Some(value.clone());
1061                     return Some(value);
1062                 }
1063             }
1064         }
1065     }
1066 }
1067
1068 impl<A: BTreeValue> ExactSizeIterator for ConsumingIter<A> {}
1069
1070 // DiffIter
1071
1072 pub struct DiffIter<'a, A: 'a> {
1073     old_stack: Vec<IterItem<'a, A>>,
1074     new_stack: Vec<IterItem<'a, A>>,
1075 }
1076
1077 #[derive(PartialEq, Eq)]
1078 pub enum DiffItem<'a, A: 'a> {
1079     Add(&'a A),
1080     Update { old: &'a A, new: &'a A },
1081     Remove(&'a A),
1082 }
1083
1084 enum IterItem<'a, A: 'a> {
1085     Consider(&'a Node<A>),
1086     Yield(&'a A),
1087 }
1088
1089 impl<'a, A: 'a> DiffIter<'a, A> {
1090     pub fn new(old: &'a Node<A>, new: &'a Node<A>) -> Self {
1091         DiffIter {
1092             old_stack: if old.keys.is_empty() {
1093                 Vec::new()
1094             } else {
1095                 vec![IterItem::Consider(old)]
1096             },
1097             new_stack: if new.keys.is_empty() {
1098                 Vec::new()
1099             } else {
1100                 vec![IterItem::Consider(new)]
1101             },
1102         }
1103     }
1104
1105     fn push_node(stack: &mut Vec<IterItem<'a, A>>, maybe_node: &'a Option<Ref<Node<A>>>) {
1106         if let Some(ref node) = *maybe_node {
1107             stack.push(IterItem::Consider(&node))
1108         }
1109     }
1110
1111     fn push(stack: &mut Vec<IterItem<'a, A>>, node: &'a Node<A>) {
1112         for n in 0..node.keys.len() {
1113             let i = node.keys.len() - n;
1114             Self::push_node(stack, &node.children[i]);
1115             stack.push(IterItem::Yield(&node.keys[i - 1]));
1116         }
1117         Self::push_node(stack, &node.children[0]);
1118     }
1119 }
1120
1121 impl<'a, A> Iterator for DiffIter<'a, A>
1122 where
1123     A: 'a + BTreeValue + PartialEq,
1124 {
1125     type Item = DiffItem<'a, A>;
1126
1127     fn next(&mut self) -> Option<Self::Item> {
1128         loop {
1129             match (self.old_stack.pop(), self.new_stack.pop()) {
1130                 (None, None) => return None,
1131                 (None, Some(new)) => match new {
1132                     IterItem::Consider(new) => Self::push(&mut self.new_stack, &new),
1133                     IterItem::Yield(new) => return Some(DiffItem::Add(new)),
1134                 },
1135                 (Some(old), None) => match old {
1136                     IterItem::Consider(old) => Self::push(&mut self.old_stack, &old),
1137                     IterItem::Yield(old) => return Some(DiffItem::Remove(old)),
1138                 },
1139                 (Some(old), Some(new)) => match (old, new) {
1140                     (IterItem::Consider(old), IterItem::Consider(new)) => {
1141                         match old.keys[0].cmp_values(&new.keys[0]) {
1142                             Ordering::Less => {
1143                                 Self::push(&mut self.old_stack, &old);
1144                                 self.new_stack.push(IterItem::Consider(new));
1145                             }
1146                             Ordering::Greater => {
1147                                 self.old_stack.push(IterItem::Consider(old));
1148                                 Self::push(&mut self.new_stack, &new);
1149                             }
1150                             Ordering::Equal => {
1151                                 Self::push(&mut self.old_stack, &old);
1152                                 Self::push(&mut self.new_stack, &new);
1153                             }
1154                         }
1155                     }
1156                     (IterItem::Consider(old), IterItem::Yield(new)) => {
1157                         Self::push(&mut self.old_stack, &old);
1158                         self.new_stack.push(IterItem::Yield(new));
1159                     }
1160                     (IterItem::Yield(old), IterItem::Consider(new)) => {
1161                         self.old_stack.push(IterItem::Yield(old));
1162                         Self::push(&mut self.new_stack, &new);
1163                     }
1164                     (IterItem::Yield(old), IterItem::Yield(new)) => match old.cmp_values(&new) {
1165                         Ordering::Less => {
1166                             self.new_stack.push(IterItem::Yield(new));
1167                             return Some(DiffItem::Remove(old));
1168                         }
1169                         Ordering::Equal => {
1170                             if old != new {
1171                                 return Some(DiffItem::Update { old, new });
1172                             }
1173                         }
1174                         Ordering::Greater => {
1175                             self.old_stack.push(IterItem::Yield(old));
1176                             return Some(DiffItem::Add(new));
1177                         }
1178                     },
1179                 },
1180             }
1181         }
1182     }
1183 }