diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:19:43 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:19:43 +0000 |
commit | 3e3e70d529d8c7d7c4d7bc4fefc9f109393b9245 (patch) | |
tree | daf049b282ab10e8c3d03e409b3cd84ff3f7690c /library/alloc/src/collections/btree/navigate.rs | |
parent | Adding debian version 1.68.2+dfsg1-1. (diff) | |
download | rustc-3e3e70d529d8c7d7c4d7bc4fefc9f109393b9245.tar.xz rustc-3e3e70d529d8c7d7c4d7bc4fefc9f109393b9245.zip |
Merging upstream version 1.69.0+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'library/alloc/src/collections/btree/navigate.rs')
-rw-r--r-- | library/alloc/src/collections/btree/navigate.rs | 55 |
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; + } + } + } + } +} |