diff options
Diffstat (limited to 'src/strawman/collections/CollectionStrawMan4.scala')
| -rw-r--r-- | src/strawman/collections/CollectionStrawMan4.scala | 111 |
1 files changed, 82 insertions, 29 deletions
diff --git a/src/strawman/collections/CollectionStrawMan4.scala b/src/strawman/collections/CollectionStrawMan4.scala index 9159b1cfc..874f67a2d 100644 --- a/src/strawman/collections/CollectionStrawMan4.scala +++ b/src/strawman/collections/CollectionStrawMan4.scala @@ -2,6 +2,8 @@ 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 @@ -20,14 +22,7 @@ object CollectionStrawMan4 { def iterator: Iterator[A] } - /** Base trait for generic collections */ - trait Iterable[+A] extends IterableOnce[A] with FromIterable[Iterable] { - def iterator: Iterator[A] - def view: View[A] = View.fromIterator(iterator) - def knownLength: Int = -1 - } - - /** Base trait for instances that can construct a collection from an iterator */ + /** 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] } @@ -38,16 +33,27 @@ object CollectionStrawMan4 { 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 ++=(xs: IterableOnce[A]): Unit = xs.iterator.foreach(+=) def result: To + + def ++=(xs: IterableOnce[A]): this.type = { + xs.iterator.foreach(+=) + this + } } /* ------------ Operations ----------------------------------- */ @@ -134,17 +140,18 @@ object CollectionStrawMan4 { require(!isEmpty) if (i == 0) head else tail.apply(i - 1) } - def :::[B >: A](prefix: List[B]): List[B] = - if (prefix.isEmpty) this - else Cons(prefix.head, prefix.tail ::: this) 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, xs: List[A]) extends List[A] { + 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 = xs + def tail = next } case object Nil extends List[Nothing] { @@ -157,20 +164,64 @@ object CollectionStrawMan4 { 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: Iterable[B]) => - fromIterable(xs) ::: fromIterable(ys) + case View.Concat(xs, ys: List[B]) => + fromIterable(xs) ++: ys case View.Drop(xs: List[B], n) => - var i = 0 - var ys = xs - while (i < n && !xs.isEmpty) { - ys = ys.tail - i += 1 - } - ys + @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]) => + partition.distribute(new ListBuffer[B]()) + pd.forced.get.asInstanceOf[ListBuffer[B]] + 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]] { @@ -234,12 +285,6 @@ object CollectionStrawMan4 { def apply(n: Int) = elems(start + n).asInstanceOf[A] } - case class StringView(s: String) extends RandomAccessView[Char] { - val start = 0 - val end = s.length - def apply(n: Int) = s.charAt(n) - } - /** Concrete collection type: String */ implicit class StringOps(val s: String) extends AnyVal with Ops[Char] { def iterator: Iterator[Char] = new StringView(s).iterator @@ -277,6 +322,12 @@ object CollectionStrawMan4 { 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 */ @@ -322,6 +373,8 @@ object CollectionStrawMan4 { } 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 |