From 288874d80856317744c582f1468d7af420d9e0ee Mon Sep 17 00:00:00 2001 From: Erik Rozendaal Date: Sat, 7 Jan 2012 15:26:40 +0100 Subject: 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. --- test/files/scalacheck/redblack.scala | 113 ++++++++-------- test/files/scalacheck/redblacktree.scala | 212 +++++++++++++++++++++++++++++++ 2 files changed, 269 insertions(+), 56 deletions(-) create mode 100644 test/files/scalacheck/redblacktree.scala (limited to 'test') 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) +} -- cgit v1.2.3