Views using methods implemented in terms of isE...

Views using methods implemented in terms of isEmpty (in particular,
headOption and lastOption) were traversing the collection twice up
to the nonEmpty element, because "if (isEmpty) None else Some(head)"
means calling isEmpty separately from head. I overrode those methods in
TraversableViewLike to avoid the second traversal.

This leaves at least init and tail still in that boat, but they were
getting too involved.

How do I say "review by pool of reviewers", who can help set that up? In
the meantime no review.

3 files changed, 67 insertions, 0 deletions

diff --git a/src/library/scala/collection/TraversableViewLike.scala b/src/library/scala/collection/TraversableViewLike.scala
index 36fe6251df..03286fef67 100644
--- a/src/library/scala/collection/TraversableViewLike.scala
+++ b/src/library/scala/collection/TraversableViewLike.scala
@@ -82,6 +82,27 @@ trait TraversableViewLike[+A,
   trait Transformed[+B] extends TraversableView[B, Coll] with super.Transformed[B] {
     def foreach[U](f: B => U): Unit
 
+    // Methods whose standard implementations use "isEmpty" need to be rewritten
+    // for views, else they will end up traversing twice in a situation like:
+    //   xs.view.flatMap(f).headOption
+    override def headOption: Option[B] = {
+      for (x <- this)
+        return Some(x)
+
+      None
+    }
+    override def lastOption: Option[B] = {
+      // (Should be) better than allocating a Some for every element.
+      var empty = true
+      var result: B = null.asInstanceOf[B]
+      for (x <- this) {
+        empty = false
+        result = x
+      }
+      if (empty) None else Some(result)
+    }
+
+    // XXX: As yet not dealt with, tail and init both call isEmpty.
     override def stringPrefix = self.stringPrefix
     override def toString = viewToString
   }
diff --git a/test/files/run/view-headoption.check b/test/files/run/view-headoption.check
new file mode 100644
index 0000000000..5c98b54b46
--- /dev/null
+++ b/test/files/run/view-headoption.check
@@ -0,0 +1,28 @@
+fail
+success
+f1: Some(5)
+fail
+success
+f2: 5
+fail
+success
+fail
+fail
+success
+fail
+fail
+fail
+success
+f3: Some(5)
+fail
+success
+fail
+success
+fail
+fail
+success
+fail
+fail
+fail
+success
+f4: 5
diff --git a/test/files/run/view-headoption.scala b/test/files/run/view-headoption.scala
new file mode 100644
index 0000000000..659c7e6b82
--- /dev/null
+++ b/test/files/run/view-headoption.scala
@@ -0,0 +1,18 @@
+object Test {
+  val failer    = () => { println("fail") ; None }
+  val succeeder = () => { println("success") ; Some(5) }
+  val fs = List(failer, succeeder, failer, failer, succeeder, failer, failer, failer, succeeder)
+
+  def f0 = fs.view flatMap (f => f())
+  def f1 = f0.headOption
+  def f2 = f0.head
+  def f3 = f0.lastOption
+  def f4 = f0.last
+
+  def main(args: Array[String]): Unit = {
+    println("f1: " + f1)
+    println("f2: " + f2)
+    println("f3: " + f3)
+    println("f4: " + f4)
+  }
+}