diff options
author | Erik Rozendaal <erik@deler.org> | 2012-01-07 15:26:40 +0100 |
---|---|---|
committer | Erik Rozendaal <erik@deler.org> | 2012-01-07 15:29:56 +0100 |
commit | 288874d80856317744c582f1468d7af420d9e0ee (patch) | |
tree | 76bc86c56e83fcf4184dec83eff0493cc65fdb8c /test | |
parent | f656142ddbcecfd3f8482e2b55067de3d0ebd3ce (diff) | |
download | scala-288874d80856317744c582f1468d7af420d9e0ee.tar.gz scala-288874d80856317744c582f1468d7af420d9e0ee.tar.bz2 scala-288874d80856317744c582f1468d7af420d9e0ee.zip |
Renamed object RedBlack to RedBlackTree.
This more clearly separates the new implementation from the now
deprecated abstract class RedBlack and avoids naming conflicts
for the member classes.
Diffstat (limited to 'test')
-rw-r--r-- | test/files/scalacheck/redblack.scala | 113 | ||||
-rw-r--r-- | test/files/scalacheck/redblacktree.scala | 212 |
2 files changed, 269 insertions, 56 deletions
diff --git a/test/files/scalacheck/redblack.scala b/test/files/scalacheck/redblack.scala index 83d3ca0c1f..bbc6504f58 100644 --- a/test/files/scalacheck/redblack.scala +++ b/test/files/scalacheck/redblack.scala @@ -1,4 +1,3 @@ -import collection.immutable._ import org.scalacheck._ import Prop._ import Gen._ @@ -15,23 +14,26 @@ Both children of every red node are black. Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. */ -package scala.collection.immutable { abstract class RedBlackTest extends Properties("RedBlack") { def minimumSize = 0 def maximumSize = 5 - import RedBlack._ + object RedBlackTest extends scala.collection.immutable.RedBlack[String] { + def isSmaller(x: String, y: String) = x < y + } + + import RedBlackTest._ - def nodeAt[A](tree: Node[String, A], n: Int): Option[(String, A)] = if (n < iterator(tree).size && n >= 0) - Some(iterator(tree).drop(n).next) + def nodeAt[A](tree: Tree[A], n: Int): Option[(String, A)] = if (n < tree.iterator.size && n >= 0) + Some(tree.iterator.drop(n).next) else None - def treeContains[A](tree: Node[String, A], key: String) = iterator(tree).map(_._1) contains key + def treeContains[A](tree: Tree[A], key: String) = tree.iterator.map(_._1) contains key - def mkTree(level: Int, parentIsBlack: Boolean = false, label: String = ""): Gen[Node[String, Int]] = + def mkTree(level: Int, parentIsBlack: Boolean = false, label: String = ""): Gen[Tree[Int]] = if (level == 0) { - value(null) + value(Empty) } else { for { oddOrEven <- choose(0, 2) @@ -42,9 +44,9 @@ abstract class RedBlackTest extends Properties("RedBlack") { right <- mkTree(nextLevel, !isRed, label + "R") } yield { if (isRed) - RedNode(label + "N", 0, left, right) + RedTree(label + "N", 0, left, right) else - BlackNode(label + "N", 0, left, right) + BlackTree(label + "N", 0, left, right) } } @@ -54,10 +56,10 @@ abstract class RedBlackTest extends Properties("RedBlack") { } yield tree type ModifyParm - def genParm(tree: Node[String, Int]): Gen[ModifyParm] - def modify(tree: Node[String, Int], parm: ModifyParm): Node[String, Int] + def genParm(tree: Tree[Int]): Gen[ModifyParm] + def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int] - def genInput: Gen[(Node[String, Int], ModifyParm, Node[String, Int])] = for { + def genInput: Gen[(Tree[Int], ModifyParm, Tree[Int])] = for { tree <- genTree parm <- genParm(tree) } yield (tree, parm, modify(tree, parm)) @@ -66,30 +68,30 @@ abstract class RedBlackTest extends Properties("RedBlack") { trait RedBlackInvariants { self: RedBlackTest => - import RedBlack._ + import RedBlackTest._ - def rootIsBlack[A](t: Node[String, A]) = isBlack(t) + def rootIsBlack[A](t: Tree[A]) = t.isBlack - def areAllLeavesBlack[A](t: Node[String, A]): Boolean = t match { - case null => isBlack(t) - case ne => List(ne.left, ne.right) forall areAllLeavesBlack + def areAllLeavesBlack[A](t: Tree[A]): Boolean = t match { + case Empty => t.isBlack + case ne: NonEmpty[_] => List(ne.left, ne.right) forall areAllLeavesBlack } - def areRedNodeChildrenBlack[A](t: Node[String, A]): Boolean = t match { - case RedNode(_, _, left, right) => List(left, right) forall (t => isBlack(t) && areRedNodeChildrenBlack(t)) - case BlackNode(_, _, left, right) => List(left, right) forall areRedNodeChildrenBlack - case null => true + def areRedNodeChildrenBlack[A](t: Tree[A]): Boolean = t match { + case RedTree(_, _, left, right) => List(left, right) forall (t => t.isBlack && areRedNodeChildrenBlack(t)) + case BlackTree(_, _, left, right) => List(left, right) forall areRedNodeChildrenBlack + case Empty => true } - def blackNodesToLeaves[A](t: Node[String, A]): List[Int] = t match { - case null => List(1) - case BlackNode(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves map (_ + 1) - case RedNode(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves + def blackNodesToLeaves[A](t: Tree[A]): List[Int] = t match { + case Empty => List(1) + case BlackTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves map (_ + 1) + case RedTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves } - def areBlackNodesToLeavesEqual[A](t: Node[String, A]): Boolean = t match { - case null => true - case ne => + def areBlackNodesToLeavesEqual[A](t: Tree[A]): Boolean = t match { + case Empty => true + case ne: NonEmpty[_] => ( blackNodesToLeaves(ne).distinct.size == 1 && areBlackNodesToLeavesEqual(ne.left) @@ -97,10 +99,10 @@ trait RedBlackInvariants { ) } - def orderIsPreserved[A](t: Node[String, A]): Boolean = - iterator(t) zip iterator(t).drop(1) forall { case (x, y) => x._1 < y._1 } + def orderIsPreserved[A](t: Tree[A]): Boolean = + t.iterator zip t.iterator.drop(1) forall { case (x, y) => isSmaller(x._1, y._1) } - def setup(invariant: Node[String, Int] => Boolean) = forAll(genInput) { case (tree, parm, newTree) => + def setup(invariant: Tree[Int] => Boolean) = forAll(genInput) { case (tree, parm, newTree) => invariant(newTree) } @@ -112,13 +114,13 @@ trait RedBlackInvariants { } object TestInsert extends RedBlackTest with RedBlackInvariants { - import RedBlack._ + import RedBlackTest._ override type ModifyParm = Int - override def genParm(tree: Node[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size + 1) - override def modify(tree: Node[String, Int], parm: ModifyParm): Node[String, Int] = update(tree, generateKey(tree, parm), 0) + override def genParm(tree: Tree[Int]): Gen[ModifyParm] = choose(0, tree.iterator.size + 1) + override def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int] = tree update (generateKey(tree, parm), 0) - def generateKey(tree: Node[String, Int], parm: ModifyParm): String = nodeAt(tree, parm) match { + def generateKey(tree: Tree[Int], parm: ModifyParm): String = nodeAt(tree, parm) match { case Some((key, _)) => key.init.mkString + "MN" case None => nodeAt(tree, parm - 1) match { case Some((key, _)) => key.init.mkString + "RN" @@ -132,31 +134,31 @@ object TestInsert extends RedBlackTest with RedBlackInvariants { } object TestModify extends RedBlackTest { - import RedBlack._ + import RedBlackTest._ def newValue = 1 override def minimumSize = 1 override type ModifyParm = Int - override def genParm(tree: Node[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size) - override def modify(tree: Node[String, Int], parm: ModifyParm): Node[String, Int] = nodeAt(tree, parm) map { - case (key, _) => update(tree, key, newValue) + override def genParm(tree: Tree[Int]): Gen[ModifyParm] = choose(0, tree.iterator.size) + override def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int] = nodeAt(tree, parm) map { + case (key, _) => tree update (key, newValue) } getOrElse tree property("update modifies values") = forAll(genInput) { case (tree, parm, newTree) => nodeAt(tree,parm) forall { case (key, _) => - iterator(newTree) contains (key, newValue) + newTree.iterator contains (key, newValue) } } } object TestDelete extends RedBlackTest with RedBlackInvariants { - import RedBlack._ + import RedBlackTest._ override def minimumSize = 1 override type ModifyParm = Int - override def genParm(tree: Node[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size) - override def modify(tree: Node[String, Int], parm: ModifyParm): Node[String, Int] = nodeAt(tree, parm) map { - case (key, _) => delete(tree, key) + override def genParm(tree: Tree[Int]): Gen[ModifyParm] = choose(0, tree.iterator.size) + override def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int] = nodeAt(tree, parm) map { + case (key, _) => tree delete key } getOrElse tree property("delete removes elements") = forAll(genInput) { case (tree, parm, newTree) => @@ -167,41 +169,40 @@ object TestDelete extends RedBlackTest with RedBlackInvariants { } object TestRange extends RedBlackTest with RedBlackInvariants { - import RedBlack._ + import RedBlackTest._ override type ModifyParm = (Option[Int], Option[Int]) - override def genParm(tree: Node[String, Int]): Gen[ModifyParm] = for { - from <- choose(0, iterator(tree).size) - to <- choose(0, iterator(tree).size) suchThat (from <=) + override def genParm(tree: Tree[Int]): Gen[ModifyParm] = for { + from <- choose(0, tree.iterator.size) + to <- choose(0, tree.iterator.size) suchThat (from <=) optionalFrom <- oneOf(Some(from), None, Some(from)) // Double Some(n) to get around a bug optionalTo <- oneOf(Some(to), None, Some(to)) // Double Some(n) to get around a bug } yield (optionalFrom, optionalTo) - override def modify(tree: Node[String, Int], parm: ModifyParm): Node[String, Int] = { + override def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int] = { val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) - range(tree, from, to) + tree range (from, to) } property("range boundaries respected") = forAll(genInput) { case (tree, parm, newTree) => val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) - ("lower boundary" |: (from forall ( key => iterator(newTree).map(_._1) forall (key <=)))) && - ("upper boundary" |: (to forall ( key => iterator(newTree).map(_._1) forall (key >)))) + ("lower boundary" |: (from forall ( key => newTree.iterator.map(_._1) forall (key <=)))) && + ("upper boundary" |: (to forall ( key => newTree.iterator.map(_._1) forall (key >)))) } property("range returns all elements") = forAll(genInput) { case (tree, parm, newTree) => val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) - val filteredTree = (iterator(tree) + val filteredTree = (tree.iterator .map(_._1) .filter(key => from forall (key >=)) .filter(key => to forall (key <)) .toList) - filteredTree == iterator(newTree).map(_._1).toList + filteredTree == newTree.iterator.map(_._1).toList } } -} object Test extends Properties("RedBlack") { include(TestInsert) diff --git a/test/files/scalacheck/redblacktree.scala b/test/files/scalacheck/redblacktree.scala new file mode 100644 index 0000000000..10f3f0fbbf --- /dev/null +++ b/test/files/scalacheck/redblacktree.scala @@ -0,0 +1,212 @@ +import collection.immutable.{RedBlackTree => RB} +import org.scalacheck._ +import Prop._ +import Gen._ + +/* +Properties of a Red & Black Tree: + +A node is either red or black. +The root is black. (This rule is used in some definitions and not others. Since the +root can always be changed from red to black but not necessarily vice-versa this +rule has little effect on analysis.) +All leaves are black. +Both children of every red node are black. +Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. +*/ + +package scala.collection.immutable.redblacktree { + abstract class RedBlackTreeTest extends Properties("RedBlackTree") { + def minimumSize = 0 + def maximumSize = 5 + + import RB._ + + def nodeAt[A](tree: Tree[String, A], n: Int): Option[(String, A)] = if (n < iterator(tree).size && n >= 0) + Some(iterator(tree).drop(n).next) + else + None + + def treeContains[A](tree: Tree[String, A], key: String) = iterator(tree).map(_._1) contains key + + def mkTree(level: Int, parentIsBlack: Boolean = false, label: String = ""): Gen[Tree[String, Int]] = + if (level == 0) { + value(null) + } else { + for { + oddOrEven <- choose(0, 2) + tryRed = oddOrEven.sample.get % 2 == 0 // work around arbitrary[Boolean] bug + isRed = parentIsBlack && tryRed + nextLevel = if (isRed) level else level - 1 + left <- mkTree(nextLevel, !isRed, label + "L") + right <- mkTree(nextLevel, !isRed, label + "R") + } yield { + if (isRed) + RedTree(label + "N", 0, left, right) + else + BlackTree(label + "N", 0, left, right) + } + } + + def genTree = for { + depth <- choose(minimumSize, maximumSize + 1) + tree <- mkTree(depth) + } yield tree + + type ModifyParm + def genParm(tree: Tree[String, Int]): Gen[ModifyParm] + def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] + + def genInput: Gen[(Tree[String, Int], ModifyParm, Tree[String, Int])] = for { + tree <- genTree + parm <- genParm(tree) + } yield (tree, parm, modify(tree, parm)) + } + + trait RedBlackTreeInvariants { + self: RedBlackTreeTest => + + import RB._ + + def rootIsBlack[A](t: Tree[String, A]) = isBlack(t) + + def areAllLeavesBlack[A](t: Tree[String, A]): Boolean = t match { + case null => isBlack(t) + case ne => List(ne.left, ne.right) forall areAllLeavesBlack + } + + def areRedNodeChildrenBlack[A](t: Tree[String, A]): Boolean = t match { + case RedTree(_, _, left, right) => List(left, right) forall (t => isBlack(t) && areRedNodeChildrenBlack(t)) + case BlackTree(_, _, left, right) => List(left, right) forall areRedNodeChildrenBlack + case null => true + } + + def blackNodesToLeaves[A](t: Tree[String, A]): List[Int] = t match { + case null => List(1) + case BlackTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves map (_ + 1) + case RedTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves + } + + def areBlackNodesToLeavesEqual[A](t: Tree[String, A]): Boolean = t match { + case null => true + case ne => + ( + blackNodesToLeaves(ne).distinct.size == 1 + && areBlackNodesToLeavesEqual(ne.left) + && areBlackNodesToLeavesEqual(ne.right) + ) + } + + def orderIsPreserved[A](t: Tree[String, A]): Boolean = + iterator(t) zip iterator(t).drop(1) forall { case (x, y) => x._1 < y._1 } + + def setup(invariant: Tree[String, Int] => Boolean) = forAll(genInput) { case (tree, parm, newTree) => + invariant(newTree) + } + + property("root is black") = setup(rootIsBlack) + property("all leaves are black") = setup(areAllLeavesBlack) + property("children of red nodes are black") = setup(areRedNodeChildrenBlack) + property("black nodes are balanced") = setup(areBlackNodesToLeavesEqual) + property("ordering of keys is preserved") = setup(orderIsPreserved) + } + + object TestInsert extends RedBlackTreeTest with RedBlackTreeInvariants { + import RB._ + + override type ModifyParm = Int + override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size + 1) + override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = update(tree, generateKey(tree, parm), 0) + + def generateKey(tree: Tree[String, Int], parm: ModifyParm): String = nodeAt(tree, parm) match { + case Some((key, _)) => key.init.mkString + "MN" + case None => nodeAt(tree, parm - 1) match { + case Some((key, _)) => key.init.mkString + "RN" + case None => "N" + } + } + + property("update adds elements") = forAll(genInput) { case (tree, parm, newTree) => + treeContains(newTree, generateKey(tree, parm)) + } + } + + object TestModify extends RedBlackTreeTest { + import RB._ + + def newValue = 1 + override def minimumSize = 1 + override type ModifyParm = Int + override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size) + override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = nodeAt(tree, parm) map { + case (key, _) => update(tree, key, newValue) + } getOrElse tree + + property("update modifies values") = forAll(genInput) { case (tree, parm, newTree) => + nodeAt(tree,parm) forall { case (key, _) => + iterator(newTree) contains (key, newValue) + } + } + } + + object TestDelete extends RedBlackTreeTest with RedBlackTreeInvariants { + import RB._ + + override def minimumSize = 1 + override type ModifyParm = Int + override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size) + override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = nodeAt(tree, parm) map { + case (key, _) => delete(tree, key) + } getOrElse tree + + property("delete removes elements") = forAll(genInput) { case (tree, parm, newTree) => + nodeAt(tree, parm) forall { case (key, _) => + !treeContains(newTree, key) + } + } + } + + object TestRange extends RedBlackTreeTest with RedBlackTreeInvariants { + import RB._ + + override type ModifyParm = (Option[Int], Option[Int]) + override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = for { + from <- choose(0, iterator(tree).size) + to <- choose(0, iterator(tree).size) suchThat (from <=) + optionalFrom <- oneOf(Some(from), None, Some(from)) // Double Some(n) to get around a bug + optionalTo <- oneOf(Some(to), None, Some(to)) // Double Some(n) to get around a bug + } yield (optionalFrom, optionalTo) + + override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = { + val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) + val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) + range(tree, from, to) + } + + property("range boundaries respected") = forAll(genInput) { case (tree, parm, newTree) => + val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) + val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) + ("lower boundary" |: (from forall ( key => iterator(newTree).map(_._1) forall (key <=)))) && + ("upper boundary" |: (to forall ( key => iterator(newTree).map(_._1) forall (key >)))) + } + + property("range returns all elements") = forAll(genInput) { case (tree, parm, newTree) => + val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) + val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) + val filteredTree = (iterator(tree) + .map(_._1) + .filter(key => from forall (key >=)) + .filter(key => to forall (key <)) + .toList) + filteredTree == iterator(newTree).map(_._1).toList + } + } +} + +object Test extends Properties("RedBlackTree") { + import collection.immutable.redblacktree._ + include(TestInsert) + include(TestModify) + include(TestDelete) + include(TestRange) +} |