1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2006-2011, 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 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)
class Range(val start: Int, val end: Int, val step: Int)
extends collection.AbstractSeq[Int]
with IndexedSeq[Int]
with 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
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 description = "%d %s %d by %s".format(start, if (isInclusive) "to" else "until", end, step)
private def fail() = throw new IllegalArgumentException(description + ": seqs cannot contain more than Int.MaxValue elements.")
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
}
}
@inline 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) {
if (validateRangeBoundaries(f)) {
var i = start
val terminal = terminalElement
val step = this.step
while (i != terminal) {
f(i)
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
/** 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)
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 an range from `start` to `end` inclusive 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
*/
@inline 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.
*/
@inline 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)
}
}
|