Merge branch 'develop'

2 files changed, 213 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/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)
+}
+