From 09b81e513ba703882e2350e39d5c94ba2ce46b9c Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Thu, 28 Jul 2016 14:38:48 +0200 Subject: 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 --- src/strawman/collections/CollectionStrawMan6.scala | 182 ++++++++++++--------- 1 file changed, 101 insertions(+), 81 deletions(-) (limited to 'src/strawman/collections') 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: - * - * (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: + * + * (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()) -- cgit v1.2.3