SortedSet: implement IntersectWith, UnionWith, ExceptWith and SymmetricExceptWith

* System.Collections.Generic/SortedSet.cs (CheckArgumentNotNull): New helper.
(IntersectWith, UnionWith): Implement.
(ExceptWith, SymmetricExceptWith): Likewise.
(SortedSubSet.IntersectWith): Implement override.
* Test/System.Collections.Generic/SortedSetTest.cs: Add tests for IntersectWith,
UnionWith, ExceptWith and SymmetricExceptWith.

svn path=/trunk/mcs/; revision=154769

diff --git a/mcs/class/System/System.Collections.Generic/ChangeLog b/mcs/class/System/System.Collections.Generic/ChangeLog
index bb1881d6cf92d27d61cf35458085591e8ce15463..6036d2aebc5b1b0aad0a201dd101da54baf7d56b 100644 (file)
--- a/mcs/class/System/System.Collections.Generic/ChangeLog
+++ b/mcs/class/System/System.Collections.Generic/ChangeLog
@@ -1,5 +1,10 @@
 2010-04-04  Raja R Harinath  <harinath@hurrynot.org>
 
+       * SortedSet.cs (CheckArgumentNotNull): New helper.
+       (IntersectWith, UnionWith): Implement.
+       (ExceptWith, SymmetricExceptWith): Likewise.
+       (SortedSubSet.IntersectWith): Implement override.
+
        * RBTree.cs (do_remove): Ensure the node returned is suitable for
        re-insertion.
 

diff --git a/mcs/class/System/System.Collections.Generic/SortedSet.cs b/mcs/class/System/System.Collections.Generic/SortedSet.cs
index e0eaa670b2221f336b9741566b3738dc63342dab..39cdb3b80f551dd2944eb74d060c80e5e6cedb2e 100644 (file)
--- a/mcs/class/System/System.Collections.Generic/SortedSet.cs
+++ b/mcs/class/System/System.Collections.Generic/SortedSet.cs
@@ -307,10 +307,12 @@ namespace System.Collections.Generic {
                        OnDeserialization (sender);
                }
 
-               [MonoTODO]
+               [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
                public void ExceptWith (IEnumerable<T> other)
                {
-                       throw new NotImplementedException ();
+                       CheckArgumentNotNull (other, "other");
+                       foreach (T item in other)
+                               Remove (item);
                }
 
                public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
@@ -321,10 +323,18 @@ namespace System.Collections.Generic {
                        return new SortedSubSet (this, lowerValue, upperValue);
                }
 
-               [MonoTODO]
+               [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
                public virtual void IntersectWith (IEnumerable<T> other)
                {
-                       throw new NotImplementedException ();
+                       CheckArgumentNotNull (other, "other");
+
+                       RBTree newtree = new RBTree (helper);
+                       foreach (T item in other) {
+                               var node = tree.Remove (item);
+                               if (node != null)
+                                       newtree.Intern (item, node);
+                       }
+                       tree = newtree;
                }
 
                [MonoTODO]
@@ -363,16 +373,33 @@ namespace System.Collections.Generic {
                        throw new NotImplementedException ();
                }
 
-               [MonoTODO]
+               [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
                public void SymmetricExceptWith (IEnumerable<T> other)
                {
-                       throw new NotImplementedException ();
+                       SortedSet<T> other_nodups = new SortedSet<T> (other, Comparer);
+                       SortedSet<T> other_minus_this = new SortedSet<T> (Comparer);
+
+                       // compute this - other and other - this in parallel
+                       foreach (T item in other_nodups)
+                               if (!Remove (item))
+                                       other_minus_this.Add (item);
+
+                       UnionWith (other_minus_this);
                }
 
-               [MonoTODO]
+               [MonoLimitation ("Isn't O(n) when other is SortedSet<T>")]
                public void UnionWith (IEnumerable<T> other)
                {
-                       throw new NotImplementedException ();
+                       CheckArgumentNotNull (other, "other");
+
+                       foreach (T item in other)
+                               Add (item);
+               }
+
+               static void CheckArgumentNotNull (object arg, string name)
+               {
+                       if (arg == null)
+                               throw new ArgumentNullException (name);
                }
 
                void ICollection<T>.Add (T item)
@@ -565,6 +592,17 @@ namespace System.Collections.Generic {
                        {
                                return GetEnumerator ();
                        }
+
+                       public override void IntersectWith (IEnumerable<T> other)
+                       {
+                               CheckArgumentNotNull (other, "other");
+
+                               var slice = new SortedSet<T> (this);
+                               slice.IntersectWith (other);
+
+                               Clear ();
+                               set.UnionWith (slice);
+                       }
                }
        }
 }

diff --git a/mcs/class/System/Test/System.Collections.Generic/ChangeLog b/mcs/class/System/Test/System.Collections.Generic/ChangeLog
index 2a4a8a3d63e1e8c071dab1c539e70ffc781dff7d..41d635d53e08baaf26df801056e5f4ccf47a38c6 100644 (file)
--- a/mcs/class/System/Test/System.Collections.Generic/ChangeLog
+++ b/mcs/class/System/Test/System.Collections.Generic/ChangeLog
@@ -1,3 +1,8 @@
+2010-04-04  Raja R Harinath  <harinath@hurrynot.org>
+
+       * SortedSetTest.cs: Add tests for IntersectWith, UnionWith,
+       ExceptWith and SymmetricExceptWith.
+
 2010-04-02  Jb Evain  <jbevain@novell.com>
 
        * SortedSetTest.cs: add tests for Min and Max on subsets.

diff --git a/mcs/class/System/Test/System.Collections.Generic/SortedSetTest.cs b/mcs/class/System/Test/System.Collections.Generic/SortedSetTest.cs
index 5249d1833ff52cf3e7caffb82248152a313bc9a3..38e8b1d0c3cd2a8fa0520363235289e610eccfa3 100644 (file)
--- a/mcs/class/System/Test/System.Collections.Generic/SortedSetTest.cs
+++ b/mcs/class/System/Test/System.Collections.Generic/SortedSetTest.cs
@@ -264,6 +264,128 @@ namespace MonoTests.System.Collections.Generic
 
                        Assert.AreEqual (7, view.Max);
                }
+
+               [Test, ExpectedException (typeof (ArgumentNullException))]
+               public void IntersectWith_Null ()
+               {
+                       var set = new SortedSet<int> ();
+                       set.IntersectWith (null);
+               }
+
+               [Test]
+               public void IntersectWith ()
+               {
+                       var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
+                       set.IntersectWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
+                       Assert.IsTrue (set.SequenceEqual (new [] { 3, 5, 7 }));
+               }
+
+               [Test]
+               public void ViewIntersectWith ()
+               {
+                       var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
+                       var view = set.GetViewBetween (4, 8);
+                       view.IntersectWith (new [] { 1, 5, 9 });
+                       Assert.IsTrue (view.SequenceEqual (new [] { 5 }));
+                       Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 5, 9 }));
+                       view.IntersectWith (new [] { 1, 2 });
+                       Assert.IsTrue (view.SequenceEqual (new int [] {}));
+                       Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 9 }));
+               }
+
+               [Test, ExpectedException (typeof (ArgumentNullException))]
+               public void UnionWith_Null ()
+               {
+                       var set = new SortedSet<int> ();
+                       set.UnionWith (null);
+               }
+
+               [Test]
+               public void UnionWith ()
+               {
+                       var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
+                       set.UnionWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
+                       Assert.IsTrue (set.SequenceEqual (new [] { 1, 2, 3, 5, 7, 9, 11 }));
+               }
+
+               [Test]
+               public void ViewUnionWith ()
+               {
+                       var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
+                       var view = set.GetViewBetween (4, 8);
+                       view.UnionWith (new [] { 4, 5, 6, 6, 4 });
+                       Assert.IsTrue (view.SequenceEqual (new [] { 4, 5, 6, 7 }));
+                       Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 4, 5, 6, 7, 9 }));
+               }
+
+               [Test, ExpectedException (typeof (ArgumentOutOfRangeException))]
+               public void ViewUnionWith_oor ()
+               {
+                       var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
+                       var view = set.GetViewBetween (4, 8);
+                       view.UnionWith (new [] {1});
+               }
+
+               [Test, ExpectedException (typeof (ArgumentNullException))]
+               public void ExceptWith_Null ()
+               {
+                       var set = new SortedSet<int> ();
+                       set.ExceptWith (null);
+               }
+
+               [Test]
+               public void ExceptWith ()
+               {
+                       var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
+                       set.ExceptWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
+                       Assert.IsTrue (set.SequenceEqual (new [] { 1, 9 }));
+               }
+
+               [Test]
+               public void ViewExceptWith ()
+               {
+                       var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
+                       var view = set.GetViewBetween (4, 8);
+                       view.ExceptWith (new [] { 4, 5, 6, 6, 4 });
+                       Assert.IsTrue (view.SequenceEqual (new [] { 7 }));
+                       Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 7, 9 }));
+                       view.ExceptWith (new [] { 1, 2 });
+                       Assert.IsTrue (view.SequenceEqual (new [] { 7 }));
+                       Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 7, 9 }));
+               }
+
+               [Test, ExpectedException (typeof (ArgumentNullException))]
+               public void SymmetricExceptWith_Null ()
+               {
+                       var set = new SortedSet<int> ();
+                       set.SymmetricExceptWith (null);
+               }
+
+               [Test]
+               public void SymmetricExceptWith ()
+               {
+                       var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
+                       set.SymmetricExceptWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
+                       Assert.IsTrue (set.SequenceEqual (new [] { 1, 2, 9, 11 }));
+               }
+
+               [Test]
+               public void ViewSymmetricExceptWith ()
+               {
+                       var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
+                       var view = set.GetViewBetween (4, 8);
+                       view.SymmetricExceptWith (new [] { 4, 5, 6, 6, 4 });
+                       Assert.IsTrue (view.SequenceEqual (new [] { 4, 6, 7 }));
+                       Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 4, 6, 7, 9 }));
+               }
+
+               [Test, ExpectedException (typeof (ArgumentOutOfRangeException))]
+               public void ViewSymmetricExceptWith_oor ()
+               {
+                       var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
+                       var view = set.GetViewBetween (4, 8);
+                       view.SymmetricExceptWith (new [] {2});
+               }
        }
 }