1 files changed, 53 insertions, 2 deletions
diff --git a/library/alloc/src/collections/btree/navigate.rs b/library/alloc/src/collections/btree/navigate.rs
index 1e33c1e64..b890717e5 100644
--- a/library/alloc/src/collections/btree/navigate.rs
+++ b/library/alloc/src/collections/btree/navigate.rs
@@ -4,6 +4,7 @@ use core::ops::RangeBounds;
 use core::ptr;
 
 use super::node::{marker, ForceResult::*, Handle, NodeRef};
+use super::search::SearchBound;
 
 use crate::alloc::Allocator;
 // `front` and `back` are always both `None` or both `Some`.
@@ -386,7 +387,7 @@ impl<BorrowType: marker::BorrowType, K, V>
     /// Given a leaf edge handle, returns [`Result::Ok`] with a handle to the neighboring KV
     /// on the left side, which is either in the same leaf node or in an ancestor node.
     /// If the leaf edge is the first one in the tree, returns [`Result::Err`] with the root node.
-    fn next_back_kv(
+    pub fn next_back_kv(
         self,
     ) -> Result<
         Handle<NodeRef<BorrowType, K, V, marker::LeafOrInternal>, marker::KV>,
@@ -707,7 +708,9 @@ impl<BorrowType: marker::BorrowType, K, V>
     }
 
     /// Returns the leaf edge closest to a KV for backward navigation.
-    fn next_back_leaf_edge(self) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
+    pub fn next_back_leaf_edge(
+        self,
+    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge> {
         match self.force() {
             Leaf(leaf_kv) => leaf_kv.left_edge(),
             Internal(internal_kv) => {
@@ -717,3 +720,51 @@ impl<BorrowType: marker::BorrowType, K, V>
         }
     }
 }
+
+impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
+    /// Returns the leaf edge corresponding to the first point at which the
+    /// given bound is true.
+    pub fn lower_bound<Q: ?Sized>(
+        self,
+        mut bound: SearchBound<&Q>,
+    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>
+    where
+        Q: Ord,
+        K: Borrow<Q>,
+    {
+        let mut node = self;
+        loop {
+            let (edge, new_bound) = node.find_lower_bound_edge(bound);
+            match edge.force() {
+                Leaf(edge) => return edge,
+                Internal(edge) => {
+                    node = edge.descend();
+                    bound = new_bound;
+                }
+            }
+        }
+    }
+
+    /// Returns the leaf edge corresponding to the last point at which the
+    /// given bound is true.
+    pub fn upper_bound<Q: ?Sized>(
+        self,
+        mut bound: SearchBound<&Q>,
+    ) -> Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>
+    where
+        Q: Ord,
+        K: Borrow<Q>,
+    {
+        let mut node = self;
+        loop {
+            let (edge, new_bound) = node.find_upper_bound_edge(bound);
+            match edge.force() {
+                Leaf(edge) => return edge,
+                Internal(edge) => {
+                    node = edge.descend();
+                    bound = new_bound;
+                }
+            }
+        }
+    }
+}