diff options
author | michelou <michelou@epfl.ch> | 2009-03-20 13:41:07 +0000 |
---|---|---|
committer | michelou <michelou@epfl.ch> | 2009-03-20 13:41:07 +0000 |
commit | 65b7d0575977d9bac92e845dea02f0cb5d237051 (patch) | |
tree | 108e8b7822c37e3c4cc9e6de255dc5da91378ada | |
parent | 9a4199709d2c3c910dbbe17bffdac97df69b1d8f (diff) | |
download | scala-65b7d0575977d9bac92e845dea02f0cb5d237051.tar.gz scala-65b7d0575977d9bac92e845dea02f0cb5d237051.tar.bz2 scala-65b7d0575977d9bac92e845dea02f0cb5d237051.zip |
reimplemented list union/intersect/diff as mult...
reimplemented list union/intersect/diff as multiset ops
-rw-r--r-- | src/library/scala/List.scala | 92 | ||||
-rw-r--r-- | test/files/run/lists.scala | 89 |
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) |