Refactoring the collections api to support diff...

Refactoring the collections api to support differentiation between
referring to a sequential collection and a parallel collection, and to
support referring to both types of collections.

New set of traits Gen* are now superclasses of both their * and Par* subclasses. For example, GenIterable is a superclass of both Iterable and ParIterable. Iterable and ParIterable are not in a subclassing relation. The new class hierarchy is illustrated below (simplified, not all relations and classes are shown):

TraversableOnce --> GenTraversableOnce
  ^                    ^
  |                    |
Traversable     --> GenTraversable
  ^                    ^
  |                    |
Iterable        --> GenIterable        <-- ParIterable
  ^                    ^                      ^
  |                    |                      |
Seq             --> GenSeq             <-- ParSeq

(the *Like, *View and *ViewLike traits have a similar hierarchy)

General views extract common view functionality from parallel and
sequential collections.

This design also allows for more flexible extensions to the collections
framework. It also allows slowly factoring out common functionality up
into Gen* traits.

From now on, it is possible to write this:

import collection._

val p = parallel.ParSeq(1, 2, 3)
val g: GenSeq[Int] = p // meaning a General Sequence
val s = g.seq // type of s is Seq[Int]

for (elem <- g) {
  // do something without guarantees on sequentiality of foreach
  // this foreach may be executed in parallel
}

for (elem <- s) {
  // do something with a guarantee that foreach is executed in order, sequentially
}

for (elem <- p) {
  // do something concurrently, in parallel
}

This also means that some signatures had to be changed. For example,
method `flatMap` now takes `A => GenTraversableOnce[B]`, and `zip` takes
a `GenIterable[B]`.

Also, there are mutable & immutable Gen* trait variants. They have
generic companion functionality.

1 files changed, 30 insertions, 109 deletions

diff --git a/src/library/scala/collection/TraversableViewLike.scala b/src/library/scala/collection/TraversableViewLike.scala
index b5b18b7a8a..6dc0936c61 100644
--- a/src/library/scala/collection/TraversableViewLike.scala
+++ b/src/library/scala/collection/TraversableViewLike.scala
@@ -59,7 +59,7 @@ trait ViewMkString[+A] {
 trait TraversableViewLike[+A,
                           +Coll,
                           +This <: TraversableView[A, Coll] with TraversableViewLike[A, Coll, This]]
-  extends Traversable[A] with TraversableLike[A, This] with ViewMkString[A]
+  extends Traversable[A] with TraversableLike[A, This] with ViewMkString[A] with GenTraversableViewLike[A, Coll, This]
 {
   self =>
 
@@ -70,7 +70,6 @@ trait TraversableViewLike[+A,
   protected[this] def viewIdentifier: String = ""
   protected[this] def viewIdString: String = ""
   override def stringPrefix = "TraversableView"
-  def viewToString = stringPrefix + viewIdString + "(...)"
 
   def force[B >: A, That](implicit bf: CanBuildFrom[Coll, B, That]) = {
     val b = bf(underlying)
@@ -78,129 +77,36 @@ trait TraversableViewLike[+A,
     b.result()
   }
 
-  /** The implementation base trait of this view.
-   *  This trait and all its subtraits has to be re-implemented for each
-   *  ViewLike class.
-   */
-  trait Transformed[+B] extends TraversableView[B, Coll] {
+  trait Transformed[+B] extends TraversableView[B, Coll] with super.Transformed[B] {
     def foreach[U](f: B => U): Unit
 
-    lazy val underlying = self.underlying
-    final override protected[this] def viewIdString = self.viewIdString + viewIdentifier
     override def stringPrefix = self.stringPrefix
     override def toString = viewToString
   }
-  trait EmptyView extends Transformed[Nothing] {
-    final override def isEmpty = true
-    final override def foreach[U](f: Nothing => U): Unit = ()
-  }
+
+  trait EmptyView extends Transformed[Nothing] with super.EmptyView
 
   /** A fall back which forces everything into a vector and then applies an operation
    *  on it. Used for those operations which do not naturally lend themselves to a view
    */
-  trait Forced[B] extends Transformed[B] {
-    protected[this] val forced: Seq[B]
-    def foreach[U](f: B => U) = forced foreach f
-    final override protected[this] def viewIdentifier = "C"
-  }
+  trait Forced[B] extends Transformed[B] with super.Forced[B]
 
-  trait Sliced extends Transformed[A] {
-    protected[this] val endpoints: SliceInterval
-    protected[this] def from  = endpoints.from
-    protected[this] def until = endpoints.until
-    // protected def newSliced(_endpoints: SliceInterval): Transformed[A] =
-    //   self.newSliced(endpoints.recalculate(_endpoints))
-
-    def foreach[U](f: A => U) {
-      var index = 0
-      for (x <- self) {
-        if (from <= index) {
-          if (until <= index) return
-          f(x)
-        }
-        index += 1
-      }
-    }
-    final override protected[this] def viewIdentifier = "S"
-  }
+  trait Sliced extends Transformed[A] with super.Sliced
 
-  trait Mapped[B] extends Transformed[B] {
-    protected[this] val mapping: A => B
-    def foreach[U](f: B => U) {
-      for (x <- self)
-        f(mapping(x))
-    }
-    final override protected[this] def viewIdentifier = "M"
-  }
+  trait Mapped[B] extends Transformed[B] with super.Mapped[B]
 
-  trait FlatMapped[B] extends Transformed[B] {
-    protected[this] val mapping: A => TraversableOnce[B]
-    def foreach[U](f: B => U) {
-      for (x <- self)
-        for (y <- mapping(x))
-          f(y)
-    }
-    final override protected[this] def viewIdentifier = "N"
-  }
+  trait FlatMapped[B] extends Transformed[B] with super.FlatMapped[B]
 
-  trait Appended[B >: A] extends Transformed[B] {
-    protected[this] val rest: Traversable[B]
-    def foreach[U](f: B => U) {
-      self foreach f
-      rest foreach f
-    }
-    final override protected[this] def viewIdentifier = "A"
-  }
+  trait Appended[B >: A] extends Transformed[B] with super.Appended[B]
 
-  trait Filtered extends Transformed[A] {
-    protected[this] val pred: A => Boolean
-    def foreach[U](f: A => U) {
-      for (x <- self)
-        if (pred(x)) f(x)
-    }
-    final override protected[this] def viewIdentifier = "F"
-  }
+  trait Filtered extends Transformed[A] with super.Filtered
 
-  trait TakenWhile extends Transformed[A] {
-    protected[this] val pred: A => Boolean
-    def foreach[U](f: A => U) {
-      for (x <- self) {
-        if (!pred(x)) return
-        f(x)
-      }
-    }
-    final override protected[this] def viewIdentifier = "T"
-  }
+  trait TakenWhile extends Transformed[A] with super.TakenWhile
 
-  trait DroppedWhile extends Transformed[A] {
-    protected[this] val pred: A => Boolean
-    def foreach[U](f: A => U) {
-      var go = false
-      for (x <- self) {
-        if (!go && !pred(x)) go = true
-        if (go) f(x)
-      }
-    }
-    final override protected[this] def viewIdentifier = "D"
-  }
+  trait DroppedWhile extends Transformed[A] with super.DroppedWhile
 
-  /** Boilerplate method, to override in each subclass
-   *  This method could be eliminated if Scala had virtual classes
-   */
-  protected def newForced[B](xs: => Seq[B]): Transformed[B] = new { val forced = xs } with Forced[B]
-  protected def newAppended[B >: A](that: Traversable[B]): Transformed[B] = new { val rest = that } with Appended[B]
-  protected def newMapped[B](f: A => B): Transformed[B] = new { val mapping = f } with Mapped[B]
-  protected def newFlatMapped[B](f: A => TraversableOnce[B]): Transformed[B] = new { val mapping = f } with FlatMapped[B]
-  protected def newFiltered(p: A => Boolean): Transformed[A] = new { val pred = p } with Filtered
-  protected def newSliced(_endpoints: SliceInterval): Transformed[A] = new { val endpoints = _endpoints } with Sliced
-  protected def newDroppedWhile(p: A => Boolean): Transformed[A] = new { val pred = p } with DroppedWhile
-  protected def newTakenWhile(p: A => Boolean): Transformed[A] = new { val pred = p } with TakenWhile
-
-  protected def newTaken(n: Int): Transformed[A] = newSliced(SliceInterval(0, n))
-  protected def newDropped(n: Int): Transformed[A] = newSliced(SliceInterval(n, Int.MaxValue))
-
-  override def ++[B >: A, That](xs: TraversableOnce[B])(implicit bf: CanBuildFrom[This, B, That]): That = {
-    newAppended(xs.toTraversable).asInstanceOf[That]
+  override def ++[B >: A, That](xs: GenTraversableOnce[B])(implicit bf: CanBuildFrom[This, B, That]): That = {
+    newAppended(xs.seq.toTraversable).asInstanceOf[That]
 // was:    if (bf.isInstanceOf[ByPassCanBuildFrom]) newAppended(that).asInstanceOf[That]
 //         else super.++[B, That](that)(bf)
   }
@@ -215,7 +121,7 @@ trait TraversableViewLike[+A,
   override def collect[B, That](pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[This, B, That]): That =
     filter(pf.isDefinedAt).map(pf)(bf)
 
-  override def flatMap[B, That](f: A => TraversableOnce[B])(implicit bf: CanBuildFrom[This, B, That]): That = {
+  override def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[This, B, That]): That = {
     newFlatMapped(f).asInstanceOf[That]
 // was:    val b = bf(repr)
 //     if (b.isInstanceOf[NoBuilder[_]]) newFlatMapped(f).asInstanceOf[That]
@@ -223,6 +129,21 @@ trait TraversableViewLike[+A,
   }
   private[this] implicit def asThis(xs: Transformed[A]): This = xs.asInstanceOf[This]
 
+  /** Boilerplate method, to override in each subclass
+   *  This method could be eliminated if Scala had virtual classes
+   */
+  protected def newForced[B](xs: => GenSeq[B]): Transformed[B] = new { val forced = xs } with Forced[B]
+  protected def newAppended[B >: A](that: GenTraversable[B]): Transformed[B] = new { val rest = that } with Appended[B]
+  protected def newMapped[B](f: A => B): Transformed[B] = new { val mapping = f } with Mapped[B]
+  protected def newFlatMapped[B](f: A => GenTraversableOnce[B]): Transformed[B] = new { val mapping = f } with FlatMapped[B]
+  protected def newFiltered(p: A => Boolean): Transformed[A] = new { val pred = p } with Filtered
+  protected def newSliced(_endpoints: SliceInterval): Transformed[A] = new { val endpoints = _endpoints } with Sliced
+  protected def newDroppedWhile(p: A => Boolean): Transformed[A] = new { val pred = p } with DroppedWhile
+  protected def newTakenWhile(p: A => Boolean): Transformed[A] = new { val pred = p } with TakenWhile
+
+  protected def newTaken(n: Int): Transformed[A] = newSliced(SliceInterval(0, n))
+  protected def newDropped(n: Int): Transformed[A] = newSliced(SliceInterval(n, Int.MaxValue))
+
   override def filter(p: A => Boolean): This = newFiltered(p)
   override def withFilter(p: A => Boolean): This = newFiltered(p)
   override def partition(p: A => Boolean): (This, This) = (newFiltered(p), newFiltered(!p(_)))