diff options
Diffstat (limited to 'library/alloc/src/collections/btree')
| -rw-r--r-- | library/alloc/src/collections/btree/map.rs | 128 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/map/tests.rs | 67 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/mod.rs | 1 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/navigate.rs | 12 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/set.rs | 55 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/set/tests.rs | 1 |
6 files changed, 248 insertions, 16 deletions
diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 386cd1a16..afdc99817 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -3,7 +3,7 @@ use core::borrow::Borrow; use core::cmp::Ordering; use core::fmt::{self, Debug}; use core::hash::{Hash, Hasher}; -use core::iter::{FromIterator, FusedIterator}; +use core::iter::FusedIterator; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop}; use core::ops::{Bound, Index, RangeBounds}; @@ -362,6 +362,20 @@ impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<'a, K: 'a, V: 'a> Default for Iter<'a, K, V> { + /// Creates an empty `btree_map::Iter`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::Iter<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + Iter { range: Default::default(), length: 0 } + } +} + /// A mutable iterator over the entries of a `BTreeMap`. /// /// This `struct` is created by the [`iter_mut`] method on [`BTreeMap`]. See its @@ -386,13 +400,26 @@ impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<'a, K: 'a, V: 'a> Default for IterMut<'a, K, V> { + /// Creates an empty `btree_map::IterMut`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::IterMut<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IterMut { range: Default::default(), length: 0, _marker: PhantomData {} } + } +} + /// An owning iterator over the entries of a `BTreeMap`. /// /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`] /// (provided by the [`IntoIterator`] trait). See its documentation for more. /// /// [`into_iter`]: IntoIterator::into_iter -/// [`IntoIterator`]: core::iter::IntoIterator #[stable(feature = "rust1", since = "1.0.0")] #[rustc_insignificant_dtor] pub struct IntoIter< @@ -421,6 +448,23 @@ impl<K: Debug, V: Debug, A: Allocator + Clone> Debug for IntoIter<K, V, A> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V, A> Default for IntoIter<K, V, A> +where + A: Allocator + Default + Clone, +{ + /// Creates an empty `btree_map::IntoIter`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::IntoIter<u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IntoIter { range: Default::default(), length: 0, alloc: Default::default() } + } +} + /// An iterator over the keys of a `BTreeMap`. /// /// This `struct` is created by the [`keys`] method on [`BTreeMap`]. See its @@ -605,7 +649,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { #[stable(feature = "rust1", since = "1.0.0")] pub fn clear(&mut self) { // avoid moving the allocator - mem::drop(BTreeMap { + drop(BTreeMap { root: mem::replace(&mut self.root, None), length: mem::replace(&mut self.length, 0), alloc: self.alloc.clone(), @@ -1768,6 +1812,20 @@ impl<K, V> Clone for Keys<'_, K, V> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V> Default for Keys<'_, K, V> { + /// Creates an empty `btree_map::Keys`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::Keys<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + Keys { inner: Default::default() } + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K, V> Iterator for Values<'a, K, V> { type Item = &'a V; @@ -1809,6 +1867,20 @@ impl<K, V> Clone for Values<'_, K, V> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V> Default for Values<'_, K, V> { + /// Creates an empty `btree_map::Values`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::Values<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + Values { inner: Default::default() } + } +} + /// An iterator produced by calling `drain_filter` on BTreeMap. #[unstable(feature = "btree_drain_filter", issue = "70530")] pub struct DrainFilter< @@ -1945,6 +2017,20 @@ impl<'a, K, V> Iterator for Range<'a, K, V> { } } +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V> Default for Range<'_, K, V> { + /// Creates an empty `btree_map::Range`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::Range<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.count(), 0); + /// ``` + fn default() -> Self { + Range { inner: Default::default() } + } +} + #[stable(feature = "map_values_mut", since = "1.10.0")] impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { type Item = &'a mut V; @@ -2021,6 +2107,23 @@ impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoKeys<K, V, A> { #[stable(feature = "map_into_keys_values", since = "1.54.0")] impl<K, V, A: Allocator + Clone> FusedIterator for IntoKeys<K, V, A> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V, A> Default for IntoKeys<K, V, A> +where + A: Allocator + Default + Clone, +{ + /// Creates an empty `btree_map::IntoKeys`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::IntoKeys<u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IntoKeys { inner: Default::default() } + } +} + #[stable(feature = "map_into_keys_values", since = "1.54.0")] impl<K, V, A: Allocator + Clone> Iterator for IntoValues<K, V, A> { type Item = V; @@ -2055,6 +2158,23 @@ impl<K, V, A: Allocator + Clone> ExactSizeIterator for IntoValues<K, V, A> { #[stable(feature = "map_into_keys_values", since = "1.54.0")] impl<K, V, A: Allocator + Clone> FusedIterator for IntoValues<K, V, A> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<K, V, A> Default for IntoValues<K, V, A> +where + A: Allocator + Default + Clone, +{ + /// Creates an empty `btree_map::IntoValues`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::IntoValues<u8, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IntoValues { inner: Default::default() } + } +} + #[stable(feature = "btree_range", since = "1.17.0")] impl<'a, K, V> DoubleEndedIterator for Range<'a, K, V> { fn next_back(&mut self) -> Option<(&'a K, &'a V)> { @@ -3062,7 +3182,7 @@ impl<'a, K: Ord, V, A: Allocator + Clone> CursorMut<'a, K, V, A> { panic!("key must be ordered above the current element"); } } - if let Some((next, _)) = self.peek_prev() { + if let Some((next, _)) = self.peek_next() { if &key >= next { panic!("key must be ordered below the next element"); } diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index 76c2f27b4..da00d83bd 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -9,8 +9,7 @@ use crate::testing::ord_chaos::{Cyclic3, Governed, Governor}; use crate::testing::rng::DeterministicRng; use crate::vec::Vec; use std::cmp::Ordering; -use std::convert::TryFrom; -use std::iter::{self, FromIterator}; +use std::iter; use std::mem; use std::ops::Bound::{self, Excluded, Included, Unbounded}; use std::ops::RangeBounds; @@ -2385,3 +2384,67 @@ fn test_cursor_mut() { assert_eq!(cur.key(), Some(&4)); assert_eq!(map, BTreeMap::from([(0, '?'), (1, 'a'), (3, 'c'), (4, 'd')])); } + +#[should_panic(expected = "key must be ordered above the previous element")] +#[test] +fn test_cursor_mut_insert_before_1() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_before(0, 'd'); +} + +#[should_panic(expected = "key must be ordered above the previous element")] +#[test] +fn test_cursor_mut_insert_before_2() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_before(1, 'd'); +} + +#[should_panic(expected = "key must be ordered below the current element")] +#[test] +fn test_cursor_mut_insert_before_3() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_before(2, 'd'); +} + +#[should_panic(expected = "key must be ordered below the current element")] +#[test] +fn test_cursor_mut_insert_before_4() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_before(3, 'd'); +} + +#[should_panic(expected = "key must be ordered above the current element")] +#[test] +fn test_cursor_mut_insert_after_1() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_after(1, 'd'); +} + +#[should_panic(expected = "key must be ordered above the current element")] +#[test] +fn test_cursor_mut_insert_after_2() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_after(2, 'd'); +} + +#[should_panic(expected = "key must be ordered below the next element")] +#[test] +fn test_cursor_mut_insert_after_3() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_after(3, 'd'); +} + +#[should_panic(expected = "key must be ordered below the next element")] +#[test] +fn test_cursor_mut_insert_after_4() { + let mut map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); + let mut cur = map.upper_bound_mut(Bound::Included(&2)); + cur.insert_after(4, 'd'); +} diff --git a/library/alloc/src/collections/btree/mod.rs b/library/alloc/src/collections/btree/mod.rs index 7552f2fc0..c7d0144de 100644 --- a/library/alloc/src/collections/btree/mod.rs +++ b/library/alloc/src/collections/btree/mod.rs @@ -13,7 +13,6 @@ pub mod set; mod set_val; mod split; -#[doc(hidden)] trait Recover<Q: ?Sized> { type Key; diff --git a/library/alloc/src/collections/btree/navigate.rs b/library/alloc/src/collections/btree/navigate.rs index b890717e5..a85a31624 100644 --- a/library/alloc/src/collections/btree/navigate.rs +++ b/library/alloc/src/collections/btree/navigate.rs @@ -19,6 +19,12 @@ impl<'a, K: 'a, V: 'a> Clone for LeafRange<marker::Immut<'a>, K, V> { } } +impl<B, K, V> Default for LeafRange<B, K, V> { + fn default() -> Self { + LeafRange { front: None, back: None } + } +} + impl<BorrowType, K, V> LeafRange<BorrowType, K, V> { pub fn none() -> Self { LeafRange { front: None, back: None } @@ -124,6 +130,12 @@ pub struct LazyLeafRange<BorrowType, K, V> { back: Option<LazyLeafHandle<BorrowType, K, V>>, } +impl<B, K, V> Default for LazyLeafRange<B, K, V> { + fn default() -> Self { + LazyLeafRange { front: None, back: None } + } +} + impl<'a, K: 'a, V: 'a> Clone for LazyLeafRange<marker::Immut<'a>, K, V> { fn clone(&self) -> Self { LazyLeafRange { front: self.front.clone(), back: self.back.clone() } diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs index 4ddb21192..da952a13f 100644 --- a/library/alloc/src/collections/btree/set.rs +++ b/library/alloc/src/collections/btree/set.rs @@ -1,13 +1,10 @@ -// This is pretty much entirely stolen from TreeSet, since BTreeMap has an identical interface -// to TreeMap - use crate::vec::Vec; use core::borrow::Borrow; use core::cmp::Ordering::{self, Equal, Greater, Less}; use core::cmp::{max, min}; use core::fmt::{self, Debug}; use core::hash::{Hash, Hasher}; -use core::iter::{FromIterator, FusedIterator, Peekable}; +use core::iter::{FusedIterator, Peekable}; use core::mem::ManuallyDrop; use core::ops::{BitAnd, BitOr, BitXor, RangeBounds, Sub}; @@ -18,8 +15,6 @@ use super::Recover; use crate::alloc::{Allocator, Global}; -// FIXME(conventions): implement bounded iterators - /// An ordered set based on a B-Tree. /// /// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance @@ -35,7 +30,6 @@ use crate::alloc::{Allocator, Global}; /// Iterators returned by [`BTreeSet::iter`] produce their items in order, and take worst-case /// logarithmic and amortized constant time per item returned. /// -/// [`Ord`]: core::cmp::Ord /// [`Cell`]: core::cell::Cell /// [`RefCell`]: core::cell::RefCell /// @@ -152,7 +146,6 @@ impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { /// (provided by the [`IntoIterator`] trait). See its documentation for more. /// /// [`into_iter`]: BTreeSet#method.into_iter -/// [`IntoIterator`]: core::iter::IntoIterator #[stable(feature = "rust1", since = "1.0.0")] #[derive(Debug)] pub struct IntoIter< @@ -1544,6 +1537,21 @@ impl<T, A: Allocator + Clone> Iterator for IntoIter<T, A> { self.iter.size_hint() } } + +#[stable(feature = "default_iters", since = "1.70.0")] +impl<T> Default for Iter<'_, T> { + /// Creates an empty `btree_set::Iter`. + /// + /// ``` + /// # use std::collections::btree_set; + /// let iter: btree_set::Iter<'_, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + Iter { iter: Default::default() } + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<T, A: Allocator + Clone> DoubleEndedIterator for IntoIter<T, A> { fn next_back(&mut self) -> Option<T> { @@ -1560,6 +1568,23 @@ impl<T, A: Allocator + Clone> ExactSizeIterator for IntoIter<T, A> { #[stable(feature = "fused", since = "1.26.0")] impl<T, A: Allocator + Clone> FusedIterator for IntoIter<T, A> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<T, A> Default for IntoIter<T, A> +where + A: Allocator + Default + Clone, +{ + /// Creates an empty `btree_set::IntoIter`. + /// + /// ``` + /// # use std::collections::btree_set; + /// let iter: btree_set::IntoIter<u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IntoIter { iter: Default::default() } + } +} + #[stable(feature = "btree_range", since = "1.17.0")] impl<T> Clone for Range<'_, T> { fn clone(&self) -> Self { @@ -1598,6 +1623,20 @@ impl<'a, T> DoubleEndedIterator for Range<'a, T> { #[stable(feature = "fused", since = "1.26.0")] impl<T> FusedIterator for Range<'_, T> {} +#[stable(feature = "default_iters", since = "1.70.0")] +impl<T> Default for Range<'_, T> { + /// Creates an empty `btree_set::Range`. + /// + /// ``` + /// # use std::collections::btree_set; + /// let iter: btree_set::Range<'_, u8> = Default::default(); + /// assert_eq!(iter.count(), 0); + /// ``` + fn default() -> Self { + Range { iter: Default::default() } + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<T, A: Allocator + Clone> Clone for Difference<'_, T, A> { fn clone(&self) -> Self { diff --git a/library/alloc/src/collections/btree/set/tests.rs b/library/alloc/src/collections/btree/set/tests.rs index 7b8d41a60..a7c839d77 100644 --- a/library/alloc/src/collections/btree/set/tests.rs +++ b/library/alloc/src/collections/btree/set/tests.rs @@ -4,7 +4,6 @@ use crate::testing::rng::DeterministicRng; use crate::vec::Vec; use std::cmp::Ordering; use std::hash::{Hash, Hasher}; -use std::iter::FromIterator; use std::ops::Bound::{Excluded, Included}; use std::panic::{catch_unwind, AssertUnwindSafe}; |