path: root/scalalib/overrides-2.10/scala/collection/immutable/Range.scala

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


package scala.collection.immutable

import scala.collection.parallel.immutable.ParRange

/** The `Range` class represents integer values in range
 *  ''[start;end)'' with non-zero step value `step`.
 *  It's a special case of an indexed sequence.
 *  For example:
 *
 *  {{{
 *     val r1 = 0 until 10
 *     val r2 = r1.start until r1.end by r1.step + 1
 *     println(r2.length) // = 5
 *  }}}
 *
 *  @param start      the start of this range.
 *  @param end        the exclusive end of the range.
 *  @param step       the step for the range.
 *
 *  @author Martin Odersky
 *  @author Paul Phillips
 *  @version 2.8
 *  @since   2.5
 *  @see [[http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html#ranges "Scala's Collection Library overview"]]
 *  section on `Ranges` for more information.
 *
 *  @define coll range
 *  @define mayNotTerminateInf
 *  @define willNotTerminateInf
 *  @define doesNotUseBuilders
 *    '''Note:''' this method does not use builders to construct a new range,
 *         and its complexity is O(1).
 */
@SerialVersionUID(7618862778670199309L)
@inline
class Range(val start: Int, val end: Int, val step: Int)
extends scala.collection.AbstractSeq[Int]
   with IndexedSeq[Int]
   with scala.collection.CustomParallelizable[Int, ParRange]
   with Serializable
{
  override def par = new ParRange(this)

  private def gap           = end.toLong - start.toLong
  private def isExact       = gap % step == 0
  private def hasStub       = isInclusive || !isExact
  private def longLength    = gap / step + ( if (hasStub) 1 else 0 )

  // Check cannot be evaluated eagerly because we have a pattern where
  // ranges are constructed like: "x to y by z" The "x to y" piece
  // should not trigger an exception. So the calculation is delayed,
  // which means it will not fail fast for those cases where failing was
  // correct.
  override final val isEmpty = (
       (start > end && step > 0)
    || (start < end && step < 0)
    || (start == end && !isInclusive)
  )
  final val numRangeElements: Int = {
    if (step == 0) throw new IllegalArgumentException("step cannot be 0.")
    else if (isEmpty) 0
    else {
      val len = longLength
      if (len > scala.Int.MaxValue) -1
      else len.toInt
    }
  }
  final val lastElement     = start + (numRangeElements - 1) * step
  final val terminalElement = start + numRangeElements * step

  override def last = if (isEmpty) Nil.last else lastElement

  override def min[A1 >: Int](implicit ord: Ordering[A1]): Int =
    if (ord eq Ordering.Int) {
      if (step > 0) start
      else last
    } else super.min(ord)

  override def max[A1 >: Int](implicit ord: Ordering[A1]): Int =
    if (ord eq Ordering.Int) {
      if (step > 0) last
      else start
    } else super.max(ord)

  protected def copy(start: Int, end: Int, step: Int): Range = new Range(start, end, step)

  /** Create a new range with the `start` and `end` values of this range and
   *  a new `step`.
   *
   *  @return a new range with a different step
   */
  def by(step: Int): Range = copy(start, end, step)

  def isInclusive = false

  override def size = length
  override def length = if (numRangeElements < 0) fail() else numRangeElements

  private def fail() = Range.fail(start, end, step, isInclusive)
  private def validateMaxLength() {
    if (numRangeElements < 0)
      fail()
  }

  def validateRangeBoundaries(f: Int => Any): Boolean = {
    validateMaxLength()

    start != Int.MinValue || end != Int.MinValue || {
      var count = 0
      var num = start
      while (count < numRangeElements) {
        f(num)
        count += 1
        num += step
      }
      false
    }
  }

  final def apply(idx: Int): Int = {
    validateMaxLength()
    if (idx < 0 || idx >= numRangeElements) throw new IndexOutOfBoundsException(idx.toString)
    else start + (step * idx)
  }

  @inline final override def foreach[@specialized(Unit) U](f: Int => U) {
    validateMaxLength()
    val isCommonCase = (start != Int.MinValue || end != Int.MinValue)
    var i = start
    var count = 0
    val terminal = terminalElement
    val step = this.step
    while(
      if(isCommonCase) { i != terminal }
      else             { count < numRangeElements }
    ) {
      f(i)
      count += 1
      i += step
    }
  }

  /** Creates a new range containing the first `n` elements of this range.
   *
   *  $doesNotUseBuilders
   *
   *  @param n  the number of elements to take.
   *  @return   a new range consisting of `n` first elements.
   */
  final override def take(n: Int): Range = (
    if (n <= 0 || isEmpty) newEmptyRange(start)
    else if (n >= numRangeElements) this
    else new Range.Inclusive(start, locationAfterN(n - 1), step)
  )

  /** Creates a new range containing all the elements of this range except the first `n` elements.
   *
   *  $doesNotUseBuilders
   *
   *  @param n  the number of elements to drop.
   *  @return   a new range consisting of all the elements of this range except `n` first elements.
   */
  final override def drop(n: Int): Range = (
    if (n <= 0 || isEmpty) this
    else if (n >= numRangeElements) newEmptyRange(end)
    else copy(locationAfterN(n), end, step)
  )

  /** Creates a new range containing all the elements of this range except the last one.
   *
   *  $doesNotUseBuilders
   *
   *  @return  a new range consisting of all the elements of this range except the last one.
   */
  final override def init: Range = {
    if (isEmpty)
      Nil.init

    dropRight(1)
  }

  /** Creates a new range containing all the elements of this range except the first one.
   *
   *  $doesNotUseBuilders
   *
   *  @return  a new range consisting of all the elements of this range except the first one.
   */
  final override def tail: Range = {
    if (isEmpty)
      Nil.tail

    drop(1)
  }

  // Counts how many elements from the start meet the given test.
  private def skipCount(p: Int => Boolean): Int = {
    var current = start
    var counted = 0

    while (counted < numRangeElements && p(current)) {
      counted += 1
      current += step
    }
    counted
  }
  // Tests whether a number is within the endpoints, without testing
  // whether it is a member of the sequence (i.e. when step > 1.)
  private def isWithinBoundaries(elem: Int) = !isEmpty && (
    (step > 0 && start <= elem && elem <= last ) ||
    (step < 0 &&  last <= elem && elem <= start)
  )
  // Methods like apply throw exceptions on invalid n, but methods like take/drop
  // are forgiving: therefore the checks are with the methods.
  private def locationAfterN(n: Int) = start + (step * n)

  // When one drops everything.  Can't ever have unchecked operations
  // like "end + 1" or "end - 1" because ranges involving Int.{ MinValue, MaxValue }
  // will overflow.  This creates an exclusive range where start == end
  // based on the given value.
  private def newEmptyRange(value: Int) = new Range(value, value, step)

  final override def takeWhile(p: Int => Boolean): Range = take(skipCount(p))
  final override def dropWhile(p: Int => Boolean): Range = drop(skipCount(p))
  final override def span(p: Int => Boolean): (Range, Range) = splitAt(skipCount(p))

  /** Creates a pair of new ranges, first consisting of elements before `n`, and the second
   *  of elements after `n`.
   *
   *  $doesNotUseBuilders
   */
  final override def splitAt(n: Int) = (take(n), drop(n))

  /** Creates a new range consisting of the `length - n` last elements of the range.
   *
   *  $doesNotUseBuilders
   */
  final override def takeRight(n: Int): Range = drop(numRangeElements - n)

  /** Creates a new range consisting of the initial `length - n` elements of the range.
   *
   *  $doesNotUseBuilders
   */
  final override def dropRight(n: Int): Range = take(numRangeElements - n)

  /** Returns the reverse of this range.
   *
   *  $doesNotUseBuilders
   */
  final override def reverse: Range =
    if (isEmpty) this
    else new Range.Inclusive(last, start, -step)

  /** Make range inclusive.
   */
  def inclusive =
    if (isInclusive) this
    else new Range.Inclusive(start, end, step)

  final def contains(x: Int) = isWithinBoundaries(x) && ((x - start) % step == 0)

  final override def sum[B >: Int](implicit num: Numeric[B]): Int = {
    if (isEmpty) 0
    else if (numRangeElements == 1) head
    else (numRangeElements.toLong * (head + last) / 2).toInt
  }

  override def toIterable = this

  override def toSeq = this

  override def equals(other: Any) = other match {
    case x: Range =>
      (x canEqual this) && (length == x.length) && (
        isEmpty ||                            // all empty sequences are equal
        (start == x.start && last == x.last)  // same length and same endpoints implies equality
      )
    case _ =>
      super.equals(other)
  }
  /** Note: hashCode can't be overridden without breaking Seq's
   *  equals contract.
   */

  override def toString() = {
    val endStr = if (numRangeElements > Range.MAX_PRINT) ", ... )" else ")"
    take(Range.MAX_PRINT).mkString("Range(", ", ", endStr)
  }
}

/** A companion object for the `Range` class.
 */
object Range {
  private[immutable] val MAX_PRINT = 512  // some arbitrary value

  private def description(start: Int, end: Int, step: Int, isInclusive: Boolean) =
    "%d %s %d by %s".format(start, if (isInclusive) "to" else "until", end, step)

  private def fail(start: Int, end: Int, step: Int, isInclusive: Boolean) =
    throw new IllegalArgumentException(description(start, end, step, isInclusive) +
        ": seqs cannot contain more than Int.MaxValue elements.")

  /** Counts the number of range elements.
   *  @pre  step != 0
   *  If the size of the range exceeds Int.MaxValue, the
   *  result will be negative.
   */
  def count(start: Int, end: Int, step: Int, isInclusive: Boolean): Int = {
    if (step == 0)
      throw new IllegalArgumentException("step cannot be 0.")

    val isEmpty = (
      if (start == end) !isInclusive
      else if (start < end) step < 0
      else step > 0
    )
    if (isEmpty) 0
    else {
      // Counts with Longs so we can recognize too-large ranges.
      val gap: Long    = end.toLong - start.toLong
      val jumps: Long  = gap / step
      // Whether the size of this range is one larger than the
      // number of full-sized jumps.
      val hasStub      = isInclusive || (gap % step != 0)
      val result: Long = jumps + ( if (hasStub) 1 else 0 )

      if (result > scala.Int.MaxValue) -1
      else result.toInt
    }
  }
  def count(start: Int, end: Int, step: Int): Int =
    count(start, end, step, false)

  @inline
  class Inclusive(start: Int, end: Int, step: Int) extends Range(start, end, step) {
//    override def par = new ParRange(this)
    override def isInclusive = true
    override protected def copy(start: Int, end: Int, step: Int): Range = new Inclusive(start, end, step)
  }

  /** Make a range from `start` until `end` (exclusive) with given step value.
   * @note step != 0
   */
  def apply(start: Int, end: Int, step: Int): Range = new Range(start, end, step)

  /** Make a range from `start` until `end` (exclusive) with step value 1.
   */
  def apply(start: Int, end: Int): Range = new Range(start, end, 1)

  /** Make an inclusive range from `start` to `end` with given step value.
   * @note step != 0
   */
  def inclusive(start: Int, end: Int, step: Int): Range.Inclusive = new Inclusive(start, end, step)

  /** Make an inclusive range from `start` to `end` with step value 1.
   */
  def inclusive(start: Int, end: Int): Range.Inclusive = new Inclusive(start, end, 1)

  // BigInt and Long are straightforward generic ranges.
  object BigInt {
    def apply(start: BigInt, end: BigInt, step: BigInt) = NumericRange(start, end, step)
    def inclusive(start: BigInt, end: BigInt, step: BigInt) = NumericRange.inclusive(start, end, step)
  }

  object Long {
    def apply(start: Long, end: Long, step: Long) = NumericRange(start, end, step)
    def inclusive(start: Long, end: Long, step: Long) = NumericRange.inclusive(start, end, step)
  }

  // BigDecimal uses an alternative implementation of Numeric in which
  // it pretends to be Integral[T] instead of Fractional[T].  See Numeric for
  // details.  The intention is for it to throw an exception anytime
  // imprecision or surprises might result from anything, although this may
  // not yet be fully implemented.
  object BigDecimal {
    implicit val bigDecAsIntegral = scala.math.Numeric.BigDecimalAsIfIntegral

    def apply(start: BigDecimal, end: BigDecimal, step: BigDecimal) =
      NumericRange(start, end, step)
    def inclusive(start: BigDecimal, end: BigDecimal, step: BigDecimal) =
      NumericRange.inclusive(start, end, step)
  }

  // Double works by using a BigDecimal under the hood for precise
  // stepping, but mapping the sequence values back to doubles with
  // .doubleValue.  This constructs the BigDecimals by way of the
  // String constructor (valueOf) instead of the Double one, which
  // is necessary to keep 0.3d at 0.3 as opposed to
  // 0.299999999999999988897769753748434595763683319091796875 or so.
  object Double {
    implicit val bigDecAsIntegral = scala.math.Numeric.BigDecimalAsIfIntegral
    implicit val doubleAsIntegral = scala.math.Numeric.DoubleAsIfIntegral
    def toBD(x: Double): BigDecimal = scala.math.BigDecimal valueOf x

    def apply(start: Double, end: Double, step: Double) =
      BigDecimal(toBD(start), toBD(end), toBD(step)) mapRange (_.doubleValue)

    def inclusive(start: Double, end: Double, step: Double) =
      BigDecimal.inclusive(toBD(start), toBD(end), toBD(step)) mapRange (_.doubleValue)
  }

  // As there is no appealing default step size for not-really-integral ranges,
  // we offer a partially constructed object.
  class Partial[T, U](f: T => U) {
    def by(x: T): U = f(x)
  }

  // Illustrating genericity with Int Range, which should have the same behavior
  // as the original Range class.  However we leave the original Range
  // indefinitely, for performance and because the compiler seems to bootstrap
  // off it and won't do so with our parameterized version without modifications.
  object Int {
    def apply(start: Int, end: Int, step: Int) = NumericRange(start, end, step)
    def inclusive(start: Int, end: Int, step: Int) = NumericRange.inclusive(start, end, step)
  }
}