summaryrefslogtreecommitdiff
path: root/test
diff options
context:
space:
mode:
Diffstat (limited to 'test')
-rw-r--r--test/disabled/scalacheck/redblack.scala157
-rw-r--r--test/files/neg/t3481.check29
-rw-r--r--test/files/neg/t3481.scala28
-rw-r--r--test/files/run/bitsets.check46
-rw-r--r--test/files/run/bitsets.scala85
-rw-r--r--test/files/scalacheck/redblack.scala213
6 files changed, 401 insertions, 157 deletions
diff --git a/test/disabled/scalacheck/redblack.scala b/test/disabled/scalacheck/redblack.scala
deleted file mode 100644
index 0334c1218d..0000000000
--- a/test/disabled/scalacheck/redblack.scala
+++ /dev/null
@@ -1,157 +0,0 @@
-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.
-*/
-
-abstract class RedBlackTest extends Properties("RedBlack") {
- object RedBlackTest extends scala.collection.immutable.RedBlack[Int] {
- def isSmaller(x: Int, y: Int) = x < y
- }
-
- 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 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[_] =>
- (
- blackNodesToLeaves(ne).removeDuplicates.size == 1
- && areBlackNodesToLeavesEqual(ne.left)
- && areBlackNodesToLeavesEqual(ne.right)
- )
- }
-
- def orderIsPreserved[A](t: Tree[A]): Boolean = t match {
- case Empty => true
- case ne: NonEmpty[_] =>
- (
- (ne.left.iterator map (_._1) forall (isSmaller(_, ne.key)))
- && (ne.right.iterator map (_._1) forall (isSmaller(ne.key, _)))
- && (List(ne.left, ne.right) forall orderIsPreserved)
- )
- }
-
- def setup(l: List[Int], invariant: Tree[Unit] => Boolean): (Boolean, Tree[Unit])
-
- def listNoRepetitions(size: Int) = for {
- s <- Gen.choose(1, size)
- l <- Gen.listOfN(size, Gen.choose(0, Int.MaxValue)) suchThat (l => l.size == l.removeDuplicates.size)
- } yield l
- def listFewRepetitions(size: Int) = for {
- s <- Gen.choose(1, size)
- l <- Gen.listOfN(s, Gen.choose(0, size * 4)) suchThat (l => l.size != l.removeDuplicates.size)
- } yield l
- def listManyRepetitions(size: Int) = for {
- s <- Gen.choose(1, size)
- l <- Gen.listOfN(s, Gen.choose(0, size)) suchThat (l => l.size != l.removeDuplicates.size)
- } yield l
- def listEvenRepetitions(size: Int) = listFewRepetitions(size) map (x =>
- scala.util.Random.shuffle(x zip x flatMap { case (a, b) => List(a, b) })
- )
-
- // Arbitrarily weighted list distribution types
- val seqType: Gen[Int => Gen[List[Int]]]
-
- def myGen(sized: Int) = for {
- size <- Gen.choose(0, sized)
- seq <- seqType
- list <- seq(size)
- } yield list
-
- property("root is black") = forAll(myGen(10)) { l =>
- setup(l, rootIsBlack)._1 :| setup(l, rootIsBlack)._2.toString
- }
- property("all leaves are black") = forAll(myGen(50)) { l =>
- setup(l, areAllLeavesBlack)._1 :| setup(l, areAllLeavesBlack)._2.toString
- }
- property("children of red nodes are black") = forAll(myGen(50)) { l =>
- setup(l, areRedNodeChildrenBlack)._1 :| setup(l, areRedNodeChildrenBlack)._2.toString
- }
- property("Every path from a node to its descendant leaves contains the same number of black nodes") = forAll(myGen(50)) { l =>
- setup(l, areBlackNodesToLeavesEqual)._1 :| setup(l, areBlackNodesToLeavesEqual)._2.toString
- }
- property("Ordering of keys is preserved") = forAll(myGen(50)) { l =>
- setup(l, orderIsPreserved)._1 :| setup(l, orderIsPreserved)._2.toString
- }
-}
-
-object TestInsertion extends RedBlackTest {
- import RedBlackTest._
- override val seqType = Gen.frequency(
- (1, listNoRepetitions _),
- (1, listManyRepetitions _)
- )
-
- property("update adds elements") = forAll(myGen(50)) { l =>
- val tree = l.foldLeft(Empty: Tree[Unit])((acc, n) => acc update (n, ()))
- forAll(Gen.pick(1, l)) ( n => !(tree lookup n.head isEmpty) :| "Tree: "+tree+" N: "+n.head )
- }
-
- override def setup(l: List[Int], invariant: Tree[Unit] => Boolean) = l.foldLeft((true, Empty: Tree[Unit])) {
- case ((true, acc), n) =>
- val newRoot = acc update (n, ())
- (invariant(newRoot), newRoot)
- case (failed, _) => failed
- }
-}
-
-object TestDeletion extends RedBlackTest {
- import RedBlackTest._
- override val seqType = Gen.frequency(
- (2, listFewRepetitions _),
- (3, listManyRepetitions _),
- (1, listEvenRepetitions _)
- )
-
- property("delete removes elements") = forAll(myGen(50)) { l =>
- val tree = l.foldLeft(Empty: Tree[Unit])((acc, n) => acc update (n, ()))
- forAll(Gen.choose(1, l.size)) { numberOfElementsToRemove =>
- forAll(Gen.pick(numberOfElementsToRemove, l)) { elementsToRemove =>
- val newTree = elementsToRemove.foldLeft(tree)((acc, n) => acc delete n)
- (elementsToRemove forall (n => newTree lookup n isEmpty)) :| "Tree: "+tree+"New Tree: "+newTree+" Elements to Remove: "+elementsToRemove
- }
- }
- }
-
- override def setup(l: List[Int], invariant: Tree[Unit] => Boolean) = l.foldLeft((true, Empty: Tree[Unit])) {
- case ((true, acc), n) =>
- val newRoot = if (acc lookup n isEmpty) acc update (n, ()) else acc delete n
- (invariant(newRoot), newRoot)
- case (failed, _) => failed
- }
-}
-
-object Test extends Properties("RedBlack") {
- include(TestInsertion)
- include(TestDeletion)
-}
-
diff --git a/test/files/neg/t3481.check b/test/files/neg/t3481.check
new file mode 100644
index 0000000000..48e6ff357b
--- /dev/null
+++ b/test/files/neg/t3481.check
@@ -0,0 +1,29 @@
+t3481.scala:5: error: type mismatch;
+ found : String("hello")
+ required: _$1 where type +_$1
+ f[A[Int]]("hello")
+ ^
+t3481.scala:11: error: type mismatch;
+ found : _$2 where type +_$2
+ required: b.T
+ (which expands to) _$2
+ def f[T <: B[_]](a: T#T, b: T) = b.m(a)
+ ^
+t3481.scala:12: error: type mismatch;
+ found : String("Hello")
+ required: _$2 where type +_$2
+ f("Hello", new B[Int])
+ ^
+t3481.scala:18: error: type mismatch;
+ found : String("Hello")
+ required: t3481.ex3.b.T2
+ (which expands to) _$3
+ b.m("Hello")
+ ^
+t3481.scala:25: error: type mismatch;
+ found : String("Hello")
+ required: t3481.ex4.Test.b.T2
+ (which expands to) _$4
+ b.m("Hello")
+ ^
+5 errors found
diff --git a/test/files/neg/t3481.scala b/test/files/neg/t3481.scala
new file mode 100644
index 0000000000..f4b781ee37
--- /dev/null
+++ b/test/files/neg/t3481.scala
@@ -0,0 +1,28 @@
+object t3481 {
+ object ex1 {
+ trait A[T] { type B = T }
+ def f[T <: A[_]](a: T#B) = 1
+ f[A[Int]]("hello")
+ }
+
+ object ex2 {
+ trait A { type T; def m(t: T) = t.toString }
+ class B[T2] extends A { type T = T2 }
+ def f[T <: B[_]](a: T#T, b: T) = b.m(a)
+ f("Hello", new B[Int])
+ }
+
+ object ex3 {
+ class B[T] { type T2 = T; def m(t: T2) = t.toString }
+ val b: B[_] = new B[Int]
+ b.m("Hello")
+ }
+
+ object ex4 {
+ abstract class B[T] { type T2 = T; def m(t: T2): Any }
+ object Test {
+ val b: B[_] = sys.error("")
+ b.m("Hello")
+ }
+ }
+} \ No newline at end of file
diff --git a/test/files/run/bitsets.check b/test/files/run/bitsets.check
index 478de261af..3f01d2a400 100644
--- a/test/files/run/bitsets.check
+++ b/test/files/run/bitsets.check
@@ -14,6 +14,29 @@ mi0 = BitSet(2)
mi1 = BitSet(2)
mi2 = BitSet(2)
+m2_m0 = List(1010101010101010101010101)
+m2_m2 = List(ffffffffffffffff, ffffffffffffffff, ffffffffffffffff, ffffffffffffffff, 1, 0, 0, 0)
+m2_m0c = true
+m2_m1c = true
+m2_m2c = true
+m2_m3c = true
+m2_i0 = true
+m2_i1 = true
+m2_i2 = true
+m2_i3 = true
+m2_f0 = true
+m2_f1 = true
+m2_f2 = true
+m2_f3 = true
+m2_t0 = true
+m2_t1 = true
+m2_t2 = true
+m2_t3 = true
+m2_r0 = true
+m2_r1 = true
+m2_r2 = true
+m2_r3 = true
+
is0 = BitSet()
is1 = BitSet()
is2 = BitSet(2)
@@ -31,3 +54,26 @@ ia1 = List()
ia2 = List(2)
ia3 = List()
+i2_m0 = List(1010101010101010101010101)
+i2_m2 = List(ffffffffffffffff, ffffffffffffffff, ffffffffffffffff, ffffffffffffffff, 1)
+i2_m0c = true
+i2_m1c = true
+i2_m2c = true
+i2_m3c = true
+i2_i0 = true
+i2_i1 = true
+i2_i2 = true
+i2_i3 = true
+i2_f0 = true
+i2_f1 = true
+i2_f2 = true
+i2_f3 = true
+i2_t0 = true
+i2_t1 = true
+i2_t2 = true
+i2_t3 = true
+i2_r0 = true
+i2_r1 = true
+i2_r2 = true
+i2_r3 = true
+
diff --git a/test/files/run/bitsets.scala b/test/files/run/bitsets.scala
index a847c9940d..27395683b4 100644
--- a/test/files/run/bitsets.scala
+++ b/test/files/run/bitsets.scala
@@ -39,6 +39,48 @@ object TestMutable {
Console.println
}
+object TestMutable2 {
+ import scala.collection.mutable.BitSet
+ import scala.collection.immutable.TreeSet
+
+ val l0 = 0 to 24 by 2 toList
+ val l1 = (190 to 255 toList) reverse
+ val l2 = (0 to 256 toList)
+ val l3 = (1 to 200 by 2 toList) reverse
+ val t0 = TreeSet(l0: _*)
+ val t1 = TreeSet(l1: _*)
+ val t2 = TreeSet(l2: _*)
+ val t3 = TreeSet(l3: _*)
+ val b0 = BitSet(l0: _*)
+ val b1 = BitSet(l1: _*)
+ val b2 = BitSet(l2: _*)
+ val b3 = BitSet(l3: _*)
+
+ println("m2_m0 = " + b0.toBitMask.toList.map(_.toBinaryString))
+ println("m2_m2 = " + b2.toBitMask.toList.map(_.toHexString))
+ println("m2_m0c = " + (BitSet.fromBitMask(b0.toBitMask) == b0))
+ println("m2_m1c = " + (BitSet.fromBitMask(b1.toBitMask) == b1))
+ println("m2_m2c = " + (BitSet.fromBitMask(b2.toBitMask) == b2))
+ println("m2_m3c = " + (BitSet.fromBitMask(b3.toBitMask) == b3))
+ println("m2_i0 = " + (t0 == b0))
+ println("m2_i1 = " + (t1 == b1))
+ println("m2_i2 = " + (t2 == b2))
+ println("m2_i3 = " + (t3 == b3))
+ println("m2_f0 = " + (t0.from(42) == b0.from(42)))
+ println("m2_f1 = " + (t1.from(42) == b1.from(42)))
+ println("m2_f2 = " + (t2.from(42) == b2.from(42)))
+ println("m2_f3 = " + (t3.from(42) == b3.from(42)))
+ println("m2_t0 = " + (t0.to(195) == b0.to(195)))
+ println("m2_t1 = " + (t1.to(195) == b1.to(195)))
+ println("m2_t2 = " + (t2.to(195) == b2.to(195)))
+ println("m2_t3 = " + (t3.to(195) == b3.to(195)))
+ println("m2_r0 = " + (t0.range(43,194) == b0.range(43,194)))
+ println("m2_r1 = " + (t1.range(43,194) == b1.range(43,194)))
+ println("m2_r2 = " + (t2.range(43,194) == b2.range(43,194)))
+ println("m2_r3 = " + (t3.range(43,194) == b3.range(43,194)))
+ println
+}
+
object TestImmutable {
import scala.collection.immutable.BitSet
@@ -69,9 +111,52 @@ object TestImmutable {
Console.println
}
+object TestImmutable2 {
+ import scala.collection.immutable.{BitSet, TreeSet}
+
+ val l0 = 0 to 24 by 2 toList
+ val l1 = (190 to 255 toList) reverse
+ val l2 = (0 to 256 toList)
+ val l3 = (1 to 200 by 2 toList) reverse
+ val t0 = TreeSet(l0: _*)
+ val t1 = TreeSet(l1: _*)
+ val t2 = TreeSet(l2: _*)
+ val t3 = TreeSet(l3: _*)
+ val b0 = BitSet(l0: _*)
+ val b1 = BitSet(l1: _*)
+ val b2 = BitSet(l2: _*)
+ val b3 = BitSet(l3: _*)
+
+ println("i2_m0 = " + b0.toBitMask.toList.map(_.toBinaryString))
+ println("i2_m2 = " + b2.toBitMask.toList.map(_.toHexString))
+ println("i2_m0c = " + (BitSet.fromBitMask(b0.toBitMask) == b0))
+ println("i2_m1c = " + (BitSet.fromBitMask(b1.toBitMask) == b1))
+ println("i2_m2c = " + (BitSet.fromBitMask(b2.toBitMask) == b2))
+ println("i2_m3c = " + (BitSet.fromBitMask(b3.toBitMask) == b3))
+ println("i2_i0 = " + (t0 == b0))
+ println("i2_i1 = " + (t1 == b1))
+ println("i2_i2 = " + (t2 == b2))
+ println("i2_i3 = " + (t3 == b3))
+ println("i2_f0 = " + (t0.from(42) == b0.from(42)))
+ println("i2_f1 = " + (t1.from(42) == b1.from(42)))
+ println("i2_f2 = " + (t2.from(42) == b2.from(42)))
+ println("i2_f3 = " + (t3.from(42) == b3.from(42)))
+ println("i2_t0 = " + (t0.to(195) == b0.to(195)))
+ println("i2_t1 = " + (t1.to(195) == b1.to(195)))
+ println("i2_t2 = " + (t2.to(195) == b2.to(195)))
+ println("i2_t3 = " + (t3.to(195) == b3.to(195)))
+ println("i2_r0 = " + (t0.range(77,194) == b0.range(77,194)))
+ println("i2_r1 = " + (t1.range(77,194) == b1.range(77,194)))
+ println("i2_r2 = " + (t2.range(77,194) == b2.range(77,194)))
+ println("i2_r3 = " + (t3.range(77,194) == b3.range(77,194)))
+ println
+}
+
object Test extends App {
TestMutable
+ TestMutable2
TestImmutable
+ TestImmutable2
}
//############################################################################
diff --git a/test/files/scalacheck/redblack.scala b/test/files/scalacheck/redblack.scala
new file mode 100644
index 0000000000..1fcaa46f0e
--- /dev/null
+++ b/test/files/scalacheck/redblack.scala
@@ -0,0 +1,213 @@
+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.
+*/
+
+abstract class RedBlackTest extends Properties("RedBlack") {
+ def minimumSize = 0
+ def maximumSize = 5
+
+ 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]] =
+ if (level == 0) {
+ value(Empty)
+ } 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[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)
+ } yield (tree, parm, modify(tree, parm))
+}
+
+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 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[_] =>
+ (
+ blackNodesToLeaves(ne).distinct.size == 1
+ && areBlackNodesToLeavesEqual(ne.left)
+ && areBlackNodesToLeavesEqual(ne.right)
+ )
+ }
+
+ 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)
+ }
+
+ 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 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)
+
+ 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"
+ case None => "N"
+ }
+ }
+
+ property("update adds elements") = forAll(genInput) { case (tree, parm, newTree) =>
+ treeContains(newTree, generateKey(tree, parm))
+ }
+}
+
+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 {
+ case (key, _) => tree update (key, newValue)
+ } getOrElse tree
+
+ property("update modifies values") = forAll(genInput) { case (tree, parm, newTree) =>
+ nodeAt(tree,parm) forall { case (key, _) =>
+ newTree.iterator contains (key, newValue)
+ }
+ }
+}
+
+object TestDelete extends RedBlackTest with RedBlackInvariants {
+ import RedBlackTest._
+
+ 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 {
+ 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)
+ }
+ }
+}
+
+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)
+ 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: 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)
+ .filter(key => from forall (key >=))
+ .filter(key => to forall (key <))
+ .toList)
+ filteredTree == newTree.iterator.map(_._1).toList
+ }
+}
+
+object Test extends Properties("RedBlack") {
+ include(TestInsert)
+ include(TestModify)
+ include(TestDelete)
+ include(TestRange)
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-16 10:17:24 +0000