From af47e5b433ea538bf096a176c88f3c91116e09cd Mon Sep 17 00:00:00 2001 From: Antonio Cunei Date: Tue, 25 Nov 2008 18:05:48 +0000 Subject: Merging everything from the 2.8.x development b... Merging everything from the 2.8.x development branch back to trunk. - If you were working on trunk, please keep working on trunk If you were - working on 2.8-devel, please switch to trunk now --- .../generic/covartest/IterableFactory.scala | 108 +++ .../generic/covartest/IterableTemplate.scala | 816 +++++++++++++++++++++ .../generic/covartest/IterableView.scala | 121 +++ .../covartest/OrderedIterableTemplate.scala | 17 + .../generic/covartest/SequenceFactory.scala | 11 + .../generic/covartest/SequenceTemplate.scala | 382 ++++++++++ .../generic/covartest/SequenceView.scala | 129 ++++ .../generic/covartest/VectorTemplate.scala | 264 +++++++ 8 files changed, 1848 insertions(+) create mode 100755 src/library/scalax/collection/generic/covartest/IterableFactory.scala create mode 100755 src/library/scalax/collection/generic/covartest/IterableTemplate.scala create mode 100755 src/library/scalax/collection/generic/covartest/IterableView.scala create mode 100755 src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala create mode 100755 src/library/scalax/collection/generic/covartest/SequenceFactory.scala create mode 100755 src/library/scalax/collection/generic/covartest/SequenceTemplate.scala create mode 100755 src/library/scalax/collection/generic/covartest/SequenceView.scala create mode 100644 src/library/scalax/collection/generic/covartest/VectorTemplate.scala (limited to 'src/library/scalax/collection/generic/covartest') diff --git a/src/library/scalax/collection/generic/covartest/IterableFactory.scala b/src/library/scalax/collection/generic/covartest/IterableFactory.scala new file mode 100755 index 0000000000..d12da89987 --- /dev/null +++ b/src/library/scalax/collection/generic/covartest/IterableFactory.scala @@ -0,0 +1,108 @@ +package scalax.collection.generic.covartest + +trait IterableFactory[CC[A] <: Iterable[A]] { + + /** Create CC collection of specified elements */ + def apply[A](args: A*): CC[A] + + protected def newBuilder[A]: Builder[CC, A] = + apply().newBuilder[A].asInstanceOf[Builder[CC, A]] + + /** Concatenate all the argument lists into a single list. + * + * @param xss the lists that are to be concatenated + * @return the concatenation of all the lists + */ + def concat[A](xss: CC[A]*): CC[A] = { + val b = newBuilder[A] + for (xs <- xss) b ++= xs + b.result + } + + /** An iterable that contains the same element a number of times + * @param n The number of elements returned + * @param elem The element returned each time + */ + def fill[A](n: Int, elem: => A): CC[A] = { + val b = newBuilder[A] + var i = 0 + while (i < n) { + b += elem + i += 1 + } + b.result + } + + def fill[A](n1: Int, n2: Int, elem: => A): CC[CC[A]] = + tabulate(n1)(_ => fill(n2, elem)) + + def fill[A](n1: Int, n2: Int, n3: Int, elem: => A): CC[CC[CC[A]]] = + tabulate(n1)(_ => fill(n2, n3, elem)) + + def tabulate[A](n: Int)(f: Int => A): CC[A] = { + val b = newBuilder[A] + var i = 0 + while (i < n) { + b += f(i) + i += 1 + } + b.result + } + + def tabulate[A](n1: Int, n2: Int)(f: (Int, Int) => A): CC[CC[A]] = + tabulate(n1)(i1 => tabulate(n2)(i2 => f(i1, i2))) + + def tabulate[A](n1: Int, n2: Int, n3: Int)(f: (Int, Int, Int) => A): CC[CC[CC[A]]] = + tabulate(n1)(i1 => tabulate(n2)(i2 => tabulate(n3)(i3 => f(i1, i2, i3)))) +// todo: go up to 5(?) + + /** Create a sequence of increasing integers in a range. + * + * @param from the start value of the sequence + * @param end the end value of the sequence + * @return the sorted list of all from `from` (inclusive) + * up to, but exclusding, `end`. + */ + def range[A](start: Int, end: Int): CC[Int] = range(start, end, 1) + + /** Create a sequence of increasing integers in a range. + * + * @param from the start value of the sequence + * @param end the end value of the sequence + * @param step the increment value of successive elements + * @return a list of values from + n * step for + * increasing n. If `step > 0` the sequence terminates + * with the largest value less than `end`. If `step < 0` + * the sequence terminates with the smallest value greater than `end`. + * If `step == 0`, the sequence gors on infinitely (in that + * case the `range` operation might not terminate. + */ + def range(start: Int, end: Int, step: Int): CC[Int] = { + val b = newBuilder[Int] + var i = start + while ((step <= 0 || i < end) && (step >= 0 || i > end)) { + b += i + i += step + } + b.result + } + + /** Create a sequence by repeatedly applying a given function to a start value. + * + * @param start the start value of the sequence + * @param len the length of the sequence + * @param f the function that's repeatedly applied + * @return the sequence with elements (start, f(start), f(f(start)), ..., flen-1(start)) + */ + def iterate(start: Int, len: Int)(f: Int => Int): CC[Int] = { + val b = newBuilder[Int] + var acc = start + var i = 0 + while (i < len) { + b += acc + acc = f(acc) + i += 1 + } + b.result + } +} diff --git a/src/library/scalax/collection/generic/covartest/IterableTemplate.scala b/src/library/scalax/collection/generic/covartest/IterableTemplate.scala new file mode 100755 index 0000000000..b83f3b9247 --- /dev/null +++ b/src/library/scalax/collection/generic/covartest/IterableTemplate.scala @@ -0,0 +1,816 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $ + + +package scalax.collection.generic.covartest + +import scalax.collection.mutable.{Buffer, ArrayBuffer, ListBuffer} +import scalax.collection.immutable.{List, Nil, ::} +import util.control.Break._ +import Iterable._ + +/** Collection classes mixing in this class provide a method + * elements which returns an iterator over all the + * elements contained in the collection. + * + * @note If a collection has a known size, it should also sub-type Collection. + * Only potentially unbounded collections should directly sub-class Iterable. + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.8 + */ +trait IterableTemplate[+CC[+B] <: IterableTemplate[CC, B] with Iterable[B], +A] { self/*: CC[A]*/ => + + /** The template itself seen as an instance of `CC[A]`. + * @note: It would be logical to have a self type `CC[A]` instead, then we would not need + * this method. Unfortunately, tyis runs afoul some pecularities in Scala's member resolution + * algorithm: If the self type is a CC, then Iterable is one of its supertypes. Iterable + * defines a number of concrete methods such as newBuilder which are abstract here. + * The newBuilder method in Iterable[A] has type Builder[Iterable, A]. Because Scala + * prefers concrete over abstract members, it is this newBuilder which is chosen, instead of + * the abstract newBuilder in class IterableTemplate of type Builder[CC, A]. + * Even for concrete methods we have a problem because the last mixin in the parents of CC is + * Iterable, not IterableTemplate. So resolution picks the version in Iterable, which returns + * again an Iterable, not a CC, as would be required. + * These problems would be avoided if Scala computed the type of a member as the glb of the types + * all members in the class and its superclasses types. + * I think overall this would be a better design. + */ + protected[this] def thisCC: CC[A] = this.asInstanceOf[CC[A]] + + /** Creates a new iterator over all elements contained in this + * object. + * + * @return the new iterator + */ + def elements: Iterator[A] + + /** Create a new builder for this IterableType + */ + def newBuilder[B]: Builder[CC, B] + + /** Is this collection empty? */ + def isEmpty: Boolean = !elements.hasNext + + /** returns true iff this collection has a bound size. + * Many APIs in this trait will not work on collections of + * unbound sizes. + */ + def hasDefiniteSize = true + + /** Create a new sequence of type CC which contains all elements of this sequence + * followed by all elements of Iterable `that' + */ + def ++[B >: A](that: Iterable[B]): CC[B] = { + val b: Builder[CC, B] = (this: IterableTemplate[CC, A]).newBuilder[B] + b ++= thisCC + b ++= that + b.result + } + + /** Create a new sequence of type IterableType which contains all elements of this sequence + * followed by all elements of Iterator `that' + */ + def ++[B >: A](that: Iterator[B]): CC[B] = { + val b = newBuilder[B] + b ++= thisCC + b ++= that + b.result + } + + /** Returns the sequence resulting from applying the given function + * f to each element of this sequence. + * + * @param f function to apply to each element. + * @return f(a0), ..., f(an) if this + * sequence is a0, ..., an. + */ + def map[B](f: A => B): CC[B] = { + val b = newBuilder[B] + for (x <- this) b += f(x) + b.result + } + + /** Applies the given function f to each element of + * this sequence, then concatenates the results. + * + * @param f the function to apply on each element. + * @return f(a0) ::: ... ::: f(an) if + * this sequence is a0, ..., an. + */ + def flatMap[B](f: A => Iterable[B]): CC[B] = { + val b = newBuilder[B] + for (x <- this) b ++= f(x) + b.result + } + + /** Returns all the elements of this sequence that satisfy the + * predicate p. The order of the elements is preserved. + * @param p the predicate used to filter the list. + * @return the elements of this list satisfying p. + */ + def filter(p: A => Boolean): CC[A] = { + val b = newBuilder[A] + for (x <- this) + if (p(x)) b += x + b.result + } + + /** Removes all elements of the iterable which satisfy the predicate + * p. This is like filter with the + * predicate inversed. + * + * @param p the predicate to use to test elements + * @return the list without all elements which satisfy p + */ + def remove(p: A => Boolean): CC[A] = filter(!p(_)) + + /** Partitions this iterable in two iterables according to a predicate. + * + * @param p the predicate on which to partition + * @return a pair of iterables: the iterable that satisfies the predicate + * p and the iterable that does not. + * The relative order of the elements in the resulting iterables + * is the same as in the original iterable. + */ + def partition(p: A => Boolean): (CC[A], CC[A]) = { + val l, r = newBuilder[A] + for (x <- this) (if (p(x)) l else r) += x + (l.result, r.result) + } + + /** Apply a function f to all elements of this + * iterable object. + * + * @note Will not terminate for infinite-sized collections. + * @param f a function that is applied to every element. + * Note this function underlies the implementation of most other bulk operations. + * It should be overridden in concrete collectionc classes with efficient implementations. + */ + def foreach(f: A => Unit): Unit = elements.foreach(f) + + /** Return true iff the given predicate `p` yields true for all elements + * of this iterable. + * + * @note May not terminate for infinite-sized collections. + * @param p the predicate + */ + def forall(p: A => Boolean): Boolean = { + var result = true + breakable { + for (x <- this) + if (!p(x)) { result = false; break } + } + result + } + + /** Return true iff there is an element in this iterable for which the + * given predicate `p` yields true. + * + * @note May not terminate for infinite-sized collections. + * @param p the predicate + */ + def exists(p: A => Boolean): Boolean = { + var result = false + breakable { + for (x <- this) + if (p(x)) { result = true; break } + } + result + } + + /** Count the number of elements in the iterable which satisfy a predicate. + * + * @param p the predicate for which to count + * @return the number of elements satisfying the predicate p. + */ + def count(p: A => Boolean): Int = { + var cnt = 0 + for (x <- this) { + if (p(x)) cnt += 1 + } + cnt + } + + /** Find and return the first element of the iterable object satisfying a + * predicate, if any. + * + * @note may not terminate for infinite-sized collections. + * @param p the predicate + * @return an option containing the first element in the iterable object + * satisfying p, or None if none exists. + */ + def find(p: A => Boolean): Option[A] = { + var result: Option[A] = None + breakable { + for (x <- this) + if (p(x)) { result = Some(x); break } + } + result + } + + /** Combines the elements of this iterable object together using the binary + * function f, from left to right, and starting with + * the value z. + * + * @note Will not terminate for infinite-sized collections. + * @return f(... (f(f(z, a0), a1) ...), + * an) if the list is + * [a0, a1, ..., an]. + */ + def foldLeft[B](z: B)(op: (B, A) => B): B = { + var result = z + for (x <- this) + result = op(result, x) + result + } + + /** Combines the elements of this list together using the binary + * function f, from right to left, and starting with + * the value z. + * + * @note Will not terminate for infinite-sized collections. + * @return f(a0, f(a1, f(..., f(an, z)...))) + * if the list is [a0, a1, ..., an]. + */ + def foldRight[B](z: B)(op: (A, B) => B): B = elements.foldRight(z)(op) + + /** Similar to foldLeft but can be used as + * an operator with the order of list and zero arguments reversed. + * That is, z /: xs is the same as xs foldLeft z + * @note Will not terminate for infinite-sized collections. + */ + def /: [B](z: B)(op: (B, A) => B): B = foldLeft(z)(op) + + /** An alias for foldRight. + * That is, xs :\ z is the same as xs foldRight z + * @note Will not terminate for infinite-sized collections. + */ + def :\ [B](z: B)(op: (A, B) => B): B = foldRight(z)(op) + + /** Combines the elements of this iterable object together using the binary + * operator op, from left to right + * @note Will not terminate for infinite-sized collections. + * @param op The operator to apply + * @return op(... op(a0,a1), ..., an) + if the iterable object has elements + * a0, a1, ..., an. + * @throws Predef.UnsupportedOperationException if the iterable object is empty. + */ + def reduceLeft[B >: A](op: (B, A) => B): B = { + if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft") + var result: B = elements.next + var first = true + for (x <- this) + if (first) first = false + else result = op(result, x) + result + } + + /** Combines the elements of this iterable object together using the binary + * operator op, from right to left + * @note Will not terminate for infinite-sized collections. + * @param op The operator to apply + * + * @return a0 op (... op (an-1 op an)...) + * if the iterable object has elements a0, a1, ..., + * an. + * + * @throws Predef.UnsupportedOperationException if the iterator is empty. + */ + def reduceRight[B >: A](op: (A, B) => B): B = + elements.reduceRight(op) + + /** Returns an iterable formed from this iterable and the specified list + * `other` by associating each element of the former with + * the element at the same position in the latter. + * If one of the two iterables is longer than the other, its remaining elements are ignored. + */ + def zip[B](that: Iterable[B]): CC[(A, B)] = { + val these = this.elements + val those = that.elements + val b = this.newBuilder[(A, B)] + while (these.hasNext && those.hasNext) + b += ((these.next, those.next)) + b.result + } + + /** Returns a iterable formed from this iterable and the specified iterable + * that by associating each element of the former with + * the element at the same position in the latter. + * + * @param that iterable that may have a different length + * as the self iterable. + * @param thisElem element thisElem is used to fill up the + * resulting iterable if the self iterable is shorter than + * that +b * @param thatElem element thatElem is used to fill up the + * resulting iterable if that is shorter than + * the self iterable + * @return Iterable((a0,b0), ..., + * (an,bn), (elem,bn+1), + * ..., {elem,bm}) + * when [a0, ..., an] zip + * [b0, ..., bm] is + * invoked where m > n. + */ + def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): CC[(A1, B1)] = { + val these = this.elements + val those = that.elements + val b = newBuilder[(A1, B1)] + while (these.hasNext && those.hasNext) + b += ((these.next, those.next)) + while (these.hasNext) + b += ((these.next, thatElem)) + while (those.hasNext) + b += ((thisElem, those.next)) + b.result + } + + /** Zips this iterable with its indices. `s.zipWithIndex` is equivalent to + * `s zip s.indices`, but is usually more efficient. + */ + def zipWithIndex: CC[(A, Int)] = { + val b = newBuilder[(A, Int)] + var i = 0 + for (x <- this) { + b += ((x, i)) + i +=1 + } + b.result + } + + /** Copy all elements to a given buffer + * @note Will not terminate for infinite-sized collections. + * @param dest The buffer to which elements are copied + */ + def copyToBuffer[B >: A](dest: Buffer[B]) { + for (x <- this) dest += x + } + + /** Fills the given array xs with at most `len` elements of + * this sequence starting at position `start`. + * Copying will stop oce either the end of the current iterable is reached or + * `len` elements have been copied. + * + * @note Will not terminate for infinite-sized collections. + * @param xs the array to fill. + * @param start starting index. + * @param len number of elements to copy + * @pre the array must be large enough to hold all elements. + */ + def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) { + var i = start + val end = (start + len) min xs.length + for (x <- this) { + if (i < end) { + xs(i) = x + i += 1 + } + } + } + + /** Fills the given array xs with the elements of + * this sequence starting at position start + * until either the end of the current iterable or the end of array `xs` is reached. + * + * @note Will not terminate for infinite-sized collections. + * @param xs the array to fill. + * @param start starting index. + * @pre the array must be large enough to hold all elements. + */ + def copyToArray[B >: A](xs: Array[B], start: Int) { + copyToArray(xs, start, xs.length - start) + } + + /** Converts this collection to a fresh Array elements. + * @note Will not terminate for infinite-sized collections. + */ + def toArray[B >: A]: Array[B] = { + var size = 0 + for (x <- this) size += 1 + val result = new Array[B](size) + copyToArray(result, 0) + result + } + + /** + * Create a fresh list with all the elements of this iterable object. + * @note Will not terminate for infinite-sized collections. + */ + def toList: List[A] = (new ListBuffer[A] ++ thisCC).toList + + /** + * Returns a sequence containing all of the elements in this iterable object. + * @note Will not terminate for infinite-sized collections. + */ + def toSequence: Sequence[A] = toList.asInstanceOf[Sequence[A]] // !!! + + /** @deprecated use toSequence instead + */ + @deprecated def toSeq: Sequence[A] = toSequence + + /** + * Create a stream which contains all the elements of this iterable object. + * @note consider using projection for lazy behavior. + */ + def toStream: Stream[A] = elements.toStream + + /** Sort the iterable according to the comparison function + * <(e1: a, e2: a) => Boolean, + * which should be true iff e1 is smaller than + * e2. + * The sort is stable. That is elements that are equal wrt `lt` appear in the + * same order in the sorted iterable as in the original. + * + * @param lt the comparison function + * @return a list sorted according to the comparison function + * <(e1: a, e2: a) => Boolean. + * @ex 
+   *    List("Steve", "Tom", "John", "Bob")
+   *      .sort((e1, e2) => (e1 compareTo e2) < 0) =
+   *    List("Bob", "John", "Steve", "Tom")
+ * !!! + def sortWith(lt : (A,A) => Boolean): CC[A] = { + val arr = toArray + Array.sortWith(arr, lt) + val b = newBuilder[A] + for (x <- arr) b += x + b.result + } + */ + + /** Returns a string representation of this iterable object. The resulting string + * begins with the string start and is finished by the string + * end. Inside, the string representations of elements (w.r.t. + * the method toString()) are separated by the string + * sep. + * + * @ex List(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)" + * @note Will not terminate for infinite-sized collections. + * @param start starting string. + * @param sep separator string. + * @param end ending string. + * @return a string representation of this iterable object. + */ + def mkString(start: String, sep: String, end: String): String = + addString(new StringBuilder(), start, sep, end).toString + + /** Returns a string representation of this iterable object. The string + * representations of elements (w.r.t. the method toString()) + * are separated by the string sep. + * + * @note Will not terminate for infinite-sized collections. + * @param sep separator string. + * @return a string representation of this iterable object. + */ + def mkString(sep: String): String = + addString(new StringBuilder(), sep).toString + + /** Converts a collection into a flat String by each element's toString method. + * @note Will not terminate for infinite-sized collections. + */ + def mkString = + addString(new StringBuilder()).toString + + /** Write all elements of this iterable into given string builder. + * The written text begins with the string start and is finished by the string + * end. Inside, the string representations of elements (w.r.t. + * the method toString()) are separated by the string + * sep. + * @note Will not terminate for infinite-sized collections. + */ + def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = { + b append start + var first = true + for (x <- this) { + if (first) first = false + else b append sep + b append x + } + b append end + } + + /** Write all elements of this string into given string builder. + * The string representations of elements (w.r.t. the method toString()) + * are separated by the string sep. + * @note Will not terminate for infinite-sized collections. + */ + def addString(b: StringBuilder, sep: String): StringBuilder = { + var first = true + for (x <- this) { + if (first) first = false + else b append sep + b append x + } + b + } + + /** Write all elements of this string into given string builder without using + * any separator between consecutive elements. + * @note Will not terminate for infinite-sized collections. + */ + def addString(b: StringBuilder): StringBuilder = { + for (x <- this) { + b append x + } + b + } + + /** + * returns a projection that can be used to call non-strict filter, + * map, and flatMap methods that build projections + * of the collection. + def projection : Iterable.Projection[A] = new Iterable.Projection[A] { + def elements = Iterable.this.elements + override def force = Iterable.this + } + */ + + override def toString = mkString(stringPrefix + "(", ", ", ")") + + /** Defines the prefix of this object's toString representation. + */ + def stringPrefix : String = { + var string = this.getClass.getName + val idx1 = string.lastIndexOf('.' : Int) + if (idx1 != -1) string = string.substring(idx1 + 1) + val idx2 = string.indexOf('$') + if (idx2 != -1) string = string.substring(0, idx2) + string + } + + + /** Creates a view of this iterable @see IterableView + */ + def view: IterableView[CC, A] = new IterableView[CC, A] { // !!! Martin: We should maybe infer the type parameters here? + val origin = thisCC + val elements: Iterator[A] = self.elements + } + +// The following methods return non-deterministic results, unless this iterable is an OrderedIterable + + /** The first element of this sequence. + * + * @note Might return different results for different runs, unless this iterable is ordered + * @throws Predef.NoSuchAentException if the sequence is empty. + */ + def head: A = if (isEmpty) throw new NoSuchElementException else elements.next + + /** @deprecated use head instead */ + @deprecated def first: A = head + + /** Returns as an option the first element of this iterable + * or None if iterable is empty. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def headOption: Option[A] = if (isEmpty) None else Some(head) + + /** @deprecated use headOption instead + * None if list is empty. + */ + @deprecated def firstOption: Option[A] = headOption + + /** An iterable consisting of all elements of this iterable + * except the first one. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def tail: CC[A] = drop(1) + + /** Return an iterable consisting only of the first n + * elements of this iterable, or else the whole iterable, if it has less + * than n elements. + * + * @param n the number of elements to take + * @return a possibly projected sequence + * @note Might return different results for different runs, unless this iterable is ordered + */ + def take(n: Int): CC[A] = { + val b = newBuilder[A] + var i = 0 + breakable { + for (x <- this) { + b += x + i += 1 + if (i == n) break + } + } + b.result + } + + /** Returns this iterable without its n first elements + * If this iterable has less than n elements, the empty + * iterable is returned. + * + * @param n the number of elements to drop + * @return the new iterable + * @note Might return different results for different runs, unless this iterable is ordered + */ + def drop(n: Int): CC[A] = { + val b = newBuilder[A] + var i = 0 + for (x <- this) { + if (i >= n) b += x + i += 1 + } + b.result + } + + /** A sub-iterable starting at index `from` + * and extending up to (but not including) index `until`. + * + * @note c.slice(from, to) 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 from < 0 + * or length < from + len + * @note Might return different results for different runs, unless this iterable is ordered + */ + def slice(from: Int, until: Int): CC[A] = { + val b = newBuilder[A] + var i = 0 + breakable { + for (x <- this) { + if (i >= from) b += x + i += 1 + if (i == until) break + } + } + b.result + } + + /** The last element of this iterable. + * + * @throws Predef.NoSuchElementException if the sequence is empty. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def last: A = { + var lst = head + for (x <- this) + lst = x + lst + } + + /** Returns as an option the last element of this iterable or + * None if iterable is empty. + * + * @return the last element as an option. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def lastOption: Option[A] = if (isEmpty) None else Some(last) + + /** An iterable consisting of all elements of this iterable except the last one. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def init: CC[A] = { + var lst = head + val b = newBuilder[A] + for (x <- this) { + b += lst + lst = x + } + b.result + } + + /** Returns the rightmost n elements from this iterable. + * + * @param n the number of elements to take + * @note Might return different results for different runs, unless this iterable is ordered + */ + def takeRight(n: Int): CC[A] = { + val b = newBuilder[A] + val lead = elements drop n + var go = false + for (x <- this) { + if (go) b += x + else if (lead.hasNext) lead.next + else go = true + } + b.result + } + + /** Returns the iterable wihtout its rightmost n elements. + * + * @param n the number of elements to take + * @note Might return different results for different runs, unless this iterable is ordered + */ + def dropRight(n: Int): CC[A] = { + val b = newBuilder[A] + val lead = elements drop n + breakable { + for (x <- this) { + if (!lead.hasNext) break + lead.next + b += x + } + } + b.result + } + + /** Split the iterable at a given point and return the two parts thus + * created. + * + * @param n the position at which to split + * @return a pair of iterables composed of the first n + * elements, and the other elements. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def splitAt(n: Int): (CC[A], CC[A]) = { + val l, r = newBuilder[A] + var i = 0 + for (x <- this) + (if (i < n) l else r) += x + (l.result, r.result) + } + + /** Returns the longest prefix of this sequence whose elements satisfy + * the predicate p. + * + * @param p the test predicate. + * @return the longest prefix of this sequence whose elements satisfy + * the predicate p. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def takeWhile(p: A => Boolean): CC[A] = { + val b = newBuilder[A] + breakable { + for (x <- this) { + if (!p(x)) break + b += x + } + } + b.result + } + + /** Returns the longest suffix of this sequence whose first element + * does not satisfy the predicate p. + * + * @param p the test predicate. + * @return the longest suffix of the sequence whose first element + * does not satisfy the predicate p. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def dropWhile(p: A => Boolean): CC[A] = { + val b = newBuilder[A] + var go = false + for (x <- this) { + if (go) b += x + else if (!p(x)) { go = true; b += x } + } + b.result + } + + /** Returns a pair consisting of the longest prefix of the list whose + * elements all satisfy the given predicate, and the rest of the list. + * + * @param p the test predicate + * @return a pair consisting of the longest prefix of the list whose + * elements all satisfy p, and the rest of the list. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def span(p: A => Boolean): (CC[A], CC[A]) = { + val l, r = newBuilder[A] + var toLeft = true + for (x <- this) { + toLeft = toLeft && p(x) + (if (toLeft) l else r) += x + } + (l.result, r.result) + } + + /** Checks if the other iterable object contains the same elements as this one. + * + * @note will not terminate for infinite-sized iterables. + * @param that the other iterable + * @return true, iff both iterables contain the same elements. + * @note Might return different results for different runs, unless this iterable is ordered + */ + def sameElements[B >: A](that: OrderedIterable[B]): Boolean = { + val these = this.elements + val those = that.elements + while (these.hasNext && those.hasNext && these.next() == those.next()) {} + !these.hasNext && !those.hasNext + } + + /** A sub-sequence view starting at index `from` + * and extending up to (but not including) index `until`. + * + * @param from The index of the first element of the slice + * @param until The index of the element following the slice + * @note The difference between `view` and `slice` is that `view` produces + * a view of the current sequence, whereas `slice` produces a new sequence. + * + * @note Might return different results for different runs, unless this iterable is ordered + * @note view(from, to) is equivalent to view.slice(from, to) + */ + def view(from: Int, until: Int): IterableView[CC, A] = view.slice(from, until) +} diff --git a/src/library/scalax/collection/generic/covartest/IterableView.scala b/src/library/scalax/collection/generic/covartest/IterableView.scala new file mode 100755 index 0000000000..80a455f776 --- /dev/null +++ b/src/library/scalax/collection/generic/covartest/IterableView.scala @@ -0,0 +1,121 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $ + +package scalax.collection.generic.covartest + +/** A non-strict projection of an iterable. + * @author Sean McDirmid + * @author Martin Odersky + * @note this should really be a virtual class of SequenceFactory + */ +trait IterableView[+UC[+B] <: Iterable[B], +A] extends Iterable[A] { self => + + val origin: Iterable[_] + def elements: Iterator[A] + + val underlying: Iterable[_] = origin match { + case v: IterableView[t, _] => v.underlying + case _ => origin + } + + private def isDelay = elements eq underlying.elements + + private[this] var forced: UC[A] = _ + private[this] var wasForced = false + + def force: UC[A] = { + if (!wasForced) { + forced = { + val b = underlying.newBuilder[A] + for (x <- elements) + b += x + b.result + }.asInstanceOf[UC[A]] + wasForced = true + } + forced + } + + def newBuilder[A] = underlying.newBuilder[A] + + /** Builds a new view object. This method needs to be overridden in subclasses + * which refine in IterableView type + */ + protected def newView[B](elems: Iterator[B]) = new IterableView[UC, B] { + val origin = if (self.isDelay) self.origin else self + val elements = elems + } + + /** Non-strict variant of @see IterableLike.++ */ + override def ++[B >: A](that: Iterator[B]): IterableView[UC, B] = newView(elements ++ that) + + /** Non-strict variant of @see IterableLike.++ */ + override def ++[B >: A](that: Iterable[B]): IterableView[UC, B] = newView(elements ++ that.elements) + + /** Non-strict variant of @see IterableLike.map */ + override def map[B](f: A => B): IterableView[UC, B] = newView(elements map f) + + /** Non-strict variant of @see IterableLike.flatMap */ + override def flatMap[B](f: A => Iterable[B]): IterableView[UC, B] = newView(elements flatMap (f(_).elements)) + + /** Non-strict variant of @see IterableLike.filter */ + override def filter(p: A => Boolean): IterableView[UC, A] = newView(elements filter p) + + /** Non-strict variant of @see IterableLike.partition */ + override def partition(p: A => Boolean): (IterableView[UC, A], IterableView[UC, A]) = { + val (li, ri) = elements partition p + (newView(li), newView(ri)) + } + + /** Non-strict variant of @see IterableLike.zip */ + override def zip[B](other: Iterable[B]): IterableView[UC, (A, B)] = newView(elements zip other.elements) + + /** Non-strict variant of @see IterableLike.zipWithIndex */ + override def zipWithIndex: IterableView[UC, (A, Int)] = newView(elements.zipWithIndex) + + /* Non-strict variant of @see IterableLike.zipAll + * This is not enabled because it can't be specialized in VectorView: + * VectorView is not covariant, yet must maintain updatability. Impossible to do this + * with this type signature. + override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): IterableView[UC, (A1, B1)] = + newView(elements zipAll (that.elements, thisElem, thatElem)) + */ + + /** Non-strict variant of @see Iterable.take */ + override def take(n: Int): IterableView[UC, A] = newView(elements take n) + + /** Non-strict variant of @see Iterable.drop */ + override def drop(n: Int): IterableView[UC, A] = newView(elements drop n) + + /** Non-strict variant of @see Iterable.splitAt */ + override def splitAt(n: Int): (IterableView[UC, A], IterableView[UC, A]) = (take(n), drop(n)) + + /** Non-strict variant of @see Iterable.slice */ + override def slice(from: Int, until: Int): IterableView[UC, A] = newView(elements slice (from, until)) + + /** Non-strict variant of @see Iterable.takeWhile */ + override def takeWhile(p: A => Boolean): IterableView[UC, A] = newView(elements takeWhile p) + + /** Non-strict variant of @see Iterable.dropWhile */ + override def dropWhile(p: A => Boolean): IterableView[UC, A] = newView(elements dropWhile p) + + /** Non-strict variant of @see Iterable.span */ + override def span(p: A => Boolean): (IterableView[UC, A], IterableView[UC, A]) = (takeWhile(p), dropWhile(p)) + + /** The projection resulting from the concatenation of this projection with the rest projection. + * @param rest The projection that gets appended to this projection + * @deprecated Use ++ instead + */ + @deprecated def append[B >: A](rest : => Iterable[B]): IterableView[UC, B] = this ++ rest.elements + + override def stringPrefix = origin.stringPrefix+"V" + + +} diff --git a/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala new file mode 100755 index 0000000000..c6be1a5acd --- /dev/null +++ b/src/library/scalax/collection/generic/covartest/OrderedIterableTemplate.scala @@ -0,0 +1,17 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Iterable.scala 15188 2008-05-24 15:01:02Z stepancheg $ + + +package scalax.collection.generic.covartest + +import OrderedIterable._ + +trait OrderedIterableTemplate[+CC[+B] <: OrderedIterableTemplate[CC, B] with OrderedIterable[B], +A] + extends IterableTemplate[CC, A] diff --git a/src/library/scalax/collection/generic/covartest/SequenceFactory.scala b/src/library/scalax/collection/generic/covartest/SequenceFactory.scala new file mode 100755 index 0000000000..1fb85d02db --- /dev/null +++ b/src/library/scalax/collection/generic/covartest/SequenceFactory.scala @@ -0,0 +1,11 @@ +package scalax.collection.generic.covartest + +trait SequenceFactory[CC[A] <: Sequence[A]] extends IterableFactory[CC] { + + /** This method is called in a pattern match { case Sequence(...) => }. + * + * @param x the selector value + * @return sequence wrapped in an option, if this is a Sequence, otherwise none + */ + def unapplySequence[A](x: CC[A]): Some[CC[A]] = Some(x) +} diff --git a/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala b/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala new file mode 100755 index 0000000000..bf1915edf0 --- /dev/null +++ b/src/library/scalax/collection/generic/covartest/SequenceTemplate.scala @@ -0,0 +1,382 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Sequence.scala 16092 2008-09-12 10:37:06Z nielsen $ + + +package scalax.collection.generic.covartest + +import util.control.Break._ +import scalax.collection.immutable.{List, Nil, ::} + +import Sequence._ + +trait SequenceTemplate[+CC[+B] <: SequenceTemplate[CC, B] with Sequence[B], +A] extends PartialFunction[Int, A] with OrderedIterableTemplate[CC, A] { +self /*: CC[A]*/ => + + /** Returns the length of the sequence. + * + * @return the sequence length. + */ + def length: Int + + /** Result of comparing length with operand len. + * returns x where + * x < 0 iff this.length < len + * x == 0 iff this.length == len + * x > 0 iff this.length > len. + * + * The method as implemented here does not call length directly; its running time + * is O(length min len) instead of O(length). The method should be overwritten + * if computing length is cheap. + */ + def lengthCompare(len: Int): Int = { + var i = 0 + breakable { + for (_ <- this) { + i += 1 + if (i > len) break + } + } + i - len + } + + /** Should always be length */ + def size = length + + /** Is this partial function defined for the index x? + */ + def isDefinedAt(x: Int): Boolean = (x >= 0) && (x < length) + + /** Returns index of the first element satisying a predicate, or -1, if none exists. + * + * @note may not terminate for infinite-sized collections. + * @param p the predicate + */ + def indexWhere(p: A => Boolean): Int = indexWhere(p, 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 + */ + def segmentLength(p: A => Boolean, from: Int): Int = { + var result = 0 + var i = from + breakable { + for (x <- this) { + if (i >= from && !p(x)) { result = i - from; break } + else i += 1 + } + } + result + } + + /** Returns length of longest prefix of this seqence + * such that every element of the prefix satisfies predicate `p`. + * @note may not terminate for infinite-sized collections. + * @param p the predicate + */ + def prefixLength(p: A => Boolean) = segmentLength(p, 0) + + /** 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 collections. + * @param p the predicate + * @param from the start index + */ + def indexWhere(p: A => Boolean, from: Int): Int = { + var result = -1 + var i = from + breakable { + for (x <- this) { + if (i >= from && p(x)) { result = i; break } + else i += 1 + } + } + result + } + + /** Returns index of the first element satisying a predicate, or -1. + * + * @deprecated Use `indexWhere` instead + */ + @deprecated def findIndexOf(p: A => Boolean): Int = indexWhere(p) + + /** Returns the index of the first occurence of the specified + * object in this iterable object. + * + * @note may not terminate for infinite-sized collections. + * @param elem element to search for. + * @return the index in this sequence of the first occurence of the + * specified element, or -1 if the sequence does not contain + * this element. + */ + def indexOf[B >: A](elem: B): Int = indexOf(elem, 0) + + /** Returns the index of the first occurence of the specified + * object in this iterable object, starting from a start index, or + * -1, if none exists. + * + * @note may not terminate for infinite-sized collections. + * @param elem element to search for. + */ + def indexOf[B >: A](elem: B, from: Int): Int = indexWhere(elem ==, from) + + /** Returns the index of the last occurence of the specified element + * in this sequence, or -1 if the sequence does not contain this element. + * + * @param elem element to search for. + * @return the index in this sequence of the last occurence of the + * specified element, or -1 if the sequence does not contain + * this element. + */ + def lastIndexOf[B >: A](elem: B): Int = lastIndexOf(elem, length - 1) + + /** Returns the index of the last + * occurence of the specified element in this sequence + * before or at a given end index, + * or -1 if the sequence does not contain this element. + * + * @param elem element to search for. + * @param end the end index + */ + def lastIndexOf[B >: A](elem: B, end: Int): Int = { + var i = end + val it = reversedElements + while (it.hasNext && it.next != elem) i -= 1 + 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 p, + * or -1 if such an element does not exist + */ + def lastIndexWhere(p: A => Boolean): Int = lastIndexWhere(p, length - 1) + + /** Returns index of the last element not exceeding a given end index + * and satisying a predicate, or -1 if none exists. + * + * @param end the end index + * @param p the predicate + */ + def lastIndexWhere(p: A => Boolean, end: Int): Int = { + var i = end + val it = reversedElements + while (it.hasNext && (i > end || !p(it.next))) i -= 1 + i + } + + /** A sequence of type C consisting of all elements of + * this sequence in reverse order. + * @note the operation is implemented by building a new sequence + * from this(length - 1), ..., this(0) + * If random access is inefficient for the given sequence implementation, + * this operation should be overridden. + */ + def reverse: CC[A] = { + var xs: List[A] = List() + for (x <- this) + xs = x :: xs + val b = newBuilder[A] + for (x <- xs) + b += x + b.result + } + + /** The elements of this sequence in reversed order + */ + def reversedElements: Iterator[A] = reverse.elements + + /** + * Checks whether the argument sequence is contained at the + * specified index within the receiver object. + * + * If the both the receiver object, this and + * the argument, that are infinite sequences + * this method may not terminate. + * + * @return true if that is contained in + * this, at the specified index, otherwise false + * + * @see String.startsWith + */ + def startsWith[B](that: Sequence[B], offset: Int): Boolean = { + val i = elements.drop(offset) + val j = that.elements + while (j.hasNext && i.hasNext && i.next == j.next) {} + !j.hasNext + } + + /** + * Check whether the receiver object starts with the argument sequence. + * + * @return true if that is a prefix of this, + * otherwise false + * + * @see Sequence.startsWith + */ + def startsWith[B](that: Sequence[B]): Boolean = startsWith(that, 0) + + /** @return true if this sequence end with that sequence + * @see String.endsWith + */ + def endsWith[B](that: Sequence[B]): Boolean = { + val i = this.elements.drop(length - that.length) + val j = that.elements + while (i.hasNext && j.hasNext && i.next == j.next) () + !j.hasNext + } + + /** @return -1 if that not contained in this, otherwise the + * index where that is contained + * @see String.indexOf + */ + def indexOf[B >: A](that: Sequence[B]): Int = { + var i = 0 + var s: Sequence[A] = thisCC + while (!s.isEmpty && !(s startsWith that)) { + i += 1 + s = s drop 1 + } + if (!s.isEmpty || that.isEmpty) i else -1 + } + + /** Tests if the given value elem is a member of this + * sequence. + * + * @param elem element whose membership has to be tested. + * @return true iff there is an element of this sequence + * which is equal (w.r.t. ==) to elem. + */ + def contains(elem: Any): Boolean = exists (_ == elem) + + /** Computes the union of this sequence and the given sequence + * that. + * + * @param that the sequence of elements to add to the sequence. + * @return an sequence containing the elements of this + * sequence and those of the given sequence that + * which are not contained in this sequence. + */ + def union[B >: A](that: Sequence[B]): CC[B] = this ++ (that diff thisCC) + + /** Computes the difference between this sequence and the given sequence + * that. + * + * @param that the sequence of elements to remove from this sequence. + * @return this sequence without the elements of the given sequence + * that. + */ + def diff[B >: A](that: Sequence[B]): CC[A] = this remove (that contains _) + + /** Computes the intersection between this sequence and the given sequence + * that. + * + * @param that the sequence to intersect. + * @return the sequence of elements contained both in this sequence and + * in the given sequence that. + */ + def intersect[B >: A](that: Sequence[B]): CC[A] = this filter(that contains _) + + /** Builds a new sequence from this sequence in which any duplicates (wrt to ==) removed. + * Among duplicate elements, only the first one is retained in the result sequence + */ + def removeDuplicates: CC[A] = { + val b = newBuilder[A] + var seen = Set[A]() + for (x <- this) { + if (!(seen contains x)) { + b += x + seen += x + } + } + b.result + } + + /** Returns a sequence of given length containing the elements of this sequence followed by zero + * or more occurrences of given elements. If this sequence is already at least as long as given + * length, it is returned directly. Otherwise, a new sequence is created consisting of the elements + * of this sequence followed by enough occurrences of the given elements to reach the given length. + */ + def padTo[B >: A](len: Int, elem: B): CC[B] = { + var diff = len - length + val b = newBuilder[B] //!!! drop [B] and get surprising results! + b ++= thisCC + while (diff > 0) { + b += elem + diff -=1 + } + b.result + } + + /** + * Overridden for efficiency. + * + * @return the sequence itself + */ + override def toSequence: Sequence[A] = this.asInstanceOf[Null] // !!! + + def indices: Range = 0 until length + + /** Creates a view of this iterable @see OrderedIterable.View + */ + override def view: SequenceView[CC, A] = new SequenceView[CC, A] { // !!! Martin: We should maybe infer the type parameters here? + val origin: Sequence[_] = thisCC + val elements: Iterator[A] = self.elements + val length: Int = self.length + def apply(idx: Int): A = self.apply(idx) + } + + /** A sub-sequence view starting at index `from` + * and extending up to (but not including) index `until`. + * + * @param from The index of the first element of the slice + * @param until The index of the element following the slice + * @note The difference between `view` and `slice` is that `view` produces + * a view of the current sequence, whereas `slice` produces a new sequence. + * + * @note view(from, to) is equivalent to view.slice(from, to) + */ + override def view(from: Int, until: Int): SequenceView[CC, A] = view.slice(from, until) + + /** Returns index of the last element satisying a predicate, or -1. + * @deprecated use `lastIndexWhere` instead + */ + @deprecated def findLastIndexOf(p: A => Boolean): Int = lastIndexWhere(p) + + /** A sub-sequence starting at index from + * and extending up to the length of the current sequence + * + * @param from The index of the first element of the slice + * @throws IndexOutOfBoundsException if from < 0 + * @deprecated use drop instead + */ + @deprecated def slice(from: Int): Sequence[A] = slice(from, length) + + /** @deprecated Should be replaced by + * + * (s1, s2) forall { case (x, y) => f(x, y) } + */ + @deprecated def equalsWith[B](that: Sequence[B])(f: (A,B) => Boolean): Boolean = { + val i = this.elements + val j = that.elements + while (i.hasNext && j.hasNext && f(i.next, j.next)) () + !i.hasNext && !j.hasNext + } + + /** Is that a slice in this? + * @deprecated Should be repaced by indexOf(that) != -1 + */ + @deprecated def containsSlice[B](that: Sequence[B]): Boolean = indexOf(that) != -1 + +} diff --git a/src/library/scalax/collection/generic/covartest/SequenceView.scala b/src/library/scalax/collection/generic/covartest/SequenceView.scala new file mode 100755 index 0000000000..48477cf6e7 --- /dev/null +++ b/src/library/scalax/collection/generic/covartest/SequenceView.scala @@ -0,0 +1,129 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Sequence.scala 16092 2008-09-12 10:37:06Z nielsen $ + + +package scalax.collection.generic.covartest + +import util.control.Break._ +import annotation.unchecked.uncheckedVariance + +import Sequence._ + +/** A non-strict projection of an iterable. + * @author Sean McDirmid + * @author Martin Odersky + * @note this should really be a virtual class of SequenceFactory + */ +trait SequenceView[+UC[+B] <: Sequence[B], +A] extends IterableView[UC, A] with Sequence[A] { +self => + + /** refined from Iterable.View */ + val origin: Sequence[_] + + trait Transformed[+B] extends SequenceView[UC, B] { + val origin = self + protected def asCC = asInstanceOf[SequenceView[UC, B]] + } + + class Appended[+B >: A](that: Sequence[B]) extends Transformed[B] { + override def elements: Iterator[B] = self.elements ++ that.elements + override def length: Int = self.length + that.length + override def apply(idx: Int): B = { + val ll = self.length + if (idx < ll) self.apply(idx) else that.apply(idx - ll) + } + override def stringPrefix = self.stringPrefix + "A" + } + + class Sliced(from: Int, to: Int) extends Transformed[A] { + override def elements: Iterator[A] = self.elements slice (from, to) + override lazy val length: Int = ((to min self.length) - (from max 0) min 0) + override def apply(idx: Int): A = + if (idx >= 0 && idx < length) self.apply(idx + from) + else throw new IndexOutOfBoundsException(idx.toString) + override def stringPrefix = self.stringPrefix + "S" + override def slice(from1: Int, to1: Int) = + new self.Sliced(from + (from1 min length max 0) , to + (to1 min length max 0)).asInstanceOf[SequenceView[UC, A]] + } + + class Mapped[+B](f: A => B) extends Transformed[B] { + override def elements: Iterator[B] = self.elements map f + override def length: Int = self.length + override def apply(idx: Int): B = f(self.apply(idx)) + override def stringPrefix = self.stringPrefix + "M" + } + + class Reversed extends Transformed[A] { + override def elements: Iterator[A] = self.reversedElements + override def length: Int = self.length + override def apply(idx: Int): A = self.apply(length - 1 - idx) + override def stringPrefix = super.stringPrefix+"R" + } + + class Patched[+B >: A](from: Int, patch: Sequence[B], replaced: Int) extends Transformed[B] { + val plen = patch.length + override def elements: Iterator[B] = self.elements patch (from, patch.asInstanceOf[Null], replaced) // !!! + override def length: Int = self.length + plen - replaced + override def apply(idx: Int): B = + if (idx < from) self.apply(idx) + else if (idx < from + plen) patch.apply(idx - from) + else self.apply(idx - plen + replaced) + override def stringPrefix = super.stringPrefix+"P" + } + + class Zipped[+B](that: Sequence[B]) extends Transformed[(A, B)] { + override def elements: Iterator[(A, B)] = self.elements zip that.elements + override def length = self.length min that.length + override def apply(idx: Int): (A, B) = (self.apply(idx), that.apply(idx)) + override def stringPrefix = super.stringPrefix+"Z" + } + + override def ++[B >: A](that: Iterable[B]): SequenceView[UC, B] = + new Appended[B](that.toSequence).asCC + override def ++[B >: A](that: Iterator[B]): SequenceView[UC, B] = + new Appended[B](that.toSequence).asCC + override def map[B](f: A => B): SequenceView[UC, B] = + new Mapped(f).asCC + override def reverse: SequenceView[UC, A] = + (new Reversed).asCC + def patch[B >: A](from: Int, patch: Sequence[B], replaced: Int): SequenceView[UC, B] = + if (0 <= from && from < length) new Patched(from, patch, replaced).asCC + else throw new IndexOutOfBoundsException(from.toString) + override def padTo[B >: A](len: Int, elem: B): SequenceView[UC, B] = + patch(length, fill((len - length) max 0, elem), 0) + override def zip[B](that: Iterable[B]): SequenceView[UC, (A, B)] = + new Zipped(that.toSequence).asCC + override def zipWithIndex: SequenceView[UC, (A, Int)] = + zip((0 until length).asInstanceOf[Null]) // !!! + /* + override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): SequenceView[UC, (A1, B1)] = { + val that1 = that.toSequence + self.padTo(that1.length, thisElem) zip that1.padTo(this.length, thatElem)//.asInstanceOf[SequenceView[UC, (A1, B1)]] + }*/ + override def take(n: Int): SequenceView[UC, A] = + slice(0, n) + override def drop(n: Int): SequenceView[UC, A] = + slice(n, Math.MAX_INT) + override def splitAt(n: Int): (SequenceView[UC, A], SequenceView[UC, A]) = (take(n), drop(n)) + override def slice(from: Int, until: Int): SequenceView[UC, A] = + new Sliced(from, until).asCC + override def takeWhile(p: A => Boolean): SequenceView[UC, A] = + take(prefixLength(p)) + override def dropWhile(p: A => Boolean): SequenceView[UC, A] = + drop(prefixLength(p)) + override def span(p: A => Boolean): (SequenceView[UC, A], SequenceView[UC, A]) = { + val n = prefixLength(p) + (take(n), drop(n)) + } + + // missing here because we can't do anything about them, so we fall back to default construction + // if an IterableView via newView: flatMap, filter, partition +} + diff --git a/src/library/scalax/collection/generic/covartest/VectorTemplate.scala b/src/library/scalax/collection/generic/covartest/VectorTemplate.scala new file mode 100644 index 0000000000..0771b078d9 --- /dev/null +++ b/src/library/scalax/collection/generic/covartest/VectorTemplate.scala @@ -0,0 +1,264 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2006-2008, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: Vector.scala 15437 2008-06-25 16:22:45Z stepancheg $ + +package scalax.collection.generic.covartest + +import Vector._ + +/** Sequences that support O(1) element access and O(1) length computation. + * @author Sean McDirmid + * @author Martin Odersky + * @version 2.8 + */ +trait VectorTemplate[+CC[+B] <: VectorTemplate[CC, B] with Vector[B], +A] extends SequenceTemplate[CC, A] { +self => + + // Overridden methods from IterableTemplate + + /** The iterator returned by the elements method + */ + protected class Elements(start: Int, end: Int) extends scalax.collection.BufferedIterator[A] { + var i = start + def hasNext: Boolean = i < end + def next: A = + if (i < end) { + val x = self(i) + i += 1 + x + } else Iterator.empty.next + def head = + self(i) + /** drop is overridden to enable fast searching in the middle of random access sequences */ + override def drop(n: Int): Iterator[A] = + if (n > 0) new Elements(start + n, end) else this + /** is overridden to be symmetric to drop */ + override def take(n: Int): Iterator[A] = + if (n < 0) Iterator.empty.buffered + else if (start + n < end) new Elements(start, start + n) + else this + } + + override def elements: Iterator[A] = new Elements(0, length) + + override def isEmpty: Boolean = { length == 0 } + + override def foreach(f: A => Unit): Unit = { + var i = 0 + val len = length + while (i < len) { f(this(i)); i += 1 } + } + + override def forall(p: A => Boolean): Boolean = prefixLength(p(_)) == length + override def exists(p: A => Boolean): Boolean = prefixLength(!p(_)) != length + + override def find(p: A => Boolean): Option[A] = { + val i = prefixLength(!p(_)) + if (i < length) Some(this(i)) else None + } + + private def foldl[B](start: Int, z: B, op: (B, A) => B): B = { + var i = start + val len = length + var result = z + while (i < len) { + result = op(result, this(i)) + i += 1 + } + result + } + + private def foldr[B](start: Int, len: Int, z: B, op: (A, B) => B): B = + if (start == len) z + else op(this(start), foldr(start + 1, len, z, op)) + + override def foldLeft[B](z: B)(op: (B, A) => B): B = foldl(0, z, op) + override def foldRight[B](z: B)(op: (A, B) => B): B = foldr(0, length, z, op) + override def reduceLeft[B >: A](op: (B, A) => B): B = + if (length > 0) foldl(0, this(0), op) else super.reduceLeft(op) + override def reduceRight[B >: A](op: (A, B) => B): B = + if (length > 0) foldr(0, length - 1, this(length - 1), op) else super.reduceRight(op) + + override def zip[B](that: Iterable[B]): CC[(A, B)] = that match { + case that: Vector[_] => + var i = 0 + val len = this.length min that.length + val b = this.newBuilder[(A, B)] + while (i < len) { + b += ((this(i), that(i).asInstanceOf[B])) + i += 1 + } + b.result + case _ => + super.zip(that) + } + + override def zipAll[B, A1 >: A, B1 >: B](that: Iterable[B], thisElem: A1, thatElem: B1): CC[(A1, B1)] = that match { + case that: Vector[_] => + var i = 0 + val len = this.length min that.length + val b = this.newBuilder[(A1, B1)] + while (i < len) { + b += ((this(i), that(i).asInstanceOf[B])) + i += 1 + } + while (i < this.length) { + b += ((this(i), thatElem)) + i += 1 + } + while (i < that.length) { + b += ((this(i), thatElem.asInstanceOf[B])) + i += 1 + } + b.result + case _ => + super.zipAll(that, thisElem, thatElem) + } + + override def zipWithIndex: CC[(A, Int)] = { + val b = newBuilder[(A, Int)] + var i = 0 + val len = length + while (i < len) { + b += ((this(i), i)) + i += 1 + } + b.result + } + + override def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) { + var i = 0 + var j = start + val end = length min len min (xs.length - start) + while (i < end) { + xs(j) = this(i) + i += 1 + j += 1 + } + } + + // Overridden methods from OrderedIterableTemplate + + override def head: A = if (isEmpty) throw new NoSuchElementException else this(0) + + override def slice(from: Int, until: Int): CC[A] = { + val b = newBuilder[A] + var i = from max 0 + val end = until min length + while (i < end) { + b += this(i) + i += 1 + } + b.result + } + + override def take(n: Int): CC[A] = slice(0, n) + override def drop(n: Int): CC[A] = slice(n, length) + override def takeRight(n: Int): CC[A] = slice(length - n, length) + override def dropRight(n: Int): CC[A] = slice(0, length - n) + override def splitAt(n: Int): (CC[A], CC[A]) = (take(n), drop(n)) + override def takeWhile(p: A => Boolean): CC[A] = take(prefixLength(p)) + override def dropWhile(p: A => Boolean): CC[A] = drop(prefixLength(p)) + override def span(p: A => Boolean): (CC[A], CC[A]) = splitAt(prefixLength(p)) + override def last: A = if (length > 0) this(length - 1) else super.last + override def init: CC[A] = if (length > 0) slice(0, length - 1) else super.init + + override def sameElements[B >: A](that: OrderedIterable[B]): Boolean = that match { + case that: Vector[_] => + val len = length + len == that.length && { + var i = 0 + while (i < len && this(i) == that(i)) i += 1 + i == len + } + case _ => + super.sameElements(that) + } + + // Overridden methods from Sequence + + override def lengthCompare(len: Int): Int = length - len + + private def negLength(n: Int) = if (n == length) -1 else n + + override def indexWhere(p: A => Boolean, from: Int): Int = + negLength(from + segmentLength(!p(_), from)) + + override def lastIndexWhere(p: A => Boolean, end: Int): Int = { + var i = end + while (i >= 0 && !p(this(i))) i -= 1 + i + } + + override def lastIndexOf[B >: A](elem: B, end: Int): Int = lastIndexWhere(elem ==, end) + + override def reverse: CC[A] = { + val b = newBuilder[A] + var i = length + while (0 < i) { + i -= 1 + b += this(i) + } + b.result + } + + override def reversedElements = new Iterator[A] { + var i = length + def hasNext: Boolean = 0 < i + def next: A = + if (0 < i) { + i -= 1 + self(i) + } else Iterator.empty.next + } + + override def startsWith[B](that: Sequence[B], offset: Int): Boolean = that match { + case that: Vector[_] => + var i = offset + var j = 0 + val thisLen = length + val thatLen = that.length + while (i < thisLen && j < thatLen && this(i) == that(j)) { + i += 1 + j += 1 + } + j == thatLen + case _ => + var i = offset + val thisLen = length + val thatElems = that.elements + while (i < thisLen && thatElems.hasNext && this(i) == thatElems.next) { + i += 1 + } + !thatElems.hasNext + } + + override def endsWith[B](that: Sequence[B]): Boolean = that match { + case that: Vector[_] => + val thisLen = length + val thatLen = that.length + var i = thisLen - 1 + var j = thatLen - 1 + while (i >= 0 && j >= 0 && this(i) == that(j)) { + i -= 1 + j -= 1 + } + j == 0 + case _ => + super.endsWith(that) + } + + override def indexOf[B >: A](that: Sequence[B]): Int = { + var i = 0 + val last = length - that.length + while (i <= last && !startsWith(that, i)) i += 1 + negLength(i) + } +} + -- cgit v1.2.3