From ecee7b75328ae1f856b5fa832ebad7fc9e42f64a Mon Sep 17 00:00:00 2001
From: Stefan Zeiger <szeiger@novocode.com>
Date: Fri, 29 Jan 2016 17:28:16 +0100
Subject: SI-9623 Avoid unnecessary hasNext calls in JoinIterator &
 ConcatIterator
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

These iterator implementations are used to concatenate two (JoinIterator)
or more (ConcatIterator) other iterators with `++`. They used to perform
many unnecessary calls to the child iterators’ `hasNext` methods.

This improved state machine-based implementation reduces that number to
the bare minimum, i.e. iterating over concatenated iterators with
`foreach` calls the children's `hasNext` methods a total of (number of
children) + (number of elements) times, the same as when iterating over
all children separately.
---
 test/junit/scala/collection/IteratorTest.scala | 28 ++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)

(limited to 'test/junit/scala/collection')

diff --git a/test/junit/scala/collection/IteratorTest.scala b/test/junit/scala/collection/IteratorTest.scala
index 1c1e50aed9..329c85127a 100644
--- a/test/junit/scala/collection/IteratorTest.scala
+++ b/test/junit/scala/collection/IteratorTest.scala
@@ -164,4 +164,32 @@ class IteratorTest {
     assertEquals(1, y.next)
     assertFalse(x.hasNext)   // was true, after advancing underlying iterator
   }
+  // SI-9623
+  @Test def noExcessiveHasNextInJoinIterator: Unit = {
+    var counter = 0
+    val exp = List(1,2,3,1,2,3)
+    def it: Iterator[Int] = new Iterator[Int] {
+      val parent = List(1,2,3).iterator
+      def next(): Int = parent.next
+      def hasNext: Boolean = { counter += 1; parent.hasNext }
+    }
+    // Iterate separately
+    val res = new mutable.ArrayBuffer[Int]
+    it.foreach(res += _)
+    it.foreach(res += _)
+    assertSameElements(exp, res)
+    assertEquals(8, counter)
+    // JoinIterator
+    counter = 0
+    res.clear
+    (it ++ it).foreach(res += _)
+    assertSameElements(exp, res)
+    assertEquals(8, counter) // was 17
+    // ConcatIterator
+    counter = 0
+    res.clear
+    (Iterator.empty ++ it ++ it).foreach(res += _)
+    assertSameElements(exp, res)
+    assertEquals(8, counter) // was 14
+  }
 }
-- 
cgit v1.2.3