/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2006-2009, 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 =
if (i < end) self(i) else Iterator.empty.next
/** 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: Iterator[A] = 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)
}
}