diff options
Diffstat (limited to 'ctr-std/src/collections/hash/set.rs')
| -rw-r--r-- | ctr-std/src/collections/hash/set.rs | 233 |
1 files changed, 200 insertions, 33 deletions
diff --git a/ctr-std/src/collections/hash/set.rs b/ctr-std/src/collections/hash/set.rs index 72af612..d80df5f 100644 --- a/ctr-std/src/collections/hash/set.rs +++ b/ctr-std/src/collections/hash/set.rs @@ -24,11 +24,10 @@ use super::map::{self, HashMap, Keys, RandomState}; // for `bucket.val` in the case of HashSet. I suppose we would need HKT // to get rid of it properly. -/// An implementation of a hash set using the underlying representation of a -/// HashMap where the value is (). +/// A hash set implemented as a `HashMap` where the value is `()`. /// -/// As with the `HashMap` type, a `HashSet` requires that the elements -/// implement the `Eq` and `Hash` traits. This can frequently be achieved by +/// As with the [`HashMap`] type, a `HashSet` requires that the elements +/// implement the [`Eq`] and [`Hash`] traits. This can frequently be achieved by /// using `#[derive(PartialEq, Eq, Hash)]`. If you implement these yourself, /// it is important that the following property holds: /// @@ -40,9 +39,9 @@ use super::map::{self, HashMap, Keys, RandomState}; /// /// /// It is a logic error for an item to be modified in such a way that the -/// item's hash, as determined by the `Hash` trait, or its equality, as -/// determined by the `Eq` trait, changes while it is in the set. This is -/// normally only possible through `Cell`, `RefCell`, global state, I/O, or +/// item's hash, as determined by the [`Hash`] trait, or its equality, as +/// determined by the [`Eq`] trait, changes while it is in the set. This is +/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or /// unsafe code. /// /// # Examples @@ -75,8 +74,8 @@ use super::map::{self, HashMap, Keys, RandomState}; /// ``` /// /// The easiest way to use `HashSet` with a custom type is to derive -/// `Eq` and `Hash`. We must also derive `PartialEq`, this will in the -/// future be implied by `Eq`. +/// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`], this will in the +/// future be implied by [`Eq`]. /// /// ``` /// use std::collections::HashSet; @@ -99,7 +98,7 @@ use super::map::{self, HashMap, Keys, RandomState}; /// } /// ``` /// -/// HashSet with fixed list of elements can be initialized from an array: +/// A `HashSet` with fixed list of elements can be initialized from an array: /// /// ``` /// use std::collections::HashSet; @@ -110,8 +109,13 @@ use super::map::{self, HashMap, Keys, RandomState}; /// // use the values stored in the set /// } /// ``` - - +/// +/// [`Cell`]: ../../std/cell/struct.Cell.html +/// [`Eq`]: ../../std/cmp/trait.Eq.html +/// [`Hash`]: ../../std/hash/trait.Hash.html +/// [`HashMap`]: struct.HashMap.html +/// [`PartialEq`]: ../../std/cmp/trait.PartialEq.html +/// [`RefCell`]: ../../std/cell/struct.RefCell.html #[derive(Clone)] #[stable(feature = "rust1", since = "1.0.0")] pub struct HashSet<T, S = RandomState> { @@ -181,7 +185,7 @@ impl<T, S> HashSet<T, S> HashSet { map: HashMap::with_hasher(hasher) } } - /// Creates an empty HashSet with with the specified capacity, using + /// Creates an empty `HashSet` with with the specified capacity, using /// `hasher` to hash the keys. /// /// The hash set will be able to hold at least `capacity` elements without @@ -208,7 +212,9 @@ impl<T, S> HashSet<T, S> HashSet { map: HashMap::with_capacity_and_hasher(capacity, hasher) } } - /// Returns a reference to the set's hasher. + /// Returns a reference to the set's [`BuildHasher`]. + /// + /// [`BuildHasher`]: ../../std/hash/trait.BuildHasher.html #[stable(feature = "hashmap_public_hasher", since = "1.9.0")] pub fn hasher(&self) -> &S { self.map.hasher() @@ -271,7 +277,7 @@ impl<T, S> HashSet<T, S> } /// An iterator visiting all elements in arbitrary order. - /// Iterator element type is &'a T. + /// The iterator element type is `&'a T`. /// /// # Examples /// @@ -291,7 +297,8 @@ impl<T, S> HashSet<T, S> Iter { iter: self.map.keys() } } - /// Visit the values representing the difference. + /// Visits the values representing the difference, + /// i.e. the values that are in `self` but not in `other`. /// /// # Examples /// @@ -321,7 +328,8 @@ impl<T, S> HashSet<T, S> } } - /// Visit the values representing the symmetric difference. + /// Visits the values representing the symmetric difference, + /// i.e. the values that are in `self` or in `other` but not in both. /// /// # Examples /// @@ -348,7 +356,8 @@ impl<T, S> HashSet<T, S> SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) } } - /// Visit the values representing the intersection. + /// Visits the values representing the intersection, + /// i.e. the values that are both in `self` and `other`. /// /// # Examples /// @@ -373,7 +382,8 @@ impl<T, S> HashSet<T, S> } } - /// Visit the values representing the union. + /// Visits the values representing the union, + /// i.e. all the values in `self` or `other`, without duplicates. /// /// # Examples /// @@ -456,7 +466,7 @@ impl<T, S> HashSet<T, S> /// Returns `true` if the set contains a value. /// /// The value may be any borrowed form of the set's value type, but - /// `Hash` and `Eq` on the borrowed form *must* match those for + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for /// the value type. /// /// # Examples @@ -468,6 +478,9 @@ impl<T, S> HashSet<T, S> /// assert_eq!(set.contains(&1), true); /// assert_eq!(set.contains(&4), false); /// ``` + /// + /// [`Eq`]: ../../std/cmp/trait.Eq.html + /// [`Hash`]: ../../std/hash/trait.Hash.html #[stable(feature = "rust1", since = "1.0.0")] pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool where T: Borrow<Q>, @@ -479,8 +492,11 @@ impl<T, S> HashSet<T, S> /// Returns a reference to the value in the set, if any, that is equal to the given value. /// /// The value may be any borrowed form of the set's value type, but - /// `Hash` and `Eq` on the borrowed form *must* match those for + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for /// the value type. + /// + /// [`Eq`]: ../../std/cmp/trait.Eq.html + /// [`Hash`]: ../../std/hash/trait.Hash.html #[stable(feature = "set_recovery", since = "1.9.0")] pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T> where T: Borrow<Q>, @@ -489,7 +505,7 @@ impl<T, S> HashSet<T, S> Recover::get(&self.map, value) } - /// Returns `true` if the set has no elements in common with `other`. + /// Returns `true` if `self` has no elements in common with `other`. /// This is equivalent to checking for an empty intersection. /// /// # Examples @@ -511,7 +527,8 @@ impl<T, S> HashSet<T, S> self.iter().all(|v| !other.contains(v)) } - /// Returns `true` if the set is a subset of another. + /// Returns `true` if the set is a subset of another, + /// i.e. `other` contains at least all the values in `self`. /// /// # Examples /// @@ -532,7 +549,8 @@ impl<T, S> HashSet<T, S> self.iter().all(|v| other.contains(v)) } - /// Returns `true` if the set is a superset of another. + /// Returns `true` if the set is a superset of another, + /// i.e. `self` contains at least all the values in `other`. /// /// # Examples /// @@ -590,7 +608,7 @@ impl<T, S> HashSet<T, S> /// present in the set. /// /// The value may be any borrowed form of the set's value type, but - /// `Hash` and `Eq` on the borrowed form *must* match those for + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for /// the value type. /// /// # Examples @@ -604,6 +622,9 @@ impl<T, S> HashSet<T, S> /// assert_eq!(set.remove(&2), true); /// assert_eq!(set.remove(&2), false); /// ``` + /// + /// [`Eq`]: ../../std/cmp/trait.Eq.html + /// [`Hash`]: ../../std/hash/trait.Hash.html #[stable(feature = "rust1", since = "1.0.0")] pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool where T: Borrow<Q>, @@ -615,8 +636,11 @@ impl<T, S> HashSet<T, S> /// Removes and returns the value in the set, if any, that is equal to the given one. /// /// The value may be any borrowed form of the set's value type, but - /// `Hash` and `Eq` on the borrowed form *must* match those for + /// [`Hash`] and [`Eq`] on the borrowed form *must* match those for /// the value type. + /// + /// [`Eq`]: ../../std/cmp/trait.Eq.html + /// [`Hash`]: ../../std/hash/trait.Hash.html #[stable(feature = "set_recovery", since = "1.9.0")] pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> where T: Borrow<Q>, @@ -624,6 +648,27 @@ impl<T, S> HashSet<T, S> { Recover::take(&mut self.map, value) } + + /// Retains only the elements specified by the predicate. + /// + /// In other words, remove all elements `e` such that `f(&e)` returns `false`. + /// + /// # Examples + /// + /// ``` + /// use std::collections::HashSet; + /// + /// let xs = [1,2,3,4,5,6]; + /// let mut set: HashSet<isize> = xs.iter().cloned().collect(); + /// set.retain(|&k| k % 2 == 0); + /// assert_eq!(set.len(), 3); + /// ``` + #[stable(feature = "retain_hash_collection", since = "1.18.0")] + pub fn retain<F>(&mut self, mut f: F) + where F: FnMut(&T) -> bool + { + self.map.retain(|k, _| f(k)); + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -828,25 +873,49 @@ impl<'a, 'b, T, S> Sub<&'b HashSet<T, S>> for &'a HashSet<T, S> } } -/// HashSet iterator +/// An iterator over the items of a `HashSet`. +/// +/// This `struct` is created by the [`iter`] method on [`HashSet`]. +/// See its documentation for more. +/// +/// [`HashSet`]: struct.HashSet.html +/// [`iter`]: struct.HashSet.html#method.iter #[stable(feature = "rust1", since = "1.0.0")] pub struct Iter<'a, K: 'a> { iter: Keys<'a, K, ()>, } -/// HashSet move iterator +/// An owning iterator over the items of a `HashSet`. +/// +/// This `struct` is created by the [`into_iter`] method on [`HashSet`][`HashSet`] +/// (provided by the `IntoIterator` trait). See its documentation for more. +/// +/// [`HashSet`]: struct.HashSet.html +/// [`into_iter`]: struct.HashSet.html#method.into_iter #[stable(feature = "rust1", since = "1.0.0")] pub struct IntoIter<K> { iter: map::IntoIter<K, ()>, } -/// HashSet drain iterator +/// A draining iterator over the items of a `HashSet`. +/// +/// This `struct` is created by the [`drain`] method on [`HashSet`]. +/// See its documentation for more. +/// +/// [`HashSet`]: struct.HashSet.html +/// [`drain`]: struct.HashSet.html#method.drain #[stable(feature = "rust1", since = "1.0.0")] pub struct Drain<'a, K: 'a> { iter: map::Drain<'a, K, ()>, } -/// Intersection iterator +/// A lazy iterator producing elements in the intersection of `HashSet`s. +/// +/// This `struct` is created by the [`intersection`] method on [`HashSet`]. +/// See its documentation for more. +/// +/// [`HashSet`]: struct.HashSet.html +/// [`intersection`]: struct.HashSet.html#method.intersection #[stable(feature = "rust1", since = "1.0.0")] pub struct Intersection<'a, T: 'a, S: 'a> { // iterator of the first set @@ -855,7 +924,13 @@ pub struct Intersection<'a, T: 'a, S: 'a> { other: &'a HashSet<T, S>, } -/// Difference iterator +/// A lazy iterator producing elements in the difference of `HashSet`s. +/// +/// This `struct` is created by the [`difference`] method on [`HashSet`]. +/// See its documentation for more. +/// +/// [`HashSet`]: struct.HashSet.html +/// [`difference`]: struct.HashSet.html#method.difference #[stable(feature = "rust1", since = "1.0.0")] pub struct Difference<'a, T: 'a, S: 'a> { // iterator of the first set @@ -864,13 +939,25 @@ pub struct Difference<'a, T: 'a, S: 'a> { other: &'a HashSet<T, S>, } -/// Symmetric difference iterator. +/// A lazy iterator producing elements in the symmetric difference of `HashSet`s. +/// +/// This `struct` is created by the [`symmetric_difference`] method on +/// [`HashSet`]. See its documentation for more. +/// +/// [`HashSet`]: struct.HashSet.html +/// [`symmetric_difference`]: struct.HashSet.html#method.symmetric_difference #[stable(feature = "rust1", since = "1.0.0")] pub struct SymmetricDifference<'a, T: 'a, S: 'a> { iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>, } -/// Set union iterator. +/// A lazy iterator producing elements in the union of `HashSet`s. +/// +/// This `struct` is created by the [`union`] method on [`HashSet`]. +/// See its documentation for more. +/// +/// [`HashSet`]: struct.HashSet.html +/// [`union`]: struct.HashSet.html#method.union #[stable(feature = "rust1", since = "1.0.0")] pub struct Union<'a, T: 'a, S: 'a> { iter: Chain<Iter<'a, T>, Difference<'a, T, S>>, @@ -948,6 +1035,13 @@ impl<'a, K> ExactSizeIterator for Iter<'a, K> { #[unstable(feature = "fused", issue = "35602")] impl<'a, K> FusedIterator for Iter<'a, K> {} +#[stable(feature = "std_debug", since = "1.16.0")] +impl<'a, K: fmt::Debug> fmt::Debug for Iter<'a, K> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<K> Iterator for IntoIter<K> { type Item = K; @@ -968,6 +1062,17 @@ impl<K> ExactSizeIterator for IntoIter<K> { #[unstable(feature = "fused", issue = "35602")] impl<K> FusedIterator for IntoIter<K> {} +#[stable(feature = "std_debug", since = "1.16.0")] +impl<K: fmt::Debug> fmt::Debug for IntoIter<K> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + let entries_iter = self.iter + .inner + .iter() + .map(|(k, _)| k); + f.debug_list().entries(entries_iter).finish() + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<'a, K> Iterator for Drain<'a, K> { type Item = K; @@ -988,6 +1093,17 @@ impl<'a, K> ExactSizeIterator for Drain<'a, K> { #[unstable(feature = "fused", issue = "35602")] impl<'a, K> FusedIterator for Drain<'a, K> {} +#[stable(feature = "std_debug", since = "1.16.0")] +impl<'a, K: fmt::Debug> fmt::Debug for Drain<'a, K> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + let entries_iter = self.iter + .inner + .iter() + .map(|(k, _)| k); + f.debug_list().entries(entries_iter).finish() + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> Clone for Intersection<'a, T, S> { fn clone(&self) -> Intersection<'a, T, S> { @@ -1021,6 +1137,16 @@ impl<'a, T, S> Iterator for Intersection<'a, T, S> } } +#[stable(feature = "std_debug", since = "1.16.0")] +impl<'a, T, S> fmt::Debug for Intersection<'a, T, S> + where T: fmt::Debug + Eq + Hash, + S: BuildHasher +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + #[unstable(feature = "fused", issue = "35602")] impl<'a, T, S> FusedIterator for Intersection<'a, T, S> where T: Eq + Hash, @@ -1068,6 +1194,16 @@ impl<'a, T, S> FusedIterator for Difference<'a, T, S> { } +#[stable(feature = "std_debug", since = "1.16.0")] +impl<'a, T, S> fmt::Debug for Difference<'a, T, S> + where T: fmt::Debug + Eq + Hash, + S: BuildHasher +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> Clone for SymmetricDifference<'a, T, S> { fn clone(&self) -> SymmetricDifference<'a, T, S> { @@ -1097,6 +1233,16 @@ impl<'a, T, S> FusedIterator for SymmetricDifference<'a, T, S> { } +#[stable(feature = "std_debug", since = "1.16.0")] +impl<'a, T, S> fmt::Debug for SymmetricDifference<'a, T, S> + where T: fmt::Debug + Eq + Hash, + S: BuildHasher +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> Clone for Union<'a, T, S> { fn clone(&self) -> Union<'a, T, S> { @@ -1111,6 +1257,16 @@ impl<'a, T, S> FusedIterator for Union<'a, T, S> { } +#[stable(feature = "std_debug", since = "1.16.0")] +impl<'a, T, S> fmt::Debug for Union<'a, T, S> + where T: fmt::Debug + Eq + Hash, + S: BuildHasher +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_list().entries(self.clone()).finish() + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T, S> Iterator for Union<'a, T, S> where T: Eq + Hash, @@ -1528,4 +1684,15 @@ mod test_set { assert!(a.contains(&5)); assert!(a.contains(&6)); } + + #[test] + fn test_retain() { + let xs = [1, 2, 3, 4, 5, 6]; + let mut set: HashSet<isize> = xs.iter().cloned().collect(); + set.retain(|&k| k % 2 == 0); + assert_eq!(set.len(), 3); + assert!(set.contains(&2)); + assert!(set.contains(&4)); + assert!(set.contains(&6)); + } } |