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, 162 insertions, 0 deletions

diff --git a/src/library/scala/collection/GenSeqLike.scala b/src/library/scala/collection/GenSeqLike.scala
new file mode 100644
index 0000000000..74804faff5
--- /dev/null
+++ b/src/library/scala/collection/GenSeqLike.scala
@@ -0,0 +1,162 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2011, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+package scala.collection
+
+
+
+import generic._
+
+
+
+/** A template trait for all sequences which may possibly
+ *  have their operations implemented in parallel.
+ *
+ *  @author Martin Odersky
+ *  @author Aleksandar Prokopec
+ *  @since 2.9
+ */
+trait GenSeqLike[+T, +Repr] extends GenIterableLike[T, Repr] with Equals with Parallelizable[T, parallel.ParSeq[T]] {
+
+  def apply(idx: Int): T
+
+  def length: Int
+
+  def segmentLength(p: T => Boolean, from: Int): Int
+
+  def prefixLength(p: T => Boolean): Int
+
+  def indexWhere(p: T => Boolean, from: Int): Int
+
+  def indexWhere(p: T => Boolean): Int
+
+  def findIndexOf(p: T => Boolean): Int
+
+  def indexOf[U >: T](elem: U): Int
+
+  def indexOf[U >: T](elem: U, from: Int): Int
+
+  def lastIndexWhere(p: T => Boolean, end: Int): Int
+
+  def reverse: Repr
+
+  def reverseMap[S, That](f: T => S)(implicit bf: CanBuildFrom[Repr, S, That]): That
+
+  def startsWith[S](that: GenSeq[S]): Boolean
+
+  def startsWith[S](that: GenSeq[S], offset: Int): Boolean
+
+  def endsWith[S](that: GenSeq[S]): Boolean
+
+  def patch[U >: T, That](from: Int, patch: GenSeq[U], replaced: Int)(implicit bf: CanBuildFrom[Repr, U, That]): That
+
+  def updated[U >: T, That](index: Int, elem: U)(implicit bf: CanBuildFrom[Repr, U, That]): That
+
+  def +:[U >: T, That](elem: U)(implicit bf: CanBuildFrom[Repr, U, That]): That
+
+  def :+[U >: T, That](elem: U)(implicit bf: CanBuildFrom[Repr, U, That]): That
+
+  def padTo[U >: T, That](len: Int, elem: U)(implicit bf: CanBuildFrom[Repr, U, That]): That
+
+  def corresponds[S](that: GenSeq[S])(p: (T, S) => Boolean): Boolean
+
+  def toSeq: GenSeq[T]
+
+
+  /** Produces a new sequence which contains all elements of this $coll and also all elements of
+   *  a given sequence. `xs union ys`  is equivalent to `xs ++ ys`.
+   *  $willNotTerminateInf
+   *
+   *  Another way to express this
+   *  is that `xs union ys` computes the order-presevring multi-set union of `xs` and `ys`.
+   *  `union` is hence a counter-part of `diff` and `intersect` which also work on multi-sets.
+   *
+   *  $willNotTerminateInf
+   *
+   *  @param that   the sequence to add.
+   *  @tparam B     the element type of the returned $coll.
+   *  @tparam That  $thatinfo
+   *  @param bf     $bfinfo
+   *  @return       a new collection of type `That` which contains all elements of this $coll
+   *                followed by all elements of `that`.
+   *  @usecase def union(that: Seq[A]): $Coll[A]
+   *  @return       a new $coll which contains all elements of this $coll
+   *                followed by all elements of `that`.
+   */
+  def union[U >: T, That](that: GenSeq[U])(implicit bf: CanBuildFrom[Repr, U, That]): That = this ++ that
+
+  /** Computes the multiset difference between this $coll and another sequence.
+   *  $willNotTerminateInf
+   *
+   *  @param that   the sequence of elements to remove
+   *  @tparam B     the element type of the returned $coll.
+   *  @tparam That  $thatinfo
+   *  @param bf     $bfinfo
+   *  @return       a new collection of type `That` which contains all elements of this $coll
+   *                except some of occurrences of elements that also appear in `that`.
+   *                If an element value `x` appears
+   *                ''n'' times in `that`, then the first ''n'' occurrences of `x` will not form
+   *                part of the result, but any following occurrences will.
+   *  @usecase def diff(that: Seq[A]): $Coll[A]
+   *  @return       a new $coll which contains all elements of this $coll
+   *                except some of occurrences of elements that also appear in `that`.
+   *                If an element value `x` appears
+   *                ''n'' times in `that`, then the first ''n'' occurrences of `x` will not form
+   *                part of the result, but any following occurrences will.
+   */
+  def diff[U >: T](that: GenSeq[U]): Repr
+
+  /** Computes the multiset intersection between this $coll and another sequence.
+   *  $mayNotTerminateInf
+   *
+   *  @param that   the sequence of elements to intersect with.
+   *  @tparam B     the element type of the returned $coll.
+   *  @tparam That  $thatinfo
+   *  @param bf     $bfinfo
+   *  @return       a new collection of type `That` which contains all elements of this $coll
+   *                which also appear in `that`.
+   *                If an element value `x` appears
+   *                ''n'' times in `that`, then the first ''n'' occurrences of `x` will be retained
+   *                in the result, but any following occurrences will be omitted.
+   *  @usecase def intersect(that: Seq[A]): $Coll[A]
+   *  @return       a new $coll which contains all elements of this $coll
+   *                which also appear in `that`.
+   *                If an element value `x` appears
+   *                ''n'' times in `that`, then the first ''n'' occurrences of `x` will be retained
+   *                in the result, but any following occurrences will be omitted.
+   */
+  def intersect[U >: T](that: GenSeq[U]): Repr
+
+  /** Builds a new $coll from this $coll without any duplicate elements.
+   *  $willNotTerminateInf
+   *
+   *  @return  A new $coll which contains the first occurrence of every element of this $coll.
+   */
+  def distinct: Repr
+
+  /** Hashcodes for $Coll produce a value from the hashcodes of all the
+   *  elements of the $coll.
+   */
+  override def hashCode() = {
+    val h = new util.MurmurHash[T](Seq.hashSeed)
+    seq.foreach(h)
+    h.hash
+  }
+
+  /** The equals method for arbitrary sequences. Compares this sequence to
+   *  some other object.
+   *  @param    that  The object to compare the sequence to
+   *  @return   `true` if `that` is a sequence that has the same elements as
+   *            this sequence in the same order, `false` otherwise
+   */
+  override def equals(that: Any): Boolean = that match {
+    case that: GenSeq[_] => (that canEqual this) && (this sameElements that)
+    case _               => false
+  }
+
+}