Fill in documentation for HashSet.

Example how to use the set with a custom type. Fill in examples for the missing methods.

1 files changed, 267 insertions, 37 deletions

diff --git a/src/libstd/collections/hashmap.rs b/src/libstd/collections/hashmap.rs
index 9a53c941377..12b80d1b467 100644
--- a/src/libstd/collections/hashmap.rs
+++ b/src/libstd/collections/hashmap.rs
@@ -1514,49 +1514,39 @@ pub type SetMoveItems<K> =
 ///     println!("{}", *book);
 /// }
 /// ```
+///
+/// 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`.
+///
+/// ```rust
+/// use std::collections::HashSet;
+///
+/// #[deriving(Hash, Eq, PartialEq, Show)]
+/// struct Viking<'a> {
+///     name: &'a str,
+///     power: uint,
+/// }
+///
+/// let mut vikings = HashSet::new();
+///
+/// vikings.insert(Viking { name: "Einar", power: 9u });
+/// vikings.insert(Viking { name: "Einar", power: 9u });
+/// vikings.insert(Viking { name: "Olaf", power: 4u });
+/// vikings.insert(Viking { name: "Harald", power: 8u });
+///
+/// // Use derived implementation to print the vikings.
+/// for x in vikings.iter() {
+///     println!("{}", x);
+/// }
+/// ```
 #[deriving(Clone)]
 pub struct HashSet<T, H = RandomSipHasher> {
     map: HashMap<T, (), H>
 }
 
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
-    fn eq(&self, other: &HashSet<T, H>) -> bool {
-        if self.len() != other.len() { return false; }
-
-        self.iter().all(|key| other.contains(key))
-    }
-}
-
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {}
-
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> Collection for HashSet<T, H> {
-    fn len(&self) -> uint { self.map.len() }
-}
-
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> Mutable for HashSet<T, H> {
-    fn clear(&mut self) { self.map.clear() }
-}
-
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> Set<T> for HashSet<T, H> {
-    fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
-
-    fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
-        self.iter().all(|v| !other.contains(v))
-    }
-
-    fn is_subset(&self, other: &HashSet<T, H>) -> bool {
-        self.iter().all(|v| other.contains(v))
-    }
-}
-
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> MutableSet<T> for HashSet<T, H> {
-    fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
-
-    fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
-}
-
 impl<T: Hash + Eq> HashSet<T, RandomSipHasher> {
-    /// Create an empty HashSet
+    /// Create an empty HashSet.
     ///
     /// # Example
     ///
@@ -1589,6 +1579,17 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// keys.
     ///
     /// The hash set is also created with the default initial capacity.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// use std::hash::sip::SipHasher;
+    ///
+    /// let h = SipHasher::new();
+    /// let mut set = HashSet::with_hasher(h);
+    /// set.insert(2u);
+    /// ```
     #[inline]
     pub fn with_hasher(hasher: H) -> HashSet<T, H> {
         HashSet::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
@@ -1601,6 +1602,17 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     /// is designed to allow `HashSet`s to be resistant to attacks that
     /// cause many collisions and very poor performance. Setting it
     /// manually using this function can expose a DoS attack vector.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// use std::hash::sip::SipHasher;
+    ///
+    /// let h = SipHasher::new();
+    /// let mut set = HashSet::with_capacity_and_hasher(10u, h);
+    /// set.insert(1i);
+    /// ```
     #[inline]
     pub fn with_capacity_and_hasher(capacity: uint, hasher: H) -> HashSet<T, H> {
         HashSet { map: HashMap::with_capacity_and_hasher(capacity, hasher) }
@@ -1621,6 +1633,45 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
 
     /// Returns true if the hash set contains a value equivalent to the
     /// given query value.
+    ///
+    /// # Example
+    ///
+    /// This is a slightly silly example where we define the number's
+    /// parity as the equivilance class. It is important that the
+    /// values hash the same, which is why we implement `Hash`.
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// use std::hash::Hash;
+    /// use std::hash::sip::SipState;
+    ///
+    /// #[deriving(Eq, PartialEq)]
+    /// struct EvenOrOdd {
+    ///     num: uint
+    /// };
+    ///
+    /// impl Hash for EvenOrOdd {
+    ///     fn hash(&self, state: &mut SipState) {
+    ///         let parity = self.num % 2;
+    ///         parity.hash(state);
+    ///     }
+    /// }
+    ///
+    /// impl Equiv<EvenOrOdd> for EvenOrOdd {
+    ///     fn equiv(&self, other: &EvenOrOdd) -> bool {
+    ///         self.num % 2 == other.num % 2
+    ///     }
+    /// }
+    ///
+    /// let mut set = HashSet::new();
+    /// set.insert(EvenOrOdd { num: 3u });
+    ///
+    /// assert!(set.contains_equiv(&EvenOrOdd { num: 3u }));
+    /// assert!(set.contains_equiv(&EvenOrOdd { num: 5u }));
+    /// assert!(!set.contains_equiv(&EvenOrOdd { num: 4u }));
+    /// assert!(!set.contains_equiv(&EvenOrOdd { num: 2u }));
+    ///
+    /// ```
     pub fn contains_equiv<Q: Hash<S> + Equiv<T>>(&self, value: &Q) -> bool {
       self.map.contains_key_equiv(value)
     }
@@ -1771,7 +1822,154 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     }
 }
 
+impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
+    /// Partial equality between sets.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
+    /// let b: HashSet<int> = [1i, 2, 3, 4].iter().map(|&x| x).collect();
+    /// let c: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
+    ///
+    /// assert!(a.eq(&c));
+    ///
+    /// // eq and ne defines the == and != operators
+    /// assert!(a == c);
+    /// assert!(a != b);
+    /// ```
+    fn eq(&self, other: &HashSet<T, H>) -> bool {
+        if self.len() != other.len() { return false; }
+
+        self.iter().all(|key| other.contains(key))
+    }
+}
+
+impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {}
+
+impl<T: Eq + Hash<S>, S, H: Hasher<S>> Collection for HashSet<T, H> {
+    /// Return the number of elements in the set.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// let set: HashSet<int> = [1i, 2, 3, 2].iter().map(|&x| x).collect();
+    /// assert_eq!(set.len(), 3);
+    /// ```
+    fn len(&self) -> uint { self.map.len() }
+}
+
+impl<T: Eq + Hash<S>, S, H: Hasher<S>> Mutable for HashSet<T, H> {
+    /// Clear the set. Keeps the allocated memory for reuse.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// let mut set: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
+    /// set.clear();
+    /// assert!(set.is_empty());
+    /// ```
+    fn clear(&mut self) { self.map.clear() }
+}
+
+impl<T: Eq + Hash<S>, S, H: Hasher<S>> Set<T> for HashSet<T, H> {
+    /// Return true if `value` is contained by the set.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// let set: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
+    /// assert_eq!(set.contains(&1), true);
+    /// assert_eq!(set.contains(&4), false);
+    /// ```
+    fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
+
+    /// Return true if the set is disjoint with `other`.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
+    /// let mut b: HashSet<int> = HashSet::new();
+    ///
+    /// assert_eq!(a.is_disjoint(&b), true);
+    /// b.insert(4);
+    /// assert_eq!(a.is_disjoint(&b), true);
+    /// b.insert(1);
+    /// assert_eq!(a.is_disjoint(&b), false);
+    /// ```
+    fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
+        self.iter().all(|v| !other.contains(v))
+    }
+
+    /// Return true if the set is a subset of `other`.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// let sup: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
+    /// let mut set: HashSet<int> = HashSet::new();
+    ///
+    /// assert_eq!(set.is_subset(&sup), true);
+    /// set.insert(2);
+    /// assert_eq!(set.is_subset(&sup), true);
+    /// set.insert(4);
+    /// assert_eq!(set.is_subset(&sup), false);
+    /// ```
+    fn is_subset(&self, other: &HashSet<T, H>) -> bool {
+        self.iter().all(|v| other.contains(v))
+    }
+}
+
+impl<T: Eq + Hash<S>, S, H: Hasher<S>> MutableSet<T> for HashSet<T, H> {
+    /// Insert an element.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// let mut set = HashSet::new();
+    /// set.insert(2i);
+    /// set.insert(2i);
+    /// assert_eq!(set.len(), 1);
+    /// ```
+    fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
+
+    /// Remove an element.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// let mut set = HashSet::new();
+    /// set.insert(2i);
+    ///
+    /// // Return boolean success flag.
+    /// assert_eq!(set.remove(&2), true);
+    /// assert_eq!(set.remove(&2), false);
+    /// ```
+    fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
+}
+
+
 impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
+    /// Implement the `Show` trait for easy output format. The values in the
+    /// set must also implement `Show`.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// let a: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
+    /// // Will call .fmt() to print, in some order.
+    /// println!("{}", a);
+    /// ```
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, "{{"));
 
@@ -1785,6 +1983,17 @@ impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
 }
 
 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T, H> {
+    /// Build a set from an external iterator.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// let values = vec!(1i, 2, 3);
+    /// let set: HashSet<int> = values.move_iter().collect();
+    /// let another_set: HashSet<int> = [1i, 2, 3].iter().map(|&x| x).collect();
+    /// assert_eq!(set, another_set);
+    /// ```
     fn from_iter<I: Iterator<T>>(iter: I) -> HashSet<T, H> {
         let (lower, _) = iter.size_hint();
         let mut set = HashSet::with_capacity_and_hasher(lower, Default::default());
@@ -1794,6 +2003,18 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T,
 }
 
 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Extendable<T> for HashSet<T, H> {
+    /// Extend the set with the values yielded by an iterator.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// let values = vec!(1i, 2, 3);
+    /// let mut set = HashSet::new();
+    /// set.insert(0i);
+    /// set.extend(values.move_iter());
+    /// assert_eq!(set.len(), 4);
+    /// ```
     fn extend<I: Iterator<T>>(&mut self, mut iter: I) {
         for k in iter {
             self.insert(k);
@@ -1802,6 +2023,15 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Extendable<T> for HashSet<T, H>
 }
 
 impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Default for HashSet<T, H> {
+    /// Create a default set.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// # use std::collections::HashSet;
+    /// use std::default::Default;
+    /// let mut set: HashSet<int> = Default::default();
+    /// ```
     fn default() -> HashSet<T, H> {
         HashSet::with_hasher(Default::default())
     }