summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--bincompat-forward.whitelist.conf53
-rw-r--r--spec/05-classes-and-objects.md1
-rw-r--r--src/library/scala/collection/immutable/List.scala2
-rw-r--r--src/library/scala/util/Sorting.scala712
-rw-r--r--src/repl/scala/tools/nsc/interpreter/IMain.scala48
-rw-r--r--src/repl/scala/tools/nsc/interpreter/Imports.scala24
-rw-r--r--test/files/run/repl-serialization.check25
-rw-r--r--test/files/run/repl-serialization.scala68
-rw-r--r--test/files/run/t7747-repl.check41
-rw-r--r--test/files/run/t7747-repl.scala6
-rw-r--r--test/junit/scala/util/SortingTest.scala69
11 files changed, 547 insertions, 502 deletions
diff --git a/bincompat-forward.whitelist.conf b/bincompat-forward.whitelist.conf
index 3808083dd3..8fadb65f39 100644
--- a/bincompat-forward.whitelist.conf
+++ b/bincompat-forward.whitelist.conf
@@ -319,6 +319,59 @@ filter {
{
matchName="scala.util.Random.scala$util$Random$$nextAlphaNum$1"
problemName=MissingMethodProblem
+ },
+ // Nominally private but in practice JVM-visible methods for reworked scala.util.Sorting
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$default$5"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mBc$sp"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mFc$sp"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mJc$sp"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mCc$sp"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mSc$sp"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$insertionSort"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mZc$sp"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mDc$sp"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mIc$sp"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$mergeSorted"
+ problemName=MissingMethodProblem
+ },
+ {
+ matchName="scala.util.Sorting.scala$util$Sorting$$booleanSort"
+ problemName=MissingMethodProblem
}
]
}
diff --git a/spec/05-classes-and-objects.md b/spec/05-classes-and-objects.md
index 28abe6c3bc..8be792d3cb 100644
--- a/spec/05-classes-and-objects.md
+++ b/spec/05-classes-and-objects.md
@@ -395,6 +395,7 @@ class C extends A with B { type T <: C }
Let $C$ be a class type. The _inheritance closure_ of $C$ is the
smallest set $\mathscr{S}$ of types such that
+- $C$ is in $\mathscr{S}$.
- If $T$ is in $\mathscr{S}$, then every type $T'$ which forms syntactically
a part of $T$ is also in $\mathscr{S}$.
- If $T$ is a class type in $\mathscr{S}$, then all [parents](#templates)
diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala
index 254f14f13c..82e38d3549 100644
--- a/src/library/scala/collection/immutable/List.scala
+++ b/src/library/scala/collection/immutable/List.scala
@@ -462,6 +462,7 @@ object List extends SeqFactory[List] {
private class SerializationProxy[A](@transient private var orig: List[A]) extends Serializable {
private def writeObject(out: ObjectOutputStream) {
+ out.defaultWriteObject()
var xs: List[A] = orig
while (!xs.isEmpty) {
out.writeObject(xs.head)
@@ -473,6 +474,7 @@ object List extends SeqFactory[List] {
// Java serialization calls this before readResolve during de-serialization.
// Read the whole list and store it in `orig`.
private def readObject(in: ObjectInputStream) {
+ in.defaultReadObject()
val builder = List.newBuilder[A]
while (true) in.readObject match {
case ListSerializeEnd =>
diff --git a/src/library/scala/util/Sorting.scala b/src/library/scala/util/Sorting.scala
index 2e021ad9d9..ee2bdbc4a7 100644
--- a/src/library/scala/util/Sorting.scala
+++ b/src/library/scala/util/Sorting.scala
@@ -1,6 +1,6 @@
/* __ *\
** ________ ___ / / ___ Scala API **
-** / __/ __// _ | / / / _ | (c) 2006-2009, Ross Judson **
+** / __/ __// _ | / / / _ | (c) 2006-2015, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
@@ -9,518 +9,276 @@
package scala
package util
-import scala.reflect.{ ClassTag, classTag }
-import scala.math.{ Ordering, max, min }
+import scala.reflect.ClassTag
+import scala.math.Ordering
-/** The Sorting object provides functions that can sort various kinds of
- * objects. You can provide a comparison function, or you can request a sort
- * of items that are viewable as [[scala.math.Ordered]]. Some sorts that
- * operate directly on a subset of value types are also provided. These
- * implementations are derived from those in the Sun JDK.
+/** The `Sorting` object provides convenience wrappers for `java.util.Arrays.sort`.
+ * Methods that defer to `java.util.Arrays.sort` say that they do or under what
+ * conditions that they do.
*
- * Note that stability doesn't matter for value types, so use the `quickSort`
- * variants for those. `stableSort` is intended to be used with
- * objects when the prior ordering should be preserved, where possible.
+ * `Sorting` also implements a general-purpose quicksort and stable (merge) sort
+ * for those cases where `java.util.Arrays.sort` could only be used at the cost
+ * of a large memory penalty. If performance rather than memory usage is the
+ * primary concern, one may wish to find alternate strategies to use
+ * `java.util.Arrays.sort` directly e.g. by boxing primitives to use
+ * a custom ordering on them.
+ *
+ * `Sorting` provides methods where you can provide a comparison function, or
+ * can request a sort of items that are [[scala.math.Ordered]] or that
+ * otherwise have an implicit or explicit [[scala.math.Ordering]].
+ *
+ * Note also that high-performance non-default sorts for numeric types
+ * are not provided. If this is required, it is advisable to investigate
+ * other libraries that cover this use case.
*
* @author Ross Judson
- * @version 1.0
+ * @author Adriaan Moors
+ * @author Rex Kerr
+ * @version 1.1
*/
object Sorting {
- /** Quickly sort an array of Doubles. */
- def quickSort(a: Array[Double]) { sort1(a, 0, a.length) }
-
- /** Quickly sort an array of items with an implicit Ordering. */
- def quickSort[K: Ordering](a: Array[K]) { sort1(a, 0, a.length) }
-
- /** Quickly sort an array of Ints. */
- def quickSort(a: Array[Int]) { sort1(a, 0, a.length) }
-
- /** Quickly sort an array of Floats. */
- def quickSort(a: Array[Float]) { sort1(a, 0, a.length) }
-
- /** Sort an array of K where K is Ordered, preserving the existing order
- * where the values are equal. */
- def stableSort[K: ClassTag: Ordering](a: Array[K]) {
- stableSort(a, 0, a.length-1, new Array[K](a.length), Ordering[K].lt _)
- }
+ /** Sort an array of Doubles using `java.util.Arrays.sort`. */
+ def quickSort(a: Array[Double]): Unit = java.util.Arrays.sort(a)
- /** Sorts an array of `K` given an ordering function `f`.
- * `f` should return `true` iff its first parameter is strictly less than its second parameter.
- */
- def stableSort[K: ClassTag](a: Array[K], f: (K, K) => Boolean) {
- stableSort(a, 0, a.length-1, new Array[K](a.length), f)
- }
+ /** Sort an array of Ints using `java.util.Arrays.sort`. */
+ def quickSort(a: Array[Int]): Unit = java.util.Arrays.sort(a)
- /** Sorts an arbitrary sequence into an array, given a comparison function
- * that should return `true` iff parameter one is strictly less than parameter two.
- *
- * @param a the sequence to be sorted.
- * @param f the comparison function.
- * @return the sorted sequence of items.
- */
- def stableSort[K: ClassTag](a: Seq[K], f: (K, K) => Boolean): Array[K] = {
- val ret = a.toArray
- stableSort(ret, f)
- ret
- }
+ /** Sort an array of Floats using `java.util.Arrays.sort`. */
+ def quickSort(a: Array[Float]): Unit = java.util.Arrays.sort(a)
+
+ private final val qsortThreshold = 16
- /** Sorts an arbitrary sequence of items that are viewable as ordered. */
- def stableSort[K: ClassTag: Ordering](a: Seq[K]): Array[K] =
- stableSort(a, Ordering[K].lt _)
-
- /** Stably sorts a sequence of items given an extraction function that will
- * return an ordered key from an item.
- *
- * @param a the sequence to be sorted.
- * @param f the comparison function.
- * @return the sorted sequence of items.
- */
- def stableSort[K: ClassTag, M: Ordering](a: Seq[K], f: K => M): Array[K] =
- stableSort(a)(implicitly[ClassTag[K]], Ordering[M] on f)
-
- private def sort1[K: Ordering](x: Array[K], off: Int, len: Int) {
- val ord = Ordering[K]
- import ord._
-
- def swap(a: Int, b: Int) {
- val t = x(a)
- x(a) = x(b)
- x(b) = t
- }
- def vecswap(_a: Int, _b: Int, n: Int) {
- var a = _a
- var b = _b
- var i = 0
- while (i < n) {
- swap(a, b)
- i += 1
- a += 1
- b += 1
- }
- }
- def med3(a: Int, b: Int, c: Int) = {
- if (x(a) < x(b)) {
- if (x(b) < x(c)) b else if (x(a) < x(c)) c else a
- } else {
- if (x(b) > x(c)) b else if (x(a) > x(c)) c else a
- }
- }
- def sort2(off: Int, len: Int) {
- // Insertion sort on smallest arrays
- if (len < 7) {
- var i = off
- while (i < len + off) {
- var j = i
- while (j > off && x(j-1) > x(j)) {
- swap(j, j-1)
- j -= 1
+ /** Sort array `a` with quicksort, using the Ordering on its elements.
+ * This algorithm sorts in place, so no additional memory is used aside from
+ * what might be required to box individual elements during comparison.
+ */
+ def quickSort[K: Ordering](a: Array[K]): Unit = {
+ // Must have iN >= i0 or math will fail. Also, i0 >= 0.
+ def inner(a: Array[K], i0: Int, iN: Int, ord: Ordering[K]): Unit = {
+ if (iN - i0 < qsortThreshold) insertionSort(a, i0, iN, ord)
+ else {
+ var iK = (i0 + iN) >>> 1 // Unsigned div by 2
+ // Find index of median of first, central, and last elements
+ var pL =
+ if (ord.compare(a(i0), a(iN - 1)) <= 0)
+ if (ord.compare(a(i0), a(iK)) < 0)
+ if (ord.compare(a(iN - 1), a(iK)) < 0) iN - 1 else iK
+ else i0
+ else
+ if (ord.compare(a(i0), a(iK)) < 0) i0
+ else
+ if (ord.compare(a(iN - 1), a(iK)) <= 0) iN - 1
+ else iK
+ val pivot = a(pL)
+ // pL is the start of the pivot block; move it into the middle if needed
+ if (pL != iK) { a(pL) = a(iK); a(iK) = pivot; pL = iK }
+ // Elements equal to the pivot will be in range pL until pR
+ var pR = pL + 1
+ // Items known to be less than pivot are below iA (range i0 until iA)
+ var iA = i0
+ // Items known to be greater than pivot are at or above iB (range iB until iN)
+ var iB = iN
+ // Scan through everything in the buffer before the pivot(s)
+ while (pL - iA > 0) {
+ val current = a(iA)
+ ord.compare(current, pivot) match {
+ case 0 =>
+ // Swap current out with pivot block
+ a(iA) = a(pL - 1)
+ a(pL - 1) = current
+ pL -= 1
+ case x if x < 0 =>
+ // Already in place. Just update indicies.
+ iA += 1
+ case _ if iB > pR =>
+ // Wrong side. There's room on the other side, so swap
+ a(iA) = a(iB - 1)
+ a(iB - 1) = current
+ iB -= 1
+ case _ =>
+ // Wrong side and there is no room. Swap by rotating pivot block.
+ a(iA) = a(pL - 1)
+ a(pL - 1) = a(pR - 1)
+ a(pR - 1) = current
+ pL -= 1
+ pR -= 1
+ iB -= 1
}
- i += 1
}
- } else {
- // Choose a partition element, v
- var m = off + (len >> 1) // Small arrays, middle element
- if (len > 7) {
- var l = off
- var n = off + len - 1
- if (len > 40) { // Big arrays, pseudomedian of 9
- val s = len / 8
- l = med3(l, l+s, l+2*s)
- m = med3(m-s, m, m+s)
- n = med3(n-2*s, n-s, n)
+ // Get anything remaining in buffer after the pivot(s)
+ while (iB - pR > 0) {
+ val current = a(iB - 1)
+ ord.compare(current, pivot) match {
+ case 0 =>
+ // Swap current out with pivot block
+ a(iB - 1) = a(pR)
+ a(pR) = current
+ pR += 1
+ case x if x > 0 =>
+ // Already in place. Just update indices.
+ iB -= 1
+ case _ =>
+ // Wrong side and we already know there is no room. Swap by rotating pivot block.
+ a(iB - 1) = a(pR)
+ a(pR) = a(pL)
+ a(pL) = current
+ iA += 1
+ pL += 1
+ pR += 1
}
- m = med3(l, m, n) // Mid-size, med of 3
}
- val v = x(m)
-
- // Establish Invariant: v* (<v)* (>v)* v*
- var a = off
- var b = a
- var c = off + len - 1
- var d = c
- var done = false
- while (!done) {
- while (b <= c && x(b) <= v) {
- if (x(b) equiv v) {
- swap(a, b)
- a += 1
- }
- b += 1
- }
- while (c >= b && x(c) >= v) {
- if (x(c) equiv v) {
- swap(c, d)
- d -= 1
- }
- c -= 1
- }
- if (b > c) {
- done = true
- } else {
- swap(b, c)
- c -= 1
- b += 1
- }
+ // Use tail recursion on large half (Sedgewick's method) so we don't blow up the stack if pivots are poorly chosen
+ if (iA - i0 < iN - iB) {
+ inner(a, i0, iA, ord) // True recursion
+ inner(a, iB, iN, ord) // Should be tail recursion
+ }
+ else {
+ inner(a, iB, iN, ord) // True recursion
+ inner(a, i0, iA, ord) // Should be tail recursion
}
-
- // Swap partition elements back to middle
- val n = off + len
- var s = math.min(a-off, b-a)
- vecswap(off, b-s, s)
- s = math.min(d-c, n-d-1)
- vecswap(b, n-s, s)
-
- // Recursively sort non-partition-elements
- s = b - a
- if (s > 1)
- sort2(off, s)
- s = d - c
- if (s > 1)
- sort2(n-s, s)
}
}
- sort2(off, len)
+ inner(a, 0, a.length, implicitly[Ordering[K]])
}
-
- private def sort1(x: Array[Int], off: Int, len: Int) {
- def swap(a: Int, b: Int) {
- val t = x(a)
- x(a) = x(b)
- x(b) = t
+
+ private final val mergeThreshold = 32
+
+ // Ordering[T] might be slow especially for boxed primitives, so use binary search variant of insertion sort
+ // Caller must pass iN >= i0 or math will fail. Also, i0 >= 0.
+ private def insertionSort[@specialized T](a: Array[T], i0: Int, iN: Int, ord: Ordering[T]): Unit = {
+ val n = iN - i0
+ if (n < 2) return
+ if (ord.compare(a(i0), a(i0+1)) > 0) {
+ val temp = a(i0)
+ a(i0) = a(i0+1)
+ a(i0+1) = temp
}
- def vecswap(_a: Int, _b: Int, n: Int) {
- var a = _a
- var b = _b
- var i = 0
- while (i < n) {
- swap(a, b)
- i += 1
- a += 1
- b += 1
- }
- }
- def med3(a: Int, b: Int, c: Int) = {
- if (x(a) < x(b)) {
- if (x(b) < x(c)) b else if (x(a) < x(c)) c else a
- } else {
- if (x(b) > x(c)) b else if (x(a) > x(c)) c else a
- }
- }
- def sort2(off: Int, len: Int) {
- // Insertion sort on smallest arrays
- if (len < 7) {
- var i = off
- while (i < len + off) {
- var j = i
- while (j>off && x(j-1) > x(j)) {
- swap(j, j-1)
- j -= 1
- }
- i += 1
+ var m = 2
+ while (m < n) {
+ // Speed up already-sorted case by checking last element first
+ val next = a(i0 + m)
+ if (ord.compare(next, a(i0+m-1)) < 0) {
+ var iA = i0
+ var iB = i0 + m - 1
+ while (iB - iA > 1) {
+ val ix = (iA + iB) >>> 1 // Use bit shift to get unsigned div by 2
+ if (ord.compare(next, a(ix)) < 0) iB = ix
+ else iA = ix
}
- } else {
- // Choose a partition element, v
- var m = off + (len >> 1) // Small arrays, middle element
- if (len > 7) {
- var l = off
- var n = off + len - 1
- if (len > 40) { // Big arrays, pseudomedian of 9
- val s = len / 8
- l = med3(l, l+s, l+2*s)
- m = med3(m-s, m, m+s)
- n = med3(n-2*s, n-s, n)
- }
- m = med3(l, m, n) // Mid-size, med of 3
- }
- val v = x(m)
-
- // Establish Invariant: v* (<v)* (>v)* v*
- var a = off
- var b = a
- var c = off + len - 1
- var d = c
- var done = false
- while (!done) {
- while (b <= c && x(b) <= v) {
- if (x(b) == v) {
- swap(a, b)
- a += 1
- }
- b += 1
- }
- while (c >= b && x(c) >= v) {
- if (x(c) == v) {
- swap(c, d)
- d -= 1
- }
- c -= 1
- }
- if (b > c) {
- done = true
- } else {
- swap(b, c)
- c -= 1
- b += 1
- }
+ val ix = iA + (if (ord.compare(next, a(iA)) < 0) 0 else 1)
+ var i = i0 + m
+ while (i > ix) {
+ a(i) = a(i-1)
+ i -= 1
}
-
- // Swap partition elements back to middle
- val n = off + len
- var s = math.min(a-off, b-a)
- vecswap(off, b-s, s)
- s = math.min(d-c, n-d-1)
- vecswap(b, n-s, s)
-
- // Recursively sort non-partition-elements
- s = b - a
- if (s > 1)
- sort2(off, s)
- s = d - c
- if (s > 1)
- sort2(n-s, s)
+ a(ix) = next
}
+ m += 1
}
- sort2(off, len)
}
-
- private def sort1(x: Array[Double], off: Int, len: Int) {
- def swap(a: Int, b: Int) {
- val t = x(a)
- x(a) = x(b)
- x(b) = t
+
+ // Caller is required to pass iN >= i0, else math will fail. Also, i0 >= 0.
+ private def mergeSort[@specialized T: ClassTag](a: Array[T], i0: Int, iN: Int, ord: Ordering[T], scratch: Array[T] = null): Unit = {
+ if (iN - i0 < mergeThreshold) insertionSort(a, i0, iN, ord)
+ else {
+ val iK = (i0 + iN) >>> 1 // Bit shift equivalent to unsigned math, no overflow
+ val sc = if (scratch eq null) new Array[T](iK - i0) else scratch
+ mergeSort(a, i0, iK, ord, sc)
+ mergeSort(a, iK, iN, ord, sc)
+ mergeSorted(a, i0, iK, iN, ord, sc)
}
- def vecswap(_a: Int, _b: Int, n: Int) {
- var a = _a
- var b = _b
- var i = 0
- while (i < n) {
- swap(a, b)
+ }
+
+ // Must have 0 <= i0 < iK < iN
+ private def mergeSorted[@specialized T](a: Array[T], i0: Int, iK: Int, iN: Int, ord: Ordering[T], scratch: Array[T]): Unit = {
+ // Check to make sure we're not already in order
+ if (ord.compare(a(iK-1), a(iK)) > 0) {
+ var i = i0
+ val jN = iK - i0
+ var j = 0
+ while (i < iK) {
+ scratch (j) = a(i)
i += 1
- a += 1
- b += 1
- }
- }
- def med3(a: Int, b: Int, c: Int) = {
- val ab = x(a) compare x(b)
- val bc = x(b) compare x(c)
- val ac = x(a) compare x(c)
- if (ab < 0) {
- if (bc < 0) b else if (ac < 0) c else a
- } else {
- if (bc > 0) b else if (ac > 0) c else a
+ j += 1
}
- }
- def sort2(off: Int, len: Int) {
- // Insertion sort on smallest arrays
- if (len < 7) {
- var i = off
- while (i < len + off) {
- var j = i
- while (j > off && (x(j-1) compare x(j)) > 0) {
- swap(j, j-1)
- j -= 1
- }
- i += 1
- }
- } else {
- // Choose a partition element, v
- var m = off + (len >> 1) // Small arrays, middle element
- if (len > 7) {
- var l = off
- var n = off + len - 1
- if (len > 40) { // Big arrays, pseudomedian of 9
- val s = len / 8
- l = med3(l, l+s, l+2*s)
- m = med3(m-s, m, m+s)
- n = med3(n-2*s, n-s, n)
- }
- m = med3(l, m, n) // Mid-size, med of 3
- }
- val v = x(m)
-
- // Establish Invariant: v* (<v)* (>v)* v*
- var a = off
- var b = a
- var c = off + len - 1
- var d = c
- var done = false
- while (!done) {
- var bv = x(b) compare v
- while (b <= c && bv <= 0) {
- if (bv == 0) {
- swap(a, b)
- a += 1
- }
- b += 1
- if (b <= c) bv = x(b) compare v
- }
- var cv = x(c) compare v
- while (c >= b && cv >= 0) {
- if (cv == 0) {
- swap(c, d)
- d -= 1
- }
- c -= 1
- if (c >= b) cv = x(c) compare v
- }
- if (b > c) {
- done = true
- } else {
- swap(b, c)
- c -= 1
- b += 1
- }
- }
-
- // Swap partition elements back to middle
- val n = off + len
- var s = math.min(a-off, b-a)
- vecswap(off, b-s, s)
- s = math.min(d-c, n-d-1)
- vecswap(b, n-s, s)
-
- // Recursively sort non-partition-elements
- s = b - a
- if (s > 1)
- sort2(off, s)
- s = d - c
- if (s > 1)
- sort2(n-s, s)
+ var k = i0
+ j = 0
+ while (i < iN && j < jN) {
+ if (ord.compare(a(i), scratch(j)) < 0) { a(k) = a(i); i += 1 }
+ else { a(k) = scratch(j); j += 1 }
+ k += 1
}
+ while (j < jN) { a(k) = scratch(j); j += 1; k += 1 }
+ // Don't need to finish a(i) because it's already in place, k = i
}
- sort2(off, len)
}
-
- private def sort1(x: Array[Float], off: Int, len: Int) {
- def swap(a: Int, b: Int) {
- val t = x(a)
- x(a) = x(b)
- x(b) = t
+
+ // Why would you even do this?
+ private def booleanSort(a: Array[Boolean]): Unit = {
+ var i = 0
+ var n = 0
+ while (i < a.length) {
+ if (!a(i)) n += 1
+ i += 1
}
- def vecswap(_a: Int, _b: Int, n: Int) {
- var a = _a
- var b = _b
- var i = 0
- while (i < n) {
- swap(a, b)
- i += 1
- a += 1
- b += 1
- }
+ i = 0
+ while (i < n) {
+ a(i) = false
+ i += 1
}
- def med3(a: Int, b: Int, c: Int) = {
- val ab = x(a) compare x(b)
- val bc = x(b) compare x(c)
- val ac = x(a) compare x(c)
- if (ab < 0) {
- if (bc < 0) b else if (ac < 0) c else a
- } else {
- if (bc > 0) b else if (ac > 0) c else a
- }
+ while (i < a.length) {
+ a(i) = true
+ i += 1
}
- def sort2(off: Int, len: Int) {
- // Insertion sort on smallest arrays
- if (len < 7) {
- var i = off
- while (i < len + off) {
- var j = i
- while (j > off && (x(j-1) compare x(j)) > 0) {
- swap(j, j-1)
- j -= 1
- }
- i += 1
- }
- } else {
- // Choose a partition element, v
- var m = off + (len >> 1) // Small arrays, middle element
- if (len > 7) {
- var l = off
- var n = off + len - 1
- if (len > 40) { // Big arrays, pseudomedian of 9
- val s = len / 8
- l = med3(l, l+s, l+2*s)
- m = med3(m-s, m, m+s)
- n = med3(n-2*s, n-s, n)
- }
- m = med3(l, m, n) // Mid-size, med of 3
- }
- val v = x(m)
+ }
- // Establish Invariant: v* (<v)* (>v)* v*
- var a = off
- var b = a
- var c = off + len - 1
- var d = c
- var done = false
- while (!done) {
- var bv = x(b) compare v
- while (b <= c && bv <= 0) {
- if (bv == 0) {
- swap(a, b)
- a += 1
- }
- b += 1
- if (b <= c) bv = x(b) compare v
- }
- var cv = x(c) compare v
- while (c >= b && cv >= 0) {
- if (cv == 0) {
- swap(c, d)
- d -= 1
- }
- c -= 1
- if (c >= b) cv = x(c) compare v
- }
- if (b > c) {
- done = true
- } else {
- swap(b, c)
- c -= 1
- b += 1
- }
- }
+ // TODO: add upper bound: T <: AnyRef, propagate to callers below (not binary compatible)
+ // Maybe also rename all these methods to `sort`.
+ @inline private def sort[T](a: Array[T], ord: Ordering[T]): Unit = a match {
+ case _: Array[AnyRef] =>
+ // Note that runtime matches are covariant, so could actually be any Array[T] s.t. T is not primitive (even boxed value classes)
+ if (a.length > 1 && (ord eq null)) throw new NullPointerException("Ordering")
+ java.util.Arrays.sort(a, ord)
+ case a: Array[Int] => if (ord eq Ordering.Int) java.util.Arrays.sort(a) else mergeSort[Int](a, 0, a.length, ord)
+ case a: Array[Double] => mergeSort[Double](a, 0, a.length, ord) // Because not all NaNs are identical, stability is meaningful!
+ case a: Array[Long] => if (ord eq Ordering.Long) java.util.Arrays.sort(a) else mergeSort[Long](a, 0, a.length, ord)
+ case a: Array[Float] => mergeSort[Float](a, 0, a.length, ord) // Because not all NaNs are identical, stability is meaningful!
+ case a: Array[Char] => if (ord eq Ordering.Char) java.util.Arrays.sort(a) else mergeSort[Char](a, 0, a.length, ord)
+ case a: Array[Byte] => if (ord eq Ordering.Byte) java.util.Arrays.sort(a) else mergeSort[Byte](a, 0, a.length, ord)
+ case a: Array[Short] => if (ord eq Ordering.Short) java.util.Arrays.sort(a) else mergeSort[Short](a, 0, a.length, ord)
+ case a: Array[Boolean] => if (ord eq Ordering.Boolean) booleanSort(a) else mergeSort[Boolean](a, 0, a.length, ord)
+ // Array[Unit] is matched as an Array[AnyRef] due to covariance in runtime matching. Not worth catching it as a special case.
+ case null => throw new NullPointerException
+ }
- // Swap partition elements back to middle
- val n = off + len
- var s = math.min(a-off, b-a)
- vecswap(off, b-s, s)
- s = math.min(d-c, n-d-1)
- vecswap(b, n-s, s)
+ // TODO: remove unnecessary ClassTag (not binary compatible)
+ /** Sort array `a` using the Ordering on its elements, preserving the original ordering where possible. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */
+ def stableSort[K: ClassTag: Ordering](a: Array[K]): Unit = sort(a, Ordering[K])
- // Recursively sort non-partition-elements
- s = b - a
- if (s > 1)
- sort2(off, s)
- s = d - c
- if (s > 1)
- sort2(n-s, s)
- }
- }
- sort2(off, len)
+ // TODO: Remove unnecessary ClassTag (not binary compatible)
+ // TODO: make this fast for primitive K (could be specialized if it didn't go through Ordering)
+ /** Sort array `a` using function `f` that computes the less-than relation for each element. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */
+ def stableSort[K: ClassTag](a: Array[K], f: (K, K) => Boolean): Unit = sort(a, Ordering fromLessThan f)
+
+ /** A sorted Array, using the Ordering for the elements in the sequence `a`. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */
+ def stableSort[K: ClassTag: Ordering](a: Seq[K]): Array[K] = {
+ val ret = a.toArray
+ sort(ret, Ordering[K])
+ ret
}
- private def stableSort[K : ClassTag](a: Array[K], lo: Int, hi: Int, scratch: Array[K], f: (K,K) => Boolean) {
- if (lo < hi) {
- val mid = (lo+hi) / 2
- stableSort(a, lo, mid, scratch, f)
- stableSort(a, mid+1, hi, scratch, f)
- var k, t_lo = lo
- var t_hi = mid + 1
- while (k <= hi) {
- if ((t_lo <= mid) && ((t_hi > hi) || (!f(a(t_hi), a(t_lo))))) {
- scratch(k) = a(t_lo)
- t_lo += 1
- } else {
- scratch(k) = a(t_hi)
- t_hi += 1
- }
- k += 1
- }
- k = lo
- while (k <= hi) {
- a(k) = scratch(k)
- k += 1
- }
- }
+ // TODO: make this fast for primitive K (could be specialized if it didn't go through Ordering)
+ /** A sorted Array, given a function `f` that computes the less-than relation for each item in the sequence `a`. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */
+ def stableSort[K: ClassTag](a: Seq[K], f: (K, K) => Boolean): Array[K] = {
+ val ret = a.toArray
+ sort(ret, Ordering fromLessThan f)
+ ret
+ }
+
+ /** A sorted Array, given an extraction function `f` that returns an ordered key for each item in the sequence `a`. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */
+ def stableSort[K: ClassTag, M: Ordering](a: Seq[K], f: K => M): Array[K] = {
+ val ret = a.toArray
+ sort(ret, Ordering[M] on f)
+ ret
}
}
diff --git a/src/repl/scala/tools/nsc/interpreter/IMain.scala b/src/repl/scala/tools/nsc/interpreter/IMain.scala
index c281126d5f..e355d9f864 100644
--- a/src/repl/scala/tools/nsc/interpreter/IMain.scala
+++ b/src/repl/scala/tools/nsc/interpreter/IMain.scala
@@ -69,6 +69,8 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set
// Used in a test case.
def showDirectory() = replOutput.show(out)
+ lazy val isClassBased: Boolean = settings.Yreplclassbased.value
+
private[nsc] var printResults = true // whether to print result lines
private[nsc] var totalSilence = false // whether to print anything
private var _initializeComplete = false // compiler is initialized
@@ -310,8 +312,14 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set
}
def originalPath(name: String): String = originalPath(TermName(name))
- def originalPath(name: Name): String = typerOp path name
- def originalPath(sym: Symbol): String = typerOp path sym
+ def originalPath(name: Name): String = translateOriginalPath(typerOp path name)
+ def originalPath(sym: Symbol): String = translateOriginalPath(typerOp path sym)
+ /** For class based repl mode we use an .INSTANCE accessor. */
+ val readInstanceName = if(isClassBased) ".INSTANCE" else ""
+ def translateOriginalPath(p: String): String = {
+ val readName = java.util.regex.Matcher.quoteReplacement(sessionNames.read)
+ p.replaceFirst(readName, readName + readInstanceName)
+ }
def flatPath(sym: Symbol): String = flatOp shift sym.javaClassName
def translatePath(path: String) = {
@@ -758,11 +766,13 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set
// object and we can do that much less wrapping.
def packageDecl = "package " + packageName
+ def pathToInstance(name: String) = packageName + "." + name + readInstanceName
def pathTo(name: String) = packageName + "." + name
def packaged(code: String) = packageDecl + "\n\n" + code
- def readPath = pathTo(readName)
- def evalPath = pathTo(evalName)
+ def readPathInstance = pathToInstance(readName)
+ def readPath = pathTo(readName)
+ def evalPath = pathTo(evalName)
def call(name: String, args: Any*): AnyRef = {
val m = evalMethod(name)
@@ -802,7 +812,8 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set
/** The innermost object inside the wrapper, found by
* following accessPath into the outer one.
*/
- def resolvePathToSymbol(accessPath: String): Symbol = {
+ def resolvePathToSymbol(fullAccessPath: String): Symbol = {
+ val accessPath = fullAccessPath.stripPrefix(readPath)
val readRoot = readRootPath(readPath) // the outermost wrapper
(accessPath split '.').foldLeft(readRoot: Symbol) {
case (sym, "") => sym
@@ -849,7 +860,6 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set
def defines = defHandlers flatMap (_.definedSymbols)
def imports = importedSymbols
def value = Some(handlers.last) filter (h => h.definesValue) map (h => definedSymbols(h.definesTerm.get)) getOrElse NoSymbol
-
val lineRep = new ReadEvalPrint()
private var _originalLine: String = null
@@ -858,6 +868,11 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set
/** handlers for each tree in this request */
val handlers: List[MemberHandler] = trees map (memberHandlers chooseHandler _)
+ val definesClass = handlers.exists {
+ case _: ClassHandler => true
+ case _ => false
+ }
+
def defHandlers = handlers collect { case x: MemberDefHandler => x }
/** list of names used by this expression */
@@ -875,13 +890,13 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set
* append to objectName to access anything bound by request.
*/
lazy val ComputedImports(importsPreamble, importsTrailer, accessPath) =
- exitingTyper(importsCode(referencedNames.toSet, ObjectSourceCode))
+ exitingTyper(importsCode(referencedNames.toSet, ObjectSourceCode, definesClass))
/** the line of code to compute */
def toCompute = line
/** The path of the value that contains the user code. */
- def fullAccessPath = s"${lineRep.readPath}$accessPath"
+ def fullAccessPath = s"${lineRep.readPathInstance}$accessPath"
/** The path of the given member of the wrapping instance. */
def fullPath(vname: String) = s"$fullAccessPath.`$vname`"
@@ -911,7 +926,7 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set
def postwrap: String
}
- private class ObjectBasedWrapper extends Wrapper {
+ class ObjectBasedWrapper extends Wrapper {
def preambleHeader = "object %s {"
def postamble = importsTrailer + "\n}"
@@ -919,13 +934,16 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set
def postwrap = "}\n"
}
- private class ClassBasedWrapper extends Wrapper {
- def preambleHeader = "class %s extends Serializable {"
+ class ClassBasedWrapper extends Wrapper {
+ def preambleHeader = "class %s extends Serializable { "
/** Adds an object that instantiates the outer wrapping class. */
- def postamble = s"""$importsTrailer
+ def postamble = s"""
+ |$importsTrailer
+ |}
+ |object ${lineRep.readName} {
+ | val INSTANCE = new ${lineRep.readName}();
|}
- |object ${lineRep.readName} extends ${lineRep.readName}
|""".stripMargin
import nme.{ INTERPRETER_IMPORT_WRAPPER => iw }
@@ -935,7 +953,7 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set
}
private lazy val ObjectSourceCode: Wrapper =
- if (settings.Yreplclassbased) new ClassBasedWrapper else new ObjectBasedWrapper
+ if (isClassBased) new ClassBasedWrapper else new ObjectBasedWrapper
private object ResultObjectSourceCode extends IMain.CodeAssembler[MemberHandler] {
/** We only want to generate this code when the result
@@ -994,7 +1012,7 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set
}
}
- lazy val resultSymbol = lineRep.resolvePathToSymbol(accessPath)
+ lazy val resultSymbol = lineRep.resolvePathToSymbol(fullAccessPath)
def applyToResultMember[T](name: Name, f: Symbol => T) = exitingTyper(f(resultSymbol.info.nonPrivateDecl(name)))
/* typeOf lookup with encoding */
diff --git a/src/repl/scala/tools/nsc/interpreter/Imports.scala b/src/repl/scala/tools/nsc/interpreter/Imports.scala
index 5244858a62..3ec77e46f1 100644
--- a/src/repl/scala/tools/nsc/interpreter/Imports.scala
+++ b/src/repl/scala/tools/nsc/interpreter/Imports.scala
@@ -92,7 +92,7 @@ trait Imports {
* last one imported is actually usable.
*/
case class ComputedImports(prepend: String, append: String, access: String)
- protected def importsCode(wanted: Set[Name], wrapper: Request#Wrapper): ComputedImports = {
+ protected def importsCode(wanted: Set[Name], wrapper: Request#Wrapper, definesClass: Boolean): ComputedImports = {
/** Narrow down the list of requests from which imports
* should be taken. Removes requests which cannot contribute
* useful imports for the specified set of wanted names.
@@ -107,6 +107,8 @@ trait Imports {
// Single symbol imports might be implicits! See bug #1752. Rather than
// try to finesse this, we will mimic all imports for now.
def keepHandler(handler: MemberHandler) = handler match {
+ /* While defining classes in class based mode - implicits are not needed. */
+ case h: ImportHandler if isClassBased && definesClass => h.importedNames.exists(x => wanted.contains(x))
case _: ImportHandler => true
case x => x.definesImplicit || (x.definedNames exists wanted)
}
@@ -146,7 +148,10 @@ trait Imports {
// loop through previous requests, adding imports for each one
wrapBeforeAndAfter {
+ // Reusing a single temporary value when import from a line with multiple definitions.
+ val tempValLines = mutable.Set[Int]()
for (ReqAndHandler(req, handler) <- reqsToUse) {
+ val objName = req.lineRep.readPathInstance
handler match {
// If the user entered an import, then just use it; add an import wrapping
// level if the import might conflict with some other import
@@ -157,6 +162,23 @@ trait Imports {
code append (x.member + "\n")
currentImps ++= x.importedNames
+ case x if isClassBased =>
+ for (imv <- x.definedNames) {
+ if (!currentImps.contains(imv)) {
+ x match {
+ case _: ClassHandler =>
+ code.append("import " + objName + req.accessPath + ".`" + imv + "`\n")
+ case _ =>
+ val valName = req.lineRep.packageName + req.lineRep.readName
+ if (!tempValLines.contains(req.lineRep.lineId)) {
+ code.append(s"val $valName = $objName\n")
+ tempValLines += req.lineRep.lineId
+ }
+ code.append(s"import $valName${req.accessPath}.`$imv`;\n")
+ }
+ currentImps += imv
+ }
+ }
// For other requests, import each defined name.
// import them explicitly instead of with _, so that
// ambiguity errors will not be generated. Also, quote
diff --git a/test/files/run/repl-serialization.check b/test/files/run/repl-serialization.check
new file mode 100644
index 0000000000..eb62729f5c
--- /dev/null
+++ b/test/files/run/repl-serialization.check
@@ -0,0 +1,25 @@
+== evaluating lines
+extract: AnyRef => Unit = <function1>
+ evaluating x
+x: Int = 0
+getX: ()Int
+defined class U
+y: Int = <lazy>
+ evaluating z
+ evaluating zz
+defined class D
+z: Int = 0
+zz: Int = 0
+defined object O
+defined class A
+defined type alias AA
+constructing U
+u: U = U
+== evaluating lambda
+ evaluating y
+ evaluating O
+ constructing A
+== reconstituting into a fresh classloader
+ evaluating O
+== evaluating reconstituted lambda
+ constructing A
diff --git a/test/files/run/repl-serialization.scala b/test/files/run/repl-serialization.scala
new file mode 100644
index 0000000000..55b7519631
--- /dev/null
+++ b/test/files/run/repl-serialization.scala
@@ -0,0 +1,68 @@
+import java.io._
+
+import scala.reflect.io.AbstractFile
+import scala.tools.nsc.Settings
+import scala.tools.nsc.interpreter.IMain
+import scala.tools.nsc.util._
+import scala.reflect.internal.util.AbstractFileClassLoader
+
+object Test {
+ def main(args: Array[String]) {
+ run()
+ }
+
+ def run(): Unit = {
+ val settings = new Settings()
+ settings.Yreplclassbased.value = true
+ settings.usejavacp.value = true
+
+ var imain: IMain = null
+ object extract extends ((AnyRef) => Unit) with Serializable {
+ var value: AnyRef = null
+
+ def apply(a: AnyRef) = value = a
+ }
+
+ val code =
+ """val x = {println(" evaluating x"); 0 }
+ |def getX() = x
+ |class U extends Serializable { println("constructing U"); val x = 0 ; override def toString = "U" }
+ |lazy val y = {println(" evaluating y"); 0 }
+ |class D; val z = {println(" evaluating z"); 0}; val zz = {println(" evaluating zz"); 0}
+ |object O extends Serializable { val apply = {println(" evaluating O"); 0} }
+ |class A(i: Int) { println(" constructing A") }
+ |type AA = A
+ |val u = new U()
+ |extract(() => new AA(x + getX() + y + z + zz + O.apply + u.x))
+ """.stripMargin
+
+ imain = new IMain(settings)
+ println("== evaluating lines")
+ imain.directBind("extract", "(AnyRef => Unit)", extract)
+ code.lines.foreach(imain.interpret)
+
+ val virtualFile: AbstractFile = extract.value.getClass.getClassLoader.asInstanceOf[AbstractFileClassLoader].root
+ val newLoader = new AbstractFileClassLoader(virtualFile, getClass.getClassLoader)
+
+ def deserializeInNewLoader(string: Array[Byte]): AnyRef = {
+ val bis = new ByteArrayInputStream(string)
+ val in = new ObjectInputStream(bis) {
+ override def resolveClass(desc: ObjectStreamClass) = Class.forName(desc.getName, false, newLoader)
+ }
+ in.readObject()
+ }
+ def serialize(o: AnyRef): Array[Byte] = {
+ val bos = new ByteArrayOutputStream()
+ val out = new ObjectOutputStream(bos)
+ out.writeObject(o)
+ out.close()
+ bos.toByteArray
+ }
+ println("== evaluating lambda")
+ extract.value.asInstanceOf[() => Any].apply()
+ println("== reconstituting into a fresh classloader")
+ val reconstituted = deserializeInNewLoader(serialize(extract.value)).asInstanceOf[() => Any]
+ println("== evaluating reconstituted lambda")
+ reconstituted.apply() // should not print("evaluating x") a second time
+ }
+}
diff --git a/test/files/run/t7747-repl.check b/test/files/run/t7747-repl.check
index 105b238d01..5f436ba6b1 100644
--- a/test/files/run/t7747-repl.check
+++ b/test/files/run/t7747-repl.check
@@ -112,7 +112,7 @@ scala> 55 ; ((2 + 2)) ; (1, 2, 3)
res15: (Int, Int, Int) = (1,2,3)
scala> 55 ; (x: Int) => x + 1 ; () => ((5))
-<console>:8: warning: a pure expression does nothing in statement position; you may be omitting necessary parentheses
+<console>:9: warning: a pure expression does nothing in statement position; you may be omitting necessary parentheses
55 ; (x: Int) => x + 1 ;;
^
res16: () => Int = <function0>
@@ -258,12 +258,12 @@ class $read extends Serializable {
super.<init>;
()
};
- import $line44.$read.$iw.$iw.BippyBups;
- import $line44.$read.$iw.$iw.BippyBups;
- import $line45.$read.$iw.$iw.PuppyPups;
- import $line45.$read.$iw.$iw.PuppyPups;
- import $line46.$read.$iw.$iw.Bingo;
- import $line46.$read.$iw.$iw.Bingo;
+ import $line44.$read.INSTANCE.$iw.$iw.BippyBups;
+ import $line44.$read.INSTANCE.$iw.$iw.BippyBups;
+ import $line45.$read.INSTANCE.$iw.$iw.PuppyPups;
+ import $line45.$read.INSTANCE.$iw.$iw.PuppyPups;
+ import $line46.$read.INSTANCE.$iw.$iw.Bingo;
+ import $line46.$read.INSTANCE.$iw.$iw.Bingo;
class $iw extends Serializable {
def <init>() = {
super.<init>;
@@ -275,12 +275,35 @@ class $read extends Serializable {
};
val $iw = new $iw.<init>
}
-object $read extends $read {
+object $read extends scala.AnyRef {
def <init>() = {
super.<init>;
()
- }
+ };
+ val INSTANCE = new $read.<init>
}
res3: List[Product with Serializable] = List(BippyBups(), PuppyPups(), Bingo())
+scala> case class Sum(exp: String, exp2: String)
+defined class Sum
+
+scala> val a = Sum("A", "B")
+a: Sum = Sum(A,B)
+
+scala> def b(a: Sum): String = a match { case Sum(_, _) => "Found Sum" }
+b: (a: Sum)String
+
+scala> b(a)
+res4: String = Found Sum
+
+scala> :power
+** Power User mode enabled - BEEP WHIR GYVE **
+** :phase has been set to 'typer'. **
+** scala.tools.nsc._ has been imported **
+** global._, definitions._ also imported **
+** Try :help, :vals, power.<tab> **
+
+scala> intp.lastRequest
+res5: $r.intp.Request = Request(line=def $ires3 = intp.global, 1 trees)
+
scala> :quit
diff --git a/test/files/run/t7747-repl.scala b/test/files/run/t7747-repl.scala
index 0e64210460..141c2d9844 100644
--- a/test/files/run/t7747-repl.scala
+++ b/test/files/run/t7747-repl.scala
@@ -65,5 +65,11 @@ object Test extends ReplTest {
|case class PuppyPups()
|case class Bingo()
|List(BippyBups(), PuppyPups(), Bingo()) // show
+ |case class Sum(exp: String, exp2: String)
+ |val a = Sum("A", "B")
+ |def b(a: Sum): String = a match { case Sum(_, _) => "Found Sum" }
+ |b(a)
+ |:power
+ |intp.lastRequest
|""".stripMargin
}
diff --git a/test/junit/scala/util/SortingTest.scala b/test/junit/scala/util/SortingTest.scala
new file mode 100644
index 0000000000..15a00c8903
--- /dev/null
+++ b/test/junit/scala/util/SortingTest.scala
@@ -0,0 +1,69 @@
+package scala.util
+
+import org.junit.Test
+import org.junit.Assert._
+import scala.math.{ Ordered, Ordering }
+import scala.reflect.ClassTag
+
+class SortingTest {
+ case class N(i: Int, j: Int) extends Ordered[N] { def compare(n: N) = if (i < n.i) -1 else if (i > n.i) 1 else 0 }
+
+ def mkA(n: Int, max: Int) = Array.tabulate(n)(i => N(util.Random.nextInt(max), i))
+
+ def isStable(a: Array[N]): Boolean = { var i = 1; while (i < a.length) { if (a(i).i < a(i-1).i || (a(i).i == a(i-1).i && a(i).j < a(i-1).j)) return false; i += 1 }; true }
+
+ def isAntistable(a: Array[N]): Boolean =
+ { var i = 1; while (i < a.length) { if (a(i).i > a(i-1).i || (a(i).i == a(i-1).i && a(i).j < a(i-1).j)) return false; i += 1 }; true }
+
+ def isSorted(a: Array[N]): Boolean = { var i = 1; while (i < a.length) { if (a(i).i < a(i-1).i) return false; i += 1 }; true }
+
+ def isAntisorted(a: Array[N]): Boolean = { var i = 1; while (i < a.length) { if (a(i).i > a(i-1).i) return false; i += 1 }; true }
+
+ val sizes = Seq.range(0, 65) ++ Seq(256, 1024, 9121, 65539)
+ val variety = Seq(1, 2, 10, 100, 1000, Int.MaxValue)
+ val workLimit = 1e6
+ val rng = new util.Random(198571)
+
+ val backwardsN = Ordering by ((n: N) => -n.i)
+
+ def runOneTest(size: Int, variety: Int): Unit = {
+ val xs = Array.tabulate(size)(i => N(rng.nextInt(variety), i))
+ val ys = Array.range(0, xs.length)
+ val zs = { val temp = xs.clone; java.util.Arrays.sort(temp, new java.util.Comparator[N] { def compare(a: N, b: N) = a.compare(b) }); temp }
+ val qxs = { val temp = xs.clone; Sorting.quickSort(temp); temp }
+ val pxs = { val temp = xs.clone; Sorting.quickSort(temp)(backwardsN); temp }
+ val sxs = { val temp = xs.clone; Sorting.stableSort(temp); temp }
+ val rxs = { val temp = xs.clone; Sorting.stableSort(temp)(implicitly[ClassTag[N]], backwardsN); temp }
+ val sys = Sorting.stableSort(ys.clone: Seq[Int], (i: Int) => xs(i))
+
+ assertTrue("Quicksort should be in order", isSorted(qxs))
+ assertTrue("Quicksort should be in reverse order", isAntisorted(pxs))
+ assertTrue("Stable sort should be sorted and stable", isStable(sxs))
+ assertTrue("Stable sort should be reverse sorted but stable", isAntistable(rxs))
+ assertTrue("Stable sorting by proxy should produce sorted stable list", isStable(sys.map(i => xs(i))))
+ assertTrue("Quicksort should produce canonical ordering", (qxs zip zs).forall{ case (a,b) => a.i == b.i })
+ assertTrue("Reverse quicksort should produce canonical ordering", (pxs.reverse zip zs).forall{ case (a,b) => a.i == b.i })
+ assertTrue("Stable sort should produce exact ordering", (sxs zip zs).forall{ case (a,b) => a == b })
+ assertTrue("Reverse stable sort should produce canonical ordering", (rxs.reverse zip zs).forall{ case (a,b) => a.i == b.i })
+ assertTrue("Proxy sort and direct sort should produce exactly the same thing", (sxs zip sys.map(i => xs(i))).forall{ case (a,b) => a == b })
+ }
+
+ @Test def testSortConsistency: Unit = {
+ for {
+ size <- sizes
+ v <- variety
+ i <- 0 until math.min(100, math.max(math.min(math.floor(math.pow(v, size)/2), math.ceil(workLimit / (math.log(math.max(2,size))/math.log(2) * size))), 1).toInt)
+ } runOneTest(size, v)
+
+ for (size <- sizes) {
+ val b = Array.fill(size)(rng.nextBoolean)
+ val bfwd = Sorting.stableSort(b.clone: Seq[Boolean])
+ val bbkw = Sorting.stableSort(b.clone: Seq[Boolean], (x: Boolean, y: Boolean) => x && !y)
+ assertTrue("All falses should be first", bfwd.dropWhile(_ == false).forall(_ == true))
+ assertTrue("All falses should be last when sorted backwards", bbkw.dropWhile(_ == true).forall(_ == false))
+ assertTrue("Sorting booleans should preserve the number of trues", b.count(_ == true) == bfwd.count(_ == true))
+ assertTrue("Backwards sorting booleans should preserve the number of trues", b.count(_ == true) == bbkw.count(_ == true))
+ assertTrue("Sorting should not change the sizes of arrays", b.length == bfwd.length && b.length == bbkw.length)
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-08-29 04:24:22 +0000