diff options
Diffstat (limited to 'compiler/src/strawman/collections')
4 files changed, 2513 insertions, 0 deletions
diff --git a/compiler/src/strawman/collections/CollectionStrawMan1.scala b/compiler/src/strawman/collections/CollectionStrawMan1.scala new file mode 100644 index 000000000..c127757ad --- /dev/null +++ b/compiler/src/strawman/collections/CollectionStrawMan1.scala @@ -0,0 +1,405 @@ +package strawman.collections + +import Predef.{augmentString => _, wrapString => _, _} +import scala.reflect.ClassTag + +/** 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] + } + + /** 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[+A] extends CanIterate[A] with FromIterator[Iterable] + + /** Base trait for sequence collections */ + trait Seq[+A] extends Iterable[A] with FromIterator[Seq] { + def apply(i: Int): A + def length: Int + } + + /* ------------ Operations ----------------------------------- */ + + /** Operations returning types unrelated to current collection */ + trait Ops[A] extends Any { + def iterator: Iterator[A] + def foreach(f: A => Unit): Unit = iterator.foreach(f) + def foldLeft[B](z: B)(op: (B, A) => B): B = iterator.foldLeft(z)(op) + def foldRight[B](z: B)(op: (A, B) => B): B = iterator.foldRight(z)(op) + def indexWhere(p: A => Boolean): Int = iterator.indexWhere(p) + def isEmpty: Boolean = !iterator.hasNext + def head: A = iterator.next + def view: View[A] = new View(iterator) + def to[C[X] <: Iterable[X]](fi: FromIterator[C]): C[A] = fi.fromIterator(iterator) + } + + /** Transforms returning same collection type */ + trait MonoTransforms[A, Repr] extends Any { + protected def iter: Iterator[A] + protected def fromIter(it: => Iterator[A]): Repr + def partition(p: A => Boolean): (Repr, Repr) = { + val (xs, ys) = iter.partition(p) + (fromIter(xs), fromIter(ys)) + } + def drop(n: Int): Repr = fromIter(iter.drop(n)) + } + + /** Transforms returning same collection type constructor */ + trait PolyTransforms[A, C[X]] extends Any { + protected def iter: Iterator[A] + protected def fromIter[B](it: => Iterator[B]): C[B] + def map[B](f: A => B): C[B] = fromIter(iter.map(f)) + def flatMap[B](f: A => CanIterate[B]): C[B] = fromIter(iter.flatMap(f(_))) + def ++[B >: A](xs: CanIterate[B]): C[B] = fromIter(iter ++ xs) + def zip[B](xs: CanIterate[B]): C[(A, B)] = fromIter(iter.zip(xs.iterator)) + } + + /** Transforms that only apply to Seq */ + trait MonoTransformsOfSeqs[A, Repr] extends Any with MonoTransforms[A, Repr] { + def reverse: Repr = fromIter(iter.reverse) + } + + /** Implementation of Ops for all generic collections */ + implicit class IterableOps[A](val c: Iterable[A]) + extends AnyVal with Ops[A] { + def iterator = 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]] { + protected def iter = c.iterator + protected def fromIter(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] { + protected def iter = c.iterator + protected def fromIter[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]] { + protected def iter = c.iterator + protected def fromIter(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 Nil extends List[Nothing] { + def isEmpty = true + def head = ??? + def tail = ??? + } + + 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 + } + + /** Concrete collection type: ArrayBuffer */ + class ArrayBuffer[A] private (initElems: Array[AnyRef], initLength: Int) extends Seq[A] with FromIterator[ArrayBuffer] { + def this() = this(new Array[AnyRef](16), 0) + private var elems: Array[AnyRef] = initElems + private var start = 0 + private var limit = initLength + def apply(i: Int) = elems(start + i).asInstanceOf[A] + def length = limit - start + def iterator = new ArrayBufferIterator[A](elems, start, length) + def fromIterator[B](it: Iterator[B]): ArrayBuffer[B] = + ArrayBuffer.fromIterator(it) + def +=(elem: A): this.type = { + if (limit == elems.length) { + if (start > 0) { + Array.copy(elems, start, elems, 0, length) + limit -= start + start = 0 + } + else { + val newelems = new Array[AnyRef](limit * 2) + Array.copy(elems, 0, newelems, 0, limit) + elems = newelems + } + } + elems(limit) = elem.asInstanceOf[AnyRef] + limit += 1 + this + } + def trimStart(n: Int): Unit = start += (n max 0) + override def toString = s"ArrayBuffer(${elems.slice(start, limit).mkString(", ")})" + } + + object ArrayBuffer extends IterableFactory[ArrayBuffer] { + def fromIterator[B](it: Iterator[B]): ArrayBuffer[B] = it match { + case Iterator.Concat(fst: ArrayBufferIterator[_], snd: ArrayBufferIterator[_]) => + val elems = new Array[AnyRef](fst.remaining + snd.remaining) + Array.copy(fst.elems, fst.start, elems, 0, fst.remaining) + Array.copy(snd.elems, snd.start, elems, fst.remaining, snd.remaining) + new ArrayBuffer(elems, elems.length) + case it @ Iterator.Partition(underlying, _, buf, _) => + while (underlying.hasNext) it.distribute() + buf.asInstanceOf[ArrayBuffer[B]] + case it if it.remaining >= 0 => + val elems = new Array[AnyRef](it.remaining) + for (i <- 0 until elems.length) elems(i) = it.next.asInstanceOf[AnyRef] + new ArrayBuffer[B](elems, elems.length) + case _ => + val buf = new ArrayBuffer[B] + while (it.hasNext) buf += it.next + buf + } + } + + class ArrayBufferIterator[A](val elems: Array[AnyRef], initStart: Int, length: Int) extends RandomAccessIterator[A] { + val limit = length + def apply(n: Int) = elems(initStart + n).asInstanceOf[A] + } + + /** Concrete collection type: View */ + class View[+A](it: => Iterator[A]) extends CanIterate[A] { + def iterator = it + } + + implicit class ViewOps[A](val v: View[A]) extends AnyVal with Ops[A] { + def iterator = v.iterator + def cache = to(ArrayBuffer).view + } + + implicit class ViewMonoTransforms[A](val v: View[A]) + extends AnyVal with MonoTransforms[A, View[A]] { + protected def iter = v.iterator + protected def fromIter(it: => Iterator[A]): View[A] = new View(it) + } + + implicit class ViewPolyTransforms[A](val v: View[A]) + extends AnyVal with PolyTransforms[A, View] { + protected def iter = v.iterator + protected def fromIter[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] { + override val limit = s.length + def apply(n: Int) = s.charAt(n) + } + } + + implicit class StringMonoTransforms(val s: String) + extends AnyVal with MonoTransformsOfSeqs[Char, String] { + protected def iter = StringOps(s).iterator + protected def fromIter(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] { + protected def iter = StringOps(s).iterator + protected def fromIter[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] = Iterator.Map(this, f) + def flatMap[B](f: A => CanIterate[B]): Iterator[B] = Iterator.FlatMap(this, f) + def ++[B >: A](xs: CanIterate[B]): Iterator[B] = Iterator.Concat(this, xs.iterator) + def partition(p: A => Boolean): (Iterator[A], Iterator[A]) = { + val lookaheadTrue, lookaheadFalse = new ArrayBuffer[A] + (Iterator.Partition(this, p, lookaheadTrue, lookaheadFalse), + Iterator.Partition[A](this, !p(_), lookaheadFalse, lookaheadTrue)) + } + def drop(n: Int): Iterator[A] = Iterator.Drop(this, n) + def zip[B](that: CanIterate[B]): Iterator[(A, B)] = Iterator.Zip(this, that.iterator) + def reverse: Iterator[A] = { + var elems: List[A] = Nil + while (hasNext) elems = Cons(next, elems) + elems.iterator + } + + /** If this iterator results from applying a transfomation to another iterator, + * that other iterator, otherwise the iterator itself. + */ + def underlying: Iterator[_] = this + + /** If the number of elements still to be returned by this iterator is known, + * that number, otherwise -1. + */ + def remaining = -1 + } + + object Iterator { + val empty: Iterator[Nothing] = new Iterator[Nothing] { + def hasNext = false + def next = ??? + override def remaining = 0 + } + def apply[A](xs: A*): Iterator[A] = new RandomAccessIterator[A] { + override val limit = xs.length + def apply(n: Int) = xs(n) + } + def nextOnEmpty = throw new NoSuchElementException("next on empty iterator") + + case class Map[A, B](override val underlying: Iterator[A], f: A => B) extends Iterator[B] { + def hasNext = underlying.hasNext + def next = f(underlying.next) + override def remaining = underlying.remaining + } + case class FlatMap[A, B](override val underlying: Iterator[A], f: A => CanIterate[B]) extends Iterator[B] { + private var myCurrent: Iterator[B] = Iterator.empty + private def current = { + while (!myCurrent.hasNext && underlying.hasNext) + myCurrent = f(underlying.next).iterator + myCurrent + } + def hasNext = current.hasNext + def next = current.next + } + case class Concat[A](override val underlying: Iterator[A], other: Iterator[A]) extends Iterator[A] { + private var myCurrent = underlying + private def current = { + if (!myCurrent.hasNext && myCurrent.eq(underlying)) myCurrent = other + myCurrent + } + def hasNext = current.hasNext + def next = current.next + override def remaining = + if (underlying.remaining >= 0 && other.remaining >= 0) + underlying.remaining + other.remaining + else -1 + } + case class Partition[A](override val underlying: Iterator[A], p: A => Boolean, lookahead: ArrayBuffer[A], dual: ArrayBuffer[A]) extends Iterator[A] { + def distribute() = { + val elem = underlying.next + (if (p(elem)) lookahead else dual) += elem + } + final def hasNext: Boolean = + !lookahead.isEmpty || underlying.hasNext && { distribute(); hasNext } + final def next = + if (hasNext) { + val r = lookahead.head + lookahead.trimStart(1) + r + } else Iterator.nextOnEmpty + } + case class Drop[A](override val underlying: Iterator[A], n: Int) extends Iterator[A] { + var toSkip = n + def hasNext: Boolean = underlying.hasNext && ( + toSkip == 0 || { underlying.next; toSkip -= 1; hasNext }) + def next = if (hasNext) underlying.next else nextOnEmpty + override def remaining = (underlying.remaining - toSkip) max -1 + } + case class Zip[A, B](override val underlying: Iterator[A], other: Iterator[B]) extends Iterator[(A, B)] { + def hasNext = underlying.hasNext && other.hasNext + def next = (underlying.next, other.next) + override def remaining = underlying.remaining min other.remaining + } + case class Reverse[A](override val underlying: RandomAccessIterator[A]) extends RandomAccessIterator[A] { + def apply(n: Int) = underlying.apply(underlying.limit - 1 - n) + def limit = underlying.remaining + } + } + + trait RandomAccessIterator[+A] extends Iterator[A] { self => + def apply(n: Int): A + def limit: Int + var start = 0 + override def remaining = (limit - start) max 0 + def hasNext = start < limit + def next: A = { val r = this(start); start += 1; r } + override def drop(n: Int): Iterator[A] = { start += (n max 0); this } + override def reverse: Iterator[A] = new Iterator.Reverse(this) + } +} + diff --git a/compiler/src/strawman/collections/CollectionStrawMan4.scala b/compiler/src/strawman/collections/CollectionStrawMan4.scala new file mode 100644 index 000000000..7e8de2c82 --- /dev/null +++ b/compiler/src/strawman/collections/CollectionStrawMan4.scala @@ -0,0 +1,541 @@ +package strawman.collections + +import Predef.{augmentString => _, wrapString => _, _} +import scala.reflect.ClassTag +import annotation.unchecked.uncheckedVariance +import annotation.tailrec + +/** 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. + * + * Strawman4 is like strawman1, but built over views instead of by-name iterators + */ +object CollectionStrawMan4 { + + /* ------------ Base Traits -------------------------------- */ + + /** Iterator can be used only once */ + trait IterableOnce[+A] { + def iterator: Iterator[A] + } + + /** Base trait for instances that can construct a collection from an iterable */ + trait FromIterable[+C[X] <: Iterable[X]] { + def fromIterable[B](v: Iterable[B]): C[B] + } + + /** Base trait for companion objects of collections */ + trait IterableFactory[+C[X] <: Iterable[X]] extends FromIterable[C] { + def empty[X]: C[X] = fromIterable(View.Empty) + def apply[A](xs: A*): C[A] = fromIterable(View.Elems(xs: _*)) + } + + /** Base trait for generic collections */ + trait Iterable[+A] extends IterableOnce[A] with FromIterable[Iterable] { + def view: View[A] = View.fromIterator(iterator) // view is overridden, cannot be defined in ops + def knownLength: Int = -1 + } + + /** Base trait for sequence collections */ + trait Seq[+A] extends Iterable[A] with FromIterable[Seq] { + def apply(i: Int): A + def length: Int + } + + /** Base trait for collection builders */ + trait Builder[-A, +To] { + def +=(x: A): this.type + def result: To + + def ++=(xs: IterableOnce[A]): this.type = { + xs.iterator.foreach(+=) + this + } + } + + /* ------------ Operations ----------------------------------- */ + + /** Operations returning types unrelated to current collection */ + trait Ops[A] extends Any { + def iterator: Iterator[A] + def foreach(f: A => Unit): Unit = iterator.foreach(f) + def foldLeft[B](z: B)(op: (B, A) => B): B = iterator.foldLeft(z)(op) + def foldRight[B](z: B)(op: (A, B) => B): B = iterator.foldRight(z)(op) + def indexWhere(p: A => Boolean): Int = iterator.indexWhere(p) + def isEmpty: Boolean = !iterator.hasNext + def head: A = iterator.next + } + + /** Transforms returning same collection type */ + trait MonoTransforms[A, Repr] extends Any { + protected def coll: Iterable[A] + protected def fromIterable(it: Iterable[A]): Repr + def filter(p: A => Boolean): Repr = fromIterable(View.Filter(coll, p)) + def partition(p: A => Boolean): (Repr, Repr) = { + val pn = View.Partition(coll, p) + (fromIterable(pn.left), fromIterable(pn.right)) + } + def drop(n: Int): Repr = fromIterable(View.Drop(coll, n)) + def to[C[X] <: Iterable[X]](fv: FromIterable[C]): C[A] = fv.fromIterable(coll) + } + + trait PolyTransforms[A, C[X]] extends Any { + protected def coll: Iterable[A] + protected def fromIterable[B](it: Iterable[B]): C[B] + def map[B](f: A => B): C[B] = fromIterable(View.Map(coll, f)) + def flatMap[B](f: A => IterableOnce[B]): C[B] = fromIterable(View.FlatMap(coll, f)) + def ++[B >: A](xs: IterableOnce[B]): C[B] = fromIterable(View.Concat(coll, xs)) + def zip[B](xs: IterableOnce[B]): C[(A, B)] = fromIterable(View.Zip(coll, xs)) + } + + /** Transforms that only apply to Seq */ + trait MonoTransformsOfSeqs[A, Repr] extends Any with MonoTransforms[A, Repr] { + def reverse: Repr = fromIterable(View.Reverse(coll)) + } + + /** Implementation of Ops for all generic collections */ + implicit class IterableOps[A](val c: Iterable[A]) + extends AnyVal with Ops[A] { + def iterator = c.iterator + } + + /** Implementation of MonoTransforms for all generic collections */ + implicit class IterableMonoTransforms[A, C[X] <: Iterable[X]](val c: Iterable[A] with FromIterable[C]) + extends AnyVal with MonoTransforms[A, C[A]] { + protected def coll = c + protected def fromIterable(it: Iterable[A]): C[A] = c.fromIterable(it) + } + + /** Implementation of PolyTransforms for all generic collections */ + implicit class IterablePolyTransforms[A, C[X] <: Iterable[X]](val c: Iterable[A] with FromIterable[C]) + extends AnyVal with PolyTransforms[A, C] { + protected def coll = c + protected def fromIterable[B](it: Iterable[B]): C[B] = c.fromIterable(it) + } + + /** Implementation of MonoTransformsForSeqs for all generic collections */ + implicit class SeqMonoTransforms[A, C[X] <: Seq[X]](val c: Seq[A] with FromIterable[C]) + extends AnyVal with MonoTransformsOfSeqs[A, C[A]] { + protected def coll = c + protected def fromIterable(it: Iterable[A]): C[A] = c.fromIterable(it) + } + + /* --------- Concrete collection types ------------------------------- */ + + /** Concrete collection type: List */ + sealed trait List[+A] extends Seq[A] with FromIterable[List] { self => + def isEmpty: Boolean + def head: A + def tail: List[A] + def iterator = new Iterator[A] { + private[this] var current = self + def hasNext = !current.isEmpty + def next = { val r = current.head; current = current.tail; r } + } + def fromIterable[B](c: Iterable[B]): List[B] = List.fromIterable(c) + 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 + def ++:[B >: A](prefix: List[B]): List[B] = + if (prefix.isEmpty) this + else Cons(prefix.head, prefix.tail ++: this) + } + + case class Cons[+A](x: A, private[collections] var next: List[A @uncheckedVariance]) // sound because `next` is used only locally + extends List[A] { + def isEmpty = false + def head = x + def tail = next + } + + case object Nil extends List[Nothing] { + def isEmpty = true + def head = ??? + def tail = ??? + } + + object List extends IterableFactory[List] { + def fromIterator[B](it: Iterator[B]): List[B] = + if (it.hasNext) Cons(it.next, fromIterator(it)) else Nil + def fromIterable[B](c: Iterable[B]): List[B] = c match { + case View.Concat(xs, ys: List[B]) => + fromIterable(xs) ++: ys + case View.Drop(xs: List[B], n) => + @tailrec def loop(xs: List[B], n: Int): List[B] = + if (n > 0) loop(xs.tail, n - 1) else xs + loop(xs, n) + case c: List[B] => c + case _ => fromIterator(c.iterator) + } + } + + /** Concrete collection type: ListBuffer */ + class ListBuffer[A] extends Seq[A] with FromIterable[ListBuffer] with Builder[A, List[A]] { + private var first, last: List[A] = Nil + private var aliased = false + def iterator = first.iterator + def fromIterable[B](coll: Iterable[B]) = ListBuffer.fromIterable(coll) + def apply(i: Int) = first.apply(i) + def length = first.length + + private def copyElems(): Unit = { + val buf = ListBuffer.fromIterable(result) + first = buf.first + last = buf.last + aliased = false + } + def result = { + aliased = true + first + } + def +=(elem: A) = { + if (aliased) copyElems() + val last1 = Cons(elem, Nil) + last match { + case last: Cons[A] => last.next = last1 + case _ => first = last1 + } + last = last1 + this + } + override def toString: String = + if (first.isEmpty) "ListBuffer()" + else { + val b = new StringBuilder("ListBuffer(").append(first.head) + first.tail.foldLeft(b)(_.append(", ").append(_)).append(")").toString + } + } + + object ListBuffer extends IterableFactory[ListBuffer] { + def fromIterable[B](coll: Iterable[B]): ListBuffer[B] = coll match { + case pd @ View.Partitioned(partition: View.Partition[B] @unchecked) => + partition.distribute(new ListBuffer[B]()) + new ListBuffer[B] ++= pd.forced.get + case _ => + new ListBuffer[B] ++= coll + } + } + + /** Concrete collection type: ArrayBuffer */ + class ArrayBuffer[A] private (initElems: Array[AnyRef], initLength: Int) + extends Seq[A] with FromIterable[ArrayBuffer] with Builder[A, ArrayBuffer[A]] { + def this() = this(new Array[AnyRef](16), 0) + private var elems: Array[AnyRef] = initElems + private var start = 0 + private var end = initLength + def apply(n: Int) = elems(start + n).asInstanceOf[A] + def length = end - start + override def knownLength = length + override def view = new ArrayBufferView(elems, start, end) + def iterator = view.iterator + def fromIterable[B](it: Iterable[B]): ArrayBuffer[B] = + ArrayBuffer.fromIterable(it) + def +=(elem: A): this.type = { + if (end == elems.length) { + if (start > 0) { + Array.copy(elems, start, elems, 0, length) + end -= start + start = 0 + } + else { + val newelems = new Array[AnyRef](end * 2) + Array.copy(elems, 0, newelems, 0, end) + elems = newelems + } + } + elems(end) = elem.asInstanceOf[AnyRef] + end += 1 + this + } + def result = this + def trimStart(n: Int): Unit = start += (n max 0) + override def toString = s"ArrayBuffer(${elems.slice(start, end).mkString(", ")})" + } + + object ArrayBuffer extends IterableFactory[ArrayBuffer] { + def fromIterable[B](c: Iterable[B]): ArrayBuffer[B] = c match { + case View.Concat(fst: ArrayBuffer[B], snd: ArrayBuffer[B]) => + val elems = new Array[AnyRef](fst.length + snd.length) + Array.copy(fst.elems, fst.start, elems, 0, fst.length) + Array.copy(snd.elems, snd.start, elems, fst.length, snd.length) + new ArrayBuffer(elems, elems.length) + case pd @ View.Partitioned(partition: View.Partition[B] @unchecked) => + partition.distribute(new ArrayBuffer[B]()) + pd.forced.get.asInstanceOf[ArrayBuffer[B]] + case c if c.knownLength >= 0 => + val elems = new Array[AnyRef](c.knownLength) + val it = c.iterator + for (i <- 0 until elems.length) elems(i) = it.next().asInstanceOf[AnyRef] + new ArrayBuffer[B](elems, elems.length) + case _ => + val buf = new ArrayBuffer[B] + val it = c.iterator + while (it.hasNext) buf += it.next() + buf + } + } + + class ArrayBufferView[A](val elems: Array[AnyRef], val start: Int, val end: Int) extends RandomAccessView[A] { + def apply(n: Int) = elems(start + n).asInstanceOf[A] + } + + /** Concrete collection type: String */ + implicit class StringOps(val s: String) extends AnyVal with Ops[Char] { + def iterator: Iterator[Char] = new StringView(s).iterator + } + + implicit class StringMonoTransforms(val s: String) + extends AnyVal with MonoTransformsOfSeqs[Char, String] { + protected def coll: Iterable[Char] = StringView(s) + protected def fromIterable(it: Iterable[Char]): String = { + val sb = new StringBuilder + for (ch <- it) sb.append(ch) + sb.toString + } + } + + implicit class StringPolyTransforms(val s: String) + extends AnyVal with PolyTransforms[Char, Seq] { + protected def coll = StringView(s) + protected def fromIterable[B](it: Iterable[B]): Seq[B] = List.fromIterable(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: IterableOnce[Char]): String = { + val sb = new StringBuilder(s) + for (ch <- xs.iterator) sb.append(ch) + sb.toString + } + def ++(xs: String): String = s + xs + } + + case class StringView(s: String) extends RandomAccessView[Char] { + val start = 0 + val end = s.length + def apply(n: Int) = s.charAt(n) + } + + /* ------------ Views --------------------------------------- */ + + /** A lazy iterable */ + trait View[+A] extends Iterable[A] with FromIterable[View] { + override def view = this + override def fromIterable[B](c: Iterable[B]) = c match { + case c: View[B] => c + case _ => View.fromIterator(c.iterator) + } + } + + /** Iterator defined in terms of indexing a range */ + trait RandomAccessView[+A] extends View[A] { + def start: Int + def end: Int + def apply(i: Int): A + def iterator: Iterator[A] = new Iterator[A] { + private var current = start + def hasNext = current < end + def next: A = { + val r = apply(current) + current += 1 + r + } + } + override def knownLength = end - start max 0 + } + + object View { + def fromIterator[A](it: => Iterator[A]): View[A] = new View[A] { + def iterator = it + } + case object Empty extends View[Nothing] { + def iterator = Iterator.empty + override def knownLength = 0 + } + case class Elems[A](xs: A*) extends View[A] { + def iterator = Iterator(xs: _*) + override def knownLength = xs.length + } + case class Filter[A](val underlying: Iterable[A], p: A => Boolean) extends View[A] { + def iterator = underlying.iterator.filter(p) + } + case class Partition[A](val underlying: Iterable[A], p: A => Boolean) { + val left, right = Partitioned(this) + // `distribute` makes up for the lack of generic push-based functionality. + // It forces both halves of the partition with a given builder. + def distribute(bf: => Builder[A, Iterable[A]]) = { + val lb, rb = bf + val it = underlying.iterator + while (it.hasNext) { + val x = it.next() + (if (p(x)) lb else rb) += x + } + left.forced = Some(lb.result) + right.forced = Some(rb.result) + } + } + case class Partitioned[A](partition: Partition[A]) extends View[A] { + private var myForced: Option[Iterable[A]] = None + def forced: Option[Iterable[A]] = myForced + private[View] def forced_=(x: Option[Iterable[A]]): Unit = myForced = x + def underlying = partition.underlying + def iterator = forced match { + case Some(c) => c.iterator + case None => + underlying.iterator.filter( + if (this eq partition.left) partition.p else !partition.p(_)) + } + } + case class Drop[A](underlying: Iterable[A], n: Int) extends View[A] { + def iterator = underlying.iterator.drop(n) + override def knownLength = + if (underlying.knownLength >= 0) underlying.knownLength - n max 0 else -1 + } + case class Map[A, B](underlying: Iterable[A], f: A => B) extends View[B] { + def iterator = underlying.iterator.map(f) + override def knownLength = underlying.knownLength + } + case class FlatMap[A, B](underlying: Iterable[A], f: A => IterableOnce[B]) extends View[B] { + def iterator = underlying.iterator.flatMap(f) + } + case class Concat[A](underlying: Iterable[A], other: IterableOnce[A]) extends View[A] { + def iterator = underlying.iterator ++ other + override def knownLength = other match { + case other: Iterable[_] if underlying.knownLength >= 0 && other.knownLength >= 0 => + underlying.knownLength + other.knownLength + case _ => + -1 + } + } + case class Zip[A, B](underlying: Iterable[A], other: IterableOnce[B]) extends View[(A, B)] { + def iterator = underlying.iterator.zip(other) + override def knownLength = other match { + case other: Iterable[_] if underlying.knownLength >= 0 && other.knownLength >= 0 => + underlying.knownLength min other.knownLength + case _ => + -1 + } + } + case class Reverse[A](underlying: Iterable[A]) extends View[A] { + def iterator = { + var xs: List[A] = Nil + val it = underlying.iterator + while (it.hasNext) xs = Cons(it.next(), xs) + xs.iterator + } + override def knownLength = underlying.knownLength + } + } + +/* ---------- Iterators ---------------------------------------------------*/ + + /** A core Iterator class */ + trait Iterator[+A] extends IterableOnce[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 filter(p: A => Boolean): Iterator[A] = new Iterator[A] { + private var hd: A = _ + private var hdDefined: Boolean = false + + def hasNext: Boolean = hdDefined || { + do { + if (!self.hasNext) return false + hd = self.next() + } while (!p(hd)) + hdDefined = true + true + } + + def next() = + if (hasNext) { + hdDefined = false + hd + } + else Iterator.empty.next() + } + + 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 => IterableOnce[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: IterableOnce[B]): Iterator[B] = new Iterator[B] { + private var myCurrent: Iterator[B] = self + private var first = true + private def current = { + if (!myCurrent.hasNext && first) { + myCurrent = xs.iterator + first = false + } + myCurrent + } + def hasNext = current.hasNext + def next() = current.next() + } + def drop(n: Int): Iterator[A] = { + var i = 0 + while (i < n && hasNext) { + next() + i += 1 + } + this + } + def zip[B](that: IterableOnce[B]): Iterator[(A, B)] = new Iterator[(A, B)] { + val thatIterator = that.iterator + def hasNext = self.hasNext && thatIterator.hasNext + def next() = (self.next(), thatIterator.next()) + } + } + + object Iterator { + val empty: Iterator[Nothing] = new Iterator[Nothing] { + def hasNext = false + def next = throw new NoSuchElementException("next on empty iterator") + } + def apply[A](xs: A*): Iterator[A] = new RandomAccessView[A] { + val start = 0 + val end = xs.length + def apply(n: Int) = xs(n) + }.iterator + } +} + diff --git a/compiler/src/strawman/collections/CollectionStrawMan5.scala b/compiler/src/strawman/collections/CollectionStrawMan5.scala new file mode 100644 index 000000000..5d04c2c98 --- /dev/null +++ b/compiler/src/strawman/collections/CollectionStrawMan5.scala @@ -0,0 +1,522 @@ +package strawman.collections + +import Predef.{augmentString => _, wrapString => _, _} +import scala.reflect.ClassTag +import annotation.unchecked.uncheckedVariance +import annotation.tailrec + +/** 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. + * + * Strawman5 is like strawman4, but using inheritance through ...Like traits + * instead of decorators. + * + * Advantage: Much easier to specialize. See partition for strict (buildable) collections + * or drop for Lists. + * + * Disadvantage: More "weird" types in base traits; some awkwardness with + * @uncheckedVariance. + */ +object CollectionStrawMan5 { + + /* ------------ Base Traits -------------------------------- */ + + /** Iterator can be used only once */ + trait IterableOnce[+A] { + def iterator: Iterator[A] + } + + /** Base trait for instances that can construct a collection from an iterable */ + trait FromIterable[+C[X] <: Iterable[X]] { + def fromIterable[B](it: Iterable[B]): C[B] + } + + /** Base trait for companion objects of collections */ + trait IterableFactory[+C[X] <: Iterable[X]] extends FromIterable[C] { + def empty[X]: C[X] = fromIterable(View.Empty) + def apply[A](xs: A*): C[A] = fromIterable(View.Elems(xs: _*)) + } + + /** Base trait for generic collections */ + trait Iterable[+A] extends IterableOnce[A] with IterableLike[A, Iterable] { + protected def coll: Iterable[A] = this + def knownLength: Int = -1 + } + + /** Base trait for sequence collections */ + trait Seq[+A] extends Iterable[A] with SeqLike[A, Seq] { + def apply(i: Int): A + def length: Int + } + + /** Base trait for strict collections */ + trait Buildable[+A, +To <: Iterable[A]] extends Iterable[A] { + protected[this] def newBuilder: Builder[A, To] + override def partition(p: A => Boolean): (To, To) = { + val l, r = newBuilder + iterator.foreach(x => (if (p(x)) l else r) += x) + (l.result, r.result) + } + // one might also override other transforms here to avoid generating + // iterators if it helps efficiency. + } + + /** Base trait for collection builders */ + trait Builder[-A, +To] { + def +=(x: A): this.type + def result: To + + def ++=(xs: IterableOnce[A]): this.type = { + xs.iterator.foreach(+=) + this + } + } + + /* ------------ Operations ----------------------------------- */ + + /** Base trait for Iterable operations + * + * VarianceNote + * ============ + * + * We require that for all child classes of Iterable the variance of + * the child class and the variance of the `C` parameter passed to `IterableLike` + * are the same. We cannot express this since we lack variance polymorphism. That's + * why we have to resort at some places to write `C[A @uncheckedVariance]`. + * + */ + trait IterableLike[+A, +C[X] <: Iterable[X]] + extends FromIterable[C] + with IterableOps[A] + with IterableMonoTransforms[A, C[A @uncheckedVariance]] // sound bcs of VarianceNote + with IterablePolyTransforms[A, C] { + protected[this] def fromLikeIterable(coll: Iterable[A]): C[A] = fromIterable(coll) + } + + /** Base trait for Seq operations */ + trait SeqLike[+A, +C[X] <: Seq[X]] + extends IterableLike[A, C] with SeqMonoTransforms[A, C[A @uncheckedVariance]] // sound bcs of VarianceNote + + trait IterableOps[+A] extends Any { + def iterator: Iterator[A] + def foreach(f: A => Unit): Unit = iterator.foreach(f) + def foldLeft[B](z: B)(op: (B, A) => B): B = iterator.foldLeft(z)(op) + def foldRight[B](z: B)(op: (A, B) => B): B = iterator.foldRight(z)(op) + def indexWhere(p: A => Boolean): Int = iterator.indexWhere(p) + def isEmpty: Boolean = !iterator.hasNext + def head: A = iterator.next + def view: View[A] = View.fromIterator(iterator) + } + + trait IterableMonoTransforms[+A, +Repr] extends Any { + protected def coll: Iterable[A] + protected[this] def fromLikeIterable(coll: Iterable[A]): Repr + def filter(p: A => Boolean): Repr = fromLikeIterable(View.Filter(coll, p)) + def partition(p: A => Boolean): (Repr, Repr) = { + val pn = View.Partition(coll, p) + (fromLikeIterable(pn.left), fromLikeIterable(pn.right)) + } + def drop(n: Int): Repr = fromLikeIterable(View.Drop(coll, n)) + def to[C[X] <: Iterable[X]](fi: FromIterable[C]): C[A @uncheckedVariance] = + // variance seems sound because `to` could just as well have been added + // as a decorator. We should investigate this further to be sure. + fi.fromIterable(coll) + } + + trait IterablePolyTransforms[+A, +C[A]] extends Any { + protected def coll: Iterable[A] + def fromIterable[B](coll: Iterable[B]): C[B] + def map[B](f: A => B): C[B] = fromIterable(View.Map(coll, f)) + def flatMap[B](f: A => IterableOnce[B]): C[B] = fromIterable(View.FlatMap(coll, f)) + def ++[B >: A](xs: IterableOnce[B]): C[B] = fromIterable(View.Concat(coll, xs)) + def zip[B](xs: IterableOnce[B]): C[(A @uncheckedVariance, B)] = fromIterable(View.Zip(coll, xs)) + // sound bcs of VarianceNote + } + + trait SeqMonoTransforms[+A, +Repr] extends Any with IterableMonoTransforms[A, Repr] { + def reverse: Repr = { + var xs: List[A] = Nil + var it = coll.iterator + while (it.hasNext) xs = new Cons(it.next, xs) + fromLikeIterable(xs) + } + } + + /* --------- Concrete collection types ------------------------------- */ + + /** Concrete collection type: List */ + sealed trait List[+A] extends Seq[A] with SeqLike[A, List] with Buildable[A, List[A]] { self => + def isEmpty: Boolean + def head: A + def tail: List[A] + def iterator = new Iterator[A] { + private[this] var current = self + def hasNext = !current.isEmpty + def next = { val r = current.head; current = current.tail; r } + } + def fromIterable[B](c: Iterable[B]): List[B] = List.fromIterable(c) + 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 + protected[this] def newBuilder = new ListBuffer[A] + def ++:[B >: A](prefix: List[B]): List[B] = + if (prefix.isEmpty) this + else Cons(prefix.head, prefix.tail ++: this) + override def ++[B >: A](xs: IterableOnce[B]): List[B] = xs match { + case xs: List[B] => this ++: xs + case _ => super.++(xs) + } + @tailrec final override def drop(n: Int) = + if (n > 0) tail.drop(n - 1) else this + } + + case class Cons[+A](x: A, private[collections] var next: List[A @uncheckedVariance]) // sound because `next` is used only locally + extends List[A] { + override def isEmpty = false + override def head = x + def tail = next + } + + case object Nil extends List[Nothing] { + override def isEmpty = true + override def head = ??? + def tail = ??? + } + + object List extends IterableFactory[List] { + def fromIterable[B](coll: Iterable[B]): List[B] = coll match { + case coll: List[B] => coll + case _ => ListBuffer.fromIterable(coll).result + } + } + + /** Concrete collection type: ListBuffer */ + class ListBuffer[A] extends Seq[A] with SeqLike[A, ListBuffer] with Builder[A, List[A]] { + private var first, last: List[A] = Nil + private var aliased = false + def iterator = first.iterator + def fromIterable[B](coll: Iterable[B]) = ListBuffer.fromIterable(coll) + def apply(i: Int) = first.apply(i) + def length = first.length + + private def copyElems(): Unit = { + val buf = ListBuffer.fromIterable(result) + first = buf.first + last = buf.last + aliased = false + } + def result = { + aliased = true + first + } + def +=(elem: A) = { + if (aliased) copyElems() + val last1 = Cons(elem, Nil) + last match { + case last: Cons[A] => last.next = last1 + case _ => first = last1 + } + last = last1 + this + } + override def toString: String = + if (first.isEmpty) "ListBuffer()" + else { + val b = new StringBuilder("ListBuffer(").append(first.head) + first.tail.foldLeft(b)(_.append(", ").append(_)).append(")").toString + } + } + + object ListBuffer extends IterableFactory[ListBuffer] { + def fromIterable[B](coll: Iterable[B]): ListBuffer[B] = new ListBuffer[B] ++= coll + } + + /** Concrete collection type: ArrayBuffer */ + class ArrayBuffer[A] private (initElems: Array[AnyRef], initLength: Int) + extends Seq[A] with SeqLike[A, ArrayBuffer] with Builder[A, ArrayBuffer[A]] { + def this() = this(new Array[AnyRef](16), 0) + private var elems: Array[AnyRef] = initElems + private var start = 0 + private var end = initLength + def apply(n: Int) = elems(start + n).asInstanceOf[A] + def length = end - start + override def knownLength = length + override def view = new ArrayBufferView(elems, start, end) + def iterator = view.iterator + def fromIterable[B](it: Iterable[B]): ArrayBuffer[B] = + ArrayBuffer.fromIterable(it) + def +=(elem: A): this.type = { + if (end == elems.length) { + if (start > 0) { + Array.copy(elems, start, elems, 0, length) + end -= start + start = 0 + } + else { + val newelems = new Array[AnyRef](end * 2) + Array.copy(elems, 0, newelems, 0, end) + elems = newelems + } + } + elems(end) = elem.asInstanceOf[AnyRef] + end += 1 + this + } + def result = this + def trimStart(n: Int): Unit = start += (n max 0) + override def ++[B >: A](xs: IterableOnce[B]): ArrayBuffer[B] = xs match { + case xs: ArrayBuffer[B] => + val elems = new Array[AnyRef](length + xs.length) + Array.copy(this.elems, this.start, elems, 0, this.length) + Array.copy(xs.elems, xs.start, elems, this.length, xs.length) + new ArrayBuffer(elems, elems.length) + case _ => super.++(xs) + } + + override def toString = s"ArrayBuffer(${elems.slice(start, end).mkString(", ")})" + } + + object ArrayBuffer extends IterableFactory[ArrayBuffer] { + def fromIterable[B](coll: Iterable[B]): ArrayBuffer[B] = + if (coll.knownLength >= 0) { + val elems = new Array[AnyRef](coll.knownLength) + val it = coll.iterator + for (i <- 0 until elems.length) elems(i) = it.next().asInstanceOf[AnyRef] + new ArrayBuffer[B](elems, elems.length) + } + else { + val buf = new ArrayBuffer[B] + val it = coll.iterator + while (it.hasNext) buf += it.next() + buf + } + } + + class ArrayBufferView[A](val elems: Array[AnyRef], val start: Int, val end: Int) extends RandomAccessView[A] { + def apply(n: Int) = elems(start + n).asInstanceOf[A] + } + + /** Concrete collection type: String */ + implicit class StringOps(val s: String) + extends AnyVal with IterableOps[Char] + with SeqMonoTransforms[Char, String] + with IterablePolyTransforms[Char, List] { + protected def coll = new StringView(s) + def iterator = coll.iterator + protected def fromLikeIterable(coll: Iterable[Char]): String = { + val sb = new StringBuilder + for (ch <- coll) sb.append(ch) + sb.toString + } + def fromIterable[B](coll: Iterable[B]): List[B] = List.fromIterable(coll) + def map(f: Char => Char): String = { + val sb = new StringBuilder + for (ch <- s) sb.append(f(ch)) + sb.toString + } + def flatMap(f: Char => String): String = { + val sb = new StringBuilder + for (ch <- s) sb.append(f(ch)) + sb.toString + } + def ++(xs: IterableOnce[Char]): String = { + val sb = new StringBuilder(s) + for (ch <- xs.iterator) sb.append(ch) + sb.toString + } + def ++(xs: String): String = s + xs + } + + case class StringView(s: String) extends RandomAccessView[Char] { + val start = 0 + val end = s.length + def apply(n: Int) = s.charAt(n) + } + +/* ---------- Views -------------------------------------------------------*/ + + /** Concrete collection type: View */ + trait View[+A] extends Iterable[A] with IterableLike[A, View] { + override def view = this + override def fromIterable[B](c: Iterable[B]): View[B] = c match { + case c: View[B] => c + case _ => View.fromIterator(c.iterator) + } + } + + /** View defined in terms of indexing a range */ + trait RandomAccessView[+A] extends View[A] { + def start: Int + def end: Int + def apply(i: Int): A + def iterator: Iterator[A] = new Iterator[A] { + private var current = start + def hasNext = current < end + def next: A = { + val r = apply(current) + current += 1 + r + } + } + override def knownLength = end - start max 0 + } + + object View { + def fromIterator[A](it: => Iterator[A]): View[A] = new View[A] { + def iterator = it + } + case object Empty extends View[Nothing] { + def iterator = Iterator.empty + override def knownLength = 0 + } + case class Elems[A](xs: A*) extends View[A] { + def iterator = Iterator(xs: _*) + override def knownLength = xs.length + } + case class Filter[A](val underlying: Iterable[A], p: A => Boolean) extends View[A] { + def iterator = underlying.iterator.filter(p) + } + case class Partition[A](val underlying: Iterable[A], p: A => Boolean) { + val left = Partitioned(this, true) + val right = Partitioned(this, false) + } + case class Partitioned[A](partition: Partition[A], cond: Boolean) extends View[A] { + def iterator = partition.underlying.iterator.filter(x => partition.p(x) == cond) + } + case class Drop[A](underlying: Iterable[A], n: Int) extends View[A] { + def iterator = underlying.iterator.drop(n) + override def knownLength = + if (underlying.knownLength >= 0) underlying.knownLength - n max 0 else -1 + } + case class Map[A, B](underlying: Iterable[A], f: A => B) extends View[B] { + def iterator = underlying.iterator.map(f) + override def knownLength = underlying.knownLength + } + case class FlatMap[A, B](underlying: Iterable[A], f: A => IterableOnce[B]) extends View[B] { + def iterator = underlying.iterator.flatMap(f) + } + case class Concat[A](underlying: Iterable[A], other: IterableOnce[A]) extends View[A] { + def iterator = underlying.iterator ++ other + override def knownLength = other match { + case other: Iterable[_] if underlying.knownLength >= 0 && other.knownLength >= 0 => + underlying.knownLength + other.knownLength + case _ => + -1 + } + } + case class Zip[A, B](underlying: Iterable[A], other: IterableOnce[B]) extends View[(A, B)] { + def iterator = underlying.iterator.zip(other) + override def knownLength = other match { + case other: Iterable[_] if underlying.knownLength >= 0 && other.knownLength >= 0 => + underlying.knownLength min other.knownLength + case _ => + -1 + } + } + } + +/* ---------- Iterators ---------------------------------------------------*/ + + /** A core Iterator class */ + trait Iterator[+A] extends IterableOnce[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 filter(p: A => Boolean): Iterator[A] = new Iterator[A] { + private var hd: A = _ + private var hdDefined: Boolean = false + + def hasNext: Boolean = hdDefined || { + do { + if (!self.hasNext) return false + hd = self.next() + } while (!p(hd)) + hdDefined = true + true + } + + def next() = + if (hasNext) { + hdDefined = false + hd + } + else Iterator.empty.next() + } + + 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 => IterableOnce[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: IterableOnce[B]): Iterator[B] = new Iterator[B] { + private var myCurrent: Iterator[B] = self + private var first = true + private def current = { + if (!myCurrent.hasNext && first) { + myCurrent = xs.iterator + first = false + } + myCurrent + } + def hasNext = current.hasNext + def next() = current.next() + } + def drop(n: Int): Iterator[A] = { + var i = 0 + while (i < n && hasNext) { + next() + i += 1 + } + this + } + def zip[B](that: IterableOnce[B]): Iterator[(A, B)] = new Iterator[(A, B)] { + val thatIterator = that.iterator + def hasNext = self.hasNext && thatIterator.hasNext + def next() = (self.next(), thatIterator.next()) + } + } + + object Iterator { + val empty: Iterator[Nothing] = new Iterator[Nothing] { + def hasNext = false + def next = throw new NoSuchElementException("next on empty iterator") + } + def apply[A](xs: A*): Iterator[A] = new RandomAccessView[A] { + val start = 0 + val end = xs.length + def apply(n: Int) = xs(n) + }.iterator + } +} diff --git a/compiler/src/strawman/collections/CollectionStrawMan6.scala b/compiler/src/strawman/collections/CollectionStrawMan6.scala new file mode 100644 index 000000000..50de63488 --- /dev/null +++ b/compiler/src/strawman/collections/CollectionStrawMan6.scala @@ -0,0 +1,1045 @@ +package strawman.collections + +import Predef.{augmentString => _, wrapString => _, _} +import scala.reflect.ClassTag +import annotation.unchecked.uncheckedVariance +import annotation.tailrec + +class LowPriority { + import CollectionStrawMan6._ + + /** Convert array to iterable via view. Lower priority than ArrayOps */ + implicit def arrayToView[T](xs: Array[T]): ArrayView[T] = new ArrayView[T](xs) + + /** Convert string to iterable via view. Lower priority than StringOps */ + implicit def stringToView(s: String): StringView = new StringView(s) +} + +/** 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 odether + * 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. + * + * Strawman6 is like strawman5, and adds lazy lists (i.e. lazie streams), arrays + * and some utilitity methods (take, tail, mkString, toArray). Also, systematically + * uses builders for all strict collections. + * + * Types covered in this strawman: + * + * 1. Collection base types: + * + * IterableOnce, Iterable, Seq, LinearSeq, View, IndexedView + * + * 2. Collection creator base types: + * + * FromIterable, IterableFactory, Buildable, Builder + * + * 3. Types that bundle operations: + * + * IterableOps, IterableMonoTransforms, IterablePolyTransforms, IterableLike + * SeqMonoTransforms, SeqLike + * + * 4. Concrete collection types: + * + * List, LazyList, ListBuffer, ArrayBuffer, ArrayBufferView, StringView, ArrayView + * + * 5. Decorators for existing types + * + * StringOps, ArrayOps + * + * 6. Related non collection types: + * + * Iterator, StringBuilder + * + * Operations covered in this strawman: + * + * 1. Abstract operations, or expected to be overridden: + * + * For iterables: + * + * iterator, fromIterable, fromIterableWithSameElemType, knownLength, className + * + * For sequences: + * + * apply, length + * + * For buildables: + * + * newBuilder + * + * For builders: + * + * +=, result + * + * 2. Utility methods, might be overridden for performance: + * + * Operations returning not necessarily a collection: + * + * foreach, foldLeft, foldRight, indexWhere, isEmpty, head, size, mkString + * + * Operations returning a collection of a fixed type constructor: + * + * view, to, toArray, copyToArray + * + * Type-preserving generic transforms: + * + * filter, partition, take, drop, tail, reverse + * + * Generic transforms returning collections of different element types: + * + * map, flatMap, ++, zip + */ +object CollectionStrawMan6 extends LowPriority { + + /* ------------ Base Traits -------------------------------- */ + + /** Iterator can be used only once */ + trait IterableOnce[+A] { + def iterator: Iterator[A] + } + + /** Base trait for instances that can construct a collection from an iterable */ + trait FromIterable[+C[X] <: Iterable[X]] { + def fromIterable[B](it: Iterable[B]): C[B] + } + + /** Base trait for companion objects of collections */ + trait IterableFactory[+C[X] <: Iterable[X]] extends FromIterable[C] { + def empty[X]: C[X] = fromIterable(View.Empty) + def apply[A](xs: A*): C[A] = fromIterable(View.Elems(xs: _*)) + } + + /** Base trait for generic collections */ + trait Iterable[+A] extends IterableOnce[A] with IterableLike[A, Iterable] { + /** The collection itself */ + protected def coll: this.type = this + } + + /** A trait representing indexable collections with finite length */ + trait ArrayLike[+A] extends Any { + def length: Int + def apply(i: Int): A + } + + /** Base trait for sequence collections */ + trait Seq[+A] extends Iterable[A] with SeqLike[A, Seq] with ArrayLike[A] + + /** Base trait for linearly accessed sequences that have efficient `head` and + * `tail` operations. + * Known subclasses: List, LazyList + */ + trait LinearSeq[+A] extends Seq[A] with LinearSeqLike[A, LinearSeq] { self => + + /** To be overridden in implementations: */ + def isEmpty: Boolean + def head: A + def tail: LinearSeq[A] + + /** `iterator` is overridden in terms of `head` and `tail` */ + def iterator = new Iterator[A] { + private[this] var current: Seq[A] = self + def hasNext = !current.isEmpty + def next = { val r = current.head; current = current.tail; r } + } + + /** `length is defined in terms of `iterator` */ + def length: Int = iterator.length + + /** `apply` is defined in terms of `drop`, which is in turn defined in + * terms of `tail`. + */ + override def apply(n: Int): A = { + if (n < 0) throw new IndexOutOfBoundsException(n.toString) + val skipped = drop(n) + if (skipped.isEmpty) throw new IndexOutOfBoundsException(n.toString) + skipped.head + } + } + + type IndexedSeq[+A] = Seq[A] { def view: IndexedView[A] } + + /** Base trait for strict collections that can be built using a builder. + * @param A the element type of the collection + * @param Repr the type of the underlying collection + */ + trait Buildable[+A, +Repr] extends Any with IterableMonoTransforms[A, Repr] { + + /** Creates a new builder. */ + protected[this] def newBuilder: Builder[A, Repr] + + /** Optimized, push-based version of `partition`. */ + override def partition(p: A => Boolean): (Repr, Repr) = { + val l, r = newBuilder + coll.iterator.foreach(x => (if (p(x)) l else r) += x) + (l.result, r.result) + } + + // one might also override other transforms here to avoid generating + // iterators if it helps efficiency. + } + + /** Base trait for collection builders */ + trait Builder[-A, +To] { self => + + /** Append an element */ + def +=(x: A): this.type + + /** Result collection consisting of all elements appended so far. */ + def result: To + + /** Bulk append. Can be overridden if specialized implementations are available. */ + def ++=(xs: IterableOnce[A]): this.type = { + xs.iterator.foreach(+=) + this + } + + /** A builder resulting from this builder my mapping the result using `f`. */ + def mapResult[NewTo](f: To => NewTo) = new Builder[A, NewTo] { + def +=(x: A): this.type = { self += x; this } + override def ++=(xs: IterableOnce[A]): this.type = { self ++= xs; this } + def result: NewTo = f(self.result) + } + } + + /* ------------ Operations ----------------------------------- */ + + /** Base trait for Iterable operations + * + * VarianceNote + * ============ + * + * We require that for all child classes of Iterable the variance of + * the child class and the variance of the `C` parameter passed to `IterableLike` + * are the same. We cannot express this since we lack variance polymorphism. That's + * why we have to resort at some places to write `C[A @uncheckedVariance]`. + * + */ + trait IterableLike[+A, +C[X] <: Iterable[X]] + extends FromIterable[C] + with IterableOps[A] + with IterableMonoTransforms[A, C[A @uncheckedVariance]] // sound bcs of VarianceNote + with IterablePolyTransforms[A, C] { + + /** Create a collection of type `C[A]` from the elements of `coll`, which has + * the same element type as this collection. Overridden in StringOps and ArrayOps. + */ + protected[this] def fromIterableWithSameElemType(coll: Iterable[A]): C[A] = fromIterable(coll) + } + + /** Base trait for Seq operations */ + trait SeqLike[+A, +C[X] <: Seq[X]] + extends IterableLike[A, C] + with SeqMonoTransforms[A, C[A @uncheckedVariance]] // sound bcs of VarianceNote + + /** Base trait for linear Seq operations */ + trait LinearSeqLike[+A, +C[X] <: LinearSeq[X]] extends SeqLike[A, C] { + + /** Optimized version of `drop` that avoids copying + * Note: `drop` is defined here, rather than in a trait like `LinearSeqMonoTransforms`, + * because the `...MonoTransforms` traits make no assumption about the type of `Repr` + * whereas we need to assume here that `Repr` is the same as the underlying + * collection type. + */ + override def drop(n: Int): C[A @uncheckedVariance] = { // sound bcs of VarianceNote + def loop(n: Int, s: Iterable[A]): C[A] = + if (n <= 0) s.asInstanceOf[C[A]] + // implicit contract to guarantee success of asInstanceOf: + // (1) coll is of type C[A] + // (2) The tail of a LinearSeq is of the same type as the type of the sequence itself + // it's surprisingly tricky/ugly to turn this into actual types, so we + // leave this contract implicit. + else loop(n - 1, s.tail) + loop(n, coll) + } + } + + /** Operations over iterables. No operation defined here is generic in the + * type of the underlying collection. + */ + trait IterableOps[+A] extends Any { + protected def coll: Iterable[A] + private def iterator = coll.iterator + + /** Apply `f` to each element for tis side effects */ + def foreach(f: A => Unit): Unit = iterator.foreach(f) + + /** Fold left */ + def foldLeft[B](z: B)(op: (B, A) => B): B = iterator.foldLeft(z)(op) + + /** Fold right */ + def foldRight[B](z: B)(op: (A, B) => B): B = iterator.foldRight(z)(op) + + /** The index of the first element in this collection for which `p` holds. */ + def indexWhere(p: A => Boolean): Int = iterator.indexWhere(p) + + /** Is the collection empty? */ + def isEmpty: Boolean = !iterator.hasNext + + /** The first element of the collection. */ + def head: A = iterator.next() + + /** The number of elements in this collection, if it can be cheaply computed, + * -1 otherwise. Cheaply usually means: Not requiring a collection traversal. + */ + def knownSize: Int = -1 + + /** The number of elements in this collection. Does not terminate for + * infinite collections. + */ + def size: Int = if (knownSize >= 0) knownSize else iterator.length + + /** A view representing the elements of this collection. */ + def view: View[A] = View.fromIterator(iterator) + + /** Given a collection factory `fi` for collections of type constructor `C`, + * convert this collection to one of type `C[A]`. Example uses: + * + * xs.to(List) + * xs.to(ArrayBuffer) + */ + def to[C[X] <: Iterable[X]](fi: FromIterable[C]): C[A @uncheckedVariance] = + // variance seems sound because `to` could just as well have been added + // as a decorator. We should investigate this further to be sure. + fi.fromIterable(coll) + + /** Convert collection to array. */ + def toArray[B >: A: ClassTag]: Array[B] = + if (knownSize >= 0) copyToArray(new Array[B](knownSize), 0) + else ArrayBuffer.fromIterable(coll).toArray[B] + + /** Copy all elements of this collection to array `xs`, starting at `start`. */ + def copyToArray[B >: A](xs: Array[B], start: Int = 0): xs.type = { + var i = start + val it = iterator + while (it.hasNext) { + xs(i) = it.next() + i += 1 + } + xs + } + + /** The class name of this collection. To be used for converting to string. + * Collections generally print like this: + * + * <className>(elem_1, ..., elem_n) + */ + def className = getClass.getName + + /** A string showing all elements of this collection, separated by string `sep`. */ + def mkString(sep: String): String = { + var first: Boolean = true + val b = new StringBuilder() + foreach { elem => + if (!first) b ++= sep + first = false + b ++= String.valueOf(elem) + } + b.result + } + + override def toString = s"$className(${mkString(", ")})" + } + + /** Type-preserving transforms over iterables. + * Operations defined here return in their result iterables of the same type + * as the one they are invoked on. + */ + trait IterableMonoTransforms[+A, +Repr] extends Any { + protected def coll: Iterable[A] + protected[this] def fromIterableWithSameElemType(coll: Iterable[A]): Repr + + /** All elements satisfying predicate `p` */ + def filter(p: A => Boolean): Repr = fromIterableWithSameElemType(View.Filter(coll, p)) + + /** A pair of, first, all elements that satisfy prediacte `p` and, second, + * all elements that do not. Interesting because it splits a collection in two. + * + * The default implementation provided here needs to traverse the collection twice. + * Strict collections have an overridden version of `partition` in `Buildable`, + * which requires only a single traversal. + */ + def partition(p: A => Boolean): (Repr, Repr) = { + val pn = View.Partition(coll, p) + (fromIterableWithSameElemType(pn.left), fromIterableWithSameElemType(pn.right)) + } + + /** A collection containing the first `n` elements of this collection. */ + def take(n: Int): Repr = fromIterableWithSameElemType(View.Take(coll, n)) + + /** The rest of the collection without its `n` first elements. For + * linear, immutable collections this should avoid making a copy. + */ + def drop(n: Int): Repr = fromIterableWithSameElemType(View.Drop(coll, n)) + + /** The rest of the collection without its first element. */ + def tail: Repr = drop(1) + } + + /** Transforms over iterables that can return collections of different element types. + */ + trait IterablePolyTransforms[+A, +C[A]] extends Any { + protected def coll: Iterable[A] + def fromIterable[B](coll: Iterable[B]): C[B] + + /** Map */ + def map[B](f: A => B): C[B] = fromIterable(View.Map(coll, f)) + + /** Flatmap */ + def flatMap[B](f: A => IterableOnce[B]): C[B] = fromIterable(View.FlatMap(coll, f)) + + /** Concatenation */ + def ++[B >: A](xs: IterableOnce[B]): C[B] = fromIterable(View.Concat(coll, xs)) + + /** Zip. Interesting because it requires to align to source collections. */ + def zip[B](xs: IterableOnce[B]): C[(A @uncheckedVariance, B)] = fromIterable(View.Zip(coll, xs)) + // sound bcs of VarianceNote + } + + /** Type-preserving transforms over sequences. */ + trait SeqMonoTransforms[+A, +Repr] extends Any with IterableMonoTransforms[A, Repr] { + def reverse: Repr = coll.view match { + case v: IndexedView[A] => fromIterableWithSameElemType(v.reverse) + case _ => + var xs: List[A] = Nil + var it = coll.iterator + while (it.hasNext) xs = it.next() :: xs + fromIterableWithSameElemType(xs) + } + } + + /* --------- Concrete collection types ------------------------------- */ + + /** Concrete collection type: List */ + sealed trait List[+A] + extends LinearSeq[A] + with SeqLike[A, List] + with Buildable[A, List[A]] { + + def fromIterable[B](c: Iterable[B]): List[B] = List.fromIterable(c) + + protected[this] def newBuilder = new ListBuffer[A].mapResult(_.toList) + + /** Prepend element */ + def :: [B >: A](elem: B): List[B] = new ::(elem, this) + + /** Prepend operation that avoids copying this list */ + def ++:[B >: A](prefix: List[B]): List[B] = + if (prefix.isEmpty) this + else prefix.head :: prefix.tail ++: this + + /** When concatenating with another list `xs`, avoid copying `xs` */ + override def ++[B >: A](xs: IterableOnce[B]): List[B] = xs match { + case xs: List[B] => this ++: xs + case _ => super.++(xs) + } + + override def className = "List" + } + + case class :: [+A](x: A, private[collections] var next: List[A @uncheckedVariance]) // sound because `next` is used only locally + extends List[A] { + override def isEmpty = false + override def head = x + override def tail = next + } + + case object Nil extends List[Nothing] { + override def isEmpty = true + override def head = ??? + override def tail = ??? + } + + object List extends IterableFactory[List] { + def fromIterable[B](coll: Iterable[B]): List[B] = coll match { + case coll: List[B] => coll + case _ => ListBuffer.fromIterable(coll).toList + } + } + + /** Concrete collection type: ListBuffer */ + class ListBuffer[A] + extends Seq[A] + with SeqLike[A, ListBuffer] + with Buildable[A, ListBuffer[A]] + with Builder[A, ListBuffer[A]] { + + private var first, last: List[A] = Nil + private var aliased = false + private var len = 0 + + def iterator = first.iterator + + def fromIterable[B](coll: Iterable[B]) = ListBuffer.fromIterable(coll) + + def apply(i: Int) = first.apply(i) + + def length = len + override def knownSize = len + + protected[this] def newBuilder = new ListBuffer[A] + + private def copyElems(): Unit = { + val buf = ListBuffer.fromIterable(result) + first = buf.first + last = buf.last + aliased = false + } + + /** Convert to list; avoids copying where possible. */ + def toList = { + aliased = true + first + } + + def +=(elem: A) = { + if (aliased) copyElems() + val last1 = elem :: Nil + last match { + case last: ::[A] => last.next = last1 + case _ => first = last1 + } + last = last1 + len += 1 + this + } + + def result = this + + override def className = "ListBuffer" + } + + object ListBuffer extends IterableFactory[ListBuffer] { + def fromIterable[B](coll: Iterable[B]): ListBuffer[B] = new ListBuffer[B] ++= coll + } + + /** Concrete collection type: ArrayBuffer */ + class ArrayBuffer[A] private (initElems: Array[AnyRef], initLength: Int) + extends Seq[A] + with SeqLike[A, ArrayBuffer] + with Buildable[A, ArrayBuffer[A]] + with Builder[A, ArrayBuffer[A]] { + + def this() = this(new Array[AnyRef](16), 0) + + private var elems: Array[AnyRef] = initElems + private var start = 0 + private var end = initLength + + def apply(n: Int) = elems(start + n).asInstanceOf[A] + + def length = end - start + override def knownSize = length + + override def view = new ArrayBufferView(elems, start, end) + + def iterator = view.iterator + + def fromIterable[B](it: Iterable[B]): ArrayBuffer[B] = + ArrayBuffer.fromIterable(it) + + protected[this] def newBuilder = new ArrayBuffer[A] + + def +=(elem: A): this.type = { + if (end == elems.length) { + if (start > 0) { + Array.copy(elems, start, elems, 0, length) + end -= start + start = 0 + } + else { + val newelems = new Array[AnyRef](end * 2) + Array.copy(elems, 0, newelems, 0, end) + elems = newelems + } + } + elems(end) = elem.asInstanceOf[AnyRef] + end += 1 + this + } + + def result = this + + /** New operation: destructively drop elements at start of buffer. */ + def trimStart(n: Int): Unit = start += (n max 0) + + /** Overridden to use array copying for efficiency where possible. */ + override def ++[B >: A](xs: IterableOnce[B]): ArrayBuffer[B] = xs match { + case xs: ArrayBuffer[B] => + val elems = new Array[AnyRef](length + xs.length) + Array.copy(this.elems, this.start, elems, 0, this.length) + Array.copy(xs.elems, xs.start, elems, this.length, xs.length) + new ArrayBuffer(elems, elems.length) + case _ => super.++(xs) + } + + override def take(n: Int) = { + val elems = new Array[AnyRef](n min length) + Array.copy(this.elems, this.start, elems, 0, elems.length) + new ArrayBuffer(elems, elems.length) + } + + override def className = "ArrayBuffer" + } + + object ArrayBuffer extends IterableFactory[ArrayBuffer] { + + /** Avoid reallocation of buffer if length is known. */ + def fromIterable[B](coll: Iterable[B]): ArrayBuffer[B] = + if (coll.knownSize >= 0) { + val elems = new Array[AnyRef](coll.knownSize) + val it = coll.iterator + for (i <- 0 until elems.length) elems(i) = it.next().asInstanceOf[AnyRef] + new ArrayBuffer[B](elems, elems.length) + } + else new ArrayBuffer[B] ++= coll + } + + class ArrayBufferView[A](val elems: Array[AnyRef], val start: Int, val end: Int) extends IndexedView[A] { + def length = end - start + def apply(n: Int) = elems(start + n).asInstanceOf[A] + override def className = "ArrayBufferView" + } + + class LazyList[+A](expr: => LazyList.Evaluated[A]) + extends LinearSeq[A] with SeqLike[A, LazyList] { + private[this] var evaluated = false + private[this] var result: LazyList.Evaluated[A] = _ + + def force: LazyList.Evaluated[A] = { + if (!evaluated) { + result = expr + evaluated = true + } + result + } + + override def isEmpty = force.isEmpty + override def head = force.get._1 + override def tail = force.get._2 + + def #:: [B >: A](elem: => B): LazyList[B] = new LazyList(Some((elem, this))) + + def fromIterable[B](c: Iterable[B]): LazyList[B] = LazyList.fromIterable(c) + + override def className = "LazyList" + + override def toString = + if (evaluated) + result match { + case None => "Empty" + case Some((hd, tl)) => s"$hd #:: $tl" + } + else "LazyList(?)" + } + + object LazyList extends IterableFactory[LazyList] { + + type Evaluated[+A] = Option[(A, LazyList[A])] + + object Empty extends LazyList[Nothing](None) + + object #:: { + def unapply[A](s: LazyList[A]): Evaluated[A] = s.force + } + + def fromIterable[B](coll: Iterable[B]): LazyList[B] = coll match { + case coll: LazyList[B] => coll + case _ => fromIterator(coll.iterator) + } + + def fromIterator[B](it: Iterator[B]): LazyList[B] = + new LazyList(if (it.hasNext) Some(it.next(), fromIterator(it)) else None) + } + + // ------------------ Decorators to add collection ops to existing types ----------------------- + + /** Decorator to add collection operations to strings. + */ + implicit class StringOps(val s: String) + extends AnyVal with IterableOps[Char] + with SeqMonoTransforms[Char, String] + with IterablePolyTransforms[Char, List] + with Buildable[Char, String] + with ArrayLike[Char] { + + protected def coll = new StringView(s) + def iterator = coll.iterator + + protected def fromIterableWithSameElemType(coll: Iterable[Char]): String = { + val sb = new StringBuilder + for (ch <- coll) sb += ch + sb.result + } + + def fromIterable[B](coll: Iterable[B]): List[B] = List.fromIterable(coll) + + protected[this] def newBuilder = new StringBuilder + + def length = s.length + def apply(i: Int) = s.charAt(i) + + override def knownSize = s.length + + override def className = "String" + + /** Overloaded version of `map` that gives back a string, where the inherited + * version gives back a sequence. + */ + def map(f: Char => Char): String = { + val sb = new StringBuilder + for (ch <- s) sb += f(ch) + sb.result + } + + /** Overloaded version of `flatMap` that gives back a string, where the inherited + * version gives back a sequence. + */ + def flatMap(f: Char => String): String = { + val sb = new StringBuilder + for (ch <- s) sb ++= f(ch) + sb.result + } + + /** Overloaded version of `++` that gives back a string, where the inherited + * version gives back a sequence. + */ + def ++(xs: IterableOnce[Char]): String = { + val sb = new StringBuilder() ++= s + for (ch <- xs.iterator) sb += ch + sb.result + } + + /** Another overloaded version of `++`. */ + def ++(xs: String): String = s + xs + } + + class StringBuilder extends Builder[Char, String] { + private val sb = new java.lang.StringBuilder + + def += (x: Char) = { sb.append(x); this } + + /** Overloaded version of `++=` that takes a string */ + def ++= (s: String) = { sb.append(s); this } + + def result = sb.toString + + override def toString = result + } + + case class StringView(s: String) extends IndexedView[Char] { + def length = s.length + def apply(n: Int) = s.charAt(n) + override def className = "StringView" + } + + /** Decorator to add collection operations to arrays. + */ + implicit class ArrayOps[A](val xs: Array[A]) + extends AnyVal with IterableOps[A] + with SeqMonoTransforms[A, Array[A]] + with Buildable[A, Array[A]] + with ArrayLike[A] { + + protected def coll = new ArrayView(xs) + def iterator = coll.iterator + + def length = xs.length + def apply(i: Int) = xs.apply(i) + + override def view = new ArrayView(xs) + + def elemTag: ClassTag[A] = ClassTag(xs.getClass.getComponentType) + + protected def fromIterableWithSameElemType(coll: Iterable[A]): Array[A] = coll.toArray[A](elemTag) + + def fromIterable[B: ClassTag](coll: Iterable[B]): Array[B] = coll.toArray[B] + + protected[this] def newBuilder = new ArrayBuffer[A].mapResult(_.toArray(elemTag)) + + override def knownSize = xs.length + + override def className = "Array" + + def map[B: ClassTag](f: A => B): Array[B] = fromIterable(View.Map(coll, f)) + def flatMap[B: ClassTag](f: A => IterableOnce[B]): Array[B] = fromIterable(View.FlatMap(coll, f)) + def ++[B >: A : ClassTag](xs: IterableOnce[B]): Array[B] = fromIterable(View.Concat(coll, xs)) + def zip[B: ClassTag](xs: IterableOnce[B]): Array[(A, B)] = fromIterable(View.Zip(coll, xs)) + } + + case class ArrayView[A](xs: Array[A]) extends IndexedView[A] { + def length = xs.length + def apply(n: Int) = xs(n) + override def className = "ArrayView" + } + + /* ---------- Views -------------------------------------------------------*/ + + /** Concrete collection type: View */ + trait View[+A] extends Iterable[A] with IterableLike[A, View] { + override def view = this + + /** Avoid copying if source collection is already a view. */ + override def fromIterable[B](c: Iterable[B]): View[B] = c match { + case c: View[B] => c + case _ => View.fromIterator(c.iterator) + } + override def className = "View" + } + + /** This object reifies operations on views as case classes */ + object View { + def fromIterator[A](it: => Iterator[A]): View[A] = new View[A] { + def iterator = it + } + + /** The empty view */ + case object Empty extends View[Nothing] { + def iterator = Iterator.empty + override def knownSize = 0 + } + + /** A view with given elements */ + case class Elems[A](xs: A*) extends View[A] { + def iterator = Iterator(xs: _*) + override def knownSize = xs.length // should be: xs.knownSize, but A*'s are not sequences in this strawman. + } + + /** A view that filters an underlying collection. */ + case class Filter[A](val underlying: Iterable[A], p: A => Boolean) extends View[A] { + def iterator = underlying.iterator.filter(p) + } + + /** A view that partitions an underlying collection into two views */ + case class Partition[A](val underlying: Iterable[A], p: A => Boolean) { + + /** The view consisting of all elements of the underlying collection + * that satisfy `p`. + */ + val left = Partitioned(this, true) + + /** The view consisting of all elements of the underlying collection + * that do not satisfy `p`. + */ + val right = Partitioned(this, false) + } + + /** A view representing one half of a partition. */ + case class Partitioned[A](partition: Partition[A], cond: Boolean) extends View[A] { + def iterator = partition.underlying.iterator.filter(x => partition.p(x) == cond) + } + + /** A view that drops leading elements of the underlying collection. */ + case class Drop[A](underlying: Iterable[A], n: Int) extends View[A] { + def iterator = underlying.iterator.drop(n) + protected val normN = n max 0 + override def knownSize = + if (underlying.knownSize >= 0) (underlying.knownSize - normN) max 0 else -1 + } + + /** A view that takes leading elements of the underlying collection. */ + case class Take[A](underlying: Iterable[A], n: Int) extends View[A] { + def iterator = underlying.iterator.take(n) + protected val normN = n max 0 + override def knownSize = + if (underlying.knownSize >= 0) underlying.knownSize min normN else -1 + } + + /** A view that maps elements of the underlying collection. */ + case class Map[A, B](underlying: Iterable[A], f: A => B) extends View[B] { + def iterator = underlying.iterator.map(f) + override def knownSize = underlying.knownSize + } + + /** A view that flatmaps elements of the underlying collection. */ + case class FlatMap[A, B](underlying: Iterable[A], f: A => IterableOnce[B]) extends View[B] { + def iterator = underlying.iterator.flatMap(f) + } + + /** A view that concatenates elements of the underlying collection with the elements + * of another collection or iterator. + */ + case class Concat[A](underlying: Iterable[A], other: IterableOnce[A]) extends View[A] { + def iterator = underlying.iterator ++ other + override def knownSize = other match { + case other: Iterable[_] if underlying.knownSize >= 0 && other.knownSize >= 0 => + underlying.knownSize + other.knownSize + case _ => + -1 + } + } + + /** A view that zips elements of the underlying collection with the elements + * of another collection or iterator. + */ + case class Zip[A, B](underlying: Iterable[A], other: IterableOnce[B]) extends View[(A, B)] { + def iterator = underlying.iterator.zip(other) + override def knownSize = other match { + case other: Iterable[_] if underlying.knownSize >= 0 && other.knownSize >= 0 => + underlying.knownSize min other.knownSize + case _ => + -1 + } + } + } + + /** View defined in terms of indexing a range */ + trait IndexedView[+A] extends View[A] with ArrayLike[A] { self => + + def iterator: Iterator[A] = new Iterator[A] { + private var current = 0 + def hasNext = current < self.length + def next: A = { + val r = apply(current) + current += 1 + r + } + } + + override def take(n: Int): IndexedView[A] = new IndexedView.Take(this, n) + override def drop(n: Int): IndexedView[A] = new IndexedView.Drop(this, n) + override def map[B](f: A => B): IndexedView[B] = new IndexedView.Map(this, f) + def reverse: IndexedView[A] = new IndexedView.Reverse(this) + } + + object IndexedView { + + class Take[A](underlying: IndexedView[A], n: Int) + extends View.Take(underlying, n) with IndexedView[A] { + override def iterator = super.iterator // needed to avoid "conflicting overrides" error + def length = underlying.length min normN + def apply(i: Int) = underlying.apply(i) + } + + class Drop[A](underlying: IndexedView[A], n: Int) + extends View.Take(underlying, n) with IndexedView[A] { + override def iterator = super.iterator + def length = (underlying.length - normN) max 0 + def apply(i: Int) = underlying.apply(i + normN) + } + + class Map[A, B](underlying: IndexedView[A], f: A => B) + extends View.Map(underlying, f) with IndexedView[B] { + override def iterator = super.iterator + def length = underlying.length + def apply(n: Int) = f(underlying.apply(n)) + } + + case class Reverse[A](underlying: IndexedView[A]) extends IndexedView[A] { + def length = underlying.length + def apply(i: Int) = underlying.apply(length - 1 - i) + } + } + +/* ---------- Iterators ---------------------------------------------------*/ + + /** A core Iterator class */ + trait Iterator[+A] extends IterableOnce[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 length = { + var len = 0 + while (hasNext) { len += 1; next() } + len + } + def filter(p: A => Boolean): Iterator[A] = new Iterator[A] { + private var hd: A = _ + private var hdDefined: Boolean = false + + def hasNext: Boolean = hdDefined || { + do { + if (!self.hasNext) return false + hd = self.next() + } while (!p(hd)) + hdDefined = true + true + } + + def next() = + if (hasNext) { + hdDefined = false + hd + } + else Iterator.empty.next() + } + 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 => IterableOnce[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: IterableOnce[B]): Iterator[B] = new Iterator[B] { + private var myCurrent: Iterator[B] = self + private var first = true + private def current = { + if (!myCurrent.hasNext && first) { + myCurrent = xs.iterator + first = false + } + myCurrent + } + def hasNext = current.hasNext + def next() = current.next() + } + def take(n: Int): Iterator[A] = new Iterator[A] { + private var i = 0 + def hasNext = self.hasNext && i < n + def next = + if (hasNext) { + i += 1 + self.next() + } + else Iterator.empty.next() + } + def drop(n: Int): Iterator[A] = { + var i = 0 + while (i < n && hasNext) { + next() + i += 1 + } + this + } + def zip[B](that: IterableOnce[B]): Iterator[(A, B)] = new Iterator[(A, B)] { + val thatIterator = that.iterator + def hasNext = self.hasNext && thatIterator.hasNext + def next() = (self.next(), thatIterator.next()) + } + } + + object Iterator { + val empty: Iterator[Nothing] = new Iterator[Nothing] { + def hasNext = false + def next = throw new NoSuchElementException("next on empty iterator") + } + def apply[A](xs: A*): Iterator[A] = new IndexedView[A] { + val length = xs.length + def apply(n: Int) = xs(n) + }.iterator + } +} |