diff options
author | Paul Phillips <paulp@improving.org> | 2012-01-30 11:55:19 -0800 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2012-01-30 11:55:19 -0800 |
commit | 77291ed5e9f707f8014b40ec002091f46e5adba0 (patch) | |
tree | a1bf55d74d5222b9921d34a8ac6b4dc27ed4f1bb /test | |
parent | d762e4caf9e201e597a76566eb9f61ad53b5f4cf (diff) | |
parent | 84fd439fb1c2f08439e539aea4f9657c6768bc83 (diff) | |
download | scala-77291ed5e9f707f8014b40ec002091f46e5adba0.tar.gz scala-77291ed5e9f707f8014b40ec002091f46e5adba0.tar.bz2 scala-77291ed5e9f707f8014b40ec002091f46e5adba0.zip |
Merge branch 'master' into inline
Diffstat (limited to 'test')
-rw-r--r-- | test/benchmarking/TreeSetInsert.scala | 68 | ||||
-rw-r--r-- | test/benchmarking/TreeSetInsertRandom.scala | 65 | ||||
-rw-r--r-- | test/benchmarking/TreeSetIterator.scala | 69 | ||||
-rw-r--r-- | test/benchmarking/TreeSetRemove.scala | 69 | ||||
-rw-r--r-- | test/benchmarking/TreeSetRemoveRandom.scala | 66 | ||||
-rw-r--r-- | test/files/pos/t4336.scala | 19 | ||||
-rw-r--r-- | test/files/scalacheck/avl.scala | 114 |
7 files changed, 470 insertions, 0 deletions
diff --git a/test/benchmarking/TreeSetInsert.scala b/test/benchmarking/TreeSetInsert.scala new file mode 100644 index 0000000000..9ede8aedc5 --- /dev/null +++ b/test/benchmarking/TreeSetInsert.scala @@ -0,0 +1,68 @@ + +object TreeSetInsert { + + def main(args: Array[String]): Unit = { + val n = 500000 + JavaUtilTS.main(args) + MutableTS.main(args) + ImmutableTS.main(args) + } +} + +class Dummy(val a: Int) extends math.Ordered[Dummy] { + def compare(other: Dummy) = this.a - other.a + + override def toString = a.toString + } + + +object JavaUtilTS extends testing.Benchmark { + val length = sys.props("length").toInt + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: java.util.TreeSet[Dummy] = null + + def run = { + t = new java.util.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t add elem + i += 1 + } + } +} + +object MutableTS extends testing.Benchmark { + val length = sys.props("length").toInt + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.mutable.TreeSet[Dummy] = null + + def run = { + t = collection.mutable.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t += elem + i += 1 + } + } +} + +object ImmutableTS extends testing.Benchmark { + val length = sys.props("length").toInt + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.immutable.TreeSet[Dummy] = null + + def run = { + t = collection.immutable.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t += elem + i += 1 + } + } +} diff --git a/test/benchmarking/TreeSetInsertRandom.scala b/test/benchmarking/TreeSetInsertRandom.scala new file mode 100644 index 0000000000..7f182548b7 --- /dev/null +++ b/test/benchmarking/TreeSetInsertRandom.scala @@ -0,0 +1,65 @@ + +object TreeSetInsertRandom { + + def main(args: Array[String]): Unit = { + val n = 500000 + new JavaUtilTS(n).main(args) + new MutableTS(n).main(args) + new ImmutableTS(n).main(args) + } +} + +class Dummy(val a: Int) extends math.Ordered[Dummy] { + def compare(other: Dummy) = this.a - other.a + + override def toString = a.toString + } + + +class JavaUtilTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: java.util.TreeSet[Dummy] = null + + def run = { + t = new java.util.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t add elem + i += 1 + } + } +} + +class MutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: collection.mutable.TreeSet[Dummy] = null + + def run = { + t = collection.mutable.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t += elem + i += 1 + } + } +} + +class ImmutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: collection.immutable.TreeSet[Dummy] = null + + def run = { + t = collection.immutable.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t += elem + i += 1 + } + } +} diff --git a/test/benchmarking/TreeSetIterator.scala b/test/benchmarking/TreeSetIterator.scala new file mode 100644 index 0000000000..08c20e8b0c --- /dev/null +++ b/test/benchmarking/TreeSetIterator.scala @@ -0,0 +1,69 @@ + +object TreeSetIterator { + + def main(args: Array[String]): Unit = { + val n = 500000 + JavaUtilTS.main(args) + MutableTS.main(args) + ImmutableTS.main(args) + } +} + +class Dummy(val a: Int) extends math.Ordered[Dummy] { + def compare(other: Dummy) = this.a - other.a + + override def toString = a.toString + } + + +object JavaUtilTS extends testing.Benchmark { + val length = sys.props("length").toInt + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: java.util.TreeSet[Dummy] = null + + def run = { + t = new java.util.TreeSet[Dummy]() + data foreach { a => t add a } + + var i: Dummy = null + var it = t.iterator + while (it.hasNext) { + i = it.next + } + i + } +} + +object MutableTS extends testing.Benchmark { + val length = sys.props("length").toInt + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.mutable.TreeSet[Dummy] = null + + def run = { + t = collection.mutable.TreeSet[Dummy](data: _*) + + var i: Dummy = null + var it = t.iterator + while (it.hasNext) { + i = it.next + } + i + } +} + +object ImmutableTS extends testing.Benchmark { + val length = sys.props("length").toInt + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.immutable.TreeSet[Dummy] = null + + def run = { + t = collection.immutable.TreeSet[Dummy](data: _*) + + var i: Dummy = null + var it = t.iterator + while (it.hasNext) { + i = it.next + } + i + } +} diff --git a/test/benchmarking/TreeSetRemove.scala b/test/benchmarking/TreeSetRemove.scala new file mode 100644 index 0000000000..f84066f336 --- /dev/null +++ b/test/benchmarking/TreeSetRemove.scala @@ -0,0 +1,69 @@ + +object TreeSetRemove { + + def main(args: Array[String]): Unit = { + val n = 500000 + JavaUtilTS.main(args) + MutableTS.main(args) + ImmutableTS.main(args) + } +} + +class Dummy(val a: Int) extends math.Ordered[Dummy] { + def compare(other: Dummy) = this.a - other.a + + override def toString = a.toString + } + + +object JavaUtilTS extends testing.Benchmark { + val length = sys.props("length").toInt + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: java.util.TreeSet[Dummy] = null + + def run = { + t = new java.util.TreeSet[Dummy]() + data foreach { a => t add a } + + var i = 0 + while (i < length) { + val elem = data(i) + t remove elem + i += 1 + } + } +} + +object MutableTS extends testing.Benchmark { + val length = sys.props("length").toInt + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.mutable.TreeSet[Dummy] = null + + def run = { + t = collection.mutable.TreeSet[Dummy](data: _*) + + var i = 0 + while (i < length) { + val elem = data(i) + t -= elem + i += 1 + } + } +} + +object ImmutableTS extends testing.Benchmark { + val length = sys.props("length").toInt + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.immutable.TreeSet[Dummy] = null + + def run = { + t = collection.immutable.TreeSet[Dummy](data: _*) + + var i = 0 + while (i < length) { + val elem = data(i) + t -= elem + i += 1 + } + } +} diff --git a/test/benchmarking/TreeSetRemoveRandom.scala b/test/benchmarking/TreeSetRemoveRandom.scala new file mode 100644 index 0000000000..4d311679e3 --- /dev/null +++ b/test/benchmarking/TreeSetRemoveRandom.scala @@ -0,0 +1,66 @@ + +object TreeSetRemoveRandom { + + def main(args: Array[String]): Unit = { + val n = 500000 + new JavaUtilTS(n).main(args) + new MutableTS(n).main(args) + new ImmutableTS(n).main(args) + } +} + +class Dummy(val a: Int) extends math.Ordered[Dummy] { + def compare(other: Dummy) = this.a - other.a + + override def toString = a.toString + } + + +class JavaUtilTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: java.util.TreeSet[Dummy] = null + + def run = { + t = new java.util.TreeSet[Dummy]() + data foreach { a => t add a } + + var i = 0 + while (i < length) { + val elem = data(i) + t remove elem + i += 1 + } + } +} + +class MutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: collection.mutable.TreeSet[Dummy] = null + + def run = { + t = collection.mutable.TreeSet[Dummy](data: _*) + + var i = 0 + while (i < length) { + val elem = data(i) + t -= elem + i += 1 + } + } +} + +class ImmutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: collection.immutable.TreeSet[Dummy] = null + + def run = { + t = collection.immutable.TreeSet[Dummy](data: _*) + + var i = 0 + while (i < length) { + val elem = data(i) + t -= elem + i += 1 + } + } +} diff --git a/test/files/pos/t4336.scala b/test/files/pos/t4336.scala new file mode 100644 index 0000000000..e10d001585 --- /dev/null +++ b/test/files/pos/t4336.scala @@ -0,0 +1,19 @@ +object Main { + class NonGeneric {} + class Generic[T] {} + + class Composite { + def contains(setup : Composite => Unit) : Composite = this + } + + def generic[T](parent: Composite): Generic[T] = new Generic[T] + def nonGeneric(parent: Composite): NonGeneric = new NonGeneric + + new Composite().contains( + nonGeneric // should have type Composite => NonGeneric + ) + + new Composite().contains( + generic[Int] // should have type Composite => Generic[Int] + ) +} diff --git a/test/files/scalacheck/avl.scala b/test/files/scalacheck/avl.scala new file mode 100644 index 0000000000..51fb1fe8c3 --- /dev/null +++ b/test/files/scalacheck/avl.scala @@ -0,0 +1,114 @@ +import org.scalacheck.Gen +import org.scalacheck.Prop.forAll +import org.scalacheck.Properties + +import util.logging.ConsoleLogger + +package scala.collection.mutable { + + /** + * Property of an AVL Tree : Any node of the tree has a balance value beetween in [-1; 1] + */ + abstract class AVLTreeTest(name: String) extends Properties(name) with ConsoleLogger { + + def `2^`(n: Int) = (1 to n).fold(1)((a, b) => b*2) + + def capacityMax(depth: Int): Int = `2^`(depth+1) - 1 + + def minDepthForCapacity(x: Int): Int = { + var depth = 0 + while(capacityMax(depth) < x) + depth += 1 + depth + } + + def numberOfElementsInLeftSubTree(n: Int): collection.immutable.IndexedSeq[Int] = { + val mid = n/2 + n%2 + ((1 until mid) + .filter { i => math.abs(minDepthForCapacity(i) - minDepthForCapacity(n-i)) < 2 } + .flatMap { i => Seq(i, n-(i+1)) }).toIndexedSeq.distinct + } + + def makeAllBalancedTree[A](elements: List[A]): List[AVLTree[A]] = elements match { + case Nil => Leaf::Nil + case first::Nil => Node(first, Leaf, Leaf)::Nil + case first::second::Nil => Node(second, Node(first, Leaf, Leaf), Leaf)::Node(first, Leaf, Node(second, Leaf, Leaf))::Nil + case first::second::third::Nil => Node(second, Node(first, Leaf, Leaf), Node(third, Leaf, Leaf))::Nil + case _ => { + val combinations = for { + left <- numberOfElementsInLeftSubTree(elements.size) + root = elements(left) + right = elements.size - (left + 1) + } yield (root, left, right) + (combinations.flatMap(triple => for { + l <- makeAllBalancedTree(elements.take(triple._2)) + r <- makeAllBalancedTree(elements.takeRight(triple._3)) + } yield Node(triple._1, l, r))).toList + } + } + + def genInput: Gen[(Int, List[AVLTree[Int]])] = for { + size <- Gen.choose(20, 25) + elements <- Gen.listOfN(size, Gen.choose(0, 1000)) + selected <- Gen.choose(0, 1000) + } yield { + // selected mustn't be in elements already + val list = makeAllBalancedTree(elements.sorted.distinct.map(_*2)) + (selected*2+1, list) + } + + def genInputDelete: Gen[(Int, List[AVLTree[Int]])] = for { + size <- Gen.choose(20, 25) + elements <- Gen.listOfN(size, Gen.choose(0, 1000)) + e = elements.sorted.distinct + selected <- Gen.choose(0, e.size-1) + } yield { + // selected must be in elements already + val list = makeAllBalancedTree(e) + (e(selected), list) + } + } + + trait AVLInvariants { + self: AVLTreeTest => + + def isBalanced[A](t: AVLTree[A]): Boolean = t match { + case node: Node[A] => math.abs(node.balance) < 2 && (List(node.left, node.right) forall isBalanced) + case Leaf => true + } + + def setup(invariant: AVLTree[Int] => Boolean) = forAll(genInput) { + case (selected: Int, trees: List[AVLTree[Int]]) => + trees.map(tree => invariant(tree)).fold(true)((a, b) => a && b) + } + + property("Every tree is initially balanced.") = setup(isBalanced) + } + + object TestInsert extends AVLTreeTest("Insert") with AVLInvariants { + import math.Ordering.Int + property("`insert` creates a new tree containing the given element. The tree remains balanced.") = forAll(genInput) { + case (selected: Int, trees: List[AVLTree[Int]]) => + trees.map(tree => { + val modifiedTree = tree.insert(selected, Int) + modifiedTree.contains(selected, Int) && isBalanced(modifiedTree) + }).fold(true)((a, b) => a && b) + } + } + + object TestRemove extends AVLTreeTest("Remove") with AVLInvariants { + import math.Ordering.Int + property("`remove` creates a new tree without the given element. The tree remains balanced.") = forAll(genInputDelete) { + case (selected: Int, trees: List[AVLTree[Int]]) => + trees.map(tree => { + val modifiedTree = tree.remove(selected, Int) + tree.contains(selected, Int) && !modifiedTree.contains(selected, Int) && isBalanced(modifiedTree) + }).fold(true)((a, b) => a && b) + } + } +} + +object Test extends Properties("AVL") { + include(scala.collection.mutable.TestInsert) + include(scala.collection.mutable.TestRemove) +}
\ No newline at end of file |