reimplemented list union/intersect/diff as mult...

reimplemented list union/intersect/diff as multiset ops

2 files changed, 137 insertions, 44 deletions

diff --git a/src/library/scala/List.scala b/src/library/scala/List.scala
index 5482deabf4..8b25050de3 100644
--- a/src/library/scala/List.scala
+++ b/src/library/scala/List.scala
@@ -11,7 +11,7 @@
 
 package scala
 
-import scala.collection.mutable.ListBuffer
+import scala.collection.mutable.{ListBuffer, LinkedHashMap}
 import annotation.tailrec
 import Predef._
 
@@ -1239,33 +1239,80 @@ sealed abstract class List[+A] extends Seq[A] with Product {
     b.toList
   }
 
-  /** Computes the union of this list and the given list
-   *  <code>that</code>.
+  /** <p>
+   *    Computes the multiset union of this list and the given list
+   *    <code>that</code>. For example:
+   *  </p><pre>
+   *    <b>val</b> xs = List(1, 1, 2)
+   *    <b>val</b> ys = List(1, 2, 2, 3)
+   *    println(xs union ys)  // prints "List(1, 1, 2, 1, 2, 2, 3)"
+   *    println(ys union xs)  // prints "List(1, 2, 2, 3, 1, 1, 2)"
+   *  </pre>
    *
    *  @param that the list of elements to add to the list.
-   *  @return     a list without doubles containing the elements of this
+   *  @return     a list containing the elements of this
    *              list and those of the given list <code>that</code>.
    */
-  def union[B >: A](that: List[B]): List[B] = {
-    val b = new ListBuffer[B]
-    var these = this
-    while (!these.isEmpty) {
-      if (!that.contains(these.head)) b += these.head
-      these = these.tail
+  def union[B >: A](that: List[B]): List[B] = this ++ that
+
+  /** <p>
+   *    Computes the multiset intersection between this list and the
+   *    given list <code>that</code>; the intersection contains <i>m</i>
+   *    copies of an element contained in both lists, where <i>m</i> is
+   *    the smaller of the number of times the element appears in this
+   *    list or in <code>that</code>. For example:
+   *  </p><pre>
+   *    <b>val</b> xs = List(1, 1, 2)
+   *    <b>val</b> ys = List(3, 2, 2, 1)
+   *    println(xs intersect ys)  // prints "List(1, 2)"
+   *    println(ys intersect xs)  // prints "List(2, 1)"
+   *  </pre>
+   *
+   *  @param that the list to intersect.
+   *  @return     the list of elements contained both in this list and
+   *              in the given list <code>that</code>.
+   */
+  def intersect[B >: A](that: List[B]): List[B] = {
+    val occ = new LinkedHashMap[B, Int]
+    that foreach (e => if (occ contains e) occ(e) += 1 else occ(e) = 1)
+    val buf = new ListBuffer[B]
+    for (e <- this if occ contains e) {
+      if (occ(e) > 0) { occ(e) -= 1; buf += e }
     }
-    b.prependToList(that)
+    buf.toList
   }
 
-  /** Computes the difference between this list and the given list
-   *  <code>that</code>.
+  /** <p>
+   *    Computes the multiset difference between this list and the
+   *    given list <code>that</code>. If an element appears more
+   *    than once in both lists, the difference contains <i>m</i> copies
+   *    of that element, where <i>m</i> is the difference between the
+   *    number of times the element appears in this list and the number
+   *    of times it appears in <code>that</code>. For example:
+   *  </p><pre>
+   *    <b>val</b> xs = List(1, 1, 2)
+   *    <b>val</b> ys = List(1, 2, 2, 3)
+   *    println(xs diff ys)  // prints "List(1)"
+   *    println(xs -- ys)    // prints "List()"
+   *  </pre>
    *
    *  @param that the list of elements to remove from this list.
-   *  @return     this list without the elements of the given list
-   *              <code>that</code>.
-   *  @deprecated use <code>--</code> instead
+   *  @return     the list of elements contained only in this list plus
+   *              <i>m</i> copies of each element present in both lists,
+   *              where <i>m</i> is defined as above.
    */
-  @deprecated
-  def diff[B >: A](that: List[B]): List[B] = this -- that
+  def diff[B >: A](that: List[B]): List[B] = {
+    val occ = new LinkedHashMap[B, Int]
+    that foreach (e => if (occ contains e) occ(e) += 1 else occ(e) = 1)
+    val buf = new ListBuffer[B]
+    for (e <- this) {
+      if (occ contains e)
+        if (occ(e) > 0) occ(e) -= 1
+        else buf += e
+      else buf += e
+    }
+    buf.toList
+  }
 
   /** Computes the difference between this list and the given list
    *  <code>that</code>.
@@ -1321,15 +1368,6 @@ sealed abstract class List[+A] extends Seq[A] with Product {
     buf.toList
   }
 
-  /** Computes the intersection between this list and the given list
-   *  <code>that</code>.
-   *
-   *  @param that the list to intersect.
-   *  @return     the list of elements contained both in this list and
-   *              in the given list <code>that</code>.
-   */
-  def intersect[B >: A](that: List[B]): List[B] = filter(x => that contains x)
-
   /** Removes redundant elements from the list. Uses the method <code>==</code>
    *  to decide if two elements are identical.
    *
diff --git a/test/files/run/lists.scala b/test/files/run/lists.scala
index 93848da25f..19da548d61 100644
--- a/test/files/run/lists.scala
+++ b/test/files/run/lists.scala
@@ -13,6 +13,7 @@ import testing.SUnit._
  */
 object Test extends TestConsoleMain {
   def suite = new TestSuite(
+    Test_multiset, // multiset operations: union, intersect, diff
     Test1, //count, exists, filter, ..
     Test2, //#468
     Test3, //#1691
@@ -20,6 +21,76 @@ object Test extends TestConsoleMain {
   )
 }
 
+object Test_multiset extends TestCase("multiset") with Assert {
+  override def enableStackTrace = false
+  override def runTest {
+    def isSubListOf[A](thiz: List[A], that: List[A]): Boolean =
+      thiz forall (that contains _)
+    val xs = List(1, 1, 2)
+    val ys = List(1, 2, 2, 3)
+    assertEquals("xs_union_ys", List(1, 1, 2, 1, 2, 2, 3), xs union ys)
+    assertEquals("ys_union_xs", List(1, 2, 2, 3, 1, 1, 2), ys union xs)
+    assertEquals("xs_intersect_ys", List(1, 2), xs intersect ys)
+    assertEquals("ys_intersect_xs", List(1, 2), ys intersect xs)
+    assertEquals("xs_diff_ys", List(1), xs diff ys)
+    assertEquals("ys_diff_xs", List(2, 3), ys diff xs)
+    assertTrue("xs_subset_ys", isSubListOf(xs -- ys, xs diff ys))
+
+    val zs = List(0, 1, 1, 2, 2, 2)
+    assertEquals("zs_union_ys", List(0, 1, 1, 2, 2, 2, 1, 2, 2, 3), zs union ys)
+    assertEquals("ys_union_zs", List(1, 2, 2, 3, 0, 1, 1, 2, 2, 2), ys union zs)
+    assertEquals("zs_intersect_ys", List(1, 2, 2), zs intersect ys)
+    assertEquals("ys_intersect_zs", List(1, 2, 2), ys intersect zs)
+    assertEquals("zs_diff_ys", List(0, 1, 2), zs diff ys)
+    assertEquals("ys_diff_zs", List(3), ys diff zs)
+    assertTrue("xs_subset_ys", isSubListOf(zs -- ys, zs diff ys))
+
+    val ws = List(2)
+    assertEquals("ws_union_ys", List(2, 1, 2, 2, 3), ws union ys)
+    assertEquals("ys_union_ws", List(1, 2, 2, 3, 2), ys union ws)
+    assertEquals("ws_intersect_ys", List(2), ws intersect ys)
+    assertEquals("ys_intersect_ws", List(2), ys intersect ws)
+    assertEquals("ws_diff_ys", List(), ws diff ys)
+    assertEquals("ys_diff_ws", List(1, 2, 3), ys diff ws)
+    assertTrue("ws_subset_ys", isSubListOf(ws -- ys, ws diff ys))
+
+    val vs = List(3, 2, 2, 1)
+    assertEquals("xs_union_vs", List(1, 1, 2, 3, 2, 2, 1), xs union vs)
+    assertEquals("vs_union_xs", List(3, 2, 2, 1, 1, 1, 2), vs union xs)
+    assertEquals("xs_intersect_vs", List(1, 2), xs intersect vs)
+    assertEquals("vs_intersect_xs", List(2, 1), vs intersect xs)
+    assertEquals("xs_diff_vs", List(1), xs diff vs)
+    assertEquals("vs_diff_xs", List(3, 2), vs diff xs)
+    assertTrue("xs_subset_vs", isSubListOf(xs -- vs, xs diff vs))
+
+    // tests adapted from Thomas Jung
+    assertTrue(
+      "be symmetric after sorting", {
+        def sort(zs: List[Int]) = zs sort ( _ > _ )
+        sort(xs intersect ys) == sort(ys intersect xs)
+      })
+    assertTrue(
+      "obey min cardinality", {
+        def cardinality[A](zs: List[A], e: A): Int = zs count (e == _)
+        val intersection = xs intersect ys
+        xs forall (e => cardinality(intersection, e) == (cardinality(xs, e)
+min cardinality(ys, e)))
+      })
+    assertTrue(
+      "maintain order", {
+        val intersection = xs intersect ys
+		val unconsumed = xs.foldLeft(intersection){(rest, e) =>
+		  if (! rest.isEmpty && e == rest.head) rest.tail else rest
+		}
+		unconsumed.isEmpty
+      })
+    assertTrue(
+      "has the list as again intersection",
+      xs == (xs intersect xs)
+    )
+  }
+}
+
 object Test1 extends TestCase("ctor") with Assert {
   override def enableStackTrace = false
   override def runTest {
@@ -34,12 +105,6 @@ object Test1 extends TestCase("ctor") with Assert {
     val n2 = xs4 count { e => e < 5 }
     assertEquals("check_count", 4, n1 + n2)
   }
-  /* deprecated
-  {
-    val ys1 = xs1 diff xs4
-    val ys2 = xs3 diff xs5
-    assertEquals("check_diff", 3, ys1.length + ys2.length)
-  }*/
   {
     val b1 = xs1 exists { e => e % 2 == 0 }
     val b2 = xs4 exists { e => e == 5 }
@@ -61,21 +126,11 @@ object Test1 extends TestCase("ctor") with Assert {
     assertEquals("check_forall", true, b1 & b2)
   }
   {
-    val ys1 = xs1 intersect xs4
-    val ys2 = xs3 intersect xs5
-    assertEquals("check_intersect", 2, ys1.length + ys2.length)
-  }
-  {
     val ys1 = xs1 remove { e => e % 2 != 0 }
     val ys2 = xs4 remove { e => e < 5 }
     assertEquals("check_remove", 3, ys1.length + ys2.length)
   }
   {
-    val ys1 = xs1 union xs4
-    val ys2 = xs3 union xs5
-    assertEquals("check_union", 10, ys1.length + ys2.length)
-  }
-  {
     val ys1 = xs1 zip xs2
     val ys2 = xs1 zip xs3
     assertEquals("check_zip", 4, ys1.length + ys2.length)
@@ -96,7 +151,7 @@ object Test2 extends TestCase("t0468") with Assert {
     val xs2 = List(0)
 
     val ys1 = xs1 ::: List(4)
-    assertEquals("check_+", List(1, 2, 3, 4), ys1)
+    assertEquals("check_:::", List(1, 2, 3, 4), ys1)
 
     val ys2 = ys1 - 4
     assertEquals("check_-", xs1, ys2)