SI-7614 Minimize the times of evaluation f in TraversableOnce.maxBy/minBy.

In the previous implementation, maxBy/minBy will evaluate most of its elements
with f twice to get the ordering. That results (2n - 2) evaluations of f.

I save both the element and result of evaluation to a tuple so that it doesn't
need to re-evaluate f on next comparison. Thus only n evaluations of f, that is
the optimal.

Note that the original implementation always returns the first matched if more
than one element evaluated to same largest/smallest value of f. I document
this behavior explicitly in this commit as well.

3 files changed, 122 insertions, 2 deletions

diff --git a/src/library/scala/collection/GenTraversableOnce.scala b/src/library/scala/collection/GenTraversableOnce.scala
index d966c7324b..3d1b2c4278 100644
--- a/src/library/scala/collection/GenTraversableOnce.scala
+++ b/src/library/scala/collection/GenTraversableOnce.scala
@@ -363,8 +363,34 @@ trait GenTraversableOnce[+A] extends Any {
    */
   def max[A1 >: A](implicit ord: Ordering[A1]): A
 
+  /** Finds the first element which yields the largest value measured by function f.
+   *
+   *  @param    cmp   An ordering to be used for comparing elements.
+   *  @tparam   B     The result type of the function f.
+   *  @param    f     The measuring function.
+   *  @return   the first element of this $coll with the largest value measured by function f 
+   *  with respect to the ordering `cmp`.
+   *
+   *  @usecase def maxBy[B](f: A => B): A
+   *    @inheritdoc
+   *
+   *    @return   the first element of this $coll with the largest value measured by function f.
+   */
   def maxBy[B](f: A => B)(implicit cmp: Ordering[B]): A
 
+  /** Finds the first element which yields the smallest value measured by function f.
+   *
+   *  @param    cmp   An ordering to be used for comparing elements.
+   *  @tparam   B     The result type of the function f.
+   *  @param    f     The measuring function.
+   *  @return   the first element of this $coll with the smallest value measured by function f 
+   *  with respect to the ordering `cmp`.
+   *
+   *  @usecase def minBy[B](f: A => B): A
+   *    @inheritdoc
+   *
+   *    @return   the first element of this $coll with the smallest value measured by function f.
+   */
   def minBy[B](f: A => B)(implicit cmp: Ordering[B]): A
 
   def forall(pred: A => Boolean): Boolean
diff --git a/src/library/scala/collection/TraversableOnce.scala b/src/library/scala/collection/TraversableOnce.scala
index 526c36dda7..634807b29f 100644
--- a/src/library/scala/collection/TraversableOnce.scala
+++ b/src/library/scala/collection/TraversableOnce.scala
@@ -221,13 +221,37 @@ trait TraversableOnce[+A] extends Any with GenTraversableOnce[A] {
     if (isEmpty)
       throw new UnsupportedOperationException("empty.maxBy")
 
-    reduceLeft((x, y) => if (cmp.gteq(f(x), f(y))) x else y)
+    var maxF: B = null.asInstanceOf[B]
+    var maxElem: A = null.asInstanceOf[A]
+    var first = true
+
+    for (elem <- self) {
+      val fx = f(elem)
+      if (first || cmp.gt(fx, maxF)) {
+        maxElem = elem
+        maxF = fx
+        first = false
+      }
+    }
+    maxElem
   }
   def minBy[B](f: A => B)(implicit cmp: Ordering[B]): A = {
     if (isEmpty)
       throw new UnsupportedOperationException("empty.minBy")
 
-    reduceLeft((x, y) => if (cmp.lteq(f(x), f(y))) x else y)
+    var minF: B = null.asInstanceOf[B]
+    var minElem: A = null.asInstanceOf[A]
+    var first = true
+    
+    for (elem <- self) {
+      val fx = f(elem)
+      if (first || cmp.lt(fx, minF)) {
+        minElem = elem
+        minF = fx
+        first = false
+      }
+    }
+    minElem
   }
 
   /** Copies all elements of this $coll to a buffer.
diff --git a/test/junit/scala/collection/TraversableOnceTest.scala b/test/junit/scala/collection/TraversableOnceTest.scala
new file mode 100644
index 0000000000..56d8312336
--- /dev/null
+++ b/test/junit/scala/collection/TraversableOnceTest.scala
@@ -0,0 +1,70 @@
+package scala.collection
+
+import org.junit.Assert._
+import org.junit.Test
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+import scala.util.Random
+
+@RunWith(classOf[JUnit4])
+/* Test for SI-7614 */
+class TraversableOnceTest {
+  val list = List.fill(1000)(scala.util.Random.nextInt(10000) - 5000)
+
+  // Basic emptiness check
+  @Test
+  def checkEmpty {
+    def hasException(code: => Any): Boolean = try {
+      code
+      false
+    } catch {
+      case u: UnsupportedOperationException => true
+      case t: Throwable => false
+    }
+    assert(hasException({ List[Int]().maxBy(_ * 3) }), "maxBy: on empty list should throw UnsupportedOperationException.")
+    assert(hasException({ List[Int]().minBy(_ * 3) }), "minBy: on empty list should throw UnsupportedOperationException.")
+  }
+
+  // Basic definition of minBy/maxBy.
+  @Test
+  def testCorrectness() = {
+    def f(x: Int) = -1 * x
+    val max = list.maxBy(f)
+    assert(list.forall(f(_) <= f(max)), "f(list.maxBy(f)) should ≥ f(x) where x is any element of list.")
+
+    val min = list.minBy(f)
+    assert(list.forall(f(_) >= f(min)), "f(list.minBy(f)) should ≤ f(x) where x is any element of list.")
+  }
+
+  // Ensure that it always returns the first match if more than one element have the same largest/smallest f(x).
+  // Note that this behavior is not explicitly stated before. 
+  // To make it compatible with the previous implementation, I add this behavior to docs.
+  @Test
+  def testReturnTheFirstMatch() = {
+    val d = List(1, 2, 3, 4, 5, 6, 7, 8)
+    def f(x: Int) = x % 3;
+    assert(d.maxBy(f) == 2, "If multiple elements evaluted to the largest value, maxBy should return the first one.")
+    assert(d.minBy(f) == 3, "If multiple elements evaluted to the largest value, minBy should return the first one.")
+  }
+
+  // Make sure it evaluates f no more than list.length times.
+  @Test
+  def testOnlyEvaluateOnce() = {
+    var evaluatedCountOfMaxBy = 0
+
+    val max = list.maxBy(x => {
+      evaluatedCountOfMaxBy += 1
+      x * 10
+    })
+    assert(evaluatedCountOfMaxBy == list.length, s"maxBy: should evaluate f only ${list.length} times, but it evaluted $evaluatedCountOfMaxBy times.")
+
+    var evaluatedCountOfMinBy = 0
+
+    val min = list.minBy(x => {
+      evaluatedCountOfMinBy += 1
+      x * 10
+    })
+    assert(evaluatedCountOfMinBy == list.length, s"minBy: should evaluate f only ${list.length} times, but it evaluted $evaluatedCountOfMinBy times.")
+  }
+
+}