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.

1 files changed, 26 insertions, 0 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