diff options
| -rw-r--r-- | src/library/scala/collection/immutable/NumericRange.scala | 151 | ||||
| -rw-r--r-- | src/library/scala/collection/immutable/Range.scala | 30 | ||||
| -rw-r--r-- | test/files/run/range.scala | 17 |
3 files changed, 97 insertions, 101 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 diff --git a/test/files/run/range.scala b/test/files/run/range.scala index 02b48fad7c..31d90f2d6d 100644 --- a/test/files/run/range.scala +++ b/test/files/run/range.scala @@ -16,14 +16,15 @@ object Test { def gr2 = NumericRange.inclusive(x, x, x) def gr3 = NumericRange(x, x * fromInt(10), x) def gr4 = NumericRange.inclusive(x, x * fromInt(10), x) - - def check = assert( - gr1.isEmpty && !gr2.isEmpty && - gr3.size == 9 && gr4.size == 10 && - (gr3.toList ::: negated.gr3.toList).sum == num.zero && - !(gr3 contains (x * fromInt(10))) && - (gr4 contains (x * fromInt(10))) - ) + def gr5 = gr3.toList ::: negated.gr3.toList + + def check = { + assert(gr1.isEmpty && !gr2.isEmpty) + assert(gr3.size == 9 && gr4.size == 10) + assert(gr5.sum == num.zero, gr5.toString) + assert(!(gr3 contains (x * fromInt(10)))) + assert((gr4 contains (x * fromInt(10)))) + } } def main(args: Array[String]): Unit = { |