diff options
author | Adriaan Moors <adriaan.moors@typesafe.com> | 2015-06-16 09:37:56 -0700 |
---|---|---|
committer | Adriaan Moors <adriaan.moors@typesafe.com> | 2015-06-16 09:37:56 -0700 |
commit | 43a56fb5a1b6450ce2bdf8f73ab30ca1b16d0778 (patch) | |
tree | 9492633b8954a2899e4a6fdd1bef4d412e30fd04 /test | |
parent | 6b09c66b8e982c84f8183a9c00e2d3a43455c2ac (diff) | |
parent | 9aae16aa231ad64e3987aaad2a206beaf10c76e0 (diff) | |
download | scala-43a56fb5a1b6450ce2bdf8f73ab30ca1b16d0778.tar.gz scala-43a56fb5a1b6450ce2bdf8f73ab30ca1b16d0778.tar.bz2 scala-43a56fb5a1b6450ce2bdf8f73ab30ca1b16d0778.zip |
Merge pull request #4534 from Ichoran/sorting-reimpl
Clean implementation of sorts for scala.util.Sorting.
Diffstat (limited to 'test')
-rw-r--r-- | test/junit/scala/util/SortingTest.scala | 69 |
1 files changed, 69 insertions, 0 deletions
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) + } + } +} |