diff options
| -rw-r--r-- | src/libcollections/treemap.rs | 199 |
1 files changed, 183 insertions, 16 deletions
diff --git a/src/libcollections/treemap.rs b/src/libcollections/treemap.rs index 9bc0a1abbc5..442a4ded733 100644 --- a/src/libcollections/treemap.rs +++ b/src/libcollections/treemap.rs @@ -138,7 +138,7 @@ impl<K: Ord, V> Default for TreeMap<K,V> { } impl<K: Ord, V> TreeMap<K, V> { - /// Create an empty TreeMap + /// Create an empty `TreeMap`. pub fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} } /// Get a lazy iterator over the keys in the map. @@ -232,6 +232,7 @@ impl<K, V> TreeMap<K, V> { /// Return the value for which `f(key)` returns `Equal`. `f` is invoked /// with current key and guides tree navigation. That means `f` should /// be aware of natural ordering of the tree. + /// /// # Example /// /// ``` @@ -633,15 +634,68 @@ impl<'a, T> Iterator<&'a T> for RevSetItems<'a, T> { /// ```{rust} /// use std::collections::TreeSet; /// -/// let mut tree_set = TreeSet::new(); +/// let mut set = TreeSet::new(); /// -/// tree_set.insert(2i); -/// tree_set.insert(1i); -/// tree_set.insert(3i); +/// set.insert(2i); +/// set.insert(1i); +/// set.insert(3i); /// -/// for i in tree_set.iter() { +/// for i in set.iter() { /// println!("{}", i) // prints 1, then 2, then 3 /// } +/// +/// set.remove(&3); +/// +/// if !set.contains(&3) { +/// println!("set does not contain a 3 anymore"); +/// } +/// ``` +/// +/// The easiest way to use `TreeSet` with a custom type is to implement `Ord`. +/// We must also implement `PartialEq`, `Eq` and `PartialOrd`. +/// +/// ``` +/// use std::collections::TreeSet; +/// +/// // We need `Eq` and `PartialEq`, these can be derived. +/// #[deriving(Eq, PartialEq)] +/// struct Troll<'a> { +/// name: &'a str, +/// level: uint, +/// } +/// +/// // Implement `Ord` and sort trolls by level. +/// impl<'a> Ord for Troll<'a> { +/// fn cmp(&self, other: &Troll) -> Ordering { +/// // If we swap `self` and `other`, we get descended ordering. +/// self.level.cmp(&other.level) +/// } +/// } +/// +/// // `PartialOrd` needs to be implemented as well. +/// impl<'a> PartialOrd for Troll<'a> { +/// fn partial_cmp(&self, other: &Troll) -> Option<Ordering> { +/// Some(self.cmp(other)) +/// } +/// } +/// +/// let mut trolls = TreeSet::new(); +/// +/// trolls.insert(Troll { name: "Orgarr", level: 2 }); +/// trolls.insert(Troll { name: "Blargarr", level: 3 }); +/// trolls.insert(Troll { name: "Kron the Smelly One", level: 4 }); +/// trolls.insert(Troll { name: "Wartilda", level: 1 }); +/// +/// println!("You are facing {} trolls!", trolls.len()); +/// +/// // Print the trolls, ordered by level with smallest level first +/// for x in trolls.iter() { +/// println!("level {}: {}!", x.level, x.name); +/// } +/// +/// // Kill all trolls +/// trolls.clear(); +/// assert_eq!(trolls.len(), 0); /// ``` #[deriving(Clone)] pub struct TreeSet<T> { @@ -732,25 +786,66 @@ impl<T: Ord> Default for TreeSet<T> { } impl<T: Ord> TreeSet<T> { - /// Create an empty TreeSet + /// Create an empty `TreeSet`. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// let mut set: TreeSet<int> = TreeSet::new(); + /// ``` #[inline] pub fn new() -> TreeSet<T> { TreeSet{map: TreeMap::new()} } - /// Get a lazy iterator over the values in the set. - /// Requires that it be frozen (immutable). + /// Get a lazy iterator over the values in the set, in ascending order. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect(); + /// + /// // Will print in ascending order. + /// for x in set.iter() { + /// println!("{}", x); + /// } + /// ``` #[inline] pub fn iter<'a>(&'a self) -> SetItems<'a, T> { SetItems{iter: self.map.iter()} } - /// Get a lazy iterator over the values in the set. - /// Requires that it be frozen (immutable). + /// Get a lazy iterator over the values in the set, in descending order. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect(); + /// + /// // Will print in descending order. + /// for x in set.rev_iter() { + /// println!("{}", x); + /// } + /// ``` #[inline] pub fn rev_iter<'a>(&'a self) -> RevSetItems<'a, T> { RevSetItems{iter: self.map.rev_iter()} } - /// Get a lazy iterator that consumes the set. + /// Creates a consuming iterator, that is, one that moves each value out of the + /// set in ascending order. The set cannot be used after calling this. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect(); + /// + /// // Not possible with a regular `.iter()` + /// let v: Vec<int> = set.move_iter().collect(); + /// assert_eq!(v, vec![1, 2, 3, 4, 5]); + /// ``` #[inline] pub fn move_iter(self) -> MoveSetItems<T> { self.map.move_iter().map(|(value, _)| value) @@ -770,24 +865,96 @@ impl<T: Ord> TreeSet<T> { SetItems{iter: self.map.upper_bound(v)} } - /// Visit the values (in-order) representing the difference + /// Visit the values representing the difference, in ascending order. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); + /// let b: TreeSet<int> = [3, 4, 5].iter().map(|&x| x).collect(); + /// + /// // Can be seen as `a - b`. + /// for x in a.difference(&b) { + /// println!("{}", x); // Print 1 then 2 + /// } + /// + /// let diff: TreeSet<int> = a.difference(&b).map(|&x| x).collect(); + /// assert_eq!(diff, [1, 2].iter().map(|&x| x).collect()); + /// + /// // Note that difference is not symmetric, + /// // and `b - a` means something else: + /// let diff: TreeSet<int> = b.difference(&a).map(|&x| x).collect(); + /// assert_eq!(diff, [4, 5].iter().map(|&x| x).collect()); + /// ``` pub fn difference<'a>(&'a self, other: &'a TreeSet<T>) -> DifferenceItems<'a, T> { DifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()} } - /// Visit the values (in-order) representing the symmetric difference + /// Visit the values representing the symmetric difference, in ascending order. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); + /// let b: TreeSet<int> = [3, 4, 5].iter().map(|&x| x).collect(); + /// + /// // Print 1, 2, 4, 5 in ascending order. + /// for x in a.symmetric_difference(&b) { + /// println!("{}", x); + /// } + /// + /// let diff1: TreeSet<int> = a.symmetric_difference(&b).map(|&x| x).collect(); + /// let diff2: TreeSet<int> = b.symmetric_difference(&a).map(|&x| x).collect(); + /// + /// assert_eq!(diff1, diff2); + /// assert_eq!(diff1, [1, 2, 4, 5].iter().map(|&x| x).collect()); + /// ``` pub fn symmetric_difference<'a>(&'a self, other: &'a TreeSet<T>) -> SymDifferenceItems<'a, T> { SymDifferenceItems{a: self.iter().peekable(), b: other.iter().peekable()} } - /// Visit the values (in-order) representing the intersection + /// Visit the values representing the intersection, in ascending order. + /// + /// # Example + /// + /// ``` + /// use std::collections::TreeSet; + /// let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); + /// let b: TreeSet<int> = [2, 3, 4].iter().map(|&x| x).collect(); + /// + /// // Print 2, 3 in ascending order. + /// for x in a.intersection(&b) { + /// println!("{}", x); + /// } + /// + /// let diff: TreeSet<int> = a.intersection(&b).map(|&x| x).collect(); + /// assert_eq!(diff, [2, 3].iter().map(|&x| x).collect()); + /// ``` pub fn intersection<'a>(&'a self, other: &'a TreeSet<T>) -> IntersectionItems<'a, T> { IntersectionItems{a: self.iter().peekable(), b: other.iter().peekable()} } - /// Visit the values (in-order) representing the union + /// Visit the values representing the union, in ascending order. + /// + /// # Example + /// + /// ``` + /// use std::collections::HashSet; + /// let a: HashSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); + /// let b: HashSet<int> = [3, 4, 5].iter().map(|&x| x).collect(); + /// + /// // Print 1, 2, 3, 4, 5 in ascending order. + /// for x in a.union(&b) { + /// println!("{}", x); + /// } + /// + /// let diff: HashSet<int> = a.union(&b).map(|&x| x).collect(); + /// assert_eq!(diff, [1, 2, 3, 4, 5].iter().map(|&x| x).collect()); + /// ``` pub fn union<'a>(&'a self, other: &'a TreeSet<T>) -> UnionItems<'a, T> { UnionItems{a: self.iter().peekable(), b: other.iter().peekable()} } |