diff options
Diffstat (limited to 'tests/run/colltest6/CollectionStrawMan6_1.scala')
-rw-r--r-- | tests/run/colltest6/CollectionStrawMan6_1.scala | 182 |
1 files changed, 101 insertions, 81 deletions
diff --git a/tests/run/colltest6/CollectionStrawMan6_1.scala b/tests/run/colltest6/CollectionStrawMan6_1.scala index 9f29410ad..50a7dfec3 100644 --- a/tests/run/colltest6/CollectionStrawMan6_1.scala +++ b/tests/run/colltest6/CollectionStrawMan6_1.scala @@ -115,22 +115,9 @@ object CollectionStrawMan6 extends LowPriority { /** Base trait for generic collections */ trait Iterable[+A] extends IterableOnce[A] with IterableLike[A, Iterable] { - /** The collection itself */ - protected def coll: Iterable[A] = this - - /** The length of this collection, if it can be cheaply computed, -1 otherwise. */ - def knownLength: Int = -1 - - /** 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 - - override def toString = s"$className(${mkString(", ")})" - } + protected def coll: this.type = this + } /** Base trait for sequence collections */ trait Seq[+A] extends Iterable[A] with SeqLike[A, Seq] { @@ -141,18 +128,21 @@ object CollectionStrawMan6 extends LowPriority { /** Base trait for linearly accessed sequences */ trait LinearSeq[+A] extends Seq[A] with SeqLike[A, LinearSeq] { self => + /** To be overridden in implementations: */ + def isEmpty: Boolean + def head: A + def tail: LinearSeq[A] + 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 } } - def apply(i: Int): A = { - require(!isEmpty) - if (i == 0) head else tail.apply(i - 1) - } + def length: Int = iterator.length - def length: Int = if (isEmpty) 0 else 1 + tail.length + @tailrec final def apply(n: Int): A = + if (n == 0) head else tail.apply(n - 1) /** Optimized version of `drop` that avoids copying */ @tailrec final override def drop(n: Int) = @@ -222,7 +212,7 @@ object CollectionStrawMan6 extends LowPriority { 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. + * the same element type as this collection. Overridden in StringOps and ArrayOps. */ protected[this] def fromIterableWithSameElemType(coll: Iterable[A]): C[A] = fromIterable(coll) } @@ -257,26 +247,20 @@ object CollectionStrawMan6 extends LowPriority { /** The first element of the collection. */ def head: A = iterator.next() - /** The number of elements in this collection. */ - def size: Int = - if (coll.knownLength >= 0) coll.knownLength else foldLeft(0)((len, x) => len + 1) + /** 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) - /** 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 - } - - /** Given a collection factory `fi` for collections of type constructor `C`, + /** 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) @@ -289,7 +273,7 @@ object CollectionStrawMan6 extends LowPriority { /** Convert collection to array. */ def toArray[B >: A: ClassTag]: Array[B] = - if (coll.knownLength >= 0) copyToArray(new Array[B](coll.knownLength), 0) + 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`. */ @@ -302,6 +286,27 @@ object CollectionStrawMan6 extends LowPriority { } 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. @@ -366,7 +371,7 @@ object CollectionStrawMan6 extends LowPriority { case _ => var xs: List[A] = Nil var it = coll.iterator - while (it.hasNext) xs = new Cons(it.next(), xs) + while (it.hasNext) xs = it.next() :: xs fromIterableWithSameElemType(xs) } } @@ -374,20 +379,22 @@ object CollectionStrawMan6 extends LowPriority { /* --------- Concrete collection types ------------------------------- */ /** Concrete collection type: List */ - sealed trait List[+A] extends LinearSeq[A] with SeqLike[A, List] with Buildable[A, List[A]] { self => - - def isEmpty: Boolean - def head: A - def tail: List[A] + 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 Cons(prefix.head, prefix.tail ++: 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 { @@ -398,7 +405,7 @@ object CollectionStrawMan6 extends LowPriority { override def className = "List" } - case class Cons[+A](x: A, private[collections] var next: List[A @uncheckedVariance]) // sound because `next` is used only locally + 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 @@ -427,6 +434,7 @@ object CollectionStrawMan6 extends LowPriority { private var first, last: List[A] = Nil private var aliased = false + private var len = 0 def iterator = first.iterator @@ -434,7 +442,8 @@ object CollectionStrawMan6 extends LowPriority { def apply(i: Int) = first.apply(i) - def length = first.length + def length = len + override def knownSize = len protected[this] def newBuilder = new ListBuffer[A] @@ -453,12 +462,13 @@ object CollectionStrawMan6 extends LowPriority { def +=(elem: A) = { if (aliased) copyElems() - val last1 = Cons(elem, Nil) + val last1 = elem :: Nil last match { - case last: Cons[A] => last.next = last1 + case last: ::[A] => last.next = last1 case _ => first = last1 } last = last1 + len += 1 this } @@ -487,7 +497,7 @@ object CollectionStrawMan6 extends LowPriority { def apply(n: Int) = elems(start + n).asInstanceOf[A] def length = end - start - override def knownLength = length + override def knownSize = length override def view = new ArrayBufferView(elems, start, end) @@ -544,18 +554,13 @@ object CollectionStrawMan6 extends LowPriority { /** Avoid reallocation of buffer if length is known. */ def fromIterable[B](coll: Iterable[B]): ArrayBuffer[B] = - if (coll.knownLength >= 0) { - val elems = new Array[AnyRef](coll.knownLength) + 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 { - val buf = new ArrayBuffer[B] - val it = coll.iterator - while (it.hasNext) buf += it.next() - buf - } + else new ArrayBuffer[B] ++= coll } class ArrayBufferView[A](val elems: Array[AnyRef], val start: Int, val end: Int) extends IndexedView[A] { @@ -564,7 +569,7 @@ object CollectionStrawMan6 extends LowPriority { } class LazyList[+A](expr: => LazyList.Evaluated[A]) - extends LinearSeq[A] with SeqLike[A, LazyList] { self => + extends LinearSeq[A] with SeqLike[A, LazyList] { private[this] var evaluated = false private[this] var result: LazyList.Evaluated[A] = _ @@ -580,7 +585,7 @@ object CollectionStrawMan6 extends LowPriority { override def head = force.get._1 override def tail = force.get._2 - def #:: [B >: A](elem: => B): LazyList[B] = new LazyList(Some((elem, self))) + def #:: [B >: A](elem: => B): LazyList[B] = new LazyList(Some((elem, this))) def fromIterable[B](c: Iterable[B]): LazyList[B] = LazyList.fromIterable(c) @@ -599,16 +604,19 @@ object CollectionStrawMan6 extends LowPriority { type Evaluated[+A] = Option[(A, LazyList[A])] - def fromIterable[B](coll: Iterable[B]): LazyList[B] = coll match { - case coll: LazyList[B] => coll - case _ => new LazyList(if (coll.isEmpty) None else Some((coll.head, fromIterable(coll.tail)))) - } - 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 ----------------------- @@ -634,6 +642,10 @@ object CollectionStrawMan6 extends LowPriority { protected[this] def newBuilder = new StringBuilder + 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. */ @@ -705,6 +717,10 @@ object CollectionStrawMan6 extends LowPriority { 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)) @@ -741,13 +757,13 @@ object CollectionStrawMan6 extends LowPriority { /** The empty view */ case object Empty extends View[Nothing] { def iterator = Iterator.empty - override def knownLength = 0 + override def knownSize = 0 } /** A view with given elements */ case class Elems[A](xs: A*) extends View[A] { def iterator = Iterator(xs: _*) - override def knownLength = xs.length + 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. */ @@ -777,21 +793,21 @@ object CollectionStrawMan6 extends LowPriority { /** 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) - override def knownLength = - if (underlying.knownLength >= 0) underlying.knownLength - n max 0 else -1 + override def knownSize = + if (underlying.knownSize >= 0) underlying.knownSize - n 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) - override def knownLength = - if (underlying.knownLength >= 0) underlying.knownLength min n else -1 + override def knownSize = + if (underlying.knownSize >= 0) underlying.knownSize min n 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 knownLength = underlying.knownLength + override def knownSize = underlying.knownSize } /** A view that flatmaps elements of the underlying collection. */ @@ -804,9 +820,9 @@ object CollectionStrawMan6 extends LowPriority { */ 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 + override def knownSize = other match { + case other: Iterable[_] if underlying.knownSize >= 0 && other.knownSize >= 0 => + underlying.knownSize + other.knownSize case _ => -1 } @@ -817,9 +833,9 @@ object CollectionStrawMan6 extends LowPriority { */ 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 + override def knownSize = other match { + case other: Iterable[_] if underlying.knownSize >= 0 && other.knownSize >= 0 => + underlying.knownSize min other.knownSize case _ => -1 } @@ -848,8 +864,8 @@ object CollectionStrawMan6 extends LowPriority { def apply(i: Int) = self.apply(end - 1 - i) } - override def knownLength = end - start max 0 - def length = knownLength + def length = end - start max 0 + override def knownSize = length } /* ---------- Iterators ---------------------------------------------------*/ @@ -873,6 +889,11 @@ object CollectionStrawMan6 extends LowPriority { } -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 @@ -893,7 +914,6 @@ object CollectionStrawMan6 extends LowPriority { } else Iterator.empty.next() } - def map[B](f: A => B): Iterator[B] = new Iterator[B] { def hasNext = self.hasNext def next() = f(self.next()) |