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 /src | |
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
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/List.scala | 92 |
1 files changed, 65 insertions, 27 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. * |