From fee124a41964623dc902464bcbefecd130861eb3 Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Thu, 20 Jan 2011 20:49:03 +0000 Subject: Integrated contributed non-recursive implementa... Integrated contributed non-recursive implementation of permutations, combinations, subsets, by EastSun. Also gave mutable Seqs an in-place transform method like the one Map has. And couldn't resist slightly reformulating a few set methods, because how can we settle for "forall(that.contains)" when we could have "this forall that". (Which is also what normal people hear when we talk about sets.) Closes #4060, #3644, review by moors. --- src/library/scala/collection/SeqLike.scala | 133 +++++++++++++++++++-- src/library/scala/collection/SetLike.scala | 86 +++++++++++-- .../scala/collection/immutable/BitSet.scala | 2 - .../scala/collection/immutable/IntMap.scala | 10 +- src/library/scala/collection/mutable/SeqLike.scala | 15 +++ 5 files changed, 218 insertions(+), 28 deletions(-) (limited to 'src/library') diff --git a/src/library/scala/collection/SeqLike.scala b/src/library/scala/collection/SeqLike.scala index a16209d8f0..49098da47c 100644 --- a/src/library/scala/collection/SeqLike.scala +++ b/src/library/scala/collection/SeqLike.scala @@ -372,18 +372,127 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self => * @return An Iterator which traverses the distinct permutations of this $coll. * @example `"abb".permutations = Iterator(abb, bab, bba)` */ - def permutations: Iterator[Repr] = { - val seen = mutable.HashSet[A]() - val xs = thisCollection.toIndexedSeq - - if (xs.isEmpty) Iterator.empty - else if (xs.tail.isEmpty) Iterator(repr) - else xs.indices collect { - case idx if !seen(xs(idx)) => - seen += xs(idx) - val rest = (xs take idx) ++ (xs drop (idx + 1)) - rest.permutations map (newBuilder += xs(idx) ++= _ result) - } reduceLeft (_ ++ _) + def permutations: Iterator[Repr] = + if (isEmpty) Iterator(repr) + else new PermutationsItr + + /** Iterates over combinations. + * + * @return An Iterator which traverses the possible n-element combinations of this $coll. + * @example `"abbbc".combinations(2) = Iterator(ab, ac, bb, bc)` + */ + def combinations(n: Int): Iterator[Repr] = + if (n < 0 || n > size) Iterator.empty + else new CombinationsItr(n) + + private class PermutationsItr extends Iterator[Repr] { + private[this] val (elms, idxs) = init() + private var _hasNext = true + + def hasNext = _hasNext + def next: Repr = { + if (!hasNext) + Iterator.empty.next + + val result = (self.newBuilder ++= elms).result + var i = idxs.length - 2 + while(i >= 0 && idxs(i) >= idxs(i+1)) + i -= 1 + + if (i < 0) + _hasNext = false + else { + var j = idxs.length - 1 + while(idxs(j) <= idxs(i)) j -= 1 + swap(i,j) + + val len = (idxs.length - i) / 2 + var k = 1 + while (k <= len) { + swap(i+k, idxs.length - k) + k += 1 + } + } + result + } + private def swap(i: Int, j: Int) { + var tmpI = idxs(i) + idxs(i) = idxs(j) + idxs(j) = tmpI + var tmpE = elms(i) + elms(i) = elms(j) + elms(j) = tmpE + } + + private[this] def init() = { + val m = mutable.HashMap[A, Int]() + val (es, is) = thisCollection map (e => (e, m.getOrElseUpdate(e, m.size))) sortBy (_._2) unzip + + (es.toBuffer, is.toArray) + } + } + + private class CombinationsItr(n: Int) extends Iterator[Repr] { + // generating all nums such that: + // (1) nums(0) + .. + nums(length-1) = n + // (2) 0 <= nums(i) <= cnts(i), where 0 <= i <= cnts.length-1 + private val (elms, cnts, nums) = init() + private val offs = cnts.scanLeft(0)(_ + _) + private var _hasNext = true + + def hasNext = _hasNext + def next: Repr = { + if (!hasNext) + Iterator.empty.next + + /** Calculate this result. */ + val buf = self.newBuilder + for(k <- 0 until nums.length; j <- 0 until nums(k)) + buf += elms(offs(k)+j) + val res = buf.result + + /** Prepare for the next call to next. */ + var idx = nums.length - 1 + while (idx >= 0 && nums(idx) == cnts(idx)) + idx -= 1 + + idx = nums.lastIndexWhere(_ > 0, idx - 1) + + if (idx < 0) + _hasNext = false + else { + var sum = nums.slice(idx + 1, nums.length).sum + 1 + nums(idx) -= 1 + for (k <- (idx+1) until nums.length) { + nums(k) = sum min cnts(k) + sum -= nums(k) + } + } + + res + } + + /** Rearrange seq to newSeq a0a0..a0a1..a1...ak..ak such that + * seq.count(_ == aj) == cnts(j) + * + * @return (newSeq,cnts,nums) + */ + private def init(): (IndexedSeq[A], Array[Int], Array[Int]) = { + val m = mutable.HashMap[A, Int]() + + // e => (e, weight(e)) + val (es, is) = thisCollection map (e => (e, m.getOrElseUpdate(e, m.size))) sortBy (_._2) unzip + val cs = new Array[Int](m.size) + is foreach (i => cs(i) += 1) + val ns = new Array[Int](cs.length) + + var r = n + 0 until ns.length foreach { k => + ns(k) = r min cs(k) + r -= ns(k) + } + (es.toIndexedSeq, cs, ns) + } } /** Returns new $coll wih elements in reversed order. diff --git a/src/library/scala/collection/SetLike.scala b/src/library/scala/collection/SetLike.scala index 6d61da8547..7990837685 100644 --- a/src/library/scala/collection/SetLike.scala +++ b/src/library/scala/collection/SetLike.scala @@ -141,7 +141,7 @@ self => * @param elem the element to test for membership. * @return `true` if `elem` is contained in this set, `false` otherwise. */ - def apply(elem: A): Boolean = contains(elem) + def apply(elem: A): Boolean = this contains elem /** Computes the intersection between this set and another set. * @@ -149,7 +149,7 @@ self => * @return a new set consisting of all elements that are both in this * set and in the given set `that`. */ - def intersect(that: Set[A]): This = filter(that.contains) + def intersect(that: Set[A]): This = this filter that /** Computes the intersection between this set and another set. * @@ -158,7 +158,7 @@ self => * @return a new set consisting of all elements that are both in this * set and in the given set `that`. */ - def &(that: Set[A]): This = intersect(that) + def &(that: Set[A]): This = this intersect that /** This method is an alias for `intersect`. * It computes an intersection with set `that`. @@ -166,7 +166,8 @@ self => * * @param that the set to intersect with */ - @deprecated("use & instead") def ** (that: Set[A]): This = intersect(that) + @deprecated("use & instead") + def ** (that: Set[A]): This = &(that) /** Computes the union between of set and another set. * @@ -174,7 +175,7 @@ self => * @return a new set consisting of all elements that are in this * set or in the given set `that`. */ - def union(that: Set[A]): This = this.++(that) + def union(that: Set[A]): This = this ++ that /** Computes the union between this set and another set. * @@ -183,7 +184,7 @@ self => * @return a new set consisting of all elements that are in this * set or in the given set `that`. */ - def | (that: Set[A]): This = union(that) + def | (that: Set[A]): This = this union that /** Computes the difference of this set and another set. * @@ -191,7 +192,7 @@ self => * @return a set containing those elements of this * set that are not also contained in the given set `that`. */ - def diff(that: Set[A]): This = --(that) + def diff(that: Set[A]): This = this -- that /** The difference of this set and another set. * @@ -200,7 +201,7 @@ self => * @return a set containing those elements of this * set that are not also contained in the given set `that`. */ - def &~(that: Set[A]): This = diff(that) + def &~(that: Set[A]): This = this diff that /** Tests whether this set is a subset of another set. * @@ -208,7 +209,74 @@ self => * @return `true` if this set is a subset of `that`, i.e. if * every element of this set is also an element of `that`. */ - def subsetOf(that: Set[A]): Boolean = forall(that.contains) + def subsetOf(that: Set[A]) = this forall that + + /** An iterator over all subsets of this set of the given size. + * + * @param len the size of the subsets. + * @return the iterator. + */ + def subsets(len: Int): Iterator[This] = { + if (len < 0 || len > size) throw new IllegalArgumentException(len.toString) + else new SubsetsItr(self.toIndexedSeq, len) + } + + /** An iterator over all subsets of this set. + * + * @return the iterator. + */ + def subsets: Iterator[This] = new Iterator[This] { + private val elms = self.toIndexedSeq + private var len = 0 + private var itr: Iterator[This] = Iterator.empty + + def hasNext = len <= elms.size || itr.hasNext + def next = { + if (!itr.hasNext) { + if (len > elms.size) Iterator.empty.next + else { + itr = new SubsetsItr(elms, len) + len += 1 + } + } + + itr.next + } + } + + /** An Iterator include all subsets containing exactly len elements. + * If the elements in 'This' type is ordered, then the subsets will also be in the same order. + * ListSet(1,2,3).subsets => {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} + * + * @author Eastsun + * @date 2010.12.6 + */ + private class SubsetsItr(elms: IndexedSeq[A], len: Int) extends Iterator[This] { + private val idxs = Array.range(0, len+1) + private var _hasNext = true + idxs(len) = elms.size + + def hasNext = _hasNext + def next: This = { + if (!hasNext) Iterator.empty.next + + val buf = self.newBuilder + idxs.slice(0, len) foreach (idx => buf += elms(idx)) + val result = buf.result + + var i = len - 1 + while (i >= 0 && idxs(i) == idxs(i+1)-1) i -= 1 + + if (i < 0) _hasNext = false + else { + idxs(i) += 1 + for (j <- (i+1) until len) + idxs(j) = idxs(j-1) + 1 + } + + result + } + } /** Defines the prefix of this object's `toString` representation. * @return a string representation which starts the result of `toString` applied to this set. diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala index 6451268f83..918c79ef0d 100644 --- a/src/library/scala/collection/immutable/BitSet.scala +++ b/src/library/scala/collection/immutable/BitSet.scala @@ -79,8 +79,6 @@ object BitSet extends BitSetFactory[BitSet] { else new BitSetN(elems) } - private val hashSeed = "BitSet".hashCode - class BitSet1(val elems: Long) extends BitSet { protected def nwords = 1 protected def word(idx: Int) = if (idx == 0) elems else 0L diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala index 27548aadb9..e96b9252ea 100644 --- a/src/library/scala/collection/immutable/IntMap.scala +++ b/src/library/scala/collection/immutable/IntMap.scala @@ -55,14 +55,14 @@ object IntMap { // develops. Case objects and custom equality don't mix without // careful handling. override def equals(that : Any) = that match { - case (that : AnyRef) if (this eq that) => true; - case (that : IntMap[_]) => false; // The only empty IntMaps are eq Nil - case that => super.equals(that); + case _: this.type => true + case _: IntMap[_] => false // The only empty IntMaps are eq Nil + case _ => super.equals(that) } - }; + } private[immutable] case class Tip[+T](key : Int, value : T) extends IntMap[T]{ - def withValue[S](s : S) = + def withValue[S](s: S) = if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[IntMap.Tip[S]]; else IntMap.Tip(key, s); } diff --git a/src/library/scala/collection/mutable/SeqLike.scala b/src/library/scala/collection/mutable/SeqLike.scala index 3f1c51ec62..075bcf9e10 100644 --- a/src/library/scala/collection/mutable/SeqLike.scala +++ b/src/library/scala/collection/mutable/SeqLike.scala @@ -28,4 +28,19 @@ trait SeqLike[A, +This <: SeqLike[A, This] with Seq[A]] * @throws IndexOutofBoundsException if the index is not valid. */ def update(idx: Int, elem: A) + + /** Applies a transformation function to all values contained in this sequence. + * The transformation function produces new values from existing elements. + * + * @param f the transformation to apply + * @return the sequence itself. + */ + def transform(f: A => A): this.type = { + var i = 0 + iterator foreach { el => + update(i, f(el)) + i += 1 + } + this + } } -- cgit v1.2.3