diff options
| -rw-r--r-- | src/strawman/collections/CollectionStrawMan1.scala (renamed from src/dotty/collections/CollectionStrawMan1.scala) | 147 | ||||
| -rw-r--r-- | tests/run/CollectionTests.check | 20 |
2 files changed, 96 insertions, 71 deletions
diff --git a/src/dotty/collections/CollectionStrawMan1.scala b/src/strawman/collections/CollectionStrawMan1.scala index ea26eb932..93d4086f2 100644 --- a/src/dotty/collections/CollectionStrawMan1.scala +++ b/src/strawman/collections/CollectionStrawMan1.scala @@ -2,7 +2,6 @@ package strawman.collections import Predef.{augmentString => _, wrapString => _, _} import scala.reflect.ClassTag -import collection.mutable.ListBuffer /** A strawman architecture for new collections. It contains some * example collection classes and methods with the intent to expose @@ -36,11 +35,11 @@ object CollectionStrawMan1 { } /** Base trait for generic collections */ - trait Iterable[+IA] extends HasIterator[IA] with FromIterator[Iterable] + trait Iterable[+A] extends HasIterator[A] with FromIterator[Iterable] /** Base trait for sequence collections */ - trait Seq[+AA] extends Iterable[AA] with FromIterator[Seq] { - def apply(i: Int): AA + trait Seq[+A] extends Iterable[A] with FromIterator[Seq] { + def apply(i: Int): A def length: Int } @@ -53,6 +52,7 @@ object CollectionStrawMan1 { 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 collect[C[X] <: Iterable[X]](fi: FromIterator[C]): C[A] = fi.fromIterator(iterator) @@ -134,7 +134,13 @@ object CollectionStrawMan1 { def tail = xs } - case object List extends IterableFactory[List] { + 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 @@ -148,50 +154,62 @@ object CollectionStrawMan1 { def toList = current } - case object Nil extends List[Nothing] { - def isEmpty = true - def head = ??? - def tail = ??? - } - /** Concrete collection type: ArrayBuffer */ - class ArrayBuffer[A] private (initElems: Array[AnyRef], initLen: Int = 0) extends Seq[A] with FromIterator[ArrayBuffer] { - def this() = this(new Array[AnyRef](16)) + 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 len = 0 - def apply(i: Int) = elems(i).asInstanceOf[A] - def length = len - def iterator = new RandomAccessIterator[A] { - override val knownLength = len - def apply(n: Int) = elems(n).asInstanceOf[A] - } + 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 (len == elems.length) { - val newelems = new Array[AnyRef](len * 2) - Array.copy(elems, 0, newelems, 0, len) - elems = newelems + 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(len) = elem.asInstanceOf[AnyRef] - len += 1 + elems(limit) = elem.asInstanceOf[AnyRef] + limit += 1 this } - override def toString = elems.take(len).deep.toString + 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] = - if (it.knownLength == 0) { - val elems = new Array[AnyRef](it.knownLength) + 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(elems) - } - else { + 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 */ @@ -219,7 +237,7 @@ object CollectionStrawMan1 { /** Concrete collection type: String */ implicit class StringOps(val s: String) extends AnyVal with Ops[Char] { def iterator: Iterator[Char] = new RandomAccessIterator[Char] { - override val knownLength = s.length + override val limit = s.length def apply(n: Int) = s.charAt(n) } } @@ -281,7 +299,7 @@ object CollectionStrawMan1 { 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 ListBuffer[A] + val lookaheadTrue, lookaheadFalse = new ArrayBuffer[A] (Iterator.Partition(this, p, lookaheadTrue, lookaheadFalse), Iterator.Partition[A](this, !p(_), lookaheadFalse, lookaheadTrue)) } @@ -292,18 +310,26 @@ object CollectionStrawMan1 { 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 - def knownLength = -1 + + /** 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 val knownLength = 0 + override def remaining = 0 } def apply[A](xs: A*): Iterator[A] = new RandomAccessIterator[A] { - override val knownLength = xs.length + override val limit = xs.length def apply(n: Int) = xs(n) } def nextOnEmpty = throw new NoSuchElementException("next on empty iterator") @@ -311,7 +337,7 @@ object CollectionStrawMan1 { 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 val knownLength = underlying.knownLength + 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 @@ -331,19 +357,18 @@ object CollectionStrawMan1 { } def hasNext = current.hasNext def next = current.next - override val knownLength = - if (underlying.knownLength > 0 && other.knownLength > 0) - underlying.knownLength + other.knownLength + 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: ListBuffer[A], dual: ListBuffer[A]) extends Iterator[A] { + 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.nonEmpty || - underlying.hasNext && { - val elem = underlying.next - (if (p(elem)) lookahead else dual) += elem - hasNext - } + !lookahead.isEmpty || underlying.hasNext && { distribute(); hasNext } final def next = if (hasNext) { val r = lookahead.head @@ -356,27 +381,27 @@ object CollectionStrawMan1 { def hasNext: Boolean = underlying.hasNext && ( toSkip == 0 || { underlying.next; toSkip -= 1; hasNext }) def next = if (hasNext) underlying.next else nextOnEmpty - override val knownLength = (underlying.knownLength - n) max -1 + 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 val knownLength = underlying.knownLength min other.knownLength + override def remaining = underlying.remaining min other.remaining } - class Reverse[A](underlying: RandomAccessIterator[A]) extends RandomAccessIterator[A] { - override val knownLength = underlying.knownLength - def apply(n: Int) = underlying.apply(knownLength - 1 - n) + 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 knownLength: Int - def length: Int = knownLength - private var cur = 0 - def hasNext = cur < knownLength - def next: A = { val r = this(cur); cur += 1; r } - override def drop(n: Int): Iterator[A] = { cur += (n max 0); this } + 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/tests/run/CollectionTests.check b/tests/run/CollectionTests.check index 7c4f6e77a..6c61d8821 100644 --- a/tests/run/CollectionTests.check +++ b/tests/run/CollectionTests.check @@ -21,17 +21,17 @@ Cons(3,Cons(2,Cons(1,Nil))) 1 1 Cons(1,Cons(2,Cons(3,Nil))) -Array(2) -Array(1, 3) -Array(3) -Array(true, true, true) -Array(1, -1, 2, -2, 3, -3) -Array(1, 2, 3, 1, 2, 3) -Array(1, 2, 3) +ArrayBuffer(2) +ArrayBuffer(1, 3) +ArrayBuffer(3) +ArrayBuffer(true, true, true) +ArrayBuffer(1, -1, 2, -2, 3, -3) +ArrayBuffer(1, 2, 3, 1, 2, 3) +ArrayBuffer(1, 2, 3) Cons(1,Cons(2,Cons(3,Nil))) -Array(1, 2, 3, a) -Array((1,true), (2,true), (3,true)) -Array(3, 2, 1) +ArrayBuffer(1, 2, 3, a) +ArrayBuffer((1,true), (2,true), (3,true)) +ArrayBuffer(3, 2, 1) ------- 123 123 |