Introduce `Cursor`/`CursorMut`/`CursorMutKey` thrichotomy for `BTreeS… · patricklam/verify-rust-std@c7be27f
@@ -1249,25 +1249,25 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
12491249 ///
12501250 /// let mut set = BTreeSet::from([1, 2, 3, 4]);
12511251 ///
1252- /// let mut cursor = unsafe { set.lower_bound_mut(Bound::Included(&2)) };
1252+ /// let mut cursor = set.lower_bound_mut(Bound::Included(&2));
12531253 /// assert_eq!(cursor.peek_prev(), Some(&mut 1));
12541254 /// assert_eq!(cursor.peek_next(), Some(&mut 2));
12551255 ///
1256- /// let mut cursor = unsafe { set.lower_bound_mut(Bound::Excluded(&2)) };
1256+ /// let mut cursor = set.lower_bound_mut(Bound::Excluded(&2));
12571257 /// assert_eq!(cursor.peek_prev(), Some(&mut 2));
12581258 /// assert_eq!(cursor.peek_next(), Some(&mut 3));
12591259 ///
1260- /// let mut cursor = unsafe { set.lower_bound_mut(Bound::Unbounded) };
1260+ /// let mut cursor = set.lower_bound_mut(Bound::Unbounded);
12611261 /// assert_eq!(cursor.peek_prev(), None);
12621262 /// assert_eq!(cursor.peek_next(), Some(&mut 1));
12631263 /// ```
12641264 #[unstable(feature = "btree_cursors", issue = "107540")]
1265-pub unsafe fn lower_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, T, A>
1265+pub fn lower_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, T, A>
12661266where
12671267T: Borrow<Q> + Ord,
12681268Q: Ord,
12691269{
1270-CursorMut { inner: unsafe { self.map.lower_bound_mut(bound).with_mutable_key() } }
1270+CursorMut { inner: self.map.lower_bound_mut(bound) }
12711271}
1272127212731273/// Returns a [`Cursor`] pointing at the gap after the greatest element
@@ -1353,7 +1353,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> {
13531353T: Borrow<Q> + Ord,
13541354Q: Ord,
13551355{
1356-CursorMut { inner: unsafe { self.map.upper_bound_mut(bound).with_mutable_key() } }
1356+CursorMut { inner: self.map.upper_bound_mut(bound) }
13571357}
13581358}
13591359@@ -2010,6 +2010,31 @@ impl<K: Debug> Debug for Cursor<'_, K> {
20102010}
20112011}
201220122013+/// A cursor over a `BTreeSet` with editing operations.
2014+///
2015+/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can
2016+/// safely mutate the set during iteration. This is because the lifetime of its yielded
2017+/// references is tied to its own lifetime, instead of just the underlying map. This means
2018+/// cursors cannot yield multiple elements at once.
2019+///
2020+/// Cursors always point to a gap between two elements in the set, and can
2021+/// operate on the two immediately adjacent elements.
2022+///
2023+/// A `CursorMut` is created with the [`BTreeSet::lower_bound_mut`] and [`BTreeSet::upper_bound_mut`]
2024+/// methods.
2025+#[unstable(feature = "btree_cursors", issue = "107540")]
2026+pub struct CursorMut<'a, K: 'a, #[unstable(feature = "allocator_api", issue = "32838")] A = Global>
2027+{
2028+inner: super::map::CursorMut<'a, K, SetValZST, A>,
2029+}
2030+2031+#[unstable(feature = "btree_cursors", issue = "107540")]
2032+impl<K: Debug, A> Debug for CursorMut<'_, K, A> {
2033+fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2034+ f.write_str("CursorMut")
2035+}
2036+}
2037+20132038/// A cursor over a `BTreeSet` with editing operations, and which allows
20142039/// mutating elements.
20152040///
@@ -2021,8 +2046,8 @@ impl<K: Debug> Debug for Cursor<'_, K> {
20212046/// Cursors always point to a gap between two elements in the set, and can
20222047/// operate on the two immediately adjacent elements.
20232048///
2024-/// A `CursorMut` is created with the [`BTreeSet::lower_bound_mut`] and
2025-/// [`BTreeSet::upper_bound_mut`] methods.
2049+/// A `CursorMutKey` is created from a [`CursorMut`] with the
2050+/// [`CursorMut::with_mutable_key`] method.
20262051///
20272052/// # Safety
20282053///
@@ -2032,15 +2057,18 @@ impl<K: Debug> Debug for Cursor<'_, K> {
20322057/// * The newly inserted element must be unique in the tree.
20332058/// * All elements in the tree must remain in sorted order.
20342059#[unstable(feature = "btree_cursors", issue = "107540")]
2035-pub struct CursorMut<'a, K: 'a, #[unstable(feature = "allocator_api", issue = "32838")] A = Global>
2036-{
2060+pub struct CursorMutKey<
2061+'a,
2062+K: 'a,
2063+#[unstable(feature = "allocator_api", issue = "32838")] A = Global,
2064+> {
20372065inner: super::map::CursorMutKey<'a, K, SetValZST, A>,
20382066}
2039206720402068#[unstable(feature = "btree_cursors", issue = "107540")]
2041-impl<K: Debug, A> Debug for CursorMut<'_, K, A> {
2069+impl<K: Debug, A> Debug for CursorMutKey<'_, K, A> {
20422070fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2043- f.write_str("CursorMut")
2071+ f.write_str("CursorMutKey")
20442072}
20452073}
20462074@@ -2089,7 +2117,7 @@ impl<'a, T, A> CursorMut<'a, T, A> {
20892117 /// If the cursor is already at the end of the set then `None` is returned
20902118 /// and the cursor is not moved.
20912119 #[unstable(feature = "btree_cursors", issue = "107540")]
2092-pub fn next(&mut self) -> Option<&mut T> {
2120+pub fn next(&mut self) -> Option<&T> {
20932121self.inner.next().map(|(k, _)| k)
20942122}
20952123@@ -2099,23 +2127,23 @@ impl<'a, T, A> CursorMut<'a, T, A> {
20992127 /// If the cursor is already at the start of the set then `None` is returned
21002128 /// and the cursor is not moved.
21012129 #[unstable(feature = "btree_cursors", issue = "107540")]
2102-pub fn prev(&mut self) -> Option<&mut T> {
2130+pub fn prev(&mut self) -> Option<&T> {
21032131self.inner.prev().map(|(k, _)| k)
21042132}
2105213321062134/// Returns a reference to the next element without moving the cursor.
21072135 ///
21082136 /// If the cursor is at the end of the set then `None` is returned.
21092137 #[unstable(feature = "btree_cursors", issue = "107540")]
2110-pub fn peek_next(&mut self) -> Option<&mut T> {
2138+pub fn peek_next(&mut self) -> Option<&T> {
21112139self.inner.peek_next().map(|(k, _)| k)
21122140}
2113214121142142/// Returns a reference to the previous element without moving the cursor.
21152143 ///
21162144 /// If the cursor is at the start of the set then `None` is returned.
21172145 #[unstable(feature = "btree_cursors", issue = "107540")]
2118-pub fn peek_prev(&mut self) -> Option<&mut T> {
2146+pub fn peek_prev(&mut self) -> Option<&T> {
21192147self.inner.peek_prev().map(|(k, _)| k)
21202148}
21212149@@ -2129,6 +2157,70 @@ impl<'a, T, A> CursorMut<'a, T, A> {
21292157pub fn as_cursor(&self) -> Cursor<'_, T> {
21302158Cursor { inner: self.inner.as_cursor() }
21312159}
2160+2161+/// Converts the cursor into a [`CursorMutKey`], which allows mutating
2162+ /// elements in the tree.
2163+ ///
2164+ /// # Safety
2165+ ///
2166+ /// Since this cursor allows mutating elements, you must ensure that the
2167+ /// `BTreeSet` invariants are maintained. Specifically:
2168+ ///
2169+ /// * The newly inserted element must be unique in the tree.
2170+ /// * All elements in the tree must remain in sorted order.
2171+ #[unstable(feature = "btree_cursors", issue = "107540")]
2172+pub unsafe fn with_mutable_key(self) -> CursorMutKey<'a, T, A> {
2173+CursorMutKey { inner: unsafe { self.inner.with_mutable_key() } }
2174+}
2175+}
2176+2177+impl<'a, T, A> CursorMutKey<'a, T, A> {
2178+/// Advances the cursor to the next gap, returning the element that it
2179+ /// moved over.
2180+ ///
2181+ /// If the cursor is already at the end of the set then `None` is returned
2182+ /// and the cursor is not moved.
2183+ #[unstable(feature = "btree_cursors", issue = "107540")]
2184+pub fn next(&mut self) -> Option<&mut T> {
2185+self.inner.next().map(|(k, _)| k)
2186+}
2187+2188+/// Advances the cursor to the previous gap, returning the element that it
2189+ /// moved over.
2190+ ///
2191+ /// If the cursor is already at the start of the set then `None` is returned
2192+ /// and the cursor is not moved.
2193+ #[unstable(feature = "btree_cursors", issue = "107540")]
2194+pub fn prev(&mut self) -> Option<&mut T> {
2195+self.inner.prev().map(|(k, _)| k)
2196+}
2197+2198+/// Returns a reference to the next element without moving the cursor.
2199+ ///
2200+ /// If the cursor is at the end of the set then `None` is returned
2201+ #[unstable(feature = "btree_cursors", issue = "107540")]
2202+pub fn peek_next(&mut self) -> Option<&mut T> {
2203+self.inner.peek_next().map(|(k, _)| k)
2204+}
2205+2206+/// Returns a reference to the previous element without moving the cursor.
2207+ ///
2208+ /// If the cursor is at the start of the set then `None` is returned.
2209+ #[unstable(feature = "btree_cursors", issue = "107540")]
2210+pub fn peek_prev(&mut self) -> Option<&mut T> {
2211+self.inner.peek_prev().map(|(k, _)| k)
2212+}
2213+2214+/// Returns a read-only cursor pointing to the same location as the
2215+ /// `CursorMutKey`.
2216+ ///
2217+ /// The lifetime of the returned `Cursor` is bound to that of the
2218+ /// `CursorMutKey`, which means it cannot outlive the `CursorMutKey` and that the
2219+ /// `CursorMutKey` is frozen for the lifetime of the `Cursor`.
2220+ #[unstable(feature = "btree_cursors", issue = "107540")]
2221+pub fn as_cursor(&self) -> Cursor<'_, T> {
2222+Cursor { inner: self.inner.as_cursor() }
2223+}
21322224}
2133222521342226impl<'a, T: Ord, A: Allocator + Clone> CursorMut<'a, T, A> {
@@ -2217,6 +2309,92 @@ impl<'a, T: Ord, A: Allocator + Clone> CursorMut<'a, T, A> {
22172309}
22182310}
221923112312+impl<'a, T: Ord, A: Allocator + Clone> CursorMutKey<'a, T, A> {
2313+/// Inserts a new element into the set in the gap that the
2314+ /// cursor is currently pointing to.
2315+ ///
2316+ /// After the insertion the cursor will be pointing at the gap before the
2317+ /// newly inserted element.
2318+ ///
2319+ /// # Safety
2320+ ///
2321+ /// You must ensure that the `BTreeSet` invariants are maintained.
2322+ /// Specifically:
2323+ ///
2324+ /// * The key of the newly inserted element must be unique in the tree.
2325+ /// * All elements in the tree must remain in sorted order.
2326+ #[unstable(feature = "btree_cursors", issue = "107540")]
2327+pub unsafe fn insert_after_unchecked(&mut self, value: T) {
2328+unsafe { self.inner.insert_after_unchecked(value, SetValZST) }
2329+}
2330+2331+/// Inserts a new element into the set in the gap that the
2332+ /// cursor is currently pointing to.
2333+ ///
2334+ /// After the insertion the cursor will be pointing at the gap after the
2335+ /// newly inserted element.
2336+ ///
2337+ /// # Safety
2338+ ///
2339+ /// You must ensure that the `BTreeSet` invariants are maintained.
2340+ /// Specifically:
2341+ ///
2342+ /// * The newly inserted element must be unique in the tree.
2343+ /// * All elements in the tree must remain in sorted order.
2344+ #[unstable(feature = "btree_cursors", issue = "107540")]
2345+pub unsafe fn insert_before_unchecked(&mut self, value: T) {
2346+unsafe { self.inner.insert_before_unchecked(value, SetValZST) }
2347+}
2348+2349+/// Inserts a new element into the set in the gap that the
2350+ /// cursor is currently pointing to.
2351+ ///
2352+ /// After the insertion the cursor will be pointing at the gap before the
2353+ /// newly inserted element.
2354+ ///
2355+ /// If the inserted element is not greater than the element before the
2356+ /// cursor (if any), or if it not less than the element after the cursor (if
2357+ /// any), then an [`UnorderedKeyError`] is returned since this would
2358+ /// invalidate the [`Ord`] invariant between the elements of the set.
2359+ #[unstable(feature = "btree_cursors", issue = "107540")]
2360+pub fn insert_after(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2361+self.inner.insert_after(value, SetValZST)
2362+}
2363+2364+/// Inserts a new element into the set in the gap that the
2365+ /// cursor is currently pointing to.
2366+ ///
2367+ /// After the insertion the cursor will be pointing at the gap after the
2368+ /// newly inserted element.
2369+ ///
2370+ /// If the inserted element is not greater than the element before the
2371+ /// cursor (if any), or if it not less than the element after the cursor (if
2372+ /// any), then an [`UnorderedKeyError`] is returned since this would
2373+ /// invalidate the [`Ord`] invariant between the elements of the set.
2374+ #[unstable(feature = "btree_cursors", issue = "107540")]
2375+pub fn insert_before(&mut self, value: T) -> Result<(), UnorderedKeyError> {
2376+self.inner.insert_before(value, SetValZST)
2377+}
2378+2379+/// Removes the next element from the `BTreeSet`.
2380+ ///
2381+ /// The element that was removed is returned. The cursor position is
2382+ /// unchanged (before the removed element).
2383+ #[unstable(feature = "btree_cursors", issue = "107540")]
2384+pub fn remove_next(&mut self) -> Option<T> {
2385+self.inner.remove_next().map(|(k, _)| k)
2386+}
2387+2388+/// Removes the precending element from the `BTreeSet`.
2389+ ///
2390+ /// The element that was removed is returned. The cursor position is
2391+ /// unchanged (after the removed element).
2392+ #[unstable(feature = "btree_cursors", issue = "107540")]
2393+pub fn remove_prev(&mut self) -> Option<T> {
2394+self.inner.remove_prev().map(|(k, _)| k)
2395+}
2396+}
2397+22202398#[unstable(feature = "btree_cursors", issue = "107540")]
22212399pub use super::map::UnorderedKeyError;
22222400