diff options
author | Erik Rozendaal <erik@deler.org> | 2012-01-08 12:59:45 +0100 |
---|---|---|
committer | Erik Rozendaal <erik@deler.org> | 2012-01-08 12:59:45 +0100 |
commit | f26f610278887b842de3a4e4fdafb866dd1afb62 (patch) | |
tree | c57ae0520cd279c905c05fce62337071ba1e530a /test/files/scalacheck | |
parent | 8b3f984d4e2e444c0712a7457aefd159d4024b1f (diff) | |
download | scala-f26f610278887b842de3a4e4fdafb866dd1afb62.tar.gz scala-f26f610278887b842de3a4e4fdafb866dd1afb62.tar.bz2 scala-f26f610278887b842de3a4e4fdafb866dd1afb62.zip |
Test for maximum height of red-black tree.
Diffstat (limited to 'test/files/scalacheck')
-rw-r--r-- | test/files/scalacheck/redblacktree.scala | 5 |
1 files changed, 5 insertions, 0 deletions
diff --git a/test/files/scalacheck/redblacktree.scala b/test/files/scalacheck/redblacktree.scala index 10f3f0fbbf..34fa8eae8d 100644 --- a/test/files/scalacheck/redblacktree.scala +++ b/test/files/scalacheck/redblacktree.scala @@ -29,6 +29,8 @@ package scala.collection.immutable.redblacktree { def treeContains[A](tree: Tree[String, A], key: String) = iterator(tree).map(_._1) contains key + def height(tree: Tree[_, _]): Int = if (tree eq null) 0 else (1 + math.max(height(tree.left), height(tree.right))) + def mkTree(level: Int, parentIsBlack: Boolean = false, label: String = ""): Gen[Tree[String, Int]] = if (level == 0) { value(null) @@ -100,6 +102,8 @@ package scala.collection.immutable.redblacktree { def orderIsPreserved[A](t: Tree[String, A]): Boolean = iterator(t) zip iterator(t).drop(1) forall { case (x, y) => x._1 < y._1 } + def heightIsBounded(t: Tree[_, _]): Boolean = height(t) <= (2 * (32 - Integer.numberOfLeadingZeros(count(t) + 2)) - 2) + def setup(invariant: Tree[String, Int] => Boolean) = forAll(genInput) { case (tree, parm, newTree) => invariant(newTree) } @@ -109,6 +113,7 @@ package scala.collection.immutable.redblacktree { property("children of red nodes are black") = setup(areRedNodeChildrenBlack) property("black nodes are balanced") = setup(areBlackNodesToLeavesEqual) property("ordering of keys is preserved") = setup(orderIsPreserved) + property("height is bounded") = setup(heightIsBounded) } object TestInsert extends RedBlackTreeTest with RedBlackTreeInvariants { |