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
@tailrec 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
}
}
