Scala example source code file (IndexedSeqOptimized.scala)

This example Scala source code file (IndexedSeqOptimized.scala) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Java - Scala tags/keywords

a, a, b, b, boolean, indexedseq, int, int, iterablelike, iterablelike, repr, seqlike, that, traversablelike

The Scala IndexedSeqOptimized.scala source code

/*                     __                                               *\
**     ________ ___   / /  ___     Scala API                            **
**    / __/ __// _ | / /  / _ |    (c) 2006-2011, LAMP/EPFL             **
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
** /____/\___/_/ |_/____/_/ | |                                         **
**                          |/                                          **
\*                                                                      */



package scala.collection

import generic._
import mutable.ArrayBuffer
import scala.annotation.tailrec

/** A template trait for indexed sequences of type `IndexedSeq[A]` which optimizes
 *  the implementation of several methods under the assumption of fast random access.
 *
 *  $indexedSeqInfo
 * 
 *  @define willNotTerminateInf
 *  @define mayNotTerminateInf
 */
trait IndexedSeqOptimized[+A, +Repr] extends IndexedSeqLike[A, Repr] { self =>

  override /*IterableLike*/
  def isEmpty: Boolean = { length == 0 }

  override /*IterableLike*/
  def foreach[U](f: A => U): Unit = {
    var i = 0
    val len = length
    while (i < len) { f(this(i)); i += 1 }
  }

  override /*IterableLike*/ 
  def forall(p: A => Boolean): Boolean = prefixLength(p(_)) == length

  override /*IterableLike*/  
  def exists(p: A => Boolean): Boolean = prefixLength(!p(_)) != length

  override /*IterableLike*/
  def find(p: A => Boolean): Option[A] = {
    val i = prefixLength(!p(_))
    if (i < length) Some(this(i)) else None
  }

  @tailrec
  private def foldl[B](start: Int, end: Int, z: B, op: (B, A) => B): B =
    if (start == end) z
    else foldl(start + 1, end, op(z, this(start)), op)

  @tailrec
  private def foldr[B](start: Int, end: Int, z: B, op: (A, B) => B): B =
    if (start == end) z
    else foldr(start, end - 1, op(this(end - 1), z), op)

  override /*TraversableLike*/
  def foldLeft[B](z: B)(op: (B, A) => B): B = 
    foldl(0, length, z, op)

  override /*IterableLike*/
  def foldRight[B](z: B)(op: (A, B) => B): B = 
    foldr(0, length, z, op)

  override /*TraversableLike*/
  def reduceLeft[B >: A](op: (B, A) => B): B = 
    if (length > 0) foldl(1, length, this(0), op) else super.reduceLeft(op)

  override /*IterableLike*/
  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 /*IterableLike*/
  def zip[A1 >: A, B, That](that: GenIterable[B])(implicit bf: CanBuildFrom[Repr, (A1, B), That]): That = that match {
    case that: IndexedSeq[_] =>
      val b = bf(repr)
      var i = 0
      val len = this.length min that.length
      b.sizeHint(len)
      while (i < len) {
        b += ((this(i), that(i).asInstanceOf[B]))
        i += 1
      }
      b.result
    case _ =>
      super.zip[A1, B, That](that)(bf)
  }

  override /*IterableLike*/
  def zipWithIndex[A1 >: A, That](implicit bf: CanBuildFrom[Repr, (A1, Int), That]): That = {
    val b = bf(repr)
    val len = length
    b.sizeHint(len)
    var i = 0
    while (i < len) {
      b += ((this(i), i))
      i += 1
    }
    b.result
  }
  
  override /*IterableLike*/
  def slice(from: Int, until: Int): Repr = {
    val lo    = math.max(from, 0)
    val hi    = math.min(until, length)
    val elems = math.max(hi - lo, 0)
    val b     = newBuilder
    b.sizeHint(elems)

    var i = lo
    while (i < hi) {
      b += self(i)
      i += 1
    }
    b.result
  }

  override /*IterableLike*/
  def head: A = if (isEmpty) super.head else this(0)

  override /*TraversableLike*/
  def tail: Repr = if (isEmpty) super.tail else slice(1, length)

  override /*TraversableLike*/
  def last: A = if (length > 0) this(length - 1) else super.last

  override /*IterableLike*/
  def init: Repr = if (length > 0) slice(0, length - 1) else super.init

  override /*TraversableLike*/
  def take(n: Int): Repr = slice(0, n)

  override /*TraversableLike*/
  def drop(n: Int): Repr = slice(n, length)

  override /*IterableLike*/
  def takeRight(n: Int): Repr = slice(length - n, length)

  override /*IterableLike*/
  def dropRight(n: Int): Repr = slice(0, length - n)

  override /*TraversableLike*/
  def splitAt(n: Int): (Repr, Repr) = (take(n), drop(n))

  override /*IterableLike*/
  def takeWhile(p: A => Boolean): Repr = take(prefixLength(p))

  override /*TraversableLike*/
  def dropWhile(p: A => Boolean): Repr = drop(prefixLength(p))

  override /*TraversableLike*/
  def span(p: A => Boolean): (Repr, Repr) = splitAt(prefixLength(p))

  override /*IterableLike*/
  def sameElements[B >: A](that: GenIterable[B]): Boolean = that match {
    case that: IndexedSeq[_] =>
      val len = length
      len == that.length && {
        var i = 0
        while (i < len && this(i) == that(i)) i += 1
        i == len
      }
    case _ =>
      super.sameElements(that)
  }        
  
  override /*IterableLike*/
  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 Seq
  
  override /*SeqLike*/
  def lengthCompare(len: Int): Int = length - len
  
  override /*SeqLike*/
  def segmentLength(p: A => Boolean, from: Int): Int = {
    val len = length
    var i = from
    while (i < len && p(this(i))) i += 1
    i - from
  }

  private def negLength(n: Int) = if (n >= length) -1 else n

  override /*SeqLike*/
  def indexWhere(p: A => Boolean, from: Int): Int = {
    val start = from max 0
    negLength(start + segmentLength(!p(_), start))
  }	

  override /*SeqLike*/
  def lastIndexWhere(p: A => Boolean, end: Int): Int = {
    var i = end
    while (i >= 0 && !p(this(i))) i -= 1
    i
  }

  override /*SeqLike*/
  def reverse: Repr = {
    val b = newBuilder
    b.sizeHint(length)
    var i = length
    while (0 < i) {
      i -= 1
      b += this(i)
    }
    b.result
  }

  override /*SeqLike*/
  def reverseIterator: Iterator[A] = new Iterator[A] {
    private var i = self.length
    def hasNext: Boolean = 0 < i
    def next: A = 
      if (0 < i) {
        i -= 1
        self(i)
      } else Iterator.empty.next
  }

  override /*SeqLike*/
  def startsWith[B](that: GenSeq[B], offset: Int): Boolean = that match {
    case that: IndexedSeq[_] =>
      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.iterator
      while (i < thisLen && thatElems.hasNext) {
        if (this(i) != thatElems.next())
          return false
        
        i += 1
      }
      !thatElems.hasNext
  }

  override /*SeqLike*/
  def endsWith[B](that: GenSeq[B]): Boolean = that match {
    case that: IndexedSeq[_] =>
      var i = length - 1
      var j = that.length - 1
      
      (j <= i) && {
        while (j >= 0) {
          if (this(i) != that(j))
            return false
          i -= 1
          j -= 1
        }
        true
      }
    case _ =>
      super.endsWith(that)
  }
}