Add collection strawman and its tests

This compiles only after the changes in this branch.

3 files changed, 549 insertions, 0 deletions

diff --git a/src/dotty/collections/CollectionStrawMan1.scala b/src/dotty/collections/CollectionStrawMan1.scala
new file mode 100644
index 000000000..211c8d7da
--- /dev/null
+++ b/src/dotty/collections/CollectionStrawMan1.scala
@@ -0,0 +1,330 @@
+package strawman.collections
+
+import Predef.{augmentString => _, wrapString => _, _}
+import scala.reflect.ClassTag
+import collection.mutable.ListBuffer
+
+/** A strawman architecture for new collections. It contains some
+ *  example collection classes and methods with the intent to expose
+ *  some key issues. It would be good to compare this to other
+ *  implementations of the same functionality, to get an idea of the
+ *  strengths and weaknesses of different collection architectures.
+ *
+ *  For a test file, see tests/run/CollectionTests.scala.
+ */
+object CollectionStrawMan1 {
+
+  /* ------------ Base Traits -------------------------------- */
+
+  /** Replaces TraversableOnce */
+  trait CanIterate[+A] {
+    def iterator: Iterator[A]
+  }
+
+  /** Iterator guaranteed to be usable multiple times */
+  trait HasIterator[+A] extends CanIterate[A]
+
+  /** Base trait for instances that can construct a collection from an iterator */
+  trait FromIterator[+C[X] <: Iterable[X]] {
+    def fromIterator[B](it: Iterator[B]): C[B]
+  }
+
+  /** Base trait for companion objects of collections */
+  trait IterableFactory[+C[X] <: Iterable[X]] extends FromIterator[C] {
+    def empty[X]: C[X] = fromIterator(Iterator.empty)
+    def apply[A](xs: A*): C[A] = fromIterator(Iterator(xs: _*))
+  }
+
+  /** Base trait for generic collections */
+  trait Iterable[+IA] extends HasIterator[IA] with FromIterator[Iterable] {
+    def buildIterator: Iterator[IA] = iterator
+  }
+
+  /** Base trait for sequence collections */
+  trait Seq[+AA] extends Iterable[AA] with FromIterator[Seq] {
+    def apply(i: Int): AA
+    def length: Int
+  }
+
+  /* ------------ Operations ----------------------------------- */
+
+  /** Operations returning types unrelated to current collection */
+  trait Ops[A] extends Any {
+    def toIterator: Iterator[A]
+    def foreach(f: A => Unit): Unit = toIterator.foreach(f)
+    def foldLeft[B](z: B)(op: (B, A) => B): B = toIterator.foldLeft(z)(op)
+    def foldRight[B](z: B)(op: (A, B) => B): B = toIterator.foldRight(z)(op)
+    def indexWhere(p: A => Boolean): Int = toIterator.indexWhere(p)
+    def head: A = toIterator.next
+    def view: View[A] = new View(toIterator)
+    def collect[C[X] <: Iterable[X]](fi: FromIterator[C]): C[A] = fi.fromIterator(toIterator)
+  }
+
+  /** Transforms returning same collection type */
+  trait MonoTransforms[A, Repr] extends Any {
+    def toIterator: Iterator[A]
+    def fromIterator(it: => Iterator[A]): Repr
+    def partition(p: A => Boolean): (Repr, Repr) = {
+      val (xs, ys) = toIterator.partition(p)
+      (fromIterator(xs), fromIterator(ys))
+    }
+    def drop(n: Int): Repr = fromIterator(toIterator.drop(n))
+  }
+
+  /** Transforms returning same collection type constructor */
+  trait PolyTransforms[A, C[X]] extends Any {
+    def toIterator: Iterator[A]
+    def fromIterator[B](it: => Iterator[B]): C[B]
+    def map[B](f: A => B): C[B] = fromIterator(toIterator.map(f))
+    def flatMap[B](f: A => CanIterate[B]): C[B] = fromIterator(toIterator.flatMap(f(_)))
+    def ++[B >: A](xs: CanIterate[B]): C[B] = fromIterator(toIterator ++ xs)
+    def zip[B](xs: CanIterate[B]): C[(A, B)] = fromIterator(toIterator.zip(xs.iterator))
+  }
+
+  /** Transforms that only apply to Seq */
+  trait MonoTransformsOfSeqs[A, Repr] extends Any with MonoTransforms[A, Repr] {
+    def reverse: Repr = fromIterator(toIterator.reverse)
+  }
+
+  /** Implementation of Ops for all generic collections */
+  implicit class IterableOps[A](val c: Iterable[A])
+  extends AnyVal with Ops[A] {
+    def toIterator = c.iterator
+  }
+
+  /** Implementation of MonoTransforms for all generic collections */
+  implicit class IterableMonoTransforms[A, C[X] <: Iterable[X]](val c: Iterable[A] with FromIterator[C])
+  extends AnyVal with MonoTransforms[A, C[A]] {
+    def toIterator = c.buildIterator
+    def fromIterator(it: => Iterator[A]): C[A] = c.fromIterator(it)
+  }
+
+  /** Implementation of PolyTransforms for all generic collections */
+  implicit class IterablePolyTransforms[A, C[X] <: Iterable[X]](val c: Iterable[A] with FromIterator[C])
+  extends AnyVal with PolyTransforms[A, C] {
+    def toIterator = c.buildIterator
+    def fromIterator[B](it: => Iterator[B]) = c.fromIterator(it)
+  }
+
+  /** Implementation of MonoTransformsForSeqs for all generic collections */
+  implicit class SeqMonoTransforms[A, C[X] <: Seq[X]](val c: Seq[A] with FromIterator[C])
+  extends AnyVal with MonoTransformsOfSeqs[A, C[A]] {
+    def toIterator = c.buildIterator
+    def fromIterator(it: => Iterator[A]) = c.fromIterator(it)
+  }
+
+  /* --------- Concrete collection types ------------------------------- */
+
+  /** Concrete collection type: List */
+  sealed trait List[+A] extends Seq[A] with FromIterator[List] {
+    def isEmpty: Boolean
+    def head: A
+    def tail: List[A]
+    def iterator = new ListIterator[A](this)
+    def fromIterator[B](it: Iterator[B]): List[B] = List.fromIterator(it)
+    def apply(i: Int): A = {
+      require(!isEmpty)
+      if (i == 0) head else tail.apply(i - 1)
+    }
+    def length: Int =
+      if (isEmpty) 0 else 1 + tail.length
+  }
+
+  case class Cons[+A](x: A, xs: List[A]) extends List[A] {
+    def isEmpty = false
+    def head = x
+    def tail = xs
+  }
+
+  case object List extends IterableFactory[List] {
+    def fromIterator[B](it: Iterator[B]): List[B] = it match {
+      case it: ListIterator[B] => it.toList
+      case _ => if (it.hasNext) Cons(it.next, fromIterator(it)) else Nil
+    }
+  }
+
+  class ListIterator[+A](xs: List[A]) extends Iterator[A] {
+    private[this] var current = xs
+    def hasNext = !current.isEmpty
+    def next = { val r = current.head; current = current.tail; r }
+    def toList = current
+  }
+
+  case object Nil extends List[Nothing] {
+    def isEmpty = true
+    def head = ???
+    def tail = ???
+  }
+
+  /** Concrete collection type: View */
+  class View[+A](it: => Iterator[A]) extends HasIterator[A] {
+    def iterator = it
+  }
+
+  implicit class ViewOps[A](val v: View[A]) extends AnyVal with Ops[A] {
+    def toIterator = v.iterator
+    def cache = collect(List).view
+  }
+
+  implicit class ViewMonoTransforms[A](val v: View[A])
+  extends AnyVal with MonoTransforms[A, View[A]] {
+    def toIterator = v.iterator
+    def fromIterator(it: => Iterator[A]): View[A] = new View(it)
+  }
+
+  implicit class ViewPolyTransforms[A](val v: View[A])
+  extends AnyVal with PolyTransforms[A, View] {
+    def toIterator = v.iterator
+    def fromIterator[B](it: => Iterator[B]) = new View(it)
+  }
+
+  /** Concrete collection type: String */
+  implicit class StringOps(val s: String) extends AnyVal with Ops[Char] {
+    def iterator: Iterator[Char] = new RandomAccessIterator[Char] {
+      def length = s.length
+      def apply(n: Int) = s.charAt(n)
+    }
+    def toIterator = iterator
+  }
+
+  implicit class StringMonoTransforms(val s: String)
+  extends AnyVal with MonoTransformsOfSeqs[Char, String] {
+    def toIterator = s.iterator
+    def fromIterator(it: => Iterator[Char]) = {
+      val sb = new StringBuilder
+      for (ch <- it) sb.append(ch)
+      sb.toString
+    }
+  }
+
+  implicit class StringPolyTransforms(val s: String)
+  extends AnyVal with PolyTransforms[Char, Seq] {
+    def toIterator = s.iterator
+    def fromIterator[B](it: => Iterator[B]) = List.fromIterator(it)
+    def map(f: Char => Char): String = {
+      val sb = new StringBuilder
+      for (ch <- s) sb.append(f(ch))
+      sb.toString
+    }
+    def flatMap(f: Char => String) = {
+      val sb = new StringBuilder
+      for (ch <- s) sb.append(f(ch))
+      sb.toString
+    }
+    def ++(xs: CanIterate[Char]): String = {
+      val sb = new StringBuilder(s)
+      for (ch <- xs.iterator) sb.append(ch)
+      sb.toString
+    }
+    def ++(xs: String): String = s + xs
+  }
+
+/* ---------- Iterators --------------------------------------------------- */
+
+  /** A core Iterator class */
+  trait Iterator[+A] extends CanIterate[A] { self =>
+    def hasNext: Boolean
+    def next: A
+    def iterator = this
+    def foldLeft[B](z: B)(op: (B, A) => B): B =
+      if (hasNext) foldLeft(op(z, next))(op) else z
+    def foldRight[B](z: B)(op: (A, B) => B): B =
+      if (hasNext) op(next, foldRight(z)(op)) else z
+    def foreach(f: A => Unit): Unit =
+      while (hasNext) f(next)
+    def indexWhere(p: A => Boolean): Int = {
+      var i = 0
+      while (hasNext) {
+        if (p(next)) return i
+        i += 1
+      }
+      -1
+    }
+    def map[B](f: A => B): Iterator[B] = new Iterator[B] {
+      def hasNext = self.hasNext
+      def next = f(self.next)
+    }
+    def flatMap[B](f: A => CanIterate[B]): Iterator[B] = new Iterator[B] {
+      private var myCurrent: Iterator[B] = Iterator.empty
+      private def current = {
+        while (!myCurrent.hasNext && self.hasNext) myCurrent = f(self.next).iterator
+        myCurrent
+      }
+      def hasNext = current.hasNext
+      def next = current.next
+    }
+    def ++[B >: A](xs: CanIterate[B]): Iterator[B] = new Iterator[B] {
+      private var myCurrent: Iterator[B] = self
+      private def current = {
+        if (!myCurrent.hasNext && myCurrent.eq(self)) myCurrent = xs.iterator
+        myCurrent
+      }
+      def hasNext = current.hasNext
+      def next = current.next
+    }
+    def partition(p: A => Boolean): (Iterator[A], Iterator[A]) = {
+      val lookaheadTrue, lookaheadFalse = new ListBuffer[A]
+      class PartIterator[+A](buf: ListBuffer[A]) extends Iterator[A] {
+        final def hasNext: Boolean =
+          buf.nonEmpty ||
+            self.hasNext && {
+              val elem = self.next
+              (if (p(elem)) lookaheadTrue else lookaheadFalse) += elem
+              hasNext
+            }
+        final def next =
+          if (hasNext) {
+            val r = buf.head
+            buf.trimStart(1)
+            r
+          }
+          else Iterator.nextOnEmpty
+      }
+      (new PartIterator(lookaheadTrue), new PartIterator(lookaheadFalse))
+    }
+    def drop(n: Int): Iterator[A] = {
+      if (n <= 0) this
+      else {
+        next
+        drop(n - 1)
+      }
+    }
+    def zip[B](that: CanIterate[B]): Iterator[(A, B)] = new Iterator[(A, B)] {
+      val ti = that.iterator
+      def hasNext = self.hasNext && ti.hasNext
+      def next = (self.next, ti.next)
+    }
+    def reverse: Iterator[A] = {
+      var elems: List[A] = Nil
+      while (hasNext) elems = Cons(next, elems)
+      elems.iterator
+    }
+  }
+
+  object Iterator {
+    val empty: Iterator[Nothing] = new Iterator[Nothing] {
+      def hasNext = false
+      def next = ???
+    }
+    def apply[A](xs: A*): Iterator[A] = new RandomAccessIterator[A] {
+      def length = xs.length
+      def apply(n: Int) = xs(n)
+    }
+    def nextOnEmpty = throw new NoSuchElementException("next on empty iterator")
+  }
+
+  trait RandomAccessIterator[+A] extends Iterator[A] { self =>
+    def apply(n: Int): A
+    def length: Int
+    protected val len = length
+    private var cur = 0
+    def hasNext = cur < len
+    def next: A = { val r = this(cur); cur += 1; r }
+    override def drop(n: Int): Iterator[A] = { cur += (n max 0); this }
+    override def reverse = new RandomAccessIterator[A] {
+      def length = self.length
+      def apply(n: Int) = apply(len - 1 - n)
+    }
+  }
+}
+
diff --git a/tests/run/CollectionTests.check b/tests/run/CollectionTests.check
new file mode 100644
index 000000000..3afe62813
--- /dev/null
+++ b/tests/run/CollectionTests.check
@@ -0,0 +1,51 @@
+-------
+123
+123
+1
+1
+Cons(1,Cons(2,Cons(3,Nil)))
+Cons(2,Nil)
+Cons(1,Cons(3,Nil))
+Cons(3,Nil)
+Cons(true,Cons(true,Cons(true,Nil)))
+Cons(1,Cons(-1,Cons(2,Cons(-2,Cons(3,Cons(-3,Nil))))))
+Cons(1,Cons(2,Cons(3,Cons(1,Cons(2,Cons(3,Nil))))))
+Cons(1,Cons(2,Cons(3,Nil)))
+Cons(1,Cons(2,Cons(3,Nil)))
+Cons(1,Cons(2,Cons(3,Cons(a,Nil))))
+Cons((1,true),Cons((2,true),Cons((3,true),Nil)))
+Cons(3,Cons(2,Cons(1,Nil)))
+-------
+123
+123
+1
+1
+Cons(1,Cons(2,Cons(3,Nil)))
+Cons(2,Nil)
+Cons(1,Cons(3,Nil))
+Cons(3,Nil)
+Cons(true,Cons(true,Cons(true,Nil)))
+Cons(1,Cons(-1,Cons(2,Cons(-2,Cons(3,Cons(-3,Nil))))))
+Cons(1,Cons(2,Cons(3,Cons(1,Cons(2,Cons(3,Nil))))))
+Cons(1,Cons(2,Cons(3,Nil)))
+Cons(1,Cons(2,Cons(3,Nil)))
+Cons(1,Cons(2,Cons(3,Cons(a,Nil))))
+Cons((1,true),Cons((2,true),Cons((3,true),Nil)))
+-------
+abc
+abc
+1
+a
+Cons(a,Cons(b,Cons(c,Nil)))
+b
+ac
+c
+Cons(98,Cons(99,Cons(100,Nil)))
+ABC
+a,ab,bc,c
+abcabc
+abcxy
+abc
+Cons(a,Cons(b,Cons(c,Nil)))
+Cons(a,Cons(b,Cons(c,Cons(xyz,Nil))))
+Cons((a,98),Cons((b,99),Cons((c,100),Nil)))
diff --git a/tests/run/CollectionTests.scala b/tests/run/CollectionTests.scala
new file mode 100644
index 000000000..46cb63544
--- /dev/null
+++ b/tests/run/CollectionTests.scala
@@ -0,0 +1,168 @@
+import Predef.{augmentString => _, wrapString => _, _}
+import scala.reflect.ClassTag
+
+object Test {
+  import strawman.collections._
+  import CollectionStrawMan1._
+
+  def seqOps(xs: Seq[Int]) = {
+    val x1 = xs.foldLeft("")(_ + _)
+    val y1: String = x1
+    val x2 = xs.foldRight("")(_ + _)
+    val y2: String = x2
+    val x3 = xs.indexWhere(_ % 2 == 0)
+    val y3: Int = x3
+    val x4 = xs.head
+    val y4: Int = x4
+    val x5 = xs.collect(List)
+    val y5: List[Int] = x5
+    val (xs6, xs7) = xs.partition(_ % 2 == 0)
+    val ys6: Seq[Int] = xs6
+    val ys7: Seq[Int] = xs7
+    val xs8 = xs.drop(2)
+    val ys8: Seq[Int] = xs8
+    val xs9 = xs.map(_ >= 0)
+    val ys9: Seq[Boolean] = xs9
+    val xs10 = xs.flatMap(x => Cons(x, Cons(-x, Nil)))
+    val ys10: Seq[Int] = xs10
+    val xs11 = xs ++ xs
+    val ys11: Seq[Int] = xs11
+    val xs12 = xs ++ Nil
+    val ys12: Seq[Int] = xs12
+    val xs13 = Nil ++ xs
+    val ys13: Seq[Int] = xs13
+    val xs14 = xs ++ Cons("a", Nil)
+    val ys14: Seq[Any] = xs14
+    val xs15 = xs.zip(xs9)
+    val ys15: Seq[(Int, Boolean)] = xs15
+    val xs16 = xs.reverse
+    val ys16: Seq[Int] = xs16
+    println("-------")
+    println(x1)
+    println(x2)
+    println(x3)
+    println(x4)
+    println(x5)
+    println(xs6)
+    println(xs7)
+    println(xs8)
+    println(xs9)
+    println(xs10)
+    println(xs11)
+    println(xs12)
+    println(xs13)
+    println(xs14)
+    println(xs15)
+    println(xs16)
+  }
+
+  def viewOps(xs: View[Int]) = {
+    val x1 = xs.foldLeft("")(_ + _)
+    val y1: String = x1
+    val x2 = xs.foldRight("")(_ + _)
+    val y2: String = x2
+    val x3 = xs.indexWhere(_ % 2 == 0)
+    val y3: Int = x3
+    val x4 = xs.head
+    val y4: Int = x4
+    val x5 = xs.collect(List)
+    val y5: List[Int] = x5
+    val (xs6, xs7) = xs.partition(_ % 2 == 0)
+    val ys6: View[Int] = xs6
+    val ys7: View[Int] = xs7
+    val xs8 = xs.drop(2)
+    val ys8: View[Int] = xs8
+    val xs9 = xs.map(_ >= 0)
+    val ys9: View[Boolean] = xs9
+    val xs10 = xs.flatMap(x => Cons(x, Cons(-x, Nil)))
+    val ys10: View[Int] = xs10
+    val xs11 = xs ++ xs
+    val ys11: View[Int] = xs11
+    val xs12 = xs ++ Nil
+    val ys12: View[Int] = xs12
+    val xs13 = Nil ++ xs
+    val ys13: List[Int] = xs13
+    val xs14 = xs ++ Cons("a", Nil)
+    val ys14: View[Any] = xs14
+    val xs15 = xs.zip(xs9)
+    val ys15: View[(Int, Boolean)] = xs15
+    println("-------")
+    println(x1)
+    println(x2)
+    println(x3)
+    println(x4)
+    println(x5)
+    println(xs6.collect(List))
+    println(xs7.collect(List))
+    println(xs8.collect(List))
+    println(xs9.collect(List))
+    println(xs10.collect(List))
+    println(xs11.collect(List))
+    println(xs12.collect(List))
+    println(xs13.collect(List))
+    println(xs14.collect(List))
+    println(xs15.collect(List))
+  }
+
+  def stringOps(xs: String) = {
+    val x1 = xs.foldLeft("")(_ + _)
+    val y1: String = x1
+    val x2 = xs.foldRight("")(_ + _)
+    val y2: String = x2
+    val x3 = xs.indexWhere(_ % 2 == 0)
+    val y3: Int = x3
+    val x4 = xs.head
+    val y4: Int = x4
+    val x5 = xs.collect(List)
+    val y5: List[Char] = x5
+    val (xs6, xs7) = xs.partition(_ % 2 == 0)
+    val ys6: String = xs6
+    val ys7: String = xs7
+    val xs8 = xs.drop(2)
+    val ys8: String = xs8
+    val xs9 = xs.map((_: Char) + 1)  // !!! need a language change to make this work without the : Char
+    val ys9: Seq[Int] = xs9
+    val xs9a = xs.map((_: Char).toUpper) // !!! need a language change to make this work without the : Char
+    val ys9a: String = xs9a
+    val xs10 = xs.flatMap((x: Char) => s"$x,$x")
+    val ys10: String = xs10
+    val xs11 = xs ++ xs
+    val ys11: String = xs11
+    val xs11a = xs ++ List('x', 'y')
+    val ys11a: String = xs11a
+    val xs12 = xs ++ Nil
+    val ys12: String = xs12
+    val xs13 = Nil ++ xs.iterator
+    val ys13: List[Char] = xs13
+    val xs14 = xs ++ Cons("xyz", Nil)
+    val ys14: Seq[Any] = xs14
+    val xs15 = xs.zip(xs9)
+    val ys15: Seq[(Char, Int)] = xs15
+    println("-------")
+    println(x1)
+    println(x2)
+    println(x3)
+    println(x4)
+    println(x5)
+    println(xs6)
+    println(xs7)
+    println(xs8)
+    println(xs9)
+    println(xs9a)
+    println(xs10)
+    println(xs11)
+    println(xs11a)
+    println(xs12)
+    println(xs13)
+    println(xs14)
+    println(xs15)
+  }
+
+  def main(args: Array[String]) = {
+    val ints = Cons(1, Cons(2, Cons(3, Nil)))
+    val intsView = ints.view
+    seqOps(ints)
+    viewOps(intsView)
+    stringOps("abc")
+  }
+}