diff options
author | Paul Phillips <paulp@improving.org> | 2012-01-30 11:01:04 -0800 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2012-01-30 11:01:04 -0800 |
commit | 84fd439fb1c2f08439e539aea4f9657c6768bc83 (patch) | |
tree | b8c6d5348bc297c4fdb3e2d28a4a6e1a439c5732 /test/files | |
parent | a4d6992280b179295142f2f7c7d138ec7f08039b (diff) | |
parent | bf2ec290d9bf1a75daa0f56081a99dc2f69e2670 (diff) | |
download | scala-84fd439fb1c2f08439e539aea4f9657c6768bc83.tar.gz scala-84fd439fb1c2f08439e539aea4f9657c6768bc83.tar.bz2 scala-84fd439fb1c2f08439e539aea4f9657c6768bc83.zip |
Merge branch 'develop'
Diffstat (limited to 'test/files')
-rw-r--r-- | test/files/pos/t4336.scala | 19 | ||||
-rw-r--r-- | test/files/scalacheck/avl.scala | 114 |
2 files changed, 133 insertions, 0 deletions
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 |