summaryrefslogtreecommitdiff
path: root/test/files/scalacheck/redblack.scala
diff options
context:
space:
mode:
Diffstat (limited to 'test/files/scalacheck/redblack.scala')
-rw-r--r--test/files/scalacheck/redblack.scala64
1 files changed, 32 insertions, 32 deletions
diff --git a/test/files/scalacheck/redblack.scala b/test/files/scalacheck/redblack.scala
index 1fcaa46f0e..bbc6504f58 100644
--- a/test/files/scalacheck/redblack.scala
+++ b/test/files/scalacheck/redblack.scala
@@ -7,7 +7,7 @@ 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
+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.
@@ -21,17 +21,17 @@ abstract class RedBlackTest extends Properties("RedBlack") {
object RedBlackTest extends scala.collection.immutable.RedBlack[String] {
def isSmaller(x: String, y: String) = x < y
}
-
+
import RedBlackTest._
-
+
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: Tree[A], key: String) = tree.iterator.map(_._1) contains key
-
- def mkTree(level: Int, parentIsBlack: Boolean = false, label: String = ""): Gen[Tree[Int]] =
+
+ def mkTree(level: Int, parentIsBlack: Boolean = false, label: String = ""): Gen[Tree[Int]] =
if (level == 0) {
value(Empty)
} else {
@@ -43,7 +43,7 @@ abstract class RedBlackTest extends Properties("RedBlack") {
left <- mkTree(nextLevel, !isRed, label + "L")
right <- mkTree(nextLevel, !isRed, label + "R")
} yield {
- if (isRed)
+ if (isRed)
RedTree(label + "N", 0, left, right)
else
BlackTree(label + "N", 0, left, right)
@@ -54,11 +54,11 @@ abstract class RedBlackTest extends Properties("RedBlack") {
depth <- choose(minimumSize, maximumSize + 1)
tree <- mkTree(depth)
} yield tree
-
+
type ModifyParm
def genParm(tree: Tree[Int]): Gen[ModifyParm]
def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int]
-
+
def genInput: Gen[(Tree[Int], ModifyParm, Tree[Int])] = for {
tree <- genTree
parm <- genParm(tree)
@@ -67,41 +67,41 @@ abstract class RedBlackTest extends Properties("RedBlack") {
trait RedBlackInvariants {
self: RedBlackTest =>
-
+
import RedBlackTest._
-
+
def rootIsBlack[A](t: Tree[A]) = t.isBlack
-
+
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: Tree[A]): Boolean = t match {
- case RedTree(_, _, left, right) => List(left, right) forall (t => t.isBlack && areRedNodeChildrenBlack(t))
+ 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: 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: Tree[A]): Boolean = t match {
case Empty => true
- case ne: NonEmpty[_] =>
+ case ne: NonEmpty[_] =>
(
- blackNodesToLeaves(ne).distinct.size == 1
- && areBlackNodesToLeavesEqual(ne.left)
+ blackNodesToLeaves(ne).distinct.size == 1
+ && areBlackNodesToLeavesEqual(ne.left)
&& areBlackNodesToLeavesEqual(ne.right)
)
}
-
- def orderIsPreserved[A](t: Tree[A]): Boolean =
+
+ 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: Tree[Int] => Boolean) = forAll(genInput) { case (tree, parm, newTree) =>
invariant(newTree)
}
@@ -115,7 +115,7 @@ trait RedBlackInvariants {
object TestInsert extends RedBlackTest with RedBlackInvariants {
import RedBlackTest._
-
+
override type ModifyParm = Int
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)
@@ -135,12 +135,12 @@ object TestInsert extends RedBlackTest with RedBlackInvariants {
object TestModify extends RedBlackTest {
import RedBlackTest._
-
+
def newValue = 1
override def minimumSize = 1
override type ModifyParm = Int
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 {
+ override def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int] = nodeAt(tree, parm) map {
case (key, _) => tree update (key, newValue)
} getOrElse tree
@@ -157,10 +157,10 @@ object TestDelete extends RedBlackTest with RedBlackInvariants {
override def minimumSize = 1
override type ModifyParm = Int
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 {
+ 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) =>
nodeAt(tree, parm) forall { case (key, _) =>
!treeContains(newTree, key)
@@ -170,7 +170,7 @@ object TestDelete extends RedBlackTest with RedBlackInvariants {
object TestRange extends RedBlackTest with RedBlackInvariants {
import RedBlackTest._
-
+
override type ModifyParm = (Option[Int], Option[Int])
override def genParm(tree: Tree[Int]): Gen[ModifyParm] = for {
from <- choose(0, tree.iterator.size)
@@ -178,25 +178,25 @@ object TestRange extends RedBlackTest with RedBlackInvariants {
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[Int], parm: ModifyParm): Tree[Int] = {
val from = parm._1 flatMap (nodeAt(tree, _) map (_._1))
val to = parm._2 flatMap (nodeAt(tree, _) map (_._1))
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 => 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 = (tree.iterator
- .map(_._1)
+ .map(_._1)
.filter(key => from forall (key >=))
.filter(key => to forall (key <))
.toList)
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-08 16:11:14 +0000