diff options
-rwxr-xr-x | src/library/scala/collection/IndexedSeqOptimized.scala | 12 | ||||
-rw-r--r-- | src/library/scala/collection/IterableLike.scala | 28 | ||||
-rw-r--r-- | src/library/scala/collection/Iterator.scala | 38 | ||||
-rwxr-xr-x | src/library/scala/collection/LinearSeqOptimized.scala | 16 | ||||
-rw-r--r-- | src/library/scala/collection/TraversableLike.scala | 81 | ||||
-rw-r--r-- | src/library/scala/collection/generic/TraversableForwarder.scala | 25 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/List.scala | 6 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/Range.scala | 11 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/Stream.scala | 58 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/StreamViewLike.scala | 1 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/StringLike.scala | 8 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/StringOps.scala | 11 | ||||
-rw-r--r-- | src/library/scala/io/Source.scala | 2 | ||||
-rw-r--r-- | test/files/run/bug4288.scala | 13 |
14 files changed, 140 insertions, 170 deletions
diff --git a/src/library/scala/collection/IndexedSeqOptimized.scala b/src/library/scala/collection/IndexedSeqOptimized.scala index 0d95108235..e680d02183 100755 --- a/src/library/scala/collection/IndexedSeqOptimized.scala +++ b/src/library/scala/collection/IndexedSeqOptimized.scala @@ -102,17 +102,7 @@ trait IndexedSeqOptimized[+A, +Repr] extends IndexedSeqLike[A, Repr] { self => } override /*IterableLike*/ - def slice(from: Int, until: Int): Repr = { - var i = from max 0 - val end = until min length - val b = newBuilder - b.sizeHint(end - i) - while (i < end) { - b += this(i) - i += 1 - } - b.result - } + def slice(from: Int, until: Int): Repr = sliceWithKnownSize(from max 0, until min length) override /*IterableLike*/ def head: A = if (isEmpty) super.head else this(0) diff --git a/src/library/scala/collection/IterableLike.scala b/src/library/scala/collection/IterableLike.scala index 1b5bd4b822..16d7b0f66e 100644 --- a/src/library/scala/collection/IterableLike.scala +++ b/src/library/scala/collection/IterableLike.scala @@ -92,33 +92,13 @@ self => iterator.reduceRight(op) override /*TraversableLike*/ def toIterable: Iterable[A] = thisCollection - override /*TraversableLike*/ def head: A = - if (isEmpty) throw new NoSuchElementException - else iterator.next - - override /*TraversableLike*/ def take(n: Int): Repr = { - val b = newBuilder - b.sizeHintBounded(n, this) - var i = 0 - val it = iterator - while (i < n && it.hasNext) { - b += it.next - i += 1 - } - b.result - } + iterator.next override /*TraversableLike*/ def slice(from: Int, until: Int): Repr = { - val b = newBuilder - b.sizeHintBounded(until - from, this) - var i = from - val it = iterator drop from - while (i < until && it.hasNext) { - b += it.next - i += 1 - } - b.result + val lo = from max 0 + if (until <= lo) newBuilder.result + else newBuilder ++= (iterator drop lo take (until - lo)) result } override /*TraversableLike*/ def takeWhile(p: A => Boolean): Repr = { diff --git a/src/library/scala/collection/Iterator.scala b/src/library/scala/collection/Iterator.scala index 58df4ff0d4..18b0d1c5b5 100644 --- a/src/library/scala/collection/Iterator.scala +++ b/src/library/scala/collection/Iterator.scala @@ -284,15 +284,9 @@ trait Iterator[+A] extends TraversableOnce[A] { /** Selects first ''n'' values of this iterator. * @param n the number of values to take * @return an iterator producing only of the first `n` values of this iterator, or else the - * whole iterator, if it produces less than `n` values. + * whole iterator, if it produces fewer than `n` values. */ - def take(n: Int): Iterator[A] = new Iterator[A] { - private var remaining = n - def hasNext = remaining > 0 && self.hasNext - def next(): A = - if (hasNext) { remaining -= 1; self.next() } - else empty.next() - } + def take(n: Int): Iterator[A] = slice(0, n) /** Advances this iterator past the first ''n'' elements, * or the length of the iterator, whichever is smaller. @@ -301,14 +295,7 @@ trait Iterator[+A] extends TraversableOnce[A] { * @return an iterator which produces all values of the current iterator, except * it omits the first `n` values. */ - def drop(n: Int): Iterator[A] = { - @tailrec - def loop(left: Int): Iterator[A] = - if (left > 0 && hasNext) { next; loop(left - 1) } - else this - - loop(n) - } + def drop(n: Int): Iterator[A] = slice(n, Int.MaxValue) /** Creates an iterator returning an interval of the values produced by this iterator. * @param from the index of the first element in this iterator which forms part of the slice. @@ -316,7 +303,24 @@ trait Iterator[+A] extends TraversableOnce[A] { * @return an iterator which advances this iterator past the first `from` elements using `drop`, * and then takes `until - from` elements, using `take`. */ - def slice(from: Int, until: Int): Iterator[A] = drop(from).take(until - from) + def slice(from: Int, until: Int): Iterator[A] = { + val lo = from max 0 + var toDrop = lo + while (toDrop > 0 && self.hasNext) { + self.next + toDrop -= 1 + } + new Iterator[A] { + private var remaining = until - lo + def hasNext = remaining > 0 && self.hasNext + def next(): A = + if (remaining > 0) { + remaining -= 1 + self.next() + } + else empty.next() + } + } /** Creates a new iterator that maps all produced values of this iterator * to new values using a transformation function. diff --git a/src/library/scala/collection/LinearSeqOptimized.scala b/src/library/scala/collection/LinearSeqOptimized.scala index 5e47021110..f57dba2d3f 100755 --- a/src/library/scala/collection/LinearSeqOptimized.scala +++ b/src/library/scala/collection/LinearSeqOptimized.scala @@ -183,13 +183,21 @@ trait LinearSeqOptimized[+A, +Repr <: LinearSeqOptimized[A, Repr]] extends Linea override /*IterableLike*/ def slice(from: Int, until: Int): Repr = { + var these: Repr = repr + var count = from max 0 + if (until <= count) + return newBuilder.result + val b = newBuilder - var i = from - var these = this drop from - while (i < until && !these.isEmpty) { + var sliceElems = until - count + while (these.nonEmpty && count > 0) { + these = these.tail + count -= 1 + } + while (these.nonEmpty && sliceElems > 0) { + sliceElems -= 1 b += these.head these = these.tail - i += 1 } b.result } diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala index 57191cdd9a..293cf86eb0 100644 --- a/src/library/scala/collection/TraversableLike.scala +++ b/src/library/scala/collection/TraversableLike.scala @@ -563,19 +563,7 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] * @return a $coll consisting only of the first `n` elements of this $coll, * or else the whole $coll, if it has less than `n` elements. */ - def take(n: Int): Repr = { - val b = newBuilder - b.sizeHintBounded(n, this) - var i = 0 - breakable { - for (x <- this) { - if (i >= n) break - b += x - i += 1 - } - } - b.result - } + def take(n: Int): Repr = sliceWithKnownSize(0, n) /** Selects all elements except first ''n'' ones. * $orderDependent @@ -583,41 +571,64 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] * @return a $coll consisting of all elements of this $coll except the first `n` ones, or else the * empty $coll, if this $coll has less than `n` elements. */ - def drop(n: Int): Repr = { - val b = newBuilder - if (n >= 0) b.sizeHint(this, -n) - var i = 0 - for (x <- this) { - if (i >= n) b += x - i += 1 - } - b.result - } + def drop(n: Int): Repr = + if (n <= 0) newBuilder ++= thisCollection result + else sliceWithKnownDelta(n, Int.MaxValue, -n) - /** Selects an interval of elements. - * - * Note: `c.slice(from, to)` is equivalent to (but possibly more efficient than) - * `c.drop(from).take(to - from)` + /** Selects an interval of elements. The returned collection is made up + * of all elements `x` which satisfy the invariant: + * {{{ + * from <= indexOf(x) < until + * }}} * $orderDependent * - * @param from the index of the first returned element in this $coll. - * @param until the index one past the last returned element in this $coll. - * @return a $coll containing the elements starting at index `from` - * and extending up to (but not including) index `until` of this $coll. + * @param from the lowest index to include from this $coll. + * @param until the highest index to EXCLUDE from this $coll. + * @return a $coll containing the elements greater than or equal to + * index `from` extending up to (but not including) index `until` + * of this $coll. */ - def slice(from: Int, until: Int): Repr = { - val b = newBuilder - b.sizeHintBounded(until - from, this) + def slice(from: Int, until: Int): Repr = sliceWithKnownBound(from max 0, until) + + // Precondition: from >= 0, until > 0, builder already configured for building. + private[this] def sliceInternal(from: Int, until: Int, b: Builder[A, Repr]): Repr = { var i = 0 breakable { for (x <- this) { if (i >= from) b += x i += 1 - if (i == until) break + if (i >= until) break } } b.result } + // Precondition: from >= 0 + private[scala] def sliceWithKnownDelta(from: Int, until: Int, delta: Int): Repr = { + val b = newBuilder + if (until <= from) b.result + else { + b.sizeHint(this, delta) + sliceInternal(from, until, b) + } + } + // Precondition: from >= 0 + private[scala] def sliceWithKnownSize(from: Int, until: Int): Repr = { + val b = newBuilder + if (until <= from) b.result + else { + b.sizeHint(until - from) + sliceInternal(from, until, b) + } + } + // Precondition: from >= 0 + private[scala] def sliceWithKnownBound(from: Int, until: Int): Repr = { + val b = newBuilder + if (until <= from) b.result + else { + b.sizeHintBounded(until - from, this) + sliceInternal(from, until, b) + } + } /** Takes longest prefix of elements that satisfy a predicate. * $orderDependent diff --git a/src/library/scala/collection/generic/TraversableForwarder.scala b/src/library/scala/collection/generic/TraversableForwarder.scala index 100733abf4..0049d23a86 100644 --- a/src/library/scala/collection/generic/TraversableForwarder.scala +++ b/src/library/scala/collection/generic/TraversableForwarder.scala @@ -12,30 +12,19 @@ import scala.collection._ import mutable.{ Buffer, StringBuilder } import immutable.{ List, Stream } -/** <p> - * This trait implements a forwarder for traversable objects. It forwards - * all calls to a different iterable object, except for - * </p> - * <ul> - * <li><code>toString</code>, <code>hashCode</code>, <code>equals</code>, - * <code>stringPrefix</code> - * </li> - * <li><code>newBuilder</code>, <code>view</code></li> - * <li>all calls creating a new iterable object of the same kind</li> - * </ul> - * <p> - * The above methods are forwarded by subclass - * <a href="TraversableProxy.html" target="ContentFrame"> - * <code>TraversableProxy</code></a>. - * </p> +/** This trait implements a forwarder for traversable objects. It forwards + * all calls to a different traversable, except for: + {{{ + toString, hashCode, equals, stringPrefix, newBuilder, view + }}} + * All calls creating a new traversable of the same kind. * * @author Martin Odersky * @version 2.8 * @since 2.8 */ trait TraversableForwarder[+A] extends Traversable[A] { - - /** The iterable object to which calls are forwarded */ + /** The traversable object to which calls are forwarded. */ protected def underlying: Traversable[A] override def foreach[B](f: A => B): Unit = underlying.foreach(f) diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala index b1daf5541e..c46c487968 100644 --- a/src/library/scala/collection/immutable/List.scala +++ b/src/library/scala/collection/immutable/List.scala @@ -171,12 +171,6 @@ sealed abstract class List[+A] extends LinearSeq[A] these } - override def slice(start: Int, end: Int): List[A] = { - var len = end - if (start > 0) len -= start - drop(start) take len - } - override def takeRight(n: Int): List[A] = { @tailrec def loop(lead: List[A], lag: List[A]): List[A] = lead match { diff --git a/src/library/scala/collection/immutable/Range.scala b/src/library/scala/collection/immutable/Range.scala index 6d03adc8ea..f8b3dfa54f 100644 --- a/src/library/scala/collection/immutable/Range.scala +++ b/src/library/scala/collection/immutable/Range.scala @@ -139,17 +139,6 @@ extends IndexedSeq[Int] drop(1) } - /** Creates a new range contained in the specified slice of this range. - * - * $doesNotUseBuilders - * - * @param from the start of the slice. - * @param until the end of the slice. - * @return a new range consisting of all the elements of this range contained in the specified slice. - */ - final override def slice(from: Int, until: Int): Range = - this drop from take (until - from) - // Counts how many elements from the start meet the given test. private def skipCount(p: Int => Boolean): Int = { var current = start diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index 26fa86861c..b12b312d21 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -14,8 +14,7 @@ package immutable import generic._ import mutable.{Builder, StringBuilder, LazyBuilder, ListBuffer} import scala.annotation.tailrec - - +import Stream.cons /** The class `Stream` implements lazy lists where elements * are only evaluated when they are needed. Here is an example: @@ -78,7 +77,7 @@ self => * @return The stream containing elements of this stream and the traversable object. */ def append[B >: A](rest: => TraversableOnce[B]): Stream[B] = - if (isEmpty) rest.toStream else new Stream.Cons(head, tail append rest) + if (isEmpty) rest.toStream else cons(head, tail append rest) /** Forces evaluation of the whole stream and returns it. */ def force: Stream[A] = { @@ -143,7 +142,7 @@ self => // we assume there is no other builder factory on streams and therefore know that That = Stream[A] if (isStreamBuilder(bf)) asThat( if (isEmpty) that.toStream - else new Stream.Cons(head, asStream[A](tail ++ that)) + else cons(head, asStream[A](tail ++ that)) ) else super.++(that)(bf) @@ -155,7 +154,7 @@ self => override final def scanLeft[B, That](z: B)(op: (B, A) => B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = if (isStreamBuilder(bf)) asThat( if (isEmpty) Stream(z) - else new Stream.Cons(z, asStream[B](tail.scanLeft(op(z, head))(op))) + else cons(z, asStream[B](tail.scanLeft(op(z, head))(op))) ) else super.scanLeft(z)(op)(bf) @@ -169,7 +168,7 @@ self => override final def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = { if (isStreamBuilder(bf)) asThat( if (isEmpty) Stream.Empty - else new Stream.Cons(f(head), asStream[B](tail map f)) + else cons(f(head), asStream[B](tail map f)) ) else super.map(f)(bf) } @@ -246,7 +245,7 @@ self => def tailMap = asStream[B](tail withFilter p map f) if (isStreamBuilder(bf)) asThat( if (isEmpty) Stream.Empty - else if (p(head)) new Stream.Cons(f(head), tailMap) + else if (p(head)) cons(f(head), tailMap) else tailMap ) else super.map(f)(bf) @@ -362,7 +361,7 @@ self => // we assume there is no other builder factory on streams and therefore know that That = Stream[(A1, B)] if (isStreamBuilder(bf)) asThat( if (this.isEmpty || that.isEmpty) Stream.Empty - else new Stream.Cons((this.head, that.head), asStream[(A1, B)](this.tail zip that.tail)) + else cons((this.head, that.head), asStream[(A1, B)](this.tail zip that.tail)) ) else super.zip(that)(bf) @@ -410,6 +409,8 @@ self => override def toString = super.mkString(stringPrefix + "(", ", ", ")") + override def splitAt(n: Int): (Stream[A], Stream[A]) = (take(n), drop(n)) + /** Returns the <code>n</code> first elements of this stream, or else the whole * stream, if it has less than <code>n</code> elements. * @@ -417,27 +418,20 @@ self => * @return the <code>n</code> first elements of this stream. */ override def take(n: Int): Stream[A] = - if (n <= 0 || isEmpty) Stream.Empty - else new Stream.Cons(head, if (n == 1) Stream.empty else tail take (n-1)) + if (n <= 0 || isEmpty) Stream.empty + else if (n == 1) cons(head, Stream.empty) + else cons(head, tail take n-1) - override def splitAt(n: Int): (Stream[A], Stream[A]) = (take(n), drop(n)) - - /** A substream starting at index `from` - * and extending up to (but not including) index `until`. - * - * @note This is equivalent to (but possibly more efficient than) - * c.drop(from).take(to - from) + /** A substream starting at index `from` and extending up to (but not including) + * index `until`. * * @param start The index of the first element of the returned subsequence * @param end The index of the element following the returned subsequence - * @throws IndexOutOfBoundsException if <code>from < 0</code> - * or <code>length < from + len<code> - * @note Might return different results for different runs, unless this iterable is ordered */ - override def slice(start: Int, end: Int): Stream[A] = { - var len = end - if (start > 0) len -= start - drop(start) take len + override def slice(from: Int, until: Int): Stream[A] = { + val lo = from max 0 + if (until <= lo || isEmpty) Stream.empty + else this drop lo take (until - lo) } /** The stream without its last element. @@ -446,7 +440,7 @@ self => override def init: Stream[A] = if (isEmpty) super.init else if (tail.isEmpty) Stream.Empty - else new Stream.Cons(head, tail.init) + else cons(head, tail.init) /** Returns the rightmost <code>n</code> elements from this iterable. * @param n the number of elements to take @@ -469,7 +463,7 @@ self => * @param p the test predicate. */ override def takeWhile(p: A => Boolean): Stream[A] = - if (!isEmpty && p(head)) new Stream.Cons(head, tail takeWhile p) + if (!isEmpty && p(head)) cons(head, tail takeWhile p) else Stream.Empty /** Returns the longest suffix of this iterable whose first element @@ -488,7 +482,7 @@ self => */ override def distinct: Stream[A] = if (isEmpty) this - else new Stream.Cons(head, tail.filter(head !=).distinct) + else cons(head, tail.filter(head !=).distinct) /** Returns a new sequence of given length containing the elements of this sequence followed by zero * or more occurrences of given elements. @@ -496,7 +490,7 @@ self => override def padTo[B >: A, That](len: Int, elem: B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = { def loop(len: Int, these: Stream[A]): Stream[B] = if (these.isEmpty) Stream.fill(len)(elem) - else new Stream.Cons(these.head, loop(len - 1, these.tail)) + else cons(these.head, loop(len - 1, these.tail)) if (isStreamBuilder(bf)) asThat(loop(len, this)) else super.padTo(len, elem)(bf) @@ -519,7 +513,7 @@ self => override def flatten[B](implicit asTraversable: A => /*<:<!!!*/ TraversableOnce[B]): Stream[B] = { def flatten1(t: Traversable[B]): Stream[B] = if (!t.isEmpty) - new Stream.Cons(t.head, flatten1(t.tail)) + cons(t.head, flatten1(t.tail)) else tail.flatten @@ -593,7 +587,7 @@ object Stream extends SeqFactory[Stream] { * to streams. */ class ConsWrapper[A](tl: => Stream[A]) { - def #::(hd: A): Stream[A] = new Stream.Cons(hd, tl) + def #::(hd: A): Stream[A] = cons(hd, tl) def #:::(prefix: Stream[A]): Stream[A] = prefix append tl } @@ -702,11 +696,11 @@ object Stream extends SeqFactory[Stream] { } private[immutable] def filteredTail[A](stream: Stream[A], p: A => Boolean) = { - new Stream.Cons(stream.head, stream.tail filter p) + cons(stream.head, stream.tail filter p) } private[immutable] def collectedTail[A, B, That](stream: Stream[A], pf: PartialFunction[A, B], bf: CanBuildFrom[Stream[A], B, That]) = { - new Stream.Cons(pf(stream.head), stream.tail.collect(pf)(bf).asInstanceOf[Stream[B]]) + cons(pf(stream.head), stream.tail.collect(pf)(bf).asInstanceOf[Stream[B]]) } /** A stream containing all elements of a given iterator, in the order they are produced. diff --git a/src/library/scala/collection/immutable/StreamViewLike.scala b/src/library/scala/collection/immutable/StreamViewLike.scala index a3da3fd1b6..7995507943 100644 --- a/src/library/scala/collection/immutable/StreamViewLike.scala +++ b/src/library/scala/collection/immutable/StreamViewLike.scala @@ -67,6 +67,7 @@ extends SeqView[A, Coll] } protected override def newPrepended[B >: A](elem: B): Transformed[B] = new Prepended[B] { protected[this] val fst = elem } + override def stringPrefix = "StreamView" } diff --git a/src/library/scala/collection/immutable/StringLike.scala b/src/library/scala/collection/immutable/StringLike.scala index acb5dd586a..926fde4fe0 100644 --- a/src/library/scala/collection/immutable/StringLike.scala +++ b/src/library/scala/collection/immutable/StringLike.scala @@ -57,6 +57,14 @@ self => override def mkString = toString + override def slice(from: Int, until: Int): Repr = { + val start = from max 0 + val end = until min length + + if (start >= end) newBuilder.result + else newBuilder ++= toString.substring(start, end) result + } + /** Return the current string concatenated `n` times. */ def * (n: Int): String = { diff --git a/src/library/scala/collection/immutable/StringOps.scala b/src/library/scala/collection/immutable/StringOps.scala index fdc5a51d7d..06a62c2604 100644 --- a/src/library/scala/collection/immutable/StringOps.scala +++ b/src/library/scala/collection/immutable/StringOps.scala @@ -36,16 +36,5 @@ final class StringOps(override val repr: String) extends StringLike[String] { /** Creates a string builder buffer as builder for this class */ override protected[this] def newBuilder = StringBuilder.newBuilder - override def slice(from: Int, until: Int): String = { - /** Slice must be forgiving on all out of bounds indices and - * substring is not. - */ - val start = from max 0 - val end = until min repr.length - - if (start >= end) "" - else repr.substring(start, end) - } - override def toString = repr } diff --git a/src/library/scala/io/Source.scala b/src/library/scala/io/Source.scala index 2f9085211d..570c48a91a 100644 --- a/src/library/scala/io/Source.scala +++ b/src/library/scala/io/Source.scala @@ -199,7 +199,7 @@ abstract class Source extends Iterator[Char] { */ @deprecated("Use a collections method such as getLines().toIndexedSeq for random access.") def getLine(line: Int): String = lineNum(line) - private def lineNum(line: Int): String = getLines() drop (line - 1) next + private def lineNum(line: Int): String = getLines() drop (line - 1) take 1 mkString class LineIterator() extends Iterator[String] { private[this] val sb = new StringBuilder diff --git a/test/files/run/bug4288.scala b/test/files/run/bug4288.scala new file mode 100644 index 0000000000..4e7b366f60 --- /dev/null +++ b/test/files/run/bug4288.scala @@ -0,0 +1,13 @@ +object Test { + def f1 = scala.collection.mutable.ListBuffer(1 to 9: _*).slice(-5, -1) + def f2 = scala.collection.mutable.ListBuffer(1 to 9: _*).readOnly.slice(-5, -1) + def f3 = Vector(1 to 9: _*).slice(-5, -1) + def f4 = Traversable(1 to 9: _*).slice(-5, -1) + def f5 = (1 to 9).toArray.slice(-5, -1) + def f6 = (1 to 9).toStream.slice(-5, -1) + def f7 = (1 to 9).slice(-5, -1) + + def main(args: Array[String]): Unit = { + List[Traversable[Int]](f1, f2, f3, f4, f5, f6, f7) foreach (x => assert(x.isEmpty, x)) + } +} |