diff options
Diffstat (limited to 'test/files/scalacheck')
-rw-r--r-- | test/files/scalacheck/Ctrie.scala | 199 | ||||
-rw-r--r-- | test/files/scalacheck/avl.scala | 18 | ||||
-rw-r--r-- | test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala | 98 | ||||
-rw-r--r-- | test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala | 2 | ||||
-rw-r--r-- | test/files/scalacheck/parallel-collections/pc.scala | 3 | ||||
-rw-r--r-- | test/files/scalacheck/redblack.scala | 64 | ||||
-rw-r--r-- | test/files/scalacheck/redblacktree.scala | 216 | ||||
-rw-r--r-- | test/files/scalacheck/treemap.scala | 154 | ||||
-rw-r--r-- | test/files/scalacheck/treeset.scala | 152 |
9 files changed, 864 insertions, 42 deletions
diff --git a/test/files/scalacheck/Ctrie.scala b/test/files/scalacheck/Ctrie.scala new file mode 100644 index 0000000000..2950937278 --- /dev/null +++ b/test/files/scalacheck/Ctrie.scala @@ -0,0 +1,199 @@ + + + +import org.scalacheck._ +import Prop._ +import org.scalacheck.Gen._ +import collection._ +import collection.mutable.Ctrie + + + +case class Wrap(i: Int) { + override def hashCode = i // * 0x9e3775cd +} + + +/** A check mainly oriented towards checking snapshot correctness. + */ +object Test extends Properties("Ctrie") { + + /* generators */ + + val sizes = choose(0, 200000) + + val threadCounts = choose(2, 16) + + val threadCountsAndSizes = for { + p <- threadCounts + sz <- sizes + } yield (p, sz); + + + /* helpers */ + + def inParallel[T](totalThreads: Int)(body: Int => T): Seq[T] = { + val threads = for (idx <- 0 until totalThreads) yield new Thread { + setName("ParThread-" + idx) + private var res: T = _ + override def run() { + res = body(idx) + } + def result = { + this.join() + res + } + } + + threads foreach (_.start()) + threads map (_.result) + } + + def spawn[T](body: =>T): { def get: T } = { + val t = new Thread { + setName("SpawnThread") + private var res: T = _ + override def run() { + res = body + } + def result = res + } + t.start() + new { + def get: T = { + t.join() + t.result + } + } + } + + def elementRange(threadIdx: Int, totalThreads: Int, totalElems: Int): Range = { + val sz = totalElems + val idx = threadIdx + val p = totalThreads + val start = (sz / p) * idx + math.min(idx, sz % p) + val elems = (sz / p) + (if (idx < sz % p) 1 else 0) + val end = start + elems + (start until end) + } + + def hasGrown[K, V](last: Map[K, V], current: Map[K, V]) = { + (last.size <= current.size) && { + last forall { + case (k, v) => current.get(k) == Some(v) + } + } + } + + object err { + var buffer = new StringBuilder + def println(a: AnyRef) = buffer.append(a.toString).append("\n") + def clear() = buffer.clear() + def flush() = { + Console.out.println(buffer) + clear() + } + } + + + /* properties */ + + property("concurrent growing snapshots") = forAll(threadCounts, sizes) { + (numThreads, numElems) => + val p = 3 //numThreads + val sz = 102 //numElems + val ct = new Ctrie[Wrap, Int] + + // checker + val checker = spawn { + def check(last: Map[Wrap, Int], iterationsLeft: Int): Boolean = { + val current = ct.readOnlySnapshot() + if (!hasGrown(last, current)) false + else if (current.size >= sz) true + else if (iterationsLeft < 0) false + else check(current, iterationsLeft - 1) + } + check(ct.readOnlySnapshot(), 500) + } + + // fillers + inParallel(p) { + idx => + elementRange(idx, p, sz) foreach (i => ct.update(Wrap(i), i)) + } + + // wait for checker to finish + val growing = true//checker.get + + val ok = growing && ((0 until sz) forall { + case i => ct.get(Wrap(i)) == Some(i) + }) + + ok + } + + property("update") = forAll(sizes) { + (n: Int) => + val ct = new Ctrie[Int, Int] + for (i <- 0 until n) ct(i) = i + (0 until n) forall { + case i => ct(i) == i + } + } + + property("concurrent update") = forAll(threadCountsAndSizes) { + case (p, sz) => + val ct = new Ctrie[Wrap, Int] + + inParallel(p) { + idx => + for (i <- elementRange(idx, p, sz)) ct(Wrap(i)) = i + } + + (0 until sz) forall { + case i => ct(Wrap(i)) == i + } + } + + + property("concurrent remove") = forAll(threadCounts, sizes) { + (p, sz) => + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct(Wrap(i)) = i + + inParallel(p) { + idx => + for (i <- elementRange(idx, p, sz)) ct.remove(Wrap(i)) + } + + (0 until sz) forall { + case i => ct.get(Wrap(i)) == None + } + } + + + property("concurrent putIfAbsent") = forAll(threadCounts, sizes) { + (p, sz) => + val ct = new Ctrie[Wrap, Int] + + val results = inParallel(p) { + idx => + elementRange(idx, p, sz) find (i => ct.putIfAbsent(Wrap(i), i) != None) + } + + (results forall (_ == None)) && ((0 until sz) forall { + case i => ct.get(Wrap(i)) == Some(i) + }) + } + +} + + + + + + + + + + diff --git a/test/files/scalacheck/avl.scala b/test/files/scalacheck/avl.scala index 51fb1fe8c3..af79ad49e3 100644 --- a/test/files/scalacheck/avl.scala +++ b/test/files/scalacheck/avl.scala @@ -47,21 +47,21 @@ package scala.collection.mutable { } } - def genInput: Gen[(Int, List[AVLTree[Int]])] = for { - size <- Gen.choose(20, 25) - elements <- Gen.listOfN(size, Gen.choose(0, 1000)) - selected <- Gen.choose(0, 1000) + def genInput: org.scalacheck.Gen[(Int, List[AVLTree[Int]])] = for { + size <- org.scalacheck.Gen.choose(20, 25) + elements <- org.scalacheck.Gen.listOfN(size, org.scalacheck.Gen.choose(0, 1000)) + selected <- org.scalacheck.Gen.choose(0, 1000) } yield { // selected mustn't be in elements already val list = makeAllBalancedTree(elements.sorted.distinct.map(_*2)) (selected*2+1, list) } - def genInputDelete: Gen[(Int, List[AVLTree[Int]])] = for { - size <- Gen.choose(20, 25) - elements <- Gen.listOfN(size, Gen.choose(0, 1000)) + def genInputDelete: org.scalacheck.Gen[(Int, List[AVLTree[Int]])] = for { + size <- org.scalacheck.Gen.choose(20, 25) + elements <- org.scalacheck.Gen.listOfN(size, org.scalacheck.Gen.choose(0, 1000)) e = elements.sorted.distinct - selected <- Gen.choose(0, e.size-1) + selected <- org.scalacheck.Gen.choose(0, e.size-1) } yield { // selected must be in elements already val list = makeAllBalancedTree(e) @@ -111,4 +111,4 @@ package scala.collection.mutable { object Test extends Properties("AVL") { include(scala.collection.mutable.TestInsert) include(scala.collection.mutable.TestRemove) -}
\ No newline at end of file +} diff --git a/test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala b/test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala new file mode 100644 index 0000000000..d1924f0ada --- /dev/null +++ b/test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala @@ -0,0 +1,98 @@ +package scala.collection.parallel +package mutable + + + +import org.scalacheck._ +import org.scalacheck.Gen +import org.scalacheck.Gen._ +import org.scalacheck.Prop._ +import org.scalacheck.Properties +import org.scalacheck.Arbitrary._ + +import scala.collection._ +import scala.collection.parallel.ops._ + + + +abstract class ParallelCtrieCheck[K, V](tp: String) extends ParallelMapCheck[K, V]("mutable.ParCtrie[" + tp + "]") { + // ForkJoinTasks.defaultForkJoinPool.setMaximumPoolSize(Runtime.getRuntime.availableProcessors * 2) + // ForkJoinTasks.defaultForkJoinPool.setParallelism(Runtime.getRuntime.availableProcessors * 2) + + type CollType = ParCtrie[K, V] + + def isCheckingViews = false + + def hasStrictOrder = false + + def ofSize(vals: Seq[Gen[(K, V)]], sz: Int) = { + val ct = new mutable.Ctrie[K, V] + val gen = vals(rnd.nextInt(vals.size)) + for (i <- 0 until sz) ct += sample(gen) + ct + } + + def fromTraversable(t: Traversable[(K, V)]) = { + val pct = new ParCtrie[K, V] + var i = 0 + for (kv <- t.toList) { + pct += kv + i += 1 + } + pct + } + +} + + +object IntIntParallelCtrieCheck extends ParallelCtrieCheck[Int, Int]("Int, Int") +with PairOperators[Int, Int] +with PairValues[Int, Int] +{ + def intvalues = new IntValues {} + def kvalues = intvalues.values + def vvalues = intvalues.values + + val intoperators = new IntOperators {} + def voperators = intoperators + def koperators = intoperators + + override def printDataStructureDebugInfo(ds: AnyRef) = ds match { + case pm: ParCtrie[k, v] => + println("Mutable parallel ctrie") + case _ => + println("could not match data structure type: " + ds.getClass) + } + + override def checkDataStructureInvariants(orig: Traversable[(Int, Int)], ds: AnyRef) = ds match { + // case pm: ParHashMap[k, v] if 1 == 0 => // disabled this to make tests faster + // val invs = pm.brokenInvariants + + // val containsall = (for ((k, v) <- orig) yield { + // if (pm.asInstanceOf[ParHashMap[Int, Int]].get(k) == Some(v)) true + // else { + // println("Does not contain original element: " + (k, v)) + // false + // } + // }).foldLeft(true)(_ && _) + + + // if (invs.isEmpty) containsall + // else { + // println("Invariants broken:\n" + invs.mkString("\n")) + // false + // } + case _ => true + } + +} + + + + + + + + + + diff --git a/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala b/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala index 8273e302a2..e3f8778bca 100644 --- a/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala +++ b/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala @@ -86,7 +86,7 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col println("Collection debug info: ") coll.printDebugBuffer println("Task debug info: ") - println(tasksupport.debugMessages.mkString("\n")) + println(coll.tasksupport.debugMessages.mkString("\n")) } def printComparison(t: Traversable[_], coll: ParIterable[_], tf: Traversable[_], cf: ParIterable[_], ind: Int) { diff --git a/test/files/scalacheck/parallel-collections/pc.scala b/test/files/scalacheck/parallel-collections/pc.scala index cc0382303a..8a0dba3c25 100644 --- a/test/files/scalacheck/parallel-collections/pc.scala +++ b/test/files/scalacheck/parallel-collections/pc.scala @@ -25,6 +25,9 @@ class ParCollProperties extends Properties("Parallel collections") { // parallel mutable hash maps (tables) include(mutable.IntIntParallelHashMapCheck) + // parallel ctrie + include(mutable.IntIntParallelCtrieCheck) + // parallel mutable hash sets (tables) include(mutable.IntParallelHashSetCheck) 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) diff --git a/test/files/scalacheck/redblacktree.scala b/test/files/scalacheck/redblacktree.scala new file mode 100644 index 0000000000..e4b356c889 --- /dev/null +++ b/test/files/scalacheck/redblacktree.scala @@ -0,0 +1,216 @@ +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 height(tree: Tree[_, _]): Int = if (tree eq null) 0 else (1 + math.max(height(tree.left), height(tree.right))) + + 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 heightIsBounded(t: Tree[_, _]): Boolean = height(t) <= (2 * (32 - Integer.numberOfLeadingZeros(count(t) + 2)) - 2) + + 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) + property("height is bounded") = setup(heightIsBounded) + } + + 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)) + rangeImpl(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 => keysIterator(newTree) forall (key <=)))) && + ("upper boundary" |: (to forall ( key => keysIterator(newTree) 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 = (keysIterator(tree) + .filter(key => from forall (key >=)) + .filter(key => to forall (key <)) + .toList) + filteredTree == keysIterator(newTree).toList + } + } +} + +object Test extends Properties("RedBlackTree") { + import collection.immutable.redblacktree._ + include(TestInsert) + include(TestModify) + include(TestDelete) + include(TestRange) +} diff --git a/test/files/scalacheck/treemap.scala b/test/files/scalacheck/treemap.scala new file mode 100644 index 0000000000..f672637c57 --- /dev/null +++ b/test/files/scalacheck/treemap.scala @@ -0,0 +1,154 @@ +import collection.immutable._ +import org.scalacheck._ +import Prop._ +import Gen._ +import Arbitrary._ +import util._ +import Buildable._ + +object Test extends Properties("TreeMap") { + def genTreeMap[A: Arbitrary: Ordering, B: Arbitrary]: Gen[TreeMap[A, B]] = + for { + keys <- listOf(arbitrary[A]) + values <- listOfN(keys.size, arbitrary[B]) + } yield TreeMap(keys zip values: _*) + implicit def arbTreeMap[A : Arbitrary : Ordering, B : Arbitrary] = Arbitrary(genTreeMap[A, B]) + + property("foreach/iterator consistency") = forAll { (subject: TreeMap[Int, String]) => + val it = subject.iterator + var consistent = true + subject.foreach { element => + consistent &&= it.hasNext && element == it.next + } + consistent + } + + property("worst-case tree height is iterable") = forAll(choose(0, 10), arbitrary[Boolean]) { (n: Int, even: Boolean) => + /* + * According to "Ralf Hinze. Constructing red-black trees" [http://www.cs.ox.ac.uk/ralf.hinze/publications/#P5] + * you can construct a skinny tree of height 2n by inserting the elements [1 .. 2^(n+1) - 2] and a tree of height + * 2n+1 by inserting the elements [1 .. 3 * 2^n - 2], both in reverse order. + * + * Since we allocate a fixed size buffer in the iterator (based on the tree size) we need to ensure + * it is big enough for these worst-case trees. + */ + val highest = if (even) (1 << (n+1)) - 2 else 3*(1 << n) - 2 + val values = (1 to highest).reverse + val subject = TreeMap(values zip values: _*) + val it = subject.iterator + try { while (it.hasNext) it.next; true } catch { case _ => false } + } + + property("sorted") = forAll { (subject: TreeMap[Int, String]) => (subject.size >= 3) ==> { + subject.zip(subject.tail).forall { case (x, y) => x._1 < y._1 } + }} + + property("contains all") = forAll { (arr: List[(Int, String)]) => + val subject = TreeMap(arr: _*) + arr.map(_._1).forall(subject.contains(_)) + } + + property("size") = forAll { (elements: List[(Int, Int)]) => + val subject = TreeMap(elements: _*) + elements.map(_._1).distinct.size == subject.size + } + + property("toSeq") = forAll { (elements: List[(Int, Int)]) => + val subject = TreeMap(elements: _*) + elements.map(_._1).distinct.sorted == subject.toSeq.map(_._1) + } + + property("head") = forAll { (elements: List[Int]) => elements.nonEmpty ==> { + val subject = TreeMap(elements zip elements: _*) + elements.min == subject.head._1 + }} + + property("last") = forAll { (elements: List[Int]) => elements.nonEmpty ==> { + val subject = TreeMap(elements zip elements: _*) + elements.max == subject.last._1 + }} + + property("head/tail identity") = forAll { (subject: TreeMap[Int, String]) => subject.nonEmpty ==> { + subject == (subject.tail + subject.head) + }} + + property("init/last identity") = forAll { (subject: TreeMap[Int, String]) => subject.nonEmpty ==> { + subject == (subject.init + subject.last) + }} + + property("take") = forAll { (subject: TreeMap[Int, String]) => + val n = choose(0, subject.size).sample.get + n == subject.take(n).size && subject.take(n).forall(elt => subject.get(elt._1) == Some(elt._2)) + } + + property("drop") = forAll { (subject: TreeMap[Int, String]) => + val n = choose(0, subject.size).sample.get + (subject.size - n) == subject.drop(n).size && subject.drop(n).forall(elt => subject.get(elt._1) == Some(elt._2)) + } + + property("take/drop identity") = forAll { (subject: TreeMap[Int, String]) => + val n = choose(-1, subject.size + 1).sample.get + subject == subject.take(n) ++ subject.drop(n) + } + + property("splitAt") = forAll { (subject: TreeMap[Int, String]) => + val n = choose(-1, subject.size + 1).sample.get + val (prefix, suffix) = subject.splitAt(n) + prefix == subject.take(n) && suffix == subject.drop(n) + } + + def genSliceParms = for { + tree <- genTreeMap[Int, String] + from <- choose(0, tree.size) + until <- choose(from, tree.size) + } yield (tree, from, until) + + property("slice") = forAll(genSliceParms) { case (subject, from, until) => + val slice = subject.slice(from, until) + slice.size == until - from && subject.toSeq == subject.take(from).toSeq ++ slice ++ subject.drop(until) + } + + property("takeWhile") = forAll { (subject: TreeMap[Int, String]) => + val result = subject.takeWhile(_._1 < 0) + result.forall(_._1 < 0) && result == subject.take(result.size) + } + + property("dropWhile") = forAll { (subject: TreeMap[Int, String]) => + val result = subject.dropWhile(_._1 < 0) + result.forall(_._1 >= 0) && result == subject.takeRight(result.size) + } + + property("span identity") = forAll { (subject: TreeMap[Int, String]) => + val (prefix, suffix) = subject.span(_._1 < 0) + prefix.forall(_._1 < 0) && suffix.forall(_._1 >= 0) && subject == prefix ++ suffix + } + + property("from is inclusive") = forAll { (subject: TreeMap[Int, String]) => subject.nonEmpty ==> { + val n = choose(0, subject.size - 1).sample.get + val from = subject.drop(n).firstKey + subject.from(from).firstKey == from && subject.from(from).forall(_._1 >= from) + }} + + property("to is inclusive") = forAll { (subject: TreeMap[Int, String]) => subject.nonEmpty ==> { + val n = choose(0, subject.size - 1).sample.get + val to = subject.drop(n).firstKey + subject.to(to).lastKey == to && subject.to(to).forall(_._1 <= to) + }} + + property("until is exclusive") = forAll { (subject: TreeMap[Int, String]) => subject.size > 1 ==> { + val n = choose(1, subject.size - 1).sample.get + val until = subject.drop(n).firstKey + subject.until(until).lastKey == subject.take(n).lastKey && subject.until(until).forall(_._1 <= until) + }} + + property("remove single") = forAll { (subject: TreeMap[Int, String]) => subject.nonEmpty ==> { + val key = oneOf(subject.keys.toSeq).sample.get + val removed = subject - key + subject.contains(key) && !removed.contains(key) && subject.size - 1 == removed.size + }} + + property("remove all") = forAll { (subject: TreeMap[Int, String]) => + val result = subject.foldLeft(subject)((acc, elt) => acc - elt._1) + result.isEmpty + } +} diff --git a/test/files/scalacheck/treeset.scala b/test/files/scalacheck/treeset.scala new file mode 100644 index 0000000000..98e38c8219 --- /dev/null +++ b/test/files/scalacheck/treeset.scala @@ -0,0 +1,152 @@ +import collection.immutable._ +import org.scalacheck._ +import Prop._ +import Gen._ +import Arbitrary._ +import util._ + +object Test extends Properties("TreeSet") { + def genTreeSet[A: Arbitrary: Ordering]: Gen[TreeSet[A]] = + for { + elements <- listOf(arbitrary[A]) + } yield TreeSet(elements: _*) + implicit def arbTreeSet[A : Arbitrary : Ordering]: Arbitrary[TreeSet[A]] = Arbitrary(genTreeSet) + + property("foreach/iterator consistency") = forAll { (subject: TreeSet[Int]) => + val it = subject.iterator + var consistent = true + subject.foreach { element => + consistent &&= it.hasNext && element == it.next + } + consistent + } + + property("worst-case tree height is iterable") = forAll(choose(0, 10), arbitrary[Boolean]) { (n: Int, even: Boolean) => + /* + * According to "Ralf Hinze. Constructing red-black trees" [http://www.cs.ox.ac.uk/ralf.hinze/publications/#P5] + * you can construct a skinny tree of height 2n by inserting the elements [1 .. 2^(n+1) - 2] and a tree of height + * 2n+1 by inserting the elements [1 .. 3 * 2^n - 2], both in reverse order. + * + * Since we allocate a fixed size buffer in the iterator (based on the tree size) we need to ensure + * it is big enough for these worst-case trees. + */ + val highest = if (even) (1 << (n+1)) - 2 else 3*(1 << n) - 2 + val values = (1 to highest).reverse + val subject = TreeSet(values: _*) + val it = subject.iterator + try { while (it.hasNext) it.next; true } catch { case _ => false } + } + + property("sorted") = forAll { (subject: TreeSet[Int]) => (subject.size >= 3) ==> { + subject.zip(subject.tail).forall { case (x, y) => x < y } + }} + + property("contains all") = forAll { (elements: List[Int]) => + val subject = TreeSet(elements: _*) + elements.forall(subject.contains) + } + + property("size") = forAll { (elements: List[Int]) => + val subject = TreeSet(elements: _*) + elements.distinct.size == subject.size + } + + property("toSeq") = forAll { (elements: List[Int]) => + val subject = TreeSet(elements: _*) + elements.distinct.sorted == subject.toSeq + } + + property("head") = forAll { (elements: List[Int]) => elements.nonEmpty ==> { + val subject = TreeSet(elements: _*) + elements.min == subject.head + }} + + property("last") = forAll { (elements: List[Int]) => elements.nonEmpty ==> { + val subject = TreeSet(elements: _*) + elements.max == subject.last + }} + + property("head/tail identity") = forAll { (subject: TreeSet[Int]) => subject.nonEmpty ==> { + subject == (subject.tail + subject.head) + }} + + property("init/last identity") = forAll { (subject: TreeSet[Int]) => subject.nonEmpty ==> { + subject == (subject.init + subject.last) + }} + + property("take") = forAll { (subject: TreeSet[Int]) => + val n = choose(0, subject.size).sample.get + n == subject.take(n).size && subject.take(n).forall(subject.contains) + } + + property("drop") = forAll { (subject: TreeSet[Int]) => + val n = choose(0, subject.size).sample.get + (subject.size - n) == subject.drop(n).size && subject.drop(n).forall(subject.contains) + } + + property("take/drop identity") = forAll { (subject: TreeSet[Int]) => + val n = choose(-1, subject.size + 1).sample.get + subject == subject.take(n) ++ subject.drop(n) + } + + property("splitAt") = forAll { (subject: TreeSet[Int]) => + val n = choose(-1, subject.size + 1).sample.get + val (prefix, suffix) = subject.splitAt(n) + prefix == subject.take(n) && suffix == subject.drop(n) + } + + def genSliceParms = for { + tree <- genTreeSet[Int] + from <- choose(0, tree.size) + until <- choose(from, tree.size) + } yield (tree, from, until) + + property("slice") = forAll(genSliceParms) { case (subject, from, until) => + val slice = subject.slice(from, until) + slice.size == until - from && subject.toSeq == subject.take(from).toSeq ++ slice ++ subject.drop(until) + } + + property("takeWhile") = forAll { (subject: TreeSet[Int]) => + val result = subject.takeWhile(_ < 0) + result.forall(_ < 0) && result == subject.take(result.size) + } + + property("dropWhile") = forAll { (subject: TreeSet[Int]) => + val result = subject.dropWhile(_ < 0) + result.forall(_ >= 0) && result == subject.takeRight(result.size) + } + + property("span identity") = forAll { (subject: TreeSet[Int]) => + val (prefix, suffix) = subject.span(_ < 0) + prefix.forall(_ < 0) && suffix.forall(_ >= 0) && subject == prefix ++ suffix + } + + property("from is inclusive") = forAll { (subject: TreeSet[Int]) => subject.nonEmpty ==> { + val n = choose(0, subject.size - 1).sample.get + val from = subject.drop(n).firstKey + subject.from(from).firstKey == from && subject.from(from).forall(_ >= from) + }} + + property("to is inclusive") = forAll { (subject: TreeSet[Int]) => subject.nonEmpty ==> { + val n = choose(0, subject.size - 1).sample.get + val to = subject.drop(n).firstKey + subject.to(to).lastKey == to && subject.to(to).forall(_ <= to) + }} + + property("until is exclusive") = forAll { (subject: TreeSet[Int]) => subject.size > 1 ==> { + val n = choose(1, subject.size - 1).sample.get + val until = subject.drop(n).firstKey + subject.until(until).lastKey == subject.take(n).lastKey && subject.until(until).forall(_ <= until) + }} + + property("remove single") = forAll { (subject: TreeSet[Int]) => subject.nonEmpty ==> { + val element = oneOf(subject.toSeq).sample.get + val removed = subject - element + subject.contains(element) && !removed.contains(element) && subject.size - 1 == removed.size + }} + + property("remove all") = forAll { (subject: TreeSet[Int]) => + val result = subject.foldLeft(subject)((acc, elt) => acc - elt) + result.isEmpty + } +} |