diff options
author | Erik Erlandson <eerlands@redhat.com> | 2014-09-04 11:10:13 -0700 |
---|---|---|
committer | Erik Erlandson <eerlands@redhat.com> | 2014-10-21 19:06:41 -0700 |
commit | 59438d0647995f75bd1bf7159a248340d3708abd (patch) | |
tree | d1dd426ce8266ca117ab87523c89ecc1bd3d09e9 | |
parent | 850899b1c9347e804763a258f64d54cef0ffd69a (diff) | |
download | scala-59438d0647995f75bd1bf7159a248340d3708abd.tar.gz scala-59438d0647995f75bd1bf7159a248340d3708abd.tar.bz2 scala-59438d0647995f75bd1bf7159a248340d3708abd.zip |
SI-8835 Fix implementation of Iterator drop to remove quadratic behavior
-rw-r--r-- | src/library/scala/collection/Iterator.scala | 9 | ||||
-rw-r--r-- | test/files/run/iterators.check | 1 | ||||
-rw-r--r-- | test/files/run/iterators.scala | 44 |
3 files changed, 47 insertions, 7 deletions
diff --git a/src/library/scala/collection/Iterator.scala b/src/library/scala/collection/Iterator.scala index 660cc5a42a..0115cc154c 100644 --- a/src/library/scala/collection/Iterator.scala +++ b/src/library/scala/collection/Iterator.scala @@ -320,7 +320,14 @@ trait Iterator[+A] extends TraversableOnce[A] { * it omits the first `n` values. * @note Reuse: $consumesAndProducesIterator */ - def drop(n: Int): Iterator[A] = slice(n, Int.MaxValue) + def drop(n: Int): Iterator[A] = { + var j = 0 + while (j < n && this.hasNext) { + this.next + j += 1 + } + this + } /** Creates an iterator returning an interval of the values produced by this iterator. * diff --git a/test/files/run/iterators.check b/test/files/run/iterators.check index bb139c1610..abaf80ff38 100644 --- a/test/files/run/iterators.check +++ b/test/files/run/iterators.check @@ -4,6 +4,7 @@ test check_range2 was successful test check_range3 was successful test check_take was successful test check_drop was successful +test check_slice was successful test check_foreach was successful test check_forall was successful test check_fromArray was successful diff --git a/test/files/run/iterators.scala b/test/files/run/iterators.scala index 57e05d3472..d54da3d3ba 100644 --- a/test/files/run/iterators.scala +++ b/test/files/run/iterators.scala @@ -55,11 +55,42 @@ object Test { } def check_drop: Int = { - val it1 = Iterator.from(0) - val it2 = it1 map { 2 * _ } - val n1 = it1 drop 2 next - val n2 = it2 drop 2 next; - n1 + n2 + val tests = Array( + Iterator.from(0).take(5).drop(1).toSeq sameElements Seq(1, 2, 3, 4), + Iterator.from(0).take(5).drop(3).toSeq sameElements Seq(3, 4), + + Iterator.from(0).take(5).drop(5).toSeq sameElements Seq(), + Iterator.from(0).take(5).drop(10).toSeq sameElements Seq(), + + Iterator.from(0).take(5).drop(0).toSeq sameElements Seq(0, 1, 2, 3, 4), + Iterator.from(0).take(5).drop(-1).toSeq sameElements Seq(0, 1, 2, 3, 4), + + Iterator.from(0).take(5).drop(1).map(2 * _).toSeq sameElements Seq(2, 4, 6, 8), + Iterator.from(0).take(5).map(2 * _).drop(1).toSeq sameElements Seq(2, 4, 6, 8), + + Iterator.from(0).take(5).drop(1).drop(2).toSeq sameElements Seq(3, 4), + Iterator.from(0).take(5).drop(2).drop(1).toSeq sameElements Seq(3, 4) + ) + tests.count(result => result) + } + + def check_slice: Int = { + val tests = Array( + Iterator.from(0).slice(3, 7).toSeq sameElements Seq(3, 4, 5, 6), + Iterator.from(0).slice(3, 3).toSeq sameElements Seq(), + Iterator.from(0).slice(-1, 3).toSeq sameElements Seq(0, 1, 2), + Iterator.from(0).slice(3, -1).toSeq sameElements Seq(), + + Iterator.from(0).slice(3, 7).map(2 * _).toSeq sameElements Seq(6, 8, 10, 12), + Iterator.from(0).map(2 * _).slice(3, 7).toSeq sameElements Seq(6, 8, 10, 12), + + Iterator.from(0).slice(3, 7).drop(1).toSeq sameElements Seq(4, 5, 6), + Iterator.from(0).drop(1).slice(3, 7).toSeq sameElements Seq(4, 5, 6, 7), + + Iterator.from(0).slice(3, 7).slice(1, 3).toSeq sameElements Seq(4, 5), + Iterator.from(0).slice(3, 7).slice(1, 10).toSeq sameElements Seq(4, 5, 6) + ) + tests.count(result => result) } def check_foreach: Int = { @@ -122,7 +153,8 @@ object Test { check_success("check_range2", check_range2, 26) check_success("check_range3", check_range3, 3) check_success("check_take", check_take, 10) - check_success("check_drop", check_drop, 12) + check_success("check_drop", check_drop, 10) + check_success("check_slice", check_slice, 10) check_success("check_foreach", check_foreach, 190) check_success("check_forall", check_forall, 0) check_success("check_fromArray",check_fromArray, 14) |