diff options
Diffstat (limited to 'src/library/scala/collection/LinearSeqLike.scala')
-rw-r--r-- | src/library/scala/collection/LinearSeqLike.scala | 285 |
1 files changed, 9 insertions, 276 deletions
diff --git a/src/library/scala/collection/LinearSeqLike.scala b/src/library/scala/collection/LinearSeqLike.scala index 665b760932..1c99d4a3d9 100644 --- a/src/library/scala/collection/LinearSeqLike.scala +++ b/src/library/scala/collection/LinearSeqLike.scala @@ -19,12 +19,16 @@ import scala.util.control.Breaks._ /** A template trait for linear sequences of type `LinearSeq[A]`. * * $linearSeqInfo + * + * This trait just implements `iterator` + * in terms of `isEmpty, ``head`, and `tail`. + * However, see `LinearSeqOptimized` for an implementation trait that overrides operations + * to make them run faster under the assumption of fast linear access with `head` and `tail`. + * * @author Martin Odersky - * @author Matthias Zenger - * @version 1.0, 16/07/2003 + * @version 2.8 * @since 2.8 * - * @define Coll LinearSeq * @define linearSeqInfo * Linear sequences are defined in terms of three abstract methods, which are assumed * to have efficient implementations. These are: @@ -35,9 +39,8 @@ import scala.util.control.Breaks._ * }}} * Here, `A` is the type of the sequence elements and `Repr` is the type of the sequence itself. * - * Linear sequences do not define any new methods wrt `Seq`. However, abstract `Seq` methods - * are defined in terms of `isEmpty`, `head`, and `tail`, and several other methods are overridden - * with optimized implementations. + * Linear sequences do not add any new methods to `Seq`, but promise efficient implementations + * of linear access patterns. * * @tparam A the element type of the $coll * @tparam Repr the type of the actual $coll containing the elements. @@ -47,38 +50,6 @@ trait LinearSeqLike[+A, +Repr <: LinearSeqLike[A, Repr]] extends SeqLike[A, Repr override protected[this] def thisCollection: LinearSeq[A] = this.asInstanceOf[LinearSeq[A]] override protected[this] def toCollection(repr: Repr): LinearSeq[A] = repr.asInstanceOf[LinearSeq[A]] - def isEmpty: Boolean - - def head: A - - def tail: Repr - - /** The length of the $coll. - * - * $willNotTerminateInf - * - * Note: the execution of `length` may take time proportial to the length of the sequence. - */ - def length: Int = { - var these = self - var len = 0 - while (!these.isEmpty) { - len += 1 - these = these.tail - } - len - } - - /** Selects an element by its index in the $coll. - * Note: the execution of `apply` may take time proportial to the index value. - * @throws `IndexOutOfBoundsEsxception` if `idx` does not satisfy `0 <= idx < length`. - */ - def apply(n: Int): A = { - val rest = drop(n) - if (n < 0 || rest.isEmpty) throw new IndexOutOfBoundsException - rest.head - } - override /*IterableLike*/ def iterator: Iterator[A] = new Iterator[A] { var these = self @@ -89,242 +60,4 @@ trait LinearSeqLike[+A, +Repr <: LinearSeqLike[A, Repr]] extends SeqLike[A, Repr } else Iterator.empty.next override def toList: List[A] = these.toList } - - override /*IterableLike*/ - def foreach[B](f: A => B) { - var these = this - while (!these.isEmpty) { - f(these.head) - these = these.tail - } - } - - - override /*IterableLike*/ - def forall(p: A => Boolean): Boolean = { - var these = this - while (!these.isEmpty) { - if (!p(these.head)) return false - these = these.tail - } - true - } - - override /*IterableLike*/ - def exists(p: A => Boolean): Boolean = { - var these = this - while (!these.isEmpty) { - if (p(these.head)) return true - these = these.tail - } - false - } - - override /*TraversableLike*/ - def count(p: A => Boolean): Int = { - var these = this - var cnt = 0 - while (!these.isEmpty) { - if (p(these.head)) cnt += 1 - these = these.tail - } - cnt - } - - override /*IterableLike*/ - def find(p: A => Boolean): Option[A] = { - var these = this - while (!these.isEmpty) { - if (p(these.head)) return Some(these.head) - these = these.tail - } - None - } -/* - override def mapFind[B](f: A => Option[B]): Option[B] = { - var res: Option[B] = None - var these = this - while (res.isEmpty && !these.isEmpty) { - res = f(these.head) - these = these.tail - } - res - } -*/ - override /*TraversableLike*/ - def foldLeft[B](z: B)(f: (B, A) => B): B = { - var acc = z - var these = this - while (!these.isEmpty) { - acc = f(acc, these.head) - these = these.tail - } - acc - } - - override /*IterableLike*/ - def foldRight[B](z: B)(f: (A, B) => B): B = - if (this.isEmpty) z - else f(head, tail.foldRight(z)(f)) - - override /*TraversableLike*/ - def reduceLeft[B >: A](f: (B, A) => B): B = - if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft") - else tail.foldLeft[B](head)(f) - - override /*IterableLike*/ - def reduceRight[B >: A](op: (A, B) => B): B = - if (isEmpty) throw new UnsupportedOperationException("Nil.reduceRight") - else if (tail.isEmpty) head - else op(head, tail.reduceRight(op)) - - override /*TraversableLike*/ - def last: A = { - if (isEmpty) throw new NoSuchElementException - var these = this - var nx = these.tail - while (!nx.isEmpty) { - these = nx - nx = nx.tail - } - these.head - } - - override /*IterableLike*/ - def take(n: Int): Repr = { - val b = newBuilder - var i = 0 - var these = repr - while (!these.isEmpty && i < n) { - i += 1 - b += these.head - these = these.tail - } - b.result - } - - override /*TraversableLike*/ - def drop(n: Int): Repr = { - var these: Repr = repr - var count = n - while (!these.isEmpty && count > 0) { - these = these.tail - count -= 1 - } - these - } - - override /*IterableLike*/ - def dropRight(n: Int): Repr = { - val b = newBuilder - var these = this - var lead = this drop n - while (!lead.isEmpty) { - b += these.head - these = these.tail - lead = lead.tail - } - b.result - } - - override /*IterableLike*/ - def slice(from: Int, until: Int): Repr = { - val b = newBuilder - var i = from - var these = this drop from - while (i < until && !these.isEmpty) { - b += these.head - these = these.tail - i += 1 - } - b.result - } - - override /*IterableLike*/ - def takeWhile(p: A => Boolean): Repr = { - val b = newBuilder - var these = this - while (!these.isEmpty && p(these.head)) { - b += these.head - these = these.tail - } - b.result - } - - override /*TraversableLike*/ - def span(p: A => Boolean): (Repr, Repr) = { - var these: Repr = repr - val b = newBuilder - while (!these.isEmpty && p(these.head)) { - b += these.head - these = these.tail - } - (b.result, these) - } - - override /*IterableLike*/ - def sameElements[B >: A](that: Iterable[B]): Boolean = that match { - case that1: LinearSeq[_] => - var these = this - var those = that1 - while (!these.isEmpty && !those.isEmpty && these.head == those.head) { - these = these.tail - those = those.tail - } - these.isEmpty && those.isEmpty - case _ => - super.sameElements(that) - } - - override /*SeqLike*/ - def lengthCompare(len: Int): Int = { - var i = 0 - var these = self - while (!these.isEmpty && i <= len) { - i += 1 - these = these.tail - } - i - len - } - - override /*SeqLike*/ - def isDefinedAt(x: Int): Boolean = x >= 0 && lengthCompare(x) > 0 - - override /*SeqLike*/ - def segmentLength(p: A => Boolean, from: Int): Int = { - var i = 0 - var these = this drop from - while (!these.isEmpty && p(these.head)) { - i += 1 - these = these.tail - } - i - } - - override /*SeqLike*/ - def indexWhere(p: A => Boolean, from: Int): Int = { - var i = from - var these = this drop from - while (these.nonEmpty) { - if (p(these.head)) - return i - - i += 1 - these = these.tail - } - -1 - } - - override /*SeqLike*/ - def lastIndexWhere(p: A => Boolean, end: Int): Int = { - var i = 0 - var these = this - var last = -1 - while (!these.isEmpty && i <= end) { - if (p(these.head)) last = i - these = these.tail - i += 1 - } - last - } } |