8000 Makes Range#sum an O(1) operation instead of an O(n) one. by soc · Pull Request #83 · scala/legacy-svn-scala · GitHub
[go: up one dir, main page]

Skip to content
This repository was archived by the owner on Feb 23, 2018. It is now read-only.

Makes Range#sum an O(1) operation instead of an O(n) one. #83

Closed
wants to merge 1 commit into from
Closed
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
6 changes: 6 additions & 0 deletions src/library/scala/collection/immutable/Range.scala
Original file line number Diff line number Diff line change
Expand Up @@ -209,6 +209,12 @@ extends IndexedSeq[Int]
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 = {
val len = length
if (len > 0) (len.toLong * (head + last) / 2).toInt
else 0
}

override def toIterable = this

Expand Down
80 changes: 80 additions & 0 deletions test/files/run/t4658.check
Original file line number Diff line number Diff line change
@@ -0,0 +1,80 @@
Ranges:
1073741824
1073741824
0
0
55
25
1
-45
-55
0
-24
-30
0
-40
-55
-10
-24
-30
-10
IntRanges:
Disabled #1
Disabled #2
0
0
55
25
1
-45
-55
0
-24
-30
0
-40
-55
-10
-24
-30
-10
LongRanges:
Disabled #1
Disabled #2
0
0
55
25
1
-45
-55
0
-24
-30
0
-40
-55
-10
-24
-30
-10
BigIntRanges:
Disabled #1
Disabled #2
0
0
55
25
1
-45
-55
0
-24
-30
0
-40
-55
-10
-24
-30
-10
41 changes: 41 additions & 0 deletions test/files/run/t4658.scala
Original file line number Diff line number Diff line change
@@ -0,0 +1,41 @@
import scala.collection.immutable.NumericRange
//#4658
object Test {

case class R(start: Int, end: Int, step: Int = 1, inclusive: Boolean = true)

val rangeData = Array(
R(1, Int.MaxValue), R(-Int.MaxValue, -1), R(0, 0), R(0,0, inclusive = false), R(1,10),
R(1,10,2), R(1,10,11), R(-10, -5), R(-10, 0), R(-10, 10), R(-10, -5, 2), R(-10, 0, 2), R(-10, 10, 2),
R(-10, -5, inclusive = false), R(-10, 0, inclusive = false), R(-10, 10, inclusive = false),
R(-10, -5, 2, inclusive = false), R(-10, 0, 2, inclusive = false), R(-10, 10, 2, inclusive = false)
)

def ranges = rangeData.map(r => if (r.inclusive) r.start to r.end by r.step else r.start until r.end by r.step)

def numericIntRanges = rangeData.map(r => if (r.inclusive) NumericRange.inclusive(r.start, r.end, r.step) else NumericRange(r.start, r.end, r.step))

def numericLongRanges = rangeData.map(r => if (r.inclusive) NumericRange.inclusive(r.start.toLong, r.end, r.step) else NumericRange(r.start.toLong, r.end, r.step))

def numericBigIntRanges = rangeData.map(r => if (r.inclusive) NumericRange.inclusive(BigInt(r.start), BigInt(r.end), BigInt(r.step)) else NumericRange(BigInt(r.start), BigInt(r.end), BigInt(r.step)))

def main(args: Array[String]) {
// We drop the first two tests for all ranges which don't have a decent sum implementation,
// because it is just too slow.
println("Ranges:")
ranges.foreach{range => println(range.sum)}
println("IntRanges:")
println("Disabled #1")
println("Disabled #2")
numericIntRanges.drop(2).foreach{range => println(range.sum)}
println("LongRanges:")
println("Disabled #1")
println("Disabled #2")
numericLongRanges.drop(2).foreach{range => println(range.sum)}
println("BigIntRanges:")
println("Disabled #1")
println("Disabled #2")
numericBigIntRanges.drop(2).foreach{range => println(range.sum)}
}

}
0