summaryrefslogtreecommitdiff
path: root/test
diff options
context:
space:
mode:
Diffstat (limited to 'test')
-rw-r--r--test/files/scalacheck/redblack.scala113
-rw-r--r--test/files/scalacheck/redblacktree.scala212
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)
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-12 15:30:27 +0000