diff options
author | Martin Odersky <odersky@gmail.com> | 2008-12-09 17:40:50 +0000 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2008-12-09 17:40:50 +0000 |
commit | f83d8977544ec7fc3eed59e032e3705f30290c00 (patch) | |
tree | 2109641f8f4d84630726637ed480e0512c99e1d5 /src/library/scalax/collection/immutable/Stream.scala | |
parent | 4d32e17513cf46b786eef8523653ac366c73a09c (diff) | |
download | scala-f83d8977544ec7fc3eed59e032e3705f30290c00.tar.gz scala-f83d8977544ec7fc3eed59e032e3705f30290c00.tar.bz2 scala-f83d8977544ec7fc3eed59e032e3705f30290c00.zip |
updates to scalax collections and standard libr...
updates to scalax collections and standard library classes.
Diffstat (limited to 'src/library/scalax/collection/immutable/Stream.scala')
-rwxr-xr-x | src/library/scalax/collection/immutable/Stream.scala | 790 |
1 files changed, 790 insertions, 0 deletions
diff --git a/src/library/scalax/collection/immutable/Stream.scala b/src/library/scalax/collection/immutable/Stream.scala new file mode 100755 index 0000000000..6b4a8a60f6 --- /dev/null +++ b/src/library/scalax/collection/immutable/Stream.scala @@ -0,0 +1,790 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Stream.scala 16287 2008-10-18 13:41:36Z nielsen $ + + +package scalax.collection.immutable + +import mutable.ListBuffer +import generic.covariant.{SequenceTemplate, SequenceFactory} + +/** + * The object <code>Stream</code> provides helper functions + * to manipulate streams. + * + * @author Martin Odersky, Matthias Zenger + * @version 1.1 08/08/03 + */ +object Stream extends SequenceFactory[Stream] { + + import collection.{Iterable, OrderedIterable, Sequence, Vector} + + override val empty: Stream[Nothing] = Nil + override def apply[A](xs: A*) = xs.asInstanceOf[Iterable[A]].toList // !@! + override def newBuilder[B]: Builder[Stream, B] = new ListBuffer[B] + + class ConsWrapper[A](tl: => Stream[A]) { + def #::(hd: A): Stream[A] = new Cons(hd, tl) + def #:::(prefix: Stream[A]): Stream[A] = prefix append tl + } + + implicit def consWrapper[A](stream: => Stream[A]): ConsWrapper[A] = + new ConsWrapper[A](stream) + + object #:: { + def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] = + if (xs.isEmpty) None + else Some(xs.head, xs.tail) + } + + /** @deprecated use #:: instead */ + @deprecated lazy val lazy_:: = #:: + + /** An alternative way of building and matching Streams using Stream.cons(hd, tl). + */ + object cons { + + /** A stream consisting of a given first element and remaining elements + * @param hd The first element of the result stream + * @param tl The remaining elements of the result stream + */ + def apply[A](hd: A, tl: => Stream[A]) = new Cons(hd, tl) + + /** Maps a stream to its head and tail */ + def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] = #::.unapply(xs) + } + + final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A] { + override def isEmpty = false + override def head = hd + private[this] var tlVal: Stream[A] = _ + private def tlDefined = tlVal ne null + override def tail: Stream[A] = { + if (!tlDefined) { tlVal = tl } + tlVal + } + override def hasDefiniteSize = tlDefined && tlVal.hasDefiniteSize + + // Overridden methods from IterableTemplate or overloaded variants of such methods + + /** Create a new stream which contains all elements of this stream + * followed by all elements of Iterable `that' + */ + override def ++[B >: A](that: Iterable[B]): Stream[B] = this append that + + /** Create a new stream which contains all elements of this stream + * followed by all elements of Iterator `that' + */ + override def ++[B >: A](that: Iterator[B]): Stream[B] = this append that.toStream + + /** Returns the stream resulting from applying the given function + * <code>f</code> to each element of this stream. + * + * @param f function to apply to each element. + * @return <code>f(a<sub>0</sub>), ..., f(a<sub>n</sub>)</code> if this + * sequence is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>. + */ + override def map[B](f: A => B): Stream[B] = + new Cons(f(head), tail map f) + + /** Applies the given function <code>f</code> to each element of + * this stream, then concatenates the results. + * + * @param f the function to apply on each element. + * @return <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if + * this stream is <code>[a<sub>0</sub>, ..., a<sub>n</sub>]</code>. + */ + override def flatMap[B](f: A => Iterable[B]): Stream[B] = { + // drops A's for which f yields an empty Iterable[B] + def loop(s: Stream[A]): Stream[B] = + if (s.isEmpty) Nil + else { + val i = f(s.head) + if (i.isEmpty) loop(s.tail) + else i.toStream append loop(s.tail) + } + loop(this) + } + + /** Returns all the elements of this stream that satisfy the + * predicate <code>p</code>. The order of the elements is preserved. + * + * @param p the predicate used to filter the stream. + * @return the elements of this stream satisfying <code>p</code>. + */ + override def filter(p: A => Boolean): Stream[A] = { + // drops A's for which p yields false + def loop(s: Stream[A]): Stream[A] = + if (s.isEmpty) Nil + else { + val b = p(s.head) + if (!b) loop(s.tail) + else new Cons(s.head, tail filter p) + } + loop(this) + } + + /** Returns all the elements of this stream that satisfy the + * predicate <code>p</code>. The order of the elements is preserved. + * + * @param p the predicate used to filter the stream. + * @return the elements of this stream satisfying <code>p</code>. + */ + override def partition(p: A => Boolean): (Stream[A], Stream[A]) = (filter(p(_)), remove(p(_))) + + /** Returns a stream formed from this stream and the specified stream + * <code>that</code> by associating each element of the former with + * the element at the same position in the latter. + * If one of the two streams is longer than the other, its remaining elements are ignored. + * + * @return <code>Stream({a<sub>0</sub>,b<sub>0</sub>}, ..., + * {a<sub>min(m,n)</sub>,b<sub>min(m,n)</sub>)}</code> when + * <code>Stream(a<sub>0</sub>, ..., a<sub>m</sub>) + * zip Stream(b<sub>0</sub>, ..., b<sub>n</sub>)</code> is invoked. + */ + def zip[B](that: Stream[B]): Stream[(A, B)] = + if (that.isEmpty) empty + else new Cons((this.head, that.head), this.tail zip that.tail) + + /** Returns a list formed from this list and the specified list + * <code>that</code> by associating each element of the former with + * the element at the same position in the latter. + * + * @param that list <code>that</code> may have a different length + * as the self list. + * @param thisElem element <code>thisElem</code> is used to fill up the + * resulting list if the self list is shorter than + * <code>that</code> + * @param thatElem element <code>thatElem</code> is used to fill up the + * resulting list if <code>that</code> is shorter than + * the self list + * @return <code>List((a<sub>0</sub>,b<sub>0</sub>), ..., + * (a<sub>n</sub>,b<sub>n</sub>), (elem,b<sub>n+1</sub>), + * ..., {elem,b<sub>m</sub>})</code> + * when <code>[a<sub>0</sub>, ..., a<sub>n</sub>] zip + * [b<sub>0</sub>, ..., b<sub>m</sub>]</code> is + * invoked where <code>m > n</code>. + */ + def zipAll[B, A1 >: A, B1 >: B](that: Stream[B], thisElem: A1, thatElem: B1): Stream[(A1, B1)] = { + if (that.isEmpty) new Cons((this.head, thatElem), this.tail.zipAll(that, thisElem, thatElem)) + else new Cons((this.head, that.head), this.tail.zipAll(that.tail, thisElem, thatElem)) + } + + /** Zips this iterable with its indices. `s.zipWithIndex` is equivalent to + * `s zip s.indices` + */ + override def zipWithIndex = this zip (Iterator.from(0).toStream) + + /** Write all defined elements of this iterable into given string builder. + * The written text begins with the string <code>start</code> and is finished by the string + * <code>end</code>. Inside, the string representations of defined elements (w.r.t. + * the method <code>toString()</code>) are separated by the string + * <code>sep</code>. The method will not force evaluation of undefined elements. A + * tail of such elements will be represented by a "?" instead. + */ + override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = { + b append start append hd + if (tlDefined) tlVal.addString(b, sep, sep, end) + else b append ", ?" append end + } + + /** Returns the <code>n</code> first elements of this stream, or else the whole + * stream, if it has less than <code>n</code> elements. + * + * @param n the number of elements to take. + * @return the <code>n</code> first elements of this stream. + */ + override def take(n: Int): Stream[A] = + if (n <= 0) Nil else new Cons(head, tail take (n-1)) + + /** Returns the stream without its <code>n</code> first elements. + * If the stream has less than <code>n</code> elements, the empty stream is returned. + * + * @param n the number of elements to drop. + * @return the stream without its <code>n</code> first elements. + */ + override def drop(n: Int): Stream[A] = { + var these: Stream[A] = this + var i = n + while (!these.isEmpty && i > 0) { + these = these.tail + i -= 1 + } + these + } + + /** A substream starting at index `from` + * and extending up to (but not including) index `until`. + * + * @This is equivalent to (but possibly more efficient than) + * c.drop(from).take(to - from) + * + * @param from The index of the first element of the returned subsequence + * @param until The index of the element following the returned subsequence + * @throws IndexOutOfBoundsException if <code>from < 0</code> + * or <code>length < from + len<code> + * @note Might return different results for different runs, unless this iterable is ordered + */ + override def slice(from: Int, to: Int): Stream[A] = + this.drop(from).take(to - from) + + /** The stream without its last element. + * @throws Predef.UnsupportedOperationException if the stream is empty. + */ + override def init: Stream[A] = + if (tail.isEmpty) Nil + else new Cons(head, tail.init) + + /** Returns the rightmost <code>n</code> elements from this iterable. + * @param n the number of elements to take + */ + override def takeRight(n: Int): Stream[A] = { + var these: Stream[A] = this + var lead = this drop n + while (!lead.isEmpty) { + these = these.tail + lead = lead.tail + } + these + } + + /** Returns the longest prefix of this stream whose elements satisfy + * the predicate <code>p</code>. + * + * @param p the test predicate. + */ + override def takeWhile(p: A => Boolean): Stream[A] = + if (p(head)) new Cons(head, tail takeWhile p) else Nil + + + /** Returns the longest suffix of this iterable whose first element + * does not satisfy the predicate <code>p</code>. + * + * @param p the test predicate. + */ + override def dropWhile(p: A => Boolean): Stream[A] = { + var these: Stream[A] = this + while (!these.isEmpty && p(these.head)) these = these.tail + these + } + + /** Returns a pair consisting of the longest prefix of the stream whose + * elements all satisfy the given predicate, and the rest of the stream. + * + * @param p the test predicate + */ + override def span(p: A => Boolean): (List[A], Stream[A]) = { + var these: Stream[A] = this + val l = new ListBuffer[A] + while (!these.isEmpty && p(these.head)) { + l += these.head + these = these.tail + } + (l.toList, these) + } + + // Overridden methods from Sequence + + /** Builds a new stream from this stream in which any duplicates (wrt to ==) removed. + * Among duplicate elements, only the first one is retained in the result stream + */ + override def removeDuplicates: Stream[A] = + new Cons(head, tail.filter(head !=).removeDuplicates) + + /** Returns a new sequence of given length containing the elements of this sequence followed by zero + * or more occurrences of given elements. + */ + override def padTo[B >: A](len: Int, elem: B): Stream[B] = + new Cons(head, tail.padTo(len - 1, elem)) + } + + /** + * Create an infinite stream starting at <code>start</code> + * and incrementing by step <code>step</code> + * + * @param start the start value of the stream + * @param step the increment value of the stream + * @return the stream starting at value <code>start</code>. + */ + def from(start: Int, step: Int): Stream[Int] = + new Cons(start, from(start+step, step)) + + /** + * Create an infinite stream starting at <code>start</code> + * and incrementing by 1. + * + * @param start the start value of the stream + * @return the stream starting at value <code>start</code>. + */ + def from(start: Int): Stream[Int] = from(start, 1) + + /** + * Create an infinite stream containing the given element expression (which is computed for each + * occurrence) + * @param elem the element composing the resulting stream + * @return the stream containing an inifinite number of elem + * @deprecated use fill instead + */ + @deprecated def fill[A](elem: => A): Stream[A] = new Cons(elem, fill(elem)) + + /** A stream containing all elements of a given iterator, in the order they are produced. + * @param it The iterator producing the stream's elements + * @deprecated use it.toStream instead + */ + @deprecated def fromIterator[A](it: Iterator[A]): Stream[A] = + if (it.hasNext) cons(it.next, fromIterator(it)) else empty + + /** The concatenation of a sequence of streams + * @deprecated use xs.flatten instead + */ + @deprecated def concat[A](xs: Iterable[Stream[A]]): Stream[A] = concat(xs.elements) + + /** The concatenation of all streams returned by an iterator + * @deprecated use xs.toStream.flatten instead + */ + @deprecated def concat[A](xs: Iterator[Stream[A]]): Stream[A] = + if (xs.hasNext) xs.next append concat(xs) + else empty + + /** + * Create a stream with element values + * <code>v<sub>n+1</sub> = step(v<sub>n</sub>)</code> + * where <code>v<sub>0</sub> = start</code> + * and elements are in the range between <code>start</code> (inclusive) + * and <code>end</code> (exclusive) + * @deprecated use @see iterate instead. + * @param start the start value of the stream + * @param end the end value of the stream + * @param step the increment function of the stream, must be monotonically increasing or decreasing + * @return the stream starting at value <code>start</code>. + */ + @deprecated def range(start: Int, end: Int, step: Int => Int): Stream[Int] = { + val up = step(start) > start + val down = step(start) < start + def loop(lo: Int): Stream[Int] = + if ((!up || lo < end) && (!down || lo > end)) cons(lo, loop(step(lo))) + else empty + loop(start) + } + + /** + * Create an infinite stream containing the given element. + * + * @param elem the element composing the resulting stream + * @return the stream containing an inifinite number of elem + * @deprecated use fill(elem) instead + */ + @deprecated def const[A](elem: A): Stream[A] = cons(elem, const(elem)) + + /** Create a stream containing several copies of an element. + * + * @param n the length of the resulting stream + * @param elem the element composing the resulting stream + * @return the stream composed of n elements all equal to elem + * @deprecated use fill(n, elem) instead + */ + @deprecated def make[A](n: Int, elem: A): Stream[A] = + const(elem) take n +} + +import Stream._ + +/** + * <p>The class <code>Stream</code> implements lazy lists where elements + * are only evaluated when they are needed. Here is an example:</p> + * <pre> + * <b>object</b> Main <b>extends</b> Application { + * + * <b>def</b> from(n: Int): Stream[Int] = + * Stream.cons(n, from(n + 1)) + * + * <b>def</b> sieve(s: Stream[Int]): Stream[Int] = + * Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 })) + * + * <b>def</b> primes = sieve(from(2)) + * + * primes take 10 print + * } + * </pre> + * + * @author Martin Odersky, Matthias Zenger + * @version 1.1 08/08/03 + */ +abstract class Stream[+A] extends Sequence[A] with SequenceTemplate[Stream, A] { +self => + + import collection.{Iterable, OrderedIterable, Sequence, Vector} + + /** is this stream empty? */ + def isEmpty: Boolean + + /** The first element of this stream + * @throws Predef.NoSuchElementException if the stream is empty. + */ + def head: A + + /** A stream consisting of the remaining elements of this stream after the first one. + * @throws Predef.UnsupportedOperationException if the stream is empty. + */ + def tail: Stream[A] + + // Implementation of abstract methods + + /** Create a new @see LazyBuilder to build a stream */ + def newBuilder[B]: Builder[Stream, B] = new LazyBuilder[Stream, B] { + def result: Stream[B] = elements.toStream + } + + /** Returns the number of elements in the list. + */ + def length: Int = { + var these = self + var len = 0 + while (!these.isEmpty) { + len += 1 + these = these.tail + } + len + } + + /** Returns the <code>n</code>-th element of this stream. The first element + * (head of the stream) is at position 0. + * + * @param n index of the element to return + * @return the element at position <code>n</code> in this stream. + * @throws Predef.NoSuchElementException if the stream is too short. + */ + override def apply(n: Int): A = drop(n).head + + // New methods in Stream + + /** The stream resulting from the concatenation of this stream with the argument stream. + * @param rest The stream that gets appended to this stream + */ + def append[B >: A](rest: => Iterable[B]): Stream[B] = + if (isEmpty) rest.toStream else new Cons(head, tail append rest) + + /** Force evaluation of the whole stream and return it */ + def force: Stream[A] = { + var these = this + while (!isEmpty) these = these.tail + this + } + + /** Prints elements of this stream one by one, separated by commas */ + def print() { print(", ") } + + /** Prints elements of this stream one by one, separated by <code>sep</code> + * @param sep The separator string printed between consecutive elements. + */ + def print(sep: String) { + def loop(these: Stream[A], start: String) { + Console.print(start) + if (isEmpty) Console.print("empty") + else { + Console.print(these.head) + loop(these.tail, sep) + } + } + loop(this, "") + } + + // Overridden methods from IterableTemplate or overloaded variants of such methods + + /** Returns the elements in the sequence as an iterator + */ + override def elements: Iterator[A] = new Iterator[A] { + var these = self + def hasNext: Boolean = !these.isEmpty + def next: A = + if (hasNext) { + val result = these.head; these = these.tail; result + } else Iterator.empty.next + override def toList: List[A] = these.toList + } + + /** Apply the given function <code>f</code> to each element of this stream + * (while respecting the order of the elements). + * + * @param f the treatment to apply to each element. + */ + override def foreach(f: A => Unit) { + var these = this + while (!these.isEmpty) { + f(these.head) + these = these.tail + } + } + + /** Tests if the predicate <code>p</code> is satisfied by all elements + * in this list. + * + * !!! todo: perform speed with inherited version from Iterable, and drop + * if not significantly better + * @param p the test predicate. + * @return <code>true</code> iff all elements of this list satisfy the + * predicate <code>p</code>. + */ + override def forall(p: A => Boolean): Boolean = { + var these = this + while (!these.isEmpty) { + if (!p(these.head)) return false + these = these.tail + } + true + } + + /** Tests the existence in this list of an element that satisfies the + * predicate <code>p</code>. + * + * !!! todo: perform speed with inherited version from Iterable, and drop + * if not significantly better + * @param p the test predicate. + * @return <code>true</code> iff there exists an element in this list that + * satisfies the predicate <code>p</code>. + */ + override def exists(p: A => Boolean): Boolean = { + var these = this + while (!these.isEmpty) { + if (p(these.head)) return true + these = these.tail + } + false + } + + /** Count the number of elements in the iterable which satisfy a predicate. + * + * !!! todo: perform speed with inherited version from Iterable, and drop + * if not significantly better + * @param p the predicate for which to count + * @return the number of elements satisfying the predicate <code>p</code>. + */ + override 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 + } + + /** Find and return the first element of the list satisfying a + * predicate, if any. + * + * !!! todo: perform speed with inherited version from Iterable, and drop + * if not significantly better + * @param p the predicate + * @return the first element in the list satisfying <code>p</code>, + * or <code>None</code> if none exists. + */ + override 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 + } + + /** Combines the elements of this list together using the binary + * function <code>f</code>, from left to right, and starting with + * the value <code>z</code>. + * + * !!! todo: perform speed with inherited version from Iterable, and drop + * if not significantly better + * @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...), + * a<sub>n</sub>)</code> if the list is + * <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>. + */ + override 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 + } + + /** Combines the elements of this list together using the binary + * function <code>f</code>, from right to left, and starting with + * the value <code>z</code>. + * + * @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code> + * if the list is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>. + */ + override def foldRight[B](z: B)(f: (A, B) => B): B = + if (this.isEmpty) z + else f(head, tail.foldRight(z)(f)) + + /** Combines the elements of this list together using the binary + * operator <code>op</code>, from left to right + * @param op The operator to apply + * @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code> + if the list has elements + * <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>. + * @throws Predef.UnsupportedOperationException if the list is empty. + */ + override def reduceLeft[B >: A](f: (B, A) => B): B = + if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft") + else tail.foldLeft[B](head)(f) + + /** Combines the elements of this iterable object together using the binary + * operator <code>op</code>, from right to left + * @note Will not terminate for infinite-sized collections. + * @param op The operator to apply + * + * @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code> + * if the iterable object has elements <code>a<sub>0</sub>, a<sub>1</sub>, ..., + * a<sub>n</sub></code>. + * + * @throws Predef.UnsupportedOperationException if the iterator is empty. + */ + override 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)) + + /** + * Create a stream which contains all the elements of this iterable object. + * @note consider using <code>projection</code> for lazy behavior. + */ + override def toStream: Stream[A] = this + + /** Defines the prefix of this object's <code>toString</code> representation as ``Stream''. + */ + override def stringPrefix = "Stream" + + /** The last element of this stream. + * + * @throws Predef.NoSuchElementException if the stream is empty. + */ + override 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 + } + + /** Returns the rightmost <code>n</code> elements from this iterable. + * @param n the number of elements to take + */ + override def dropRight(n: Int): List[A] = { + val b = new ListBuffer[A] + var these = this + var lead = this drop n + while (!lead.isEmpty) { + b += these.head + these = these.tail + lead = lead.tail + } + b.toList + } + + /** Returns true iff the other stream contains the same elements as this one. + * + * @note will not terminate for two infinite-sized streams. + * @param that the other stream + */ + def sameElements[B >: A](that: Stream[B]): Boolean = { + val these = this + val those = that + while (!these.isEmpty && !those.isEmpty && these.head == those.head) {} + these.isEmpty && those.isEmpty + } + + // Overridden methods from Sequence + + /** Result of comparing <code>length</code> with operand <code>len</code>. + * returns <code>x</code> where + * <code>x < 0</code> iff <code>this.length < len</code> + * <code>x == 0</code> iff <code>this.length == len</code> + * <code>x > 0</code> iff <code>this.length > len</code>. + */ + override def lengthCompare(len: Int): Int = { + var i = 0 + var these = self + while (!these.isEmpty && i <= len) { + i += 1 + these = these.tail + } + i - len + } + + /** Is this partial function defined for the index <code>x</code>? + */ + override def isDefinedAt(x: Int): Boolean = x >= 0 && lengthCompare(x) >= 0 + + /** Returns length of longest segment starting from a start index `from` + * such that every element of the segment satisfies predicate `p`. + * @note may not terminate for infinite-sized collections. + * @param p the predicate + * @param from the start index + */ + override def segmentLength(p: A => Boolean, from: Int): Int = { + var i = from + var these = this drop from + while (!these.isEmpty && p(these.head)) { + i += 1 + these = these.tail + } + i + } + + /** Returns index of the first element starting from a start index + * satisying a predicate, or -1, if none exists. + * + * @note may not terminate for infinite-sized streams. + * @param p the predicate + * @param from the start index + */ + override def indexWhere(p: A => Boolean, from: Int): Int = { + var i = from + var these = this drop from + while (!these.isEmpty && !p(these.head)) { + i += 1 + these = these.tail + } + if (these.isEmpty) -1 else i + } + + /** Returns index of the last element satisying a predicate, or -1, if none exists. + * + * @param p the predicate + * @return the index of the last element satisfying <code>p</code>, + * or -1 if such an element does not exist + */ + override 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 + } + i + } + + /** A list consisting of all elements of this list in reverse order. + */ + override def reverse: List[A] = { + var result: List[A] = Nil + var these = this + while (!these.isEmpty) { + result = these.head :: result + these = these.tail + } + result + } +} + |