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.scala113
1 files changed, 57 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)
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-26 06:11:04 +0000