Achieved similar simplicity gains in NumericRan...

Achieved similar simplicity gains in NumericRange to those now in Range.
Obvious remaining task is to specialize NumericRange and after verifying
the performance, eliminate one or the other. For now, both soldier
onward despite near-convergence of implementation.

Closes #3232, no review.

2 files changed, 88 insertions, 93 deletions

diff --git a/src/library/scala/collection/immutable/NumericRange.scala b/src/library/scala/collection/immutable/NumericRange.scala
index b8bd5bd20e..529a1b22c5 100644
--- a/src/library/scala/collection/immutable/NumericRange.scala
+++ b/src/library/scala/collection/immutable/NumericRange.scala
@@ -29,6 +29,9 @@ import generic._
  *     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
@@ -41,34 +44,19 @@ abstract class NumericRange[T]
   (val start: T, val end: T, val step: T, val isInclusive: Boolean)
   (implicit num: Integral[T])
 extends IndexedSeq[T] {
-
   /** Note that NumericRange must be invariant so that constructs
-   *  such as
-   *
-   *    1L to 10 by 5
-   *
-   *  do not infer the range type as AnyVal.
+   *  such as "1L to 10 by 5" do not infer the range type as AnyVal.
    */
   import num._
 
-  private def fail(msg: String) = throw new IllegalArgumentException(msg)
-
-  if (step equiv zero)
-    fail("NumericRange step cannot be zero.")
-
-  // todo? - we could lift the length restriction by implementing a range as a sequence of
-  // subranges and limiting the subranges to MAX_INT.  There's no other way around it because
-  // the generics we inherit assume integer-based indexing (as well they should.)
-  // The second condition is making sure type T can meaningfully be compared to Int.MaxValue.
-  if (genericLength > fromInt(Int.MaxValue) && (Int.MaxValue == toInt(fromInt(Int.MaxValue))))
-    fail("Implementation restricts ranges to Int.MaxValue elements.")
+  private val numRangeElements: Int =
+    NumericRange.count(start, end, step, isInclusive)
 
-  // inclusive/exclusiveness captured this way because we do not have any
-  // concept of a "unit", we can't just add an epsilon to an exclusive
-  // endpoint to make it inclusive (as can be done with the int-based Range.)
-  protected def limitTest(x: T) = !isEmpty && isInclusive && equiv(x, end)
-
-  protected def underlying = collection.immutable.IndexedSeq.empty[T]
+  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`.
@@ -80,46 +68,49 @@ extends IndexedSeq[T] {
   def copy(start: T, end: T, step: T): NumericRange[T]
 
   override def foreach[U](f: T => U) {
-    var i = start
-    if (step > zero) {
-      while (i < end) {
-        f(i)
-        i += step
-      }
-    } else {
-      while (i > end) {
-        f(i)
-        i += step
-      }
+    var count = 0
+    var current = start
+    while (count < length) {
+      f(current)
+      current += step
+      count += 1
     }
-    if (limitTest(i)) f(i)
   }
 
-  def genericLength: T = {
-    def lim = if (limitTest(end)) one else zero
+  // 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.
 
-    if ((start < end && step < zero) || (start > end && step > zero)) zero
-    else if (equiv(start, end)) lim
-    else {
-      val (steps, left) = (end - start) /% step
-      val last = if (!equiv(left, zero) || isInclusive) one else zero
+  // Counts how many elements from the start meet the given test.
+  private def skipCount(p: T => Boolean): Int = {
+    var current = start
+    var counted = 0
 
-      steps + last
+    while (counted < length && p(current)) {
+      counted += 1
+      current += step
     }
+    counted
   }
-
-  def length: Int = toInt(genericLength)
-  override def isEmpty: Boolean =
-    if (step > zero)
-      if (isInclusive) end < start
-      else end <= start
-    else
-      if (isInclusive) end > start
-      else end >= start
+  // 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)
 
   def apply(idx: Int): T = {
     if (idx < 0 || idx >= length) throw new IndexOutOfBoundsException(idx.toString)
-    else start + (fromInt(idx) * step)
+    else locationAfterN(idx)
   }
 
   // Motivated by the desire for Double ranges with BigDecimal precision,
@@ -162,16 +153,8 @@ extends IndexedSeq[T] {
   }
 
   // a well-typed contains method.
-  def containsTyped(x: T): Boolean = {
-    def divides(d: T, by: T) = equiv(d % by, zero)
-
-    limitTest(x) || (
-      if (step > zero)
-        (start <= x) && (x < end) && divides(x - start, step)
-      else
-        (start >= x) && (x > end) && divides(start - x, step)
-    )
-  }
+  def containsTyped(x: T): Boolean =
+    isWithinBoundaries(x) && (((x - start) % step) == zero)
 
   override def contains(x: Any): Boolean =
     try containsTyped(x.asInstanceOf[T])
@@ -179,13 +162,15 @@ extends IndexedSeq[T] {
 
   override lazy val hashCode = super.hashCode()
   override def equals(other: Any) = other match {
-    case x: NumericRange[_] => (length == x.length) && (length match {
-      case 0  => true
-      case 1  => x.start == start
-      case n  => x.start == start && x.step == step
-    })
-    case _  => super.equals(other)
+    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)
@@ -195,6 +180,34 @@ extends IndexedSeq[T] {
 /** 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: Integral](start: T, end: T, step: T, isInclusive: Boolean): Int = {
+    val num = implicitly[Integral[T]]
+    import num._
+
+    if (step == zero)
+      throw new IllegalArgumentException("step cannot be 0.")
+
+    val longCount: Long =
+      if (start == end) { if (isInclusive) 1 else 0 }
+      else if (end > start != step > zero) 0
+      else {
+        val jumps     = toLong((end - start) / step)
+        val remainder = toLong((end - start) % step)
+
+        if (!isInclusive && zero == remainder) jumps
+        else jumps + 1L
+      }
+
+    if (longCount > scala.Int.MaxValue || longCount < 0L)
+      throw new IllegalArgumentException("Seqs cannot contain more than Int.MaxValue elements.")
+
+    longCount.toInt
+  }
+
   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] =
diff --git a/src/library/scala/collection/immutable/Range.scala b/src/library/scala/collection/immutable/Range.scala
index a400e1416d..b8bccc742f 100644
--- a/src/library/scala/collection/immutable/Range.scala
+++ b/src/library/scala/collection/immutable/Range.scala
@@ -232,31 +232,13 @@ class Range(val start: Int, val end: Int, val step: Int) extends IndexedSeq[Int]
 object Range {
   private[immutable] val MAX_PRINT = 512  // some arbitrary value
 
-  /** 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.
+  /** Counts in "Long arithmetic" so we can recognize overflow.
    */
-  def count(start: Int, end: Int, step: Int): Int = count(start, end, step, false)
-  def count(start: Int, end: Int, step: Int, isInclusive: Boolean): Int = {
-    def exclusiveEnd: Long =
-      if (isInclusive && step < 0) end.toLong - 1
-      else if (isInclusive && step > 0) end.toLong + 1
-      else end.toLong
-
-    if (step == 0)
-      throw new IllegalArgumentException("step cannot be 0.")
-
-    val result: Long =
-      if (start == end) { if (isInclusive) 1 else 0 }
-      else if (end > start != step > 0) 0
-      else if (step.abs == 1) (exclusiveEnd - start) / step
-      else ((exclusiveEnd - start - 1) / step) + 1
-
-    if (result > scala.Int.MaxValue)
-      throw new IllegalArgumentException("Seqs cannot contain more than Int.MaxValue elements.")
-
-    result.toInt
-  }
+  def count(start: Int, end: Int, step: Int): Int =
+    count(start, end, step, false)
+
+  def count(start: Int, end: Int, step: Int, isInclusive: Boolean): Int =
+    NumericRange.count[Long](start, end, step, isInclusive)
 
   class Inclusive(start: Int, end: Int, step: Int) extends Range(start, end, step) {
     override def isInclusive = true