diff options
author | Paul Phillips <paulp@improving.org> | 2009-08-28 23:56:58 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2009-08-28 23:56:58 +0000 |
commit | 1e5ffa0cc89869c7b09be43fc9cd55a01e9f1b67 (patch) | |
tree | f172f96500cbfaf9706cce6eb389ee41eb100a53 | |
parent | 0c910180fb8a300dbe84b612dc78d5a83b16c748 (diff) | |
download | scala-1e5ffa0cc89869c7b09be43fc9cd55a01e9f1b67.tar.gz scala-1e5ffa0cc89869c7b09be43fc9cd55a01e9f1b67.tar.bz2 scala-1e5ffa0cc89869c7b09be43fc9cd55a01e9f1b67.zip |
Moved zip/zipAll/zipWithIndex to Iterable and a...
Moved zip/zipAll/zipWithIndex to Iterable and attempts to get all the
views and etc working correctly and consistently. Addresses ticket #2301
and then some.
9 files changed, 129 insertions, 90 deletions
diff --git a/src/library/scala/collection/generic/IterableProxyTemplate.scala b/src/library/scala/collection/generic/IterableProxyTemplate.scala index 545294e341..3d20be52fd 100644 --- a/src/library/scala/collection/generic/IterableProxyTemplate.scala +++ b/src/library/scala/collection/generic/IterableProxyTemplate.scala @@ -33,6 +33,9 @@ trait IterableProxyTemplate[+A, +This <: IterableTemplate[A, This] with Iterable override def foldRight[B](z: B)(op: (A, B) => B): B = self.foldRight(z)(op) override def reduceRight[B >: A](op: (A, B) => B): B = self.reduceRight(op) override def toIterable: Iterable[A] = self.toIterable + override def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = self.zip[A1, B, That](that)(bf) + override def zipAll[B, A1 >: A, That](that: Iterable[B], thisElem: A1, thatElem: B)(implicit bf: BuilderFactory[(A1, B), That, This]): That = self.zipAll(that, thisElem, thatElem)(bf) + override def zipWithIndex[A1 >: A, That](implicit bf: BuilderFactory[(A1, Int), That, This]): That = self.zipWithIndex(bf) override def head: A = self.head override def takeRight(n: Int): This = self.takeRight(n) override def dropRight(n: Int): This = self.dropRight(n) diff --git a/src/library/scala/collection/generic/IterableTemplate.scala b/src/library/scala/collection/generic/IterableTemplate.scala index 01cbbcf25b..1f20ea3f07 100644 --- a/src/library/scala/collection/generic/IterableTemplate.scala +++ b/src/library/scala/collection/generic/IterableTemplate.scala @@ -147,6 +147,66 @@ trait IterableTemplate[+A, +This <: IterableTemplate[A, This] with Iterable[A]] b.result } + + /** Returns an iterable formed from this iterable and another iterable + * by combining corresponding elements in pairs. + * If one of the two iterables is longer than the other, its remaining elements are ignored. + * @param that The iterable providing the second half of each result pair + */ + def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = { + val b = bf(thisCollection) + val these = this.iterator + val those = that.iterator + while (these.hasNext && those.hasNext) + b += ((these.next, those.next)) + b.result + } + + /** Returns a iterable formed from this iterable and the specified iterable + * <code>that</code> by associating each element of the former with + * the element at the same position in the latter. + * + * @param that iterable <code>that</code> may have a different length + * as the self iterable. + * @param thisElem element <code>thisElem</code> is used to fill up the + * resulting iterable if the self iterable is shorter than + * <code>that</code> + * @param thatElem element <code>thatElem</code> is used to fill up the + * resulting iterable if <code>that</code> is shorter than + * the self iterable + * @return <code>Sequence((a<sub>0</sub>,b<sub>0</sub>), ..., + * (a<sub>n</sub>,b<sub>n</sub>), (elem,b<sub>n+1</sub>), + * ..., {elem,b<sub>m</sub>})</code> + * when <code>[a<sub>0</sub>, ..., a<sub>n</sub>] zip + * [b<sub>0</sub>, ..., b<sub>m</sub>]</code> is + * invoked where <code>m > n</code>. + * + */ + def zipAll[B, A1 >: A, That](that: Iterable[B], thisElem: A1, thatElem: B)(implicit bf: BuilderFactory[(A1, B), That, This]): That = { + val b = bf(thisCollection) + val these = this.iterator + val those = that.iterator + while (these.hasNext && those.hasNext) + b += ((these.next, those.next)) + while (these.hasNext) + b += ((these.next, thatElem)) + while (those.hasNext) + b += ((thisElem, those.next)) + b.result + } + + /** Zips this iterable with its indices (startiong from 0). + */ + def zipWithIndex[A1 >: A, That](implicit bf: BuilderFactory[(A1, Int), That, This]): That = { + val b = bf(thisCollection) + var i = 0 + for (x <- this) { + b += ((x, i)) + i +=1 + } + b.result + } + /** Checks if the other iterable object contains the same elements as this one. * * @note will not terminate for infinite-sized iterables. diff --git a/src/library/scala/collection/generic/IterableViewTemplate.scala b/src/library/scala/collection/generic/IterableViewTemplate.scala index eda3f191f0..327e719be2 100644 --- a/src/library/scala/collection/generic/IterableViewTemplate.scala +++ b/src/library/scala/collection/generic/IterableViewTemplate.scala @@ -55,6 +55,42 @@ extends Iterable[A] with IterableTemplate[A, This] with TraversableView[A, Coll] override def iterator = self.iterator dropWhile pred } + trait Zipped[B] extends Transformed[(A, B)] { + protected[this] val other: Iterable[B] + override def iterator: Iterator[(A, B)] = self.iterator zip other.iterator + override def stringPrefix = super.stringPrefix+"Z" + } + + trait ZippedAll[A1 >: A, B] extends Transformed[(A1, B)] { + protected[this] val other: Iterable[B] + val thisElem: A1 + val thatElem: B + override def iterator: Iterator[(A1, B)] = + self.iterator.zipAll(other.iterator, thisElem, thatElem) + } + + override def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = { + newZipped(that).asInstanceOf[That] +// was: val b = bf(thisCollection) +// if (b.isInstanceOf[NoBuilder[_]]) newZipped(that).asInstanceOf[That] +// else super.zip[A1, B, That](that)(bf) + } + + override def zipWithIndex[A1 >: A, That](implicit bf: BuilderFactory[(A1, Int), That, This]): That = + zip[A1, Int, That](Stream from 0)(bf) + + override def zipAll[B, A1 >: A, That](that: Iterable[B], thisElem: A1, thatElem: B)(implicit bf: BuilderFactory[(A1, B), That, This]): That = + newZippedAll(that, thisElem, thatElem).asInstanceOf[That] + + protected def newZipped[B](that: Iterable[B]): Transformed[(A, B)] = new Zipped[B] { + val other = that + } + protected def newZippedAll[A1 >: A, B](that: Iterable[B], _thisElem: A1, _thatElem: B): Transformed[(A1, B)] = new ZippedAll[A1, B] { + val other: Iterable[B] = that + val thisElem = _thisElem + val thatElem = _thatElem + } + /** Boilerplate method, to override in each subclass * This method could be eliminated if Scala had virtual classes */ diff --git a/src/library/scala/collection/generic/SequenceProxyTemplate.scala b/src/library/scala/collection/generic/SequenceProxyTemplate.scala index a731239e36..022bde02d1 100644 --- a/src/library/scala/collection/generic/SequenceProxyTemplate.scala +++ b/src/library/scala/collection/generic/SequenceProxyTemplate.scala @@ -29,9 +29,6 @@ trait SequenceProxyTemplate[+A, +This <: SequenceTemplate[A, This] with Sequence override def lengthCompare(len: Int): Int = self.lengthCompare(len) override def size = self.size override def isDefinedAt(x: Int): Boolean = self.isDefinedAt(x) - override def zip[A1 >: A, B, That](that: Sequence[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = self.zip[A1, B, That](that)(bf) - override def zipAll[B, A1 >: A, That](that: Sequence[B], thisElem: A1, thatElem: B)(implicit bf: BuilderFactory[(A1, B), That, This]): That = self.zipAll(that, thisElem, thatElem)(bf) - override def zipWithIndex[A1 >: A, That](implicit bf: BuilderFactory[(A1, Int), That, This]): That = self.zipWithIndex(bf) override def segmentLength(p: A => Boolean, from: Int): Int = self.segmentLength(p, from) override def prefixLength(p: A => Boolean) = self.prefixLength(p) override def indexWhere(p: A => Boolean): Int = self.indexWhere(p) diff --git a/src/library/scala/collection/generic/SequenceTemplate.scala b/src/library/scala/collection/generic/SequenceTemplate.scala index b436c990c6..cdbe827905 100644 --- a/src/library/scala/collection/generic/SequenceTemplate.scala +++ b/src/library/scala/collection/generic/SequenceTemplate.scala @@ -72,65 +72,6 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]] */ def isDefinedAt(x: Int): Boolean = (x >= 0) && (x < length) - /** Returns an iterable formed from this iterable and another iterable - * by combining corresponding elements in pairs. - * If one of the two iterables is longer than the other, its remaining elements are ignored. - * @param that The iterable providing the second half of each result pair - */ - def zip[A1 >: A, B, That](that: Sequence[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = { - val b = bf(thisCollection) - val these = this.iterator - val those = that.iterator - while (these.hasNext && those.hasNext) - b += ((these.next, those.next)) - b.result - } - - /** Returns a iterable formed from this iterable and the specified iterable - * <code>that</code> by associating each element of the former with - * the element at the same position in the latter. - * - * @param that iterable <code>that</code> may have a different length - * as the self iterable. - * @param thisElem element <code>thisElem</code> is used to fill up the - * resulting iterable if the self iterable is shorter than - * <code>that</code> - * @param thatElem element <code>thatElem</code> is used to fill up the - * resulting iterable if <code>that</code> is shorter than - * the self iterable - * @return <code>Sequence((a<sub>0</sub>,b<sub>0</sub>), ..., - * (a<sub>n</sub>,b<sub>n</sub>), (elem,b<sub>n+1</sub>), - * ..., {elem,b<sub>m</sub>})</code> - * when <code>[a<sub>0</sub>, ..., a<sub>n</sub>] zip - * [b<sub>0</sub>, ..., b<sub>m</sub>]</code> is - * invoked where <code>m > n</code>. - * - */ - def zipAll[B, A1 >: A, That](that: Sequence[B], thisElem: A1, thatElem: B)(implicit bf: BuilderFactory[(A1, B), That, This]): That = { - val b = bf(thisCollection) - val these = this.iterator - val those = that.iterator - while (these.hasNext && those.hasNext) - b += ((these.next, those.next)) - while (these.hasNext) - b += ((these.next, thatElem)) - while (those.hasNext) - b += ((thisElem, those.next)) - b.result - } - - /** Zips this iterable with its indices (startiong from 0). - */ - def zipWithIndex[A1 >: A, That](implicit bf: BuilderFactory[(A1, Int), That, This]): That = { - val b = bf(thisCollection) - var i = 0 - for (x <- this) { - b += ((x, i)) - i +=1 - } - b.result - } - /** Returns length of longest segment starting from a start index `from` * such that every element of the segment satisfies predicate `p`. * @note may not terminate for infinite-sized collections. diff --git a/src/library/scala/collection/generic/SequenceViewTemplate.scala b/src/library/scala/collection/generic/SequenceViewTemplate.scala index 12ccd300e2..f721072825 100644 --- a/src/library/scala/collection/generic/SequenceViewTemplate.scala +++ b/src/library/scala/collection/generic/SequenceViewTemplate.scala @@ -123,14 +123,6 @@ trait SequenceViewTemplate[+A, override def stringPrefix = super.stringPrefix+"P" } - trait Zipped[B] extends Transformed[(A, B)] { - protected[this] val other: Sequence[B] - override def iterator: Iterator[(A, B)] = self.iterator zip other.iterator - override def length = self.length min other.length - override def apply(idx: Int): (A, B) = (self.apply(idx), other.apply(idx)) - override def stringPrefix = super.stringPrefix+"Z" - } - /** Boilerplate method, to override in each subclass * This method could be eliminated if Scala had virtual classes */ @@ -145,9 +137,6 @@ trait SequenceViewTemplate[+A, protected def newPatched[B >: A](_from: Int, _patch: Sequence[B], _replaced: Int): Transformed[B] = new Patched[B] { val from = _from; val patch = _patch; val replaced = _replaced } - protected def newZipped[B](that: Sequence[B]): Transformed[(A, B)] = new Zipped[B] { - val other = that - } override def reverse: This = newReversed.asInstanceOf[This] @@ -160,19 +149,6 @@ trait SequenceViewTemplate[+A, override def padTo[B >: A, That](len: Int, elem: B)(implicit bf: BuilderFactory[B, That, This]): That = patch(length, fill(len - length)(elem), 0) - - override def zip[A1 >: A, B, That](that: Sequence[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = { - newZipped(that).asInstanceOf[That] -// was: val b = bf(thisCollection) -// if (b.isInstanceOf[NoBuilder[_]]) newZipped(that).asInstanceOf[That] -// else super.zip[A1, B, That](that)(bf) - } - - override def zipWithIndex[A1 >: A, That](implicit bf: BuilderFactory[(A1, Int), That, This]): That = - zip[A1, Int, That](Sequence.range(0, length))(bf) - - override def zipAll[B, A1 >: A, That](that: Sequence[B], thisElem: A1, thatElem: B)(implicit bf: BuilderFactory[(A1, B), That, This]): That = - self.padTo(that.length, thisElem).zip(that.padTo(this.length, thatElem))(bf.asInstanceOf[BuilderFactory[(A1, B), That, Any]]) } diff --git a/src/library/scala/collection/generic/VectorTemplate.scala b/src/library/scala/collection/generic/VectorTemplate.scala index 0925ca5d27..76f1f061b8 100644 --- a/src/library/scala/collection/generic/VectorTemplate.scala +++ b/src/library/scala/collection/generic/VectorTemplate.scala @@ -96,7 +96,7 @@ trait VectorTemplate[+A, +This <: VectorTemplate[A, This] with Vector[A]] extend override def reduceRight[B >: A](op: (A, B) => B): B = if (length > 0) foldr(0, length - 1, this(length - 1), op) else super.reduceRight(op) - override def zip[A1 >: A, B, That](that: Sequence[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = that match { + override def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: BuilderFactory[(A1, B), That, This]): That = that match { case that: Vector[_] => val b = bf(thisCollection) var i = 0 diff --git a/src/library/scala/collection/generic/VectorViewTemplate.scala b/src/library/scala/collection/generic/VectorViewTemplate.scala index f043a04685..30fb629739 100644 --- a/src/library/scala/collection/generic/VectorViewTemplate.scala +++ b/src/library/scala/collection/generic/VectorViewTemplate.scala @@ -65,7 +65,28 @@ trait VectorViewTemplate[+A, override def foreach[U](f: B => U) = super[Transformed].foreach(f) } - trait Zipped[B] extends Transformed[(A, B)] with super.Zipped[B] + trait Zipped[B] extends Transformed[(A, B)] { + protected[this] val other: Iterable[B] + def length = self.length min other.size + def apply(idx: Int): (A, B) = (self.apply(idx), other.iterator drop idx next) + override def stringPrefix = super.stringPrefix+"Z" + } + + trait ZippedAll[A1 >: A, B] extends Transformed[(A1, B)] { + protected[this] val other: Iterable[B] + val thisElem: A1 + val thatElem: B + override def iterator: Iterator[(A1, B)] = + self.iterator.zipAll(other.iterator, thisElem, thatElem) + + def length = self.length max other.size + def apply(idx: Int): (A1, B) = { + val z1 = if (idx < self.length) self.apply(idx) else thisElem + val z2 = if (idx < other.size) other drop idx head else thatElem + (z1, z2) + } + override def stringPrefix = super.stringPrefix+"Z" + } /** Boilerplate method, to override in each subclass * This method could be eliminated if Scala had virtual classes @@ -81,7 +102,12 @@ trait VectorViewTemplate[+A, protected override def newPatched[B >: A](_from: Int, _patch: Sequence[B], _replaced: Int): Transformed[B] = new Patched[B] { val from = _from; val patch = _patch; val replaced = _replaced } - protected override def newZipped[B](that: Sequence[B]): Transformed[(A, B)] = new Zipped[B] { + protected override def newZipped[B](that: Iterable[B]): Transformed[(A, B)] = new Zipped[B] { val other = that } + protected override def newZippedAll[A1 >: A, B](that: Iterable[B], _thisElem: A1, _thatElem: B): Transformed[(A1, B)] = new ZippedAll[A1, B] { + val other: Iterable[B] = that + val thisElem = _thisElem + val thatElem = _thatElem + } } diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index 4810b29e5a..b4ddb8bd4c 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -216,7 +216,7 @@ self => * <code>Stream(a<sub>0</sub>, ..., a<sub>m</sub>) * zip Stream(b<sub>0</sub>, ..., b<sub>n</sub>)</code> is invoked. */ - override final def zip[A1 >: A, B, That](that: Sequence[B])(implicit bf: BuilderFactory[(A1, B), That, Stream[A]]): That = { + override final def zip[A1 >: A, B, That](that: Iterable[B])(implicit bf: BuilderFactory[(A1, B), That, Stream[A]]): That = { // we assume there is no other builder factory on streams and therefore know that That = Stream[(A1, B)] (if (this.isEmpty || that.isEmpty) Stream.Empty else new Stream.Cons((this.head, that.head), (this.tail zip that.tail).asInstanceOf[Stream[(A1, B)]])).asInstanceOf[That] |