Scala example source code file (NumericRange.scala)

This example Scala source code file (NumericRange.scala) is included in my "Source Code Warehouse" project. The intent of this project is to help you more easily find Scala source code examples by using tags.

All credit for the original source code belongs to scala-lang.org; I'm just trying to make examples easier to find. (For my Scala work, see my Scala examples and tutorials.)

Scala tags/keywords

a, boolean, exclusive, inclusive, int, integral, numericrange, ordering, t, u

The NumericRange.scala Scala example source code

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

package scala
package collection
package immutable

import mutable.{ Builder, ListBuffer }

/** `NumericRange` is a more generic version of the
 *  `Range` class which works with arbitrary types.
 *  It must be supplied with an `Integral` implementation of the
 *  range type.
 *
 *  Factories for likely types include `Range.BigInt`, `Range.Long`,
 *  and `Range.BigDecimal`.  `Range.Int` exists for completeness, but
 *  the `Int`-based `scala.Range` should be more performant.
 *
 *  {{{
 *     val r1 = new Range(0, 100, 1)
 *     val veryBig = Int.MaxValue.toLong + 1
 *     val r2 = Range.Long(veryBig, veryBig + 100, 1)
 *     assert(r1 sameElements r2.map(_ - veryBig))
 *  }}}
 *
 *  TODO: Now the specialization exists there is no clear reason to have
 *  separate classes for Range/NumericRange.  Investigate and consolidate.
 *
 *  @author  Paul Phillips
 *  @version 2.8
 *  @define Coll `NumericRange`
 *  @define coll numeric range
 *  @define mayNotTerminateInf
 *  @define willNotTerminateInf
 */
abstract class NumericRange[T]
  (val start: T, val end: T, val step: T, val isInclusive: Boolean)
  (implicit num: Integral[T])
extends AbstractSeq[T] with IndexedSeq[T] with Serializable {
  /** Note that NumericRange must be invariant so that constructs
   *  such as "1L to 10 by 5" do not infer the range type as AnyVal.
   */
  import num._

  // See comment in Range for why this must be lazy.
  private lazy val numRangeElements: Int =
    NumericRange.count(start, end, step, isInclusive)

  override def length  = numRangeElements
  override def isEmpty = length == 0
  override lazy val last: T =
    if (length == 0) Nil.last
    else locationAfterN(length - 1)

  /** Create a new range with the start and end values of this range and
   *  a new `step`.
   */
  def by(newStep: T): NumericRange[T] = copy(start, end, newStep)

  /** Create a copy of this range.
   */
  def copy(start: T, end: T, step: T): NumericRange[T]

  override def foreach[U](f: T => U) {
    var count = 0
    var current = start
    while (count < length) {
      f(current)
      current += step
      count += 1
    }
  }

  // TODO: these private methods are straight copies from Range, duplicated
  // to guard against any (most likely illusory) performance drop.  They should
  // be eliminated one way or another.

  // 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: T) = !isEmpty && (
    (step > zero && start <= elem && elem <= last ) ||
    (step < zero &&  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): T = start + (step * fromInt(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: T) = NumericRange(value, value, step)

  final override def take(n: Int): NumericRange[T] = (
    if (n <= 0 || length == 0) newEmptyRange(start)
    else if (n >= length) this
    else new NumericRange.Inclusive(start, locationAfterN(n - 1), step)
  )

  final override def drop(n: Int): NumericRange[T] = (
    if (n <= 0 || length == 0) this
    else if (n >= length) newEmptyRange(end)
    else copy(locationAfterN(n), end, step)
  )

  def apply(idx: Int): T = {
    if (idx < 0 || idx >= length) throw new IndexOutOfBoundsException(idx.toString)
    else locationAfterN(idx)
  }

  import NumericRange.defaultOrdering

  override def min[T1 >: T](implicit ord: Ordering[T1]): T =
    if (ord eq defaultOrdering(num)) {
      if (num.signum(step) > 0) start
      else last
    } else super.min(ord)

  override def max[T1 >: T](implicit ord: Ordering[T1]): T =
    if (ord eq defaultOrdering(num)) {
      if (num.signum(step) > 0) last
      else start
    } else super.max(ord)

  // Motivated by the desire for Double ranges with BigDecimal precision,
  // we need some way to map a Range and get another Range.  This can't be
  // done in any fully general way because Ranges are not arbitrary
  // sequences but step-valued, so we have a custom method only we can call
  // which we promise to use responsibly.
  //
  // The point of it all is that
  //
  //   0.0 to 1.0 by 0.1
  //
  // should result in
  //
  //   NumericRange[Double](0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0)
  //
  // and not
  //
  //   NumericRange[Double](0.0, 0.1, 0.2, 0.30000000000000004, 0.4, 0.5, 0.6000000000000001, 0.7000000000000001, 0.8, 0.9)
  //
  // or perhaps more importantly,
  //
  //   (0.1 to 0.3 by 0.1 contains 0.3) == true
  //
  private[immutable] def mapRange[A](fm: T => A)(implicit unum: Integral[A]): NumericRange[A] = {
    val self = this

    // XXX This may be incomplete.
    new NumericRange[A](fm(start), fm(end), fm(step), isInclusive) {
      def copy(start: A, end: A, step: A): NumericRange[A] =
        if (isInclusive) NumericRange.inclusive(start, end, step)
        else NumericRange(start, end, step)

      private lazy val underlyingRange: NumericRange[T] = self
      override def foreach[U](f: A => U) { underlyingRange foreach (x => f(fm(x))) }
      override def isEmpty = underlyingRange.isEmpty
      override def apply(idx: Int): A = fm(underlyingRange(idx))
      override def containsTyped(el: A) = underlyingRange exists (x => fm(x) == el)
    }
  }

  // a well-typed contains method.
  def containsTyped(x: T): Boolean =
    isWithinBoundaries(x) && (((x - start) % step) == zero)

  override def contains[A1 >: T](x: A1): Boolean =
    try containsTyped(x.asInstanceOf[T])
    catch { case _: ClassCastException => false }

  final override def sum[B >: T](implicit num: Numeric[B]): B = {
    // arithmetic series formula  can be used for regular addition
    if ((num eq scala.math.Numeric.IntIsIntegral)||
        (num eq scala.math.Numeric.BigIntIsIntegral)||
        (num eq scala.math.Numeric.ShortIsIntegral)||
        (num eq scala.math.Numeric.ByteIsIntegral)||
        (num eq scala.math.Numeric.CharIsIntegral)||
        (num eq scala.math.Numeric.LongIsIntegral)||
        (num eq scala.math.Numeric.FloatAsIfIntegral)||
        (num eq scala.math.Numeric.BigDecimalIsFractional)||
        (num eq scala.math.Numeric.DoubleAsIfIntegral)) {
      val numAsIntegral = num.asInstanceOf[Integral[B]]
      import numAsIntegral._
      if (isEmpty) num fromInt 0
      else if (numRangeElements == 1) head
      else ((num fromInt numRangeElements) * (head + last) / (num fromInt 2))
    } else {
      // user provided custom Numeric, we cannot rely on arithmetic series formula
      if (isEmpty) num.zero
      else {
        var acc = num.zero
        var i = head
        var idx = 0
        while(idx < length) {
          acc = num.plus(acc, i)
          i = i + step
          idx = idx + 1
        }
        acc
      }
    }
  }

  override lazy val hashCode = super.hashCode()
  override def equals(other: Any) = other match {
    case x: NumericRange[_] =>
      (x canEqual this) && (length == x.length) && (
        (length == 0) ||                      // all empty sequences are equal
        (start == x.start && last == x.last)  // same length and same endpoints implies equality
      )
    case _ =>
      super.equals(other)
  }

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

/** A companion object for numeric ranges.
 */
object NumericRange {

  /** Calculates the number of elements in a range given start, end, step, and
   *  whether or not it is inclusive.  Throws an exception if step == 0 or
   *  the number of elements exceeds the maximum Int.
   */
  def count[T](start: T, end: T, step: T, isInclusive: Boolean)(implicit num: Integral[T]): Int = {
    val zero    = num.zero
    val upward  = num.lt(start, end)
    val posStep = num.gt(step, zero)

    if (step == zero) throw new IllegalArgumentException("step cannot be 0.")
    else if (start == end) if (isInclusive) 1 else 0
    else if (upward != posStep) 0
    else {
      /* We have to be frightfully paranoid about running out of range.
       * We also can't assume that the numbers will fit in a Long.
       * We will assume that if a > 0, -a can be represented, and if
       * a < 0, -a+1 can be represented.  We also assume that if we
       * can't fit in Int, we can represent 2*Int.MaxValue+3 (at least).
       * And we assume that numbers wrap rather than cap when they overflow.
       */
      // Check whether we can short-circuit by deferring to Int range.
      val startint = num.toInt(start)
      if (start == num.fromInt(startint)) {
        val endint = num.toInt(end)
        if (end == num.fromInt(endint)) {
          val stepint = num.toInt(step)
          if (step == num.fromInt(stepint)) {
            return {
              if (isInclusive) Range.inclusive(startint, endint, stepint).length
              else             Range          (startint, endint, stepint).length
            }
          }
        }
      }
      // If we reach this point, deferring to Int failed.
      // Numbers may be big.
      val one = num.one
      val limit = num.fromInt(Int.MaxValue)
      def check(t: T): T = 
        if (num.gt(t, limit)) throw new IllegalArgumentException("More than Int.MaxValue elements.")
        else t
      // If the range crosses zero, it might overflow when subtracted
      val startside = num.signum(start)
      val endside = num.signum(end)
      num.toInt{
        if (startside*endside >= 0) {
          // We're sure we can subtract these numbers.
          // Note that we do not use .rem because of different conventions for Long and BigInt
          val diff = num.minus(end, start)
          val quotient = check(num.quot(diff, step))
          val remainder = num.minus(diff, num.times(quotient, step))
          if (!isInclusive && zero == remainder) quotient else check(num.plus(quotient, one))
        }
        else {
          // We might not even be able to subtract these numbers.
          // Jump in three pieces:
          //   * start to -1 or 1, whichever is closer (waypointA)
          //   * one step, which will take us at least to 0 (ends at waypointB)
          //   * there to the end
          val negone = num.fromInt(-1)
          val startlim  = if (posStep) negone else one
          val startdiff = num.minus(startlim, start)
          val startq    = check(num.quot(startdiff, step))
          val waypointA = if (startq == zero) start else num.plus(start, num.times(startq, step))
          val waypointB = num.plus(waypointA, step)
          check {
            if (num.lt(waypointB, end) != upward) {
              // No last piece
              if (isInclusive && waypointB == end) num.plus(startq, num.fromInt(2))
              else num.plus(startq, one)
            }
            else {
              // There is a last piece
              val enddiff = num.minus(end,waypointB)
              val endq    = check(num.quot(enddiff, step))
              val last    = if (endq == zero) waypointB else num.plus(waypointB, num.times(endq, step))
              // Now we have to tally up all the pieces
              //   1 for the initial value
              //   startq steps to waypointA
              //   1 step to waypointB
              //   endq steps to the end (one less if !isInclusive and last==end)
              num.plus(startq, num.plus(endq, if (!isInclusive && last==end) one else num.fromInt(2)))
            }
          }
        }
      }
    }
  }

  class Inclusive[T](start: T, end: T, step: T)(implicit num: Integral[T])
  extends NumericRange(start, end, step, true) {
    def copy(start: T, end: T, step: T): Inclusive[T] =
      NumericRange.inclusive(start, end, step)

    def exclusive: Exclusive[T] = NumericRange(start, end, step)
  }

  class Exclusive[T](start: T, end: T, step: T)(implicit num: Integral[T])
  extends NumericRange(start, end, step, false) {
    def copy(start: T, end: T, step: T): Exclusive[T] =
      NumericRange(start, end, step)

    def inclusive: Inclusive[T] = NumericRange.inclusive(start, end, step)
  }

  def apply[T](start: T, end: T, step: T)(implicit num: Integral[T]): Exclusive[T] =
    new Exclusive(start, end, step)
  def inclusive[T](start: T, end: T, step: T)(implicit num: Integral[T]): Inclusive[T] =
    new Inclusive(start, end, step)

  private[collection] val defaultOrdering = Map[Numeric[_], Ordering[_]](
    Numeric.BigIntIsIntegral -> Ordering.BigInt,
    Numeric.IntIsIntegral -> Ordering.Int,
    Numeric.ShortIsIntegral -> Ordering.Short,
    Numeric.ByteIsIntegral -> Ordering.Byte,
    Numeric.CharIsIntegral -> Ordering.Char,
    Numeric.LongIsIntegral -> Ordering.Long,
    Numeric.FloatAsIfIntegral -> Ordering.Float,
    Numeric.DoubleAsIfIntegral -> Ordering.Double,
    Numeric.BigDecimalAsIfIntegral -> Ordering.BigDecimal
  )

}