path: root/src/library/scala/collection/IndexedSeqLike.scala

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

// $Id$


package scala.collection

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

/** A template trait for indexed sequences of type `IndexedSeq[A]`.
 *
 *  $indexedSeqInfo
 *
 *  This trait just implements `iterator` in terms of `apply` and `length`.
 *  However, see `IndexedSeqOptimized` for an implementation trait that overrides operations
 *  to make them run faster under the assumption of fast random access with `apply`.
 *
 *  @author Sean McDirmid
 *  @author Martin Odersky
 *  @version 2.8
 *  @since   2.8
 *  @define  Coll  IndexedSeq
 *  @define indexedSeqInfo
 *  Indexed sequences support constant-time or near constant-time element
 *  access and length computation. They are defined in terms of abstract methods
 *  `apply` fpor indexing and `length`.
 *
 *  Indexed sequences do not add any new methods wrt `Seq`, but promise
 *  efficient implementations of random access patterns.
 *
 *  @tparam A    the element type of the $coll
 *  @tparam Repr the type of the actual $coll containing the elements.
 *  @define willNotTerminateInf
 *  @define mayNotTerminateInf
 */
trait IndexedSeqLike[+A, +Repr] extends SeqLike[A, Repr] { self =>

  override protected[this] def thisCollection: IndexedSeq[A] = this.asInstanceOf[IndexedSeq[A]]
  override protected[this] def toCollection(repr: Repr): IndexedSeq[A] = repr.asInstanceOf[IndexedSeq[A]]

  /** The class of the iterator returned by the `iterator` method.
   *  multiple `take`, `drop`, and `slice` operations on this iterator are bunched
   *  together for better efficiency.
   */
  @serializable @SerialVersionUID(1756321872811029277L)
  protected class Elements(start: Int, end: Int) extends BufferedIterator[A] {
    private 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

    /** $super
     *  @note `drop` is overridden to enable fast searching in the middle of indexed sequences.
     */
    override def drop(n: Int): Iterator[A] =
      if (n > 0) new Elements(start + n, end) else this

    /** $super
     *  @note `take` 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 /*IterableLike*/
  def iterator: Iterator[A] = new Elements(0, length)
/*
  override /*SeqLike*/
  def view = new IndexedSeqView[A, Repr] {
    protected lazy val underlying = self.repr
    override def iterator = self.iterator
    override def length = self.length
    override def apply(idx: Int) = self.apply(idx)
  }

  override /*SeqLike*/
  def view(from: Int, until: Int) = view.slice(from, until)
*/
}