library/alloc/src/collections/btree/navigate.rs

   1 use core::borrow::Borrow;
   2 use core::ops::RangeBounds;
   3 use core::ptr;
   4
   5 use super::node::{marker, ForceResult::*, Handle, NodeRef};
   6
   7 // `front` and `back` are always both `None` or both `Some`.
   8 pub struct LeafRange<BorrowType, K, V> {
   9     front: Option<Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>>,
  10     back: Option<Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>>,
  11 }
  12
  13 impl<'a, K: 'a, V: 'a> Clone for LeafRange<marker::Immut<'a>, K, V> {
  14     fn clone(&self) -> Self {
  15         LeafRange { front: self.front.clone(), back: self.back.clone() }
  16     }
  17 }
  18
  19 impl<BorrowType, K, V> LeafRange<BorrowType, K, V> {
  20     pub fn none() -> Self {
  21         LeafRange { front: None, back: None }
  22     }
  23
  24     fn is_empty(&self) -> bool {
  25         self.front == self.back
  26     }
  27
  28     /// Temporarily takes out another, immutable equivalent of the same range.
  29     pub fn reborrow(&self) -> LeafRange<marker::Immut<'_>, K, V> {
  30         LeafRange {
  31             front: self.front.as_ref().map(|f| f.reborrow()),
  32             back: self.back.as_ref().map(|b| b.reborrow()),
  33         }
  34     }
  35 }
  36
  37 impl<'a, K, V> LeafRange<marker::Immut<'a>, K, V> {
  38     #[inline]
  39     pub fn next_checked(&mut self) -> Option<(&'a K, &'a V)> {
  40         if self.is_empty() { None } else { Some(unsafe { self.next_unchecked() }) }
  41     }
  42
  43     #[inline]
  44     pub fn next_back_checked(&mut self) -> Option<(&'a K, &'a V)> {
  45         if self.is_empty() { None } else { Some(unsafe { self.next_back_unchecked() }) }
  46     }
  47
  48     #[inline]
  49     pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
  50         unsafe { self.front.as_mut().unwrap().next_unchecked() }
  51     }
  52
  53     #[inline]
  54     pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
  55         unsafe { self.back.as_mut().unwrap().next_back_unchecked() }
  56     }
  57 }
  58
  59 impl<'a, K, V> LeafRange<marker::ValMut<'a>, K, V> {
  60     #[inline]
  61     pub fn next_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
  62         if self.is_empty() { None } else { Some(unsafe { self.next_unchecked() }) }
  63     }
  64
  65     #[inline]
  66     pub fn next_back_checked(&mut self) -> Option<(&'a K, &'a mut V)> {
  67         if self.is_empty() { None } else { Some(unsafe { self.next_back_unchecked() }) }
  68     }
  69
  70     #[inline]
  71     pub unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
  72         unsafe { self.front.as_mut().unwrap().next_unchecked() }
  73     }
  74
  75     #[inline]
  76     pub unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
  77         unsafe { self.back.as_mut().unwrap().next_back_unchecked() }
  78     }
  79 }
  80
  81 impl<K, V> LeafRange<marker::Dying, K, V> {
  82     #[inline]
  83     pub fn take_front(
  84         &mut self,
  85     ) -> Option<Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge>> {
  86         self.front.take()
  87     }
  88
  89     #[inline]
  90     pub unsafe fn deallocating_next_unchecked(
  91         &mut self,
  92     ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
  93         debug_assert!(self.front.is_some());
  94         let front = self.front.as_mut().unwrap();
  95         unsafe { front.deallocating_next_unchecked() }
  96     }
  97
  98     #[inline]
  99     pub unsafe fn deallocating_next_back_unchecked(
 100         &mut self,
 101     ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
 102         debug_assert!(self.back.is_some());
 103         let back = self.back.as_mut().unwrap();
 104         unsafe { back.deallocating_next_back_unchecked() }
 105     }
 106 }
 107
 108 impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
 109     /// Finds the distinct leaf edges delimiting a specified range in a tree.
 110     ///
 111     /// If such distinct edges exist, returns them in ascending order, meaning
 112     /// that a non-zero number of calls to `next_unchecked` on the `front` of
 113     /// the result and/or calls to `next_back_unchecked` on the `back` of the
 114     /// result will eventually reach the same edge.
 115     ///
 116     /// If there are no such edges, i.e., if the tree contains no key within
 117     /// the range, returns an empty `front` and `back`.
 118     ///
 119     /// # Safety
 120     /// Unless `BorrowType` is `Immut`, do not use the handles to visit the same
 121     /// KV twice.
 122     unsafe fn find_leaf_edges_spanning_range<Q: ?Sized, R>(
 123         self,
 124         range: R,
 125     ) -> LeafRange<BorrowType, K, V>
 126     where
 127         Q: Ord,
 128         K: Borrow<Q>,
 129         R: RangeBounds<Q>,
 130     {
 131         match self.search_tree_for_bifurcation(&range) {
 132             Err(_) => LeafRange::none(),
 133             Ok((
 134                 node,
 135                 lower_edge_idx,
 136                 upper_edge_idx,
 137                 mut lower_child_bound,
 138                 mut upper_child_bound,
 139             )) => {
 140                 let mut lower_edge = unsafe { Handle::new_edge(ptr::read(&node), lower_edge_idx) };
 141                 let mut upper_edge = unsafe { Handle::new_edge(node, upper_edge_idx) };
 142                 loop {
 143                     match (lower_edge.force(), upper_edge.force()) {
 144                         (Leaf(f), Leaf(b)) => return LeafRange { front: Some(f), back: Some(b) },
 145                         (Internal(f), Internal(b)) => {
 146                             (lower_edge, lower_child_bound) =
 147                                 f.descend().find_lower_bound_edge(lower_child_bound);
 148                             (upper_edge, upper_child_bound) =
 149                                 b.descend().find_upper_bound_edge(upper_child_bound);
 150                         }
 151                         _ => unreachable!("BTreeMap has different depths"),
 152                     }
 153                 }
 154             }
 155         }
 156     }
 157 }
 158
 159 /// Equivalent to `(root1.first_leaf_edge(), root2.last_leaf_edge())` but more efficient.
 160 fn full_range<BorrowType: marker::BorrowType, K, V>(
 161     root1: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
 162     root2: NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
 163 ) -> LeafRange<BorrowType, K, V> {
 164     let mut min_node = root1;
 165     let mut max_node = root2;
 166     loop {
 167         let front = min_node.first_edge();
 168         let back = max_node.last_edge();
 169         match (front.force(), back.force()) {
 170             (Leaf(f), Leaf(b)) => {
 171                 return LeafRange { front: Some(f), back: Some(b) };
 172             }
 173             (Internal(min_int), Internal(max_int)) => {
 174                 min_node = min_int.descend();
 175                 max_node = max_int.descend();
 176             }
 177             _ => unreachable!("BTreeMap has different depths"),
 178         };
 179     }
 180 }
 181
 182 impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> {
 183     /// Finds the pair of leaf edges delimiting a specific range in a tree.
 184     ///
 185     /// The result is meaningful only if the tree is ordered by key, like the tree
 186     /// in a `BTreeMap` is.
 187     pub fn range_search<Q, R>(self, range: R) -> LeafRange<marker::Immut<'a>, K, V>
 188     where
 189         Q: ?Sized + Ord,
 190         K: Borrow<Q>,
 191         R: RangeBounds<Q>,
 192     {
 193         // SAFETY: our borrow type is immutable.
 194         unsafe { self.find_leaf_edges_spanning_range(range) }
 195     }
 196
 197     /// Finds the pair of leaf edges delimiting an entire tree.
 198     pub fn full_range(self) -> LeafRange<marker::Immut<'a>, K, V> {
 199         full_range(self, self)
 200     }
 201 }
 202
 203 impl<'a, K: 'a, V: 'a> NodeRef<marker::ValMut<'a>, K, V, marker::LeafOrInternal> {
 204     /// Splits a unique reference into a pair of leaf edges delimiting a specified range.
 205     /// The result are non-unique references allowing (some) mutation, which must be used
 206     /// carefully.
 207     ///
 208     /// The result is meaningful only if the tree is ordered by key, like the tree
 209     /// in a `BTreeMap` is.
 210     ///
 211     /// # Safety
 212     /// Do not use the duplicate handles to visit the same KV twice.
 213     pub fn range_search<Q, R>(self, range: R) -> LeafRange<marker::ValMut<'a>, K, V>
 214     where
 215         Q: ?Sized + Ord,
 216         K: Borrow<Q>,
 217         R: RangeBounds<Q>,
 218     {
 219         unsafe { self.find_leaf_edges_spanning_range(range) }
 220     }
 221
 222     /// Splits a unique reference into a pair of leaf edges delimiting the full range of the tree.
 223     /// The results are non-unique references allowing mutation (of values only), so must be used
 224     /// with care.
 225     pub fn full_range(self) -> LeafRange<marker::ValMut<'a>, K, V> {
 226         // We duplicate the root NodeRef here -- we will never visit the same KV
 227         // twice, and never end up with overlapping value references.
 228         let self2 = unsafe { ptr::read(&self) };
 229         full_range(self, self2)
 230     }
 231 }
 232
 233 impl<K, V> NodeRef<marker::Dying, K, V, marker::LeafOrInternal> {
 234     /// Splits a unique reference into a pair of leaf edges delimiting the full range of the tree.
 235     /// The results are non-unique references allowing massively destructive mutation, so must be
 236     /// used with the utmost care.
 237     pub fn full_range(self) -> LeafRange<marker::Dying, K, V> {
 238         // We duplicate the root NodeRef here -- we will never access it in a way
 239         // that overlaps references obtained from the root.
 240         let self2 = unsafe { ptr::read(&self) };
 241         full_range(self, self2)
 242     }
 243 }
 244
 245 impl<BorrowType: marker::BorrowType, K, V>
 246     Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>
 247 {
 248     /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
 249     /// on the right side, which is either in the same leaf node or in an ancestor node.
 250     /// If the leaf edge is the last one in the tree, returns [`Result::Err`] with the root node.
 251     pub fn next_kv(
 252         self,
 253     ) -> Result<
 254         Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>,
 255         NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
 256     > {
 257         let mut edge = self.forget_node_type();
 258         loop {
 259             edge = match edge.right_kv() {
 260                 Ok(kv) => return Ok(kv),
 261                 Err(last_edge) => match last_edge.into_node().ascend() {
 262                     Ok(parent_edge) => parent_edge.forget_node_type(),
 263                     Err(root) => return Err(root),
 264                 },
 265             }
 266         }
 267     }
 268
 269     /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
 270     /// on the left side, which is either in the same leaf node or in an ancestor node.
 271     /// If the leaf edge is the first one in the tree, returns [`Result::Err`] with the root node.
 272     fn next_back_kv(
 273         self,
 274     ) -> Result<
 275         Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>,
 276         NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
 277     > {
 278         let mut edge = self.forget_node_type();
 279         loop {
 280             edge = match edge.left_kv() {
 281                 Ok(kv) => return Ok(kv),
 282                 Err(last_edge) => match last_edge.into_node().ascend() {
 283                     Ok(parent_edge) => parent_edge.forget_node_type(),
 284                     Err(root) => return Err(root),
 285                 },
 286             }
 287         }
 288     }
 289 }
 290
 291 impl<BorrowType: marker::BorrowType, K, V>
 292     Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>
 293 {
 294     /// Given an internal edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
 295     /// on the right side, which is either in the same internal node or in an ancestor node.
 296     /// If the internal edge is the last one in the tree, returns [`Result::Err`] with the root node.
 297     fn next_kv(
 298         self,
 299     ) -> Result<
 300         Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>,
 301         NodeRef<BorrowType, K, V, marker::Internal>,
 302     > {
 303         let mut edge = self;
 304         loop {
 305             edge = match edge.right_kv() {
 306                 Ok(internal_kv) => return Ok(internal_kv),
 307                 Err(last_edge) => match last_edge.into_node().ascend() {
 308                     Ok(parent_edge) => parent_edge,
 309                     Err(root) => return Err(root),
 310                 },
 311             }
 312         }
 313     }
 314 }
 315
 316 impl<K, V> Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge> {
 317     /// Given a leaf edge handle into a dying tree, returns the next leaf edge
 318     /// on the right side, and the key-value pair in between, if they exist.
 319     ///
 320     /// If the given edge is the last one in a leaf, this method deallocates
 321     /// the leaf, as well as any ancestor nodes whose last edge was reached.
 322     /// This implies that if no more key-value pair follows, the entire tree
 323     /// will have been deallocated and there is nothing left to return.
 324     ///
 325     /// # Safety
 326     /// - The given edge must not have been previously returned by counterpart
 327     ///   `deallocating_next_back`.
 328     /// - The returned KV handle is only valid to access the key and value,
 329     ///   and only valid until the next call to this method or counterpart
 330     ///   `deallocating_next_back`.
 331     unsafe fn deallocating_next(
 332         self,
 333     ) -> Option<(Self, Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>)>
 334     {
 335         let mut edge = self.forget_node_type();
 336         loop {
 337             edge = match edge.right_kv() {
 338                 Ok(kv) => return Some((unsafe { ptr::read(&kv) }.next_leaf_edge(), kv)),
 339                 Err(last_edge) => match unsafe { last_edge.into_node().deallocate_and_ascend() } {
 340                     Some(parent_edge) => parent_edge.forget_node_type(),
 341                     None => return None,
 342                 },
 343             }
 344         }
 345     }
 346
 347     /// Given a leaf edge handle into a dying tree, returns the next leaf edge
 348     /// on the left side, and the key-value pair in between, if they exist.
 349     ///
 350     /// If the given edge is the first one in a leaf, this method deallocates
 351     /// the leaf, as well as any ancestor nodes whose first edge was reached.
 352     /// This implies that if no more key-value pair follows, the entire tree
 353     /// will have been deallocated and there is nothing left to return.
 354     ///
 355     /// # Safety
 356     /// - The given edge must not have been previously returned by counterpart
 357     ///   `deallocating_next`.
 358     /// - The returned KV handle is only valid to access the key and value,
 359     ///   and only valid until the next call to this method or counterpart
 360     ///   `deallocating_next`.
 361     unsafe fn deallocating_next_back(
 362         self,
 363     ) -> Option<(Self, Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV>)>
 364     {
 365         let mut edge = self.forget_node_type();
 366         loop {
 367             edge = match edge.left_kv() {
 368                 Ok(kv) => return Some((unsafe { ptr::read(&kv) }.next_back_leaf_edge(), kv)),
 369                 Err(last_edge) => match unsafe { last_edge.into_node().deallocate_and_ascend() } {
 370                     Some(parent_edge) => parent_edge.forget_node_type(),
 371                     None => return None,
 372                 },
 373             }
 374         }
 375     }
 376
 377     /// Deallocates a pile of nodes from the leaf up to the root.
 378     /// This is the only way to deallocate the remainder of a tree after
 379     /// `deallocating_next` and `deallocating_next_back` have been nibbling at
 380     /// both sides of the tree, and have hit the same edge. As it is intended
 381     /// only to be called when all keys and values have been returned,
 382     /// no cleanup is done on any of the keys or values.
 383     pub fn deallocating_end(self) {
 384         let mut edge = self.forget_node_type();
 385         while let Some(parent_edge) = unsafe { edge.into_node().deallocate_and_ascend() } {
 386             edge = parent_edge.forget_node_type();
 387         }
 388     }
 389 }
 390
 391 impl<'a, K, V> Handle<NodeRef<marker::Immut<'a>, K, V, marker::Leaf>, marker::Edge> {
 392     /// Moves the leaf edge handle to the next leaf edge and returns references to the
 393     /// key and value in between.
 394     ///
 395     /// # Safety
 396     /// There must be another KV in the direction travelled.
 397     unsafe fn next_unchecked(&mut self) -> (&'a K, &'a V) {
 398         super::mem::replace(self, |leaf_edge| {
 399             let kv = leaf_edge.next_kv().ok().unwrap();
 400             (kv.next_leaf_edge(), kv.into_kv())
 401         })
 402     }
 403
 404     /// Moves the leaf edge handle to the previous leaf edge and returns references to the
 405     /// key and value in between.
 406     ///
 407     /// # Safety
 408     /// There must be another KV in the direction travelled.
 409     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a V) {
 410         super::mem::replace(self, |leaf_edge| {
 411             let kv = leaf_edge.next_back_kv().ok().unwrap();
 412             (kv.next_back_leaf_edge(), kv.into_kv())
 413         })
 414     }
 415 }
 416
 417 impl<'a, K, V> Handle<NodeRef<marker::ValMut<'a>, K, V, marker::Leaf>, marker::Edge> {
 418     /// Moves the leaf edge handle to the next leaf edge and returns references to the
 419     /// key and value in between.
 420     ///
 421     /// # Safety
 422     /// There must be another KV in the direction travelled.
 423     unsafe fn next_unchecked(&mut self) -> (&'a K, &'a mut V) {
 424         let kv = super::mem::replace(self, |leaf_edge| {
 425             let kv = leaf_edge.next_kv().ok().unwrap();
 426             (unsafe { ptr::read(&kv) }.next_leaf_edge(), kv)
 427         });
 428         // Doing this last is faster, according to benchmarks.
 429         kv.into_kv_valmut()
 430     }
 431
 432     /// Moves the leaf edge handle to the previous leaf and returns references to the
 433     /// key and value in between.
 434     ///
 435     /// # Safety
 436     /// There must be another KV in the direction travelled.
 437     unsafe fn next_back_unchecked(&mut self) -> (&'a K, &'a mut V) {
 438         let kv = super::mem::replace(self, |leaf_edge| {
 439             let kv = leaf_edge.next_back_kv().ok().unwrap();
 440             (unsafe { ptr::read(&kv) }.next_back_leaf_edge(), kv)
 441         });
 442         // Doing this last is faster, according to benchmarks.
 443         kv.into_kv_valmut()
 444     }
 445 }
 446
 447 impl<K, V> Handle<NodeRef<marker::Dying, K, V, marker::Leaf>, marker::Edge> {
 448     /// Moves the leaf edge handle to the next leaf edge and returns the key and value
 449     /// in between, deallocating any node left behind while leaving the corresponding
 450     /// edge in its parent node dangling.
 451     ///
 452     /// # Safety
 453     /// - There must be another KV in the direction travelled.
 454     /// - That KV was not previously returned by counterpart
 455     ///   `deallocating_next_back_unchecked` on any copy of the handles
 456     ///   being used to traverse the tree.
 457     ///
 458     /// The only safe way to proceed with the updated handle is to compare it, drop it,
 459     /// or call this method or counterpart `deallocating_next_back_unchecked` again.
 460     pub unsafe fn deallocating_next_unchecked(
 461         &mut self,
 462     ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
 463         super::mem::replace(self, |leaf_edge| unsafe { leaf_edge.deallocating_next().unwrap() })
 464     }
 465
 466     /// Moves the leaf edge handle to the previous leaf edge and returns the key and value
 467     /// in between, deallocating any node left behind while leaving the corresponding
 468     /// edge in its parent node dangling.
 469     ///
 470     /// # Safety
 471     /// - There must be another KV in the direction travelled.
 472     /// - That leaf edge was not previously returned by counterpart
 473     ///   `deallocating_next_unchecked` on any copy of the handles
 474     ///   being used to traverse the tree.
 475     ///
 476     /// The only safe way to proceed with the updated handle is to compare it, drop it,
 477     /// or call this method or counterpart `deallocating_next_unchecked` again.
 478     unsafe fn deallocating_next_back_unchecked(
 479         &mut self,
 480     ) -> Handle<NodeRef<marker::Dying, K, V, marker::LeafOrInternal>, marker::KV> {
 481         super::mem::replace(self, |leaf_edge| unsafe {
 482             leaf_edge.deallocating_next_back().unwrap()
 483         })
 484     }
 485 }
 486
 487 impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
 488     /// Returns the leftmost leaf edge in or underneath a node - in other words, the edge
 489     /// you need first when navigating forward (or last when navigating backward).
 490     #[inline]
 491     pub fn first_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
 492         let mut node = self;
 493         loop {
 494             match node.force() {
 495                 Leaf(leaf) => return leaf.first_edge(),
 496                 Internal(internal) => node = internal.first_edge().descend(),
 497             }
 498         }
 499     }
 500
 501     /// Returns the rightmost leaf edge in or underneath a node - in other words, the edge
 502     /// you need last when navigating forward (or first when navigating backward).
 503     #[inline]
 504     pub fn last_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
 505         let mut node = self;
 506         loop {
 507             match node.force() {
 508                 Leaf(leaf) => return leaf.last_edge(),
 509                 Internal(internal) => node = internal.last_edge().descend(),
 510             }
 511         }
 512     }
 513 }
 514
 515 pub enum Position<BorrowType, K, V> {
 516     Leaf(NodeRef<BorrowType, K, V, marker::Leaf>),
 517     Internal(NodeRef<BorrowType, K, V, marker::Internal>),
 518     InternalKV(Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::KV>),
 519 }
 520
 521 impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> {
 522     /// Visits leaf nodes and internal KVs in order of ascending keys, and also
 523     /// visits internal nodes as a whole in a depth first order, meaning that
 524     /// internal nodes precede their individual KVs and their child nodes.
 525     pub fn visit_nodes_in_order<F>(self, mut visit: F)
 526     where
 527         F: FnMut(Position<marker::Immut<'a>, K, V>),
 528     {
 529         match self.force() {
 530             Leaf(leaf) => visit(Position::Leaf(leaf)),
 531             Internal(internal) => {
 532                 visit(Position::Internal(internal));
 533                 let mut edge = internal.first_edge();
 534                 loop {
 535                     edge = match edge.descend().force() {
 536                         Leaf(leaf) => {
 537                             visit(Position::Leaf(leaf));
 538                             match edge.next_kv() {
 539                                 Ok(kv) => {
 540                                     visit(Position::InternalKV(kv));
 541                                     kv.right_edge()
 542                                 }
 543                                 Err(_) => return,
 544                             }
 545                         }
 546                         Internal(internal) => {
 547                             visit(Position::Internal(internal));
 548                             internal.first_edge()
 549                         }
 550                     }
 551                 }
 552             }
 553         }
 554     }
 555
 556     /// Calculates the number of elements in a (sub)tree.
 557     pub fn calc_length(self) -> usize {
 558         let mut result = 0;
 559         self.visit_nodes_in_order(|pos| match pos {
 560             Position::Leaf(node) => result += node.len(),
 561             Position::Internal(node) => result += node.len(),
 562             Position::InternalKV(_) => (),
 563         });
 564         result
 565     }
 566 }
 567
 568 impl<BorrowType: marker::BorrowType, K, V>
 569     Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>
 570 {
 571     /// Returns the leaf edge closest to a KV for forward navigation.
 572     pub fn next_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
 573         match self.force() {
 574             Leaf(leaf_kv) => leaf_kv.right_edge(),
 575             Internal(internal_kv) => {
 576                 let next_internal_edge = internal_kv.right_edge();
 577                 next_internal_edge.descend().first_leaf_edge()
 578             }
 579         }
 580     }
 581
 582     /// Returns the leaf edge closest to a KV for backward navigation.
 583     fn next_back_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
 584         match self.force() {
 585             Leaf(leaf_kv) => leaf_kv.left_edge(),
 586             Internal(internal_kv) => {
 587                 let next_internal_edge = internal_kv.left_edge();
 588                 next_internal_edge.descend().last_leaf_edge()
 589             }
 590         }
 591     }
 592 }