diff options
author | Martin Odersky <odersky@gmail.com> | 2016-07-28 14:38:48 +0200 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2016-07-28 14:38:48 +0200 |
commit | 09b81e513ba703882e2350e39d5c94ba2ce46b9c (patch) | |
tree | 8494bafeef4fe5fcf3ab38f4c99fb2eaa5a191fa | |
parent | a591802a29b80df6f32fc4f8090da518b5410602 (diff) | |
download | dotty-09b81e513ba703882e2350e39d5c94ba2ce46b9c.tar.gz dotty-09b81e513ba703882e2350e39d5c94ba2ce46b9c.tar.bz2 dotty-09b81e513ba703882e2350e39d5c94ba2ce46b9c.zip |
Tweaks to strawman
- Add proper :: to lists
- Move some methods to IterableOps in order to keep Iterable clean
- Rename knownLength to knownSize
- Add some implentations for performance and completeness
-rw-r--r-- | src/strawman/collections/CollectionStrawMan6.scala | 182 | ||||
-rw-r--r-- | tests/run/colltest6/CollectionStrawMan6_1.scala | 182 | ||||
-rw-r--r-- | tests/run/colltest6/CollectionTests_2.scala | 22 |
3 files changed, 213 insertions, 173 deletions
diff --git a/src/strawman/collections/CollectionStrawMan6.scala b/src/strawman/collections/CollectionStrawMan6.scala index 5889782d6..d3d54d89b 100644 --- a/src/strawman/collections/CollectionStrawMan6.scala +++ b/src/strawman/collections/CollectionStrawMan6.scala @@ -114,22 +114,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] { @@ -140,18 +127,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) = @@ -221,7 +211,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) } @@ -256,26 +246,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) @@ -288,7 +272,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`. */ @@ -301,6 +285,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. @@ -365,7 +370,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) } } @@ -373,20 +378,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 { @@ -397,7 +404,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 @@ -426,6 +433,7 @@ object CollectionStrawMan6 extends LowPriority { private var first, last: List[A] = Nil private var aliased = false + private var len = 0 def iterator = first.iterator @@ -433,7 +441,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] @@ -452,12 +461,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 } @@ -486,7 +496,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) @@ -543,18 +553,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] { @@ -563,7 +568,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] = _ @@ -579,7 +584,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) @@ -598,16 +603,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 ----------------------- @@ -633,6 +641,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. */ @@ -704,6 +716,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)) @@ -740,13 +756,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. */ @@ -776,21 +792,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. */ @@ -803,9 +819,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 } @@ -816,9 +832,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 } @@ -847,8 +863,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 ---------------------------------------------------*/ @@ -872,6 +888,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 @@ -892,7 +913,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()) 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()) diff --git a/tests/run/colltest6/CollectionTests_2.scala b/tests/run/colltest6/CollectionTests_2.scala index f139fa151..124a526b4 100644 --- a/tests/run/colltest6/CollectionTests_2.scala +++ b/tests/run/colltest6/CollectionTests_2.scala @@ -23,7 +23,7 @@ object Test { val ys8: Seq[Int] = xs8 val xs9 = xs.map(_ >= 0) val ys9: Seq[Boolean] = xs9 - val xs10 = xs.flatMap(x => Cons(x, Cons(-x, Nil))) + val xs10 = xs.flatMap(x => x :: -x :: Nil) val ys10: Seq[Int] = xs10 val xs11 = xs ++ xs val ys11: Seq[Int] = xs11 @@ -31,7 +31,7 @@ object Test { val ys12: Seq[Int] = xs12 val xs13 = Nil ++ xs val ys13: Seq[Int] = xs13 - val xs14 = xs ++ Cons("a", Nil) + val xs14 = xs ++ ("a" :: Nil) val ys14: Seq[Any] = xs14 val xs15 = xs.zip(xs9) val ys15: Seq[(Int, Boolean)] = xs15 @@ -74,7 +74,7 @@ object Test { val ys8: View[Int] = xs8 val xs9 = xs.map(_ >= 0) val ys9: View[Boolean] = xs9 - val xs10 = xs.flatMap(x => Cons(x, Cons(-x, Nil))) + val xs10 = xs.flatMap(x => x :: -x :: Nil) val ys10: View[Int] = xs10 val xs11 = xs ++ xs val ys11: View[Int] = xs11 @@ -82,7 +82,7 @@ object Test { val ys12: View[Int] = xs12 val xs13 = Nil ++ xs val ys13: List[Int] = xs13 - val xs14 = xs ++ Cons("a", Nil) + val xs14 = xs ++ ("a" :: Nil) val ys14: View[Any] = xs14 val xs15 = xs.zip(xs9) val ys15: View[(Int, Boolean)] = xs15 @@ -128,13 +128,13 @@ object Test { val ys10: String = xs10 val xs11 = xs ++ xs val ys11: String = xs11 - val xs11a = xs ++ List('x', 'y') // Cons('x', Cons('y', Nil)) + val xs11a = xs ++ List('x', 'y') val ys11a: String = xs11a val xs12 = xs ++ Nil val ys12: String = xs12 val xs13 = Nil ++ xs.iterator val ys13: List[Char] = xs13 - val xs14 = xs ++ Cons("xyz", Nil) + val xs14 = xs ++ List("xyz") val ys14: Seq[Any] = xs14 val xs15 = xs.zip(xs9) val ys15: Seq[(Char, Int)] = xs15 @@ -178,7 +178,7 @@ object Test { val ys8: Array[Int] = xs8 val xs9 = ArrayOps(xs).map(_ >= 0) val ys9: Array[Boolean] = xs9 - val xs10 = xs.flatMap(x => Cons(x, Cons(-x, Nil))) + val xs10 = xs.flatMap(x => List(x, -x)) val ys10: Array[Int] = xs10 val xs11 = xs ++ xs val ys11: Array[Int] = xs11 @@ -186,7 +186,7 @@ object Test { val ys12: Array[Int] = xs12 val xs13 = Nil ++ xs val ys13: List[Int] = xs13 - val xs14 = xs ++ Cons("a": Any, Nil) + val xs14 = xs ++ (("a": Any) :: Nil) val ys14: Array[Any] = xs14 val xs15 = xs.zip(xs9) val ys15: Array[(Int, Boolean)] = xs15 @@ -229,7 +229,7 @@ object Test { val ys8: Seq[Int] = xs8 val xs9 = xs.map(_ >= 0) val ys9: Seq[Boolean] = xs9 - val xs10 = xs.flatMap(x => Cons(x, Cons(-x, Nil))) + val xs10 = xs.flatMap(x => x :: -x :: Nil) val ys10: Seq[Int] = xs10 val xs11 = xs ++ xs val ys11: Seq[Int] = xs11 @@ -237,7 +237,7 @@ object Test { val ys12: Seq[Int] = xs12 val xs13 = Nil ++ xs val ys13: Seq[Int] = xs13 - val xs14 = xs ++ Cons("a", Nil) + val xs14 = xs ++ ("a" :: Nil) val ys14: Seq[Any] = xs14 val xs15 = xs.zip(xs9) val ys15: Seq[(Int, Boolean)] = xs15 @@ -285,7 +285,7 @@ object Test { } def main(args: Array[String]) = { - val ints = Cons(1, Cons(2, Cons(3, Nil))) + val ints = List(1, 2, 3) val intsBuf = ints.to(ArrayBuffer) val intsListBuf = ints.to(ListBuffer) val intsView = ints.view |