A selection of collections additions from the l...

A selection of collections additions from the lower end of the
controversy scale.

// TraversableOnce
def collectFirst[B](pf: PartialFunction[A, B]): Option[B]
def maxBy[B](f: A => B)(implicit cmp: Ordering[B]): A
def minBy[B](f: A => B)(implicit cmp: Ordering[B]): A

// Iterator
def span(p: A => Boolean): (Iterator[A], Iterator[A])

// Traversable
def inits: Iterator[Repr]
def tails: Iterator[Repr]
def unzip3[A1, A2, A3](implicit asTriple: A => (A1, A2, A3)): (CC[A1], CC[A2], CC[A3])

// Sequences
def permutations: Iterator[Repr]

Review by odersky.

10 files changed, 156 insertions, 76 deletions

diff --git a/src/library/scala/collection/BufferedIterator.scala b/src/library/scala/collection/BufferedIterator.scala
index ab56d9377f..f599abc018 100644
--- a/src/library/scala/collection/BufferedIterator.scala
+++ b/src/library/scala/collection/BufferedIterator.scala
@@ -10,7 +10,7 @@
 
 package scala.collection
 
-/** Buffered iterators are iterators which provide a method <code>head</code>
+/** Buffered iterators are iterators which provide a method `head`
  *  that inspects the next element without discarding it.
  *
  *  @author  Martin Odersky
diff --git a/src/library/scala/collection/IndexedSeqOptimized.scala b/src/library/scala/collection/IndexedSeqOptimized.scala
index 6360de33f1..218ca55dc6 100755
--- a/src/library/scala/collection/IndexedSeqOptimized.scala
+++ b/src/library/scala/collection/IndexedSeqOptimized.scala
@@ -45,19 +45,7 @@ trait IndexedSeqOptimized[+A, +Repr] extends IndexedSeqLike[A, Repr] { self =>
     val i = prefixLength(!p(_))
     if (i < length) Some(this(i)) else None
   }
-/*
-  override /*IterableLike*/
-  def mapFind[B](f: A => Option[B]): Option[B] = {
-    var i = 0
-    var res: Option[B] = None
-    val len = length
-    while (res.isEmpty && i < len) {
-      res = f(this(i))
-      i += 1
-    }
-    res
-  }
-*/
+
   @tailrec
   private def foldl[B](start: Int, end: Int, z: B, op: (B, A) => B): B =
     if (start == end) z
diff --git a/src/library/scala/collection/IterableLike.scala b/src/library/scala/collection/IterableLike.scala
index 72dabbf740..00c2275ab5 100644
--- a/src/library/scala/collection/IterableLike.scala
+++ b/src/library/scala/collection/IterableLike.scala
@@ -84,10 +84,6 @@ self =>
     iterator.exists(p)
   override /*TraversableLike*/ def find(p: A => Boolean): Option[A] =
     iterator.find(p)
-/*
-  override /*TraversableLike*/ def mapFind[B](f: A => Option[B]): Option[B] =
-    iterator.mapFind(f)
-*/
   override /*TraversableLike*/ def isEmpty: Boolean =
     !iterator.hasNext
   override /*TraversableLike*/ def foldRight[B](z: B)(op: (A, B) => B): B =
diff --git a/src/library/scala/collection/Iterator.scala b/src/library/scala/collection/Iterator.scala
index 31ab2a0eb4..40f8bc7f81 100644
--- a/src/library/scala/collection/Iterator.scala
+++ b/src/library/scala/collection/Iterator.scala
@@ -461,7 +461,7 @@ trait Iterator[+A] extends TraversableOnce[A] {
     val self = buffered
     class PartitionIterator(p: A => Boolean) extends Iterator[A] {
       var other: PartitionIterator = _
-      val lookahead = new scala.collection.mutable.Queue[A]
+      val lookahead = new mutable.Queue[A]
       def skip() =
         while (self.hasNext && !p(self.head)) {
           other.lookahead += self.next
@@ -477,6 +477,48 @@ trait Iterator[+A] extends TraversableOnce[A] {
     (l, r)
   }
 
+  /** Splits this Iterator into a prefix/suffix pair according to a predicate.
+   *
+   *  @param p the test predicate
+   *  @return  a pair of Iterators consisting of the longest prefix of this
+   *           whose elements all satisfy `p`, and the rest of the Iterator.
+   */
+  def span(p: A => Boolean): (Iterator[A], Iterator[A]) = {
+    val self = buffered
+    val leading = new Iterator[A] {
+      private var isDone = false
+      val lookahead = new mutable.Queue[A]
+      def advance() = {
+        self.hasNext && p(self.head) && {
+          lookahead += self.next
+          true
+        }
+      }
+      def finish() = {
+        while (advance()) ()
+        isDone = true
+      }
+      def hasNext = lookahead.nonEmpty || advance()
+      def next() = {
+        if (lookahead.isEmpty)
+          advance()
+
+        lookahead.dequeue()
+      }
+    }
+    val trailing = new Iterator[A] {
+      private lazy val it = {
+        leading.finish()
+        self
+      }
+      def hasNext = it.hasNext
+      def next() = it.next()
+      override def toString = "unknown-if-empty iterator"
+    }
+
+    (leading, trailing)
+  }
+
   /** Skips longest sequence of elements of this iterator which satisfy given
    *  predicate `p`, and returns an iterator of the remaining elements.
    *
@@ -642,21 +684,6 @@ trait Iterator[+A] extends TraversableOnce[A] {
     res
   }
 
-  /** Applies option-valued function to successive elements of this iterator
-   *  until a defined value is found.
-   *
-   *  @param f    the function to be applied to successive elements.
-   *  @return     an option value containing the first defined result of
-   *              `f`, or `None` if `f` returns `None` for all all elements.
-  def mapFind[B](f: A => Option[B]): Option[B] = {
-    var res: Option[B] = None
-    while (res.isEmpty && hasNext) {
-      res = f(next())
-    }
-    res
-  }
-   */
-
   /** Returns the index of the first produced value satisfying a predicate, or -1.
    *  $mayNotTerminateInf
    *  @param  p the predicate to test values
diff --git a/src/library/scala/collection/LinearSeqOptimized.scala b/src/library/scala/collection/LinearSeqOptimized.scala
index abe8e2fa62..c3dd161a65 100755
--- a/src/library/scala/collection/LinearSeqOptimized.scala
+++ b/src/library/scala/collection/LinearSeqOptimized.scala
@@ -104,17 +104,7 @@ trait LinearSeqOptimized[+A, +Repr <: LinearSeqOptimized[A, Repr]] extends Linea
     }
     None
   }
-/*
-  override def mapFind[B](f: A => Option[B]): Option[B] = {
-    var res: Option[B] = None
-    var these = this
-    while (res.isEmpty && !these.isEmpty) {
-      res = f(these.head)
-      these = these.tail
-    }
-    res
-  }
-*/
+
   override /*TraversableLike*/
   def foldLeft[B](z: B)(f: (B, A) => B): B = {
     var acc = z
diff --git a/src/library/scala/collection/SeqLike.scala b/src/library/scala/collection/SeqLike.scala
index d90807437b..6d849cadc9 100644
--- a/src/library/scala/collection/SeqLike.scala
+++ b/src/library/scala/collection/SeqLike.scala
@@ -367,6 +367,25 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self =>
     i
   }
 
+  /** Iterates over distinct permutations.
+   *
+   *  @return   An Iterator which traverses the distinct permutations of this $coll.
+   *  @example  `"abb".permutations = Iterator(abb, bab, bba)`
+   */
+  def permutations: Iterator[Repr] = {
+    val seen = mutable.HashSet[A]()
+    val xs = thisCollection.toIndexedSeq
+
+    if (xs.isEmpty) Iterator.empty
+    else if (xs.tail.isEmpty) Iterator(repr)
+    else xs.indices collect {
+      case idx if !seen(xs(idx))  =>
+        seen += xs(idx)
+        val rest = (xs take idx) ++ (xs drop (idx + 1))
+        rest.permutations map (newBuilder += xs(idx) ++= _ result)
+    } reduceLeft (_ ++ _)
+  }
+
   /** Returns new $coll wih elements in reversed order.
    *
    *  $willNotTerminateInf
diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala
index 116db7dc7d..9c6b4531d4 100644
--- a/src/library/scala/collection/TraversableLike.scala
+++ b/src/library/scala/collection/TraversableLike.scala
@@ -9,11 +9,11 @@
 
 
 package scala.collection
-import generic._
 
-import scala.reflect.ClassManifest
-import mutable.{Builder, StringBuilder, Buffer, ArrayBuffer, ListBuffer}
-import immutable.{List, Stream, Nil, ::}
+import generic._
+import mutable.{ Builder, ListBuffer }
+import annotation.tailrec
+import annotation.unchecked.{ uncheckedVariance => uV }
 
 /** A template trait for traversable collections of type `Traversable[A]`.
  *  $traversableInfo
@@ -428,28 +428,6 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr]
     result
   }
 
-  /** Applies option-valued function to successive elements of this $coll
-   *  until a defined value is found.
-   *
-   *  $mayNotTerminateInf
-   *  $orderDependent
-   *
-   *  @param f    the function to be applied to successive elements.
-   *  @return     an option value containing the first defined result of
-   *              `f`, or `None` if `f` returns `None` for all all elements.
-  def mapFind[B](f: A => Option[B]): Option[B] = {
-    var result: Option[B] = None
-    breakable {
-      for (x <- this)
-        f(x) match {
-          case s @ Some(_) => result = s; break
-          case _ =>
-        }
-    }
-    result
-  }
-   */
-
   /**
    * Produces a collection containing cummulative results of applying the operator going left to right.
    * $willNotTerminateInf
@@ -699,6 +677,24 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr]
     (l.result, r.result)
   }
 
+  /** Iterates over the tails of this $coll. The first value will be this
+   *  $coll and the final one will be an empty $coll, with the intervening
+   *  values the results of successive applications of `tail`.
+   *
+   *  @return   an iterator over all the tails of this $coll
+   *  @example  `List(1,2,3).tails = Iterator(List(1,2,3), List(2,3), List(3), Nil)`
+   */
+  def tails: Iterator[Repr] = iterateUntilEmpty(_.tail)
+
+  /** Iterates over the inits of this $coll. The first value will be this
+   *  $coll and the final one will be an empty $coll, with the intervening
+   *  values the results of successive applications of `init`.
+   *
+   *  @return  an iterator over all the inits of this $coll
+   *  @example  `List(1,2,3).inits = Iterator(List(1,2,3), List(1,2), List(1), Nil)`
+   */
+  def inits: Iterator[Repr] = iterateUntilEmpty(_.init)
+
   /** Copies elements of this $coll to an array.
    *  Fills the given array `xs` with at most `len` elements of
    *  this $coll, starting at position `start`.
@@ -868,4 +864,10 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr]
     def withFilter(q: A => Boolean): WithFilter =
       new WithFilter(x => p(x) && q(x))
   }
+
+  // A helper for tails and inits.
+  private def iterateUntilEmpty(f: Traversable[A @uV] => Traversable[A @uV]): Iterator[Repr] = {
+    val it = Iterator.iterate(thisCollection)(f) takeWhile (x => !x.isEmpty)
+    it ++ Iterator(Nil) map (newBuilder ++= _ result)
+  }
 }
diff --git a/src/library/scala/collection/TraversableOnce.scala b/src/library/scala/collection/TraversableOnce.scala
index 179051553e..4836f2666c 100644
--- a/src/library/scala/collection/TraversableOnce.scala
+++ b/src/library/scala/collection/TraversableOnce.scala
@@ -9,6 +9,7 @@
 package scala.collection
 
 import mutable.{ Buffer, ListBuffer, ArrayBuffer }
+import annotation.unchecked.{ uncheckedVariance => uV }
 
 /** A template trait for collections which can be traversed either once only
  *  or one or more times.
@@ -88,7 +89,6 @@ trait TraversableOnce[+A] {
   def exists(p: A => Boolean): Boolean
   def find(p: A => Boolean): Option[A]
   def copyToArray[B >: A](xs: Array[B], start: Int, len: Int): Unit
-  // def mapFind[B](f: A => Option[B]): Option[B]
 
   // for internal use
   protected[this] def reversed = {
@@ -128,6 +128,25 @@ trait TraversableOnce[+A] {
     cnt
   }
 
+  /** Finds the first element of the $coll for which the given partial
+   *  function is defined, and applies the partial function to it.
+   *
+   *  $mayNotTerminateInf
+   *  $orderDependent
+   *
+   *  @param pf   the partial function
+   *  @return     an option value containing pf applied to the first
+   *              value for which it is defined, or `None` if none exists.
+   *  @example   `Seq("a", 1, 5L).collectFirst({ case x: Int => x*10 }) = Some(10)`
+   */
+  def collectFirst[B](pf: PartialFunction[A, B]): Option[B] = {
+    for (x <- self.toIterator) {
+      if (pf isDefinedAt x)
+        return Some(pf(x))
+    }
+    None
+  }
+
   /** Applies a binary operator to a start value and all elements of this $coll,
    *  going left to right.
    *
@@ -350,6 +369,19 @@ trait TraversableOnce[+A] {
     reduceLeft((x, y) => if (cmp.gteq(x, y)) x else y)
   }
 
+  def maxBy[B](f: A => B)(implicit cmp: Ordering[B]): A = {
+    if (isEmpty)
+      throw new UnsupportedOperationException("empty.maxBy")
+
+    reduceLeft((x, y) => if (cmp.gteq(f(x), f(y))) x else y)
+  }
+  def minBy[B](f: A => B)(implicit cmp: Ordering[B]): A = {
+    if (isEmpty)
+      throw new UnsupportedOperationException("empty.maxBy")
+
+    reduceLeft((x, y) => if (cmp.lteq(f(x), f(y))) x else y)
+  }
+
   /** Copies all elements of this $coll to a buffer.
    *  $willNotTerminateInf
    *  @param  dest   The buffer to which elements are copied.
@@ -628,8 +660,8 @@ object TraversableOnce {
   class TraversableOnceMonadOps[+A](trav: TraversableOnce[A]) {
     def map[B](f: A => B): TraversableOnce[B] = trav.toIterator map f
     def flatMap[B](f: A => TraversableOnce[B]): TraversableOnce[B] = trav.toIterator flatMap f
-    def filter(p: A => Boolean): TraversableOnce[A] = trav.toIterator filter p
-    def withFilter(p: A => Boolean) = filter(p)
+    def withFilter(p: A => Boolean) = trav.toIterator filter p
+    def filter(p: A => Boolean): TraversableOnce[A] = withFilter(p)
   }
 }
 
diff --git a/src/library/scala/collection/generic/GenericTraversableTemplate.scala b/src/library/scala/collection/generic/GenericTraversableTemplate.scala
index 5e72bdeaa7..01221da200 100644
--- a/src/library/scala/collection/generic/GenericTraversableTemplate.scala
+++ b/src/library/scala/collection/generic/GenericTraversableTemplate.scala
@@ -76,7 +76,7 @@ trait GenericTraversableTemplate[+A, +CC[X] <: Traversable[X]] extends HasNewBui
    *  @return       a pair ${coll}s, containing the first, respectively second
    *                half of each element pair of this $coll.
    */
-  def unzip[A1, A2](implicit asPair: A => /*<:<!!!*/ (A1, A2)): (CC[A1], CC[A2]) = {
+  def unzip[A1, A2](implicit asPair: A => (A1, A2)): (CC[A1], CC[A2]) = {
     val b1 = genericBuilder[A1]
     val b2 = genericBuilder[A2]
     for (xy <- this) {
@@ -87,6 +87,31 @@ trait GenericTraversableTemplate[+A, +CC[X] <: Traversable[X]] extends HasNewBui
     (b1.result, b2.result)
   }
 
+  /** Converts this $coll of triples into three collections of the first, second,
+   *  and third element of each triple.
+   *
+   *  @param A1     the type of the first member of the element triples
+   *  @param A2     the type of the second member of the element triples
+   *  @param A3     the type of the third member of the element triples
+   *  @param asPair an implicit conversion which asserts that the element type
+   *                of this $coll is a triple.
+   *  @return       a triple ${coll}s, containing the first, second, respectively
+   *                third member of each element triple of this $coll.
+   */
+  def unzip3[A1, A2, A3](implicit asTriple: A => (A1, A2, A3)): (CC[A1], CC[A2], CC[A3]) = {
+    val b1 = genericBuilder[A1]
+    val b2 = genericBuilder[A2]
+    val b3 = genericBuilder[A3]
+
+    for (xyz <- this) {
+      val (x, y, z) = asTriple(xyz)
+      b1 += x
+      b2 += y
+      b3 += z
+    }
+    (b1.result, b2.result, b3.result)
+  }
+
   /** Converts this $coll of traversable collections into
    *  a $coll in which all element collections are concatenated.
    *
@@ -130,4 +155,3 @@ trait GenericTraversableTemplate[+A, +CC[X] <: Traversable[X]] extends HasNewBui
   }
 }
 
-
diff --git a/src/library/scala/package.scala b/src/library/scala/package.scala
index a6b974b4d3..839ce4c5ea 100644
--- a/src/library/scala/package.scala
+++ b/src/library/scala/package.scala
@@ -87,6 +87,8 @@ package object scala {
   val BigInt = scala.math.BigInt
 
   type Equiv[T] = scala.math.Equiv[T]
+  val Equiv = scala.math.Equiv
+
   type Fractional[T] = scala.math.Fractional[T]
   type Integral[T] = scala.math.Integral[T]