From 8db8c110a2b2a287875222a74511511d80be2b15 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Sat, 30 Jul 2016 20:56:27 +0200 Subject: More systematic treatement of IndexedView Followinf @szeiger's suggestion, equip IndexView with optimized operations for map/drop/take. --- tests/run/colltest6/CollectionStrawMan6_1.scala | 87 +++++++++++++++++-------- 1 file changed, 61 insertions(+), 26 deletions(-) (limited to 'tests/run/colltest6') diff --git a/tests/run/colltest6/CollectionStrawMan6_1.scala b/tests/run/colltest6/CollectionStrawMan6_1.scala index 5d3ea4991..40448e5da 100644 --- a/tests/run/colltest6/CollectionStrawMan6_1.scala +++ b/tests/run/colltest6/CollectionStrawMan6_1.scala @@ -117,14 +117,17 @@ object CollectionStrawMan6 extends LowPriority { trait Iterable[+A] extends IterableOnce[A] with IterableLike[A, Iterable] { /** The collection itself */ protected def coll: this.type = this - } + } - /** Base trait for sequence collections */ - trait Seq[+A] extends Iterable[A] with SeqLike[A, Seq] { - def apply(i: Int): A + /** A trait representing indexable collections with finite length */ + trait ArrayLike[+A] extends Any { def length: Int + def apply(i: Int): A } + /** Base trait for sequence collections */ + trait Seq[+A] extends Iterable[A] with SeqLike[A, Seq] with ArrayLike[A] + /** Base trait for linearly accessed sequences that have efficient `head` and * `tail` operations. * Known subclasses: List, LazyList @@ -157,6 +160,8 @@ object CollectionStrawMan6 extends LowPriority { } } + type IndexedSeq[+A] = Seq[A] { def view: IndexedView[A] } + /** Base trait for strict collections that can be built using a builder. * @param A the element type of the collection * @param Repr the type of the underlying collection @@ -594,6 +599,7 @@ object CollectionStrawMan6 extends LowPriority { } class ArrayBufferView[A](val elems: Array[AnyRef], val start: Int, val end: Int) extends IndexedView[A] { + def length = end - start def apply(n: Int) = elems(start + n).asInstanceOf[A] override def className = "ArrayBufferView" } @@ -657,7 +663,8 @@ object CollectionStrawMan6 extends LowPriority { extends AnyVal with IterableOps[Char] with SeqMonoTransforms[Char, String] with IterablePolyTransforms[Char, List] - with Buildable[Char, String] { + with Buildable[Char, String] + with ArrayLike[Char] { protected def coll = new StringView(s) def iterator = coll.iterator @@ -672,6 +679,9 @@ object CollectionStrawMan6 extends LowPriority { protected[this] def newBuilder = new StringBuilder + def length = s.length + def apply(i: Int) = s.charAt(i) + override def knownSize = s.length override def className = "String" @@ -721,8 +731,7 @@ object CollectionStrawMan6 extends LowPriority { } case class StringView(s: String) extends IndexedView[Char] { - val start = 0 - val end = s.length + def length = s.length def apply(n: Int) = s.charAt(n) override def className = "StringView" } @@ -732,11 +741,15 @@ object CollectionStrawMan6 extends LowPriority { implicit class ArrayOps[A](val xs: Array[A]) extends AnyVal with IterableOps[A] with SeqMonoTransforms[A, Array[A]] - with Buildable[A, Array[A]] { + with Buildable[A, Array[A]] + with ArrayLike[A] { protected def coll = new ArrayView(xs) def iterator = coll.iterator + def length = xs.length + def apply(i: Int) = xs.apply(i) + override def view = new ArrayView(xs) def elemTag: ClassTag[A] = ClassTag(xs.getClass.getComponentType) @@ -758,8 +771,7 @@ object CollectionStrawMan6 extends LowPriority { } case class ArrayView[A](xs: Array[A]) extends IndexedView[A] { - val start = 0 - val end = xs.length + def length = xs.length def apply(n: Int) = xs(n) override def className = "ArrayView" } @@ -823,15 +835,17 @@ 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) + protected val normN = n max 0 override def knownSize = - if (underlying.knownSize >= 0) underlying.knownSize - n max 0 else -1 + if (underlying.knownSize >= 0) (underlying.knownSize - normN) 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) + protected val normN = n max 0 override def knownSize = - if (underlying.knownSize >= 0) underlying.knownSize min n else -1 + if (underlying.knownSize >= 0) underlying.knownSize min normN else -1 } /** A view that maps elements of the underlying collection. */ @@ -873,14 +887,11 @@ object CollectionStrawMan6 extends LowPriority { } /** View defined in terms of indexing a range */ - trait IndexedView[+A] extends View[A] { self => - def start: Int - def end: Int - def apply(i: Int): A + trait IndexedView[+A] extends View[A] with ArrayLike[A] { def iterator: Iterator[A] = new Iterator[A] { - private var current = start - def hasNext = current < end + private var current = 0 + def hasNext = current < length def next: A = { val r = apply(current) current += 1 @@ -888,14 +899,39 @@ object CollectionStrawMan6 extends LowPriority { } } - def reverse = new IndexedView[A] { - def start = self.start - def end = self.end - def apply(i: Int) = self.apply(end - 1 - i) + override def take(n: Int): IndexedView[A] = new IndexedView.Take(this, n) + override def drop(n: Int): IndexedView[A] = new IndexedView.Drop(this, n) + override def map[B](f: A => B): IndexedView[B] = new IndexedView.Map(this, f) + def reverse: IndexedView[A] = new IndexedView.Reverse(this) + } + + object IndexedView { + + class Take[A](underlying: IndexedView[A], n: Int) + extends View.Take(underlying, n) with IndexedView[A] { + override def iterator = super.iterator + def length = underlying.length min normN + def apply(i: Int) = underlying.apply(i) } - def length = end - start max 0 - override def knownSize = length + class Drop[A](underlying: IndexedView[A], n: Int) + extends View.Take(underlying, n) with IndexedView[A] { + override def iterator = super.iterator + def length = (underlying.length - normN) max 0 + def apply(i: Int) = underlying.apply(i + normN) + } + + class Map[A, B](underlying: IndexedView[A], f: A => B) + extends View.Map(underlying, f) with IndexedView[B] { + override def iterator = super.iterator + def length = underlying.length + def apply(n: Int) = f(underlying.apply(n)) + } + + case class Reverse[A](underlying: IndexedView[A]) extends IndexedView[A] { + def length = underlying.length + def apply(i: Int) = underlying.apply(length - 1 - i) + } } /* ---------- Iterators ---------------------------------------------------*/ @@ -1003,8 +1039,7 @@ object CollectionStrawMan6 extends LowPriority { def next = throw new NoSuchElementException("next on empty iterator") } def apply[A](xs: A*): Iterator[A] = new IndexedView[A] { - val start = 0 - val end = xs.length + val length = xs.length def apply(n: Int) = xs(n) }.iterator } -- cgit v1.2.3