add is_subset and is_superset to the Set trait

3 files changed, 89 insertions, 38 deletions

diff --git a/src/libcore/container.rs b/src/libcore/container.rs
index 272a2efc035..669a41be2b7 100644
--- a/src/libcore/container.rs
+++ b/src/libcore/container.rs
@@ -65,4 +65,10 @@ pub trait Set<T>: Mutable {
     /// Remove a value from the set. Return true if the value was
     /// present in the set.
     fn remove(&mut self, value: &T) -> bool;
+
+    /// Return true if the set is a subset of another
+    pure fn is_subset(&self, other: &self) -> bool;
+
+    /// Return true if the set is a superset of another
+    pure fn is_superset(&self, other: &self) -> bool;
 }
diff --git a/src/libcore/hashmap.rs b/src/libcore/hashmap.rs
index 4a3ee18440b..a9f3cd5247c 100644
--- a/src/libcore/hashmap.rs
+++ b/src/libcore/hashmap.rs
@@ -25,6 +25,7 @@ pub mod linear {
     use cmp::Eq;
     use cmp;
     use hash::Hash;
+    use iter;
     use kinds::Copy;
     use option::{None, Option, Some};
     use option;
@@ -453,6 +454,16 @@ pub mod linear {
         /// Remove a value from the set. Return true if the value was
         /// present in the set.
         fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
+
+        /// Return true if the set is a subset of another
+        pure fn is_subset(&self, other: &LinearSet<T>) -> bool {
+            iter::all(self, |v| other.contains(v))
+        }
+
+        /// Return true if the set is a superset of another
+        pure fn is_superset(&self, other: &LinearSet<T>) -> bool {
+            other.is_subset(self)
+        }
     }
 
     pub impl <T: Hash IterBytes Eq> LinearSet<T> {
@@ -462,7 +473,7 @@ pub mod linear {
 }
 
 #[test]
-pub mod test {
+mod test_map {
     use container::{Container, Mutable, Map, Set};
     use option::{None, Some};
     use hashmap::linear::LinearMap;
@@ -610,3 +621,37 @@ pub mod test {
         assert !m.is_empty();
     }
 }
+
+#[test]
+mod test_set {
+    use super::*;
+
+    #[test]
+    fn test_subset_and_superset() {
+        let mut a = linear::LinearSet::new();
+        assert a.insert(0);
+        assert a.insert(5);
+        assert a.insert(11);
+        assert a.insert(7);
+
+        let mut b = linear::LinearSet::new();
+        assert b.insert(0);
+        assert b.insert(7);
+        assert b.insert(19);
+        assert b.insert(250);
+        assert b.insert(11);
+        assert b.insert(200);
+
+        assert !a.is_subset(&b);
+        assert !a.is_superset(&b);
+        assert !b.is_subset(&a);
+        assert !b.is_superset(&a);
+
+        assert b.insert(5);
+
+        assert a.is_subset(&b);
+        assert !a.is_superset(&b);
+        assert !b.is_subset(&a);
+        assert b.is_superset(&a);
+    }
+}
diff --git a/src/libstd/treemap.rs b/src/libstd/treemap.rs
index ed06d6a34b5..ece120bb647 100644
--- a/src/libstd/treemap.rs
+++ b/src/libstd/treemap.rs
@@ -291,6 +291,43 @@ impl <T: Ord> TreeSet<T>: Set<T> {
     /// Remove a value from the set. Return true if the value was
     /// present in the set.
     fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
+
+    /// Return true if the set is a subset of another
+    pure fn is_subset(&self, other: &TreeSet<T>) -> bool {
+        other.is_superset(self)
+    }
+
+    /// Return true if the set is a superset of another
+    pure fn is_superset(&self, other: &TreeSet<T>) -> bool {
+        let mut x = self.iter();
+        let mut y = other.iter();
+        unsafe { // purity workaround
+            x = x.next();
+            y = y.next();
+            let mut a = x.get();
+            let mut b = y.get();
+            while b.is_some() {
+                if a.is_none() {
+                    return false
+                }
+
+                let a1 = a.unwrap();
+                let b1 = b.unwrap();
+
+                if b1 < a1 {
+                    return false
+                }
+
+                if !(a1 < b1) {
+                    y = y.next();
+                    b = y.get();
+                }
+                x = x.next();
+                a = x.get();
+            }
+        }
+        true
+    }
 }
 
 impl <T: Ord> TreeSet<T> {
@@ -335,43 +372,6 @@ impl <T: Ord> TreeSet<T> {
         true
     }
 
-    /// Check of the set is a subset of another
-    pure fn is_subset(&self, other: &TreeSet<T>) -> bool {
-        other.is_superset(self)
-    }
-
-    /// Check of the set is a superset of another
-    pure fn is_superset(&self, other: &TreeSet<T>) -> bool {
-        let mut x = self.iter();
-        let mut y = other.iter();
-        unsafe { // purity workaround
-            x = x.next();
-            y = y.next();
-            let mut a = x.get();
-            let mut b = y.get();
-            while b.is_some() {
-                if a.is_none() {
-                    return false
-                }
-
-                let a1 = a.unwrap();
-                let b1 = b.unwrap();
-
-                if b1 < a1 {
-                    return false
-                }
-
-                if !(a1 < b1) {
-                    y = y.next();
-                    b = y.get();
-                }
-                x = x.next();
-                a = x.get();
-            }
-        }
-        true
-    }
-
     /// Visit the values (in-order) representing the difference
     pure fn difference(&self, other: &TreeSet<T>, f: fn(&T) -> bool) {
         let mut x = self.iter();