Merged revisions 21810-21811,21816-21818,21826,...

Merged revisions 21810-21811,21816-21818,21826,21829 via svnmerge from
https://lampsvn.epfl.ch/svn-repos/scala/scala/trunk

........
  r21810 | imaier | 2010-05-05 11:59:25 +0200 (Wed, 05 May 2010) | 1 line

  Fixed #3358. Added explicit expected types to cachedWrapper calls,
deprecated explicit resizing of UIElements. ........ r21811 | rytz |
2010-05-05 13:53:31 +0200 (Wed, 05 May 2010) | 1 line

  revert the revert of r21791 (fix constructor parameter annotations).
close #3390. together with a new starr it builds. no review. ........
r21816 | extempore | 2010-05-05 18:56:55 +0200 (Wed, 05 May 2010) | 2
lines

  Rolled back a subset of partest to use StreamAppender and avoid
io.Process. No review. ........ r21817 | dragos | 2010-05-05 19:59:21
+0200 (Wed, 05 May 2010) | 3 lines

  Tightened what gets specialized: only when the type parameter appears
at top level, or as a type argument to a Java array. For example T,
Array[T] cause specialization, but List[T] does not. Resurrected
spec-matrix, forgotten among the disabled tests. No review. ........
r21818 | dragos | 2010-05-05 20:26:17 +0200 (Wed, 05 May 2010) | 1 line

  Removed some logging and prune CollectMethodBodies to not traverse
more than necessary. No review. ........ r21826 | extempore | 2010-05-06
16:57:56 +0200 (Thu, 06 May 2010) | 1 line

  Fixed bug in transpose, closes #3397, no review.
........
  r21829 | extempore | 2010-05-06 18:37:13 +0200 (Thu, 06 May 2010) | 5 lines

  Rolled partest back to r21328. Attempted to make the minimum changes
necessary to plug it back in while preserving everything which has
happened since then in tests and such, but we should be the lookout for
overreversion. Review by phaller (but as a formality, I don't think it
requires direct review.) ........

1 files changed, 157 insertions, 0 deletions

diff --git a/test/disabled/scalacheck/redblack.scala b/test/disabled/scalacheck/redblack.scala
new file mode 100644
index 0000000000..0334c1218d
--- /dev/null
+++ b/test/disabled/scalacheck/redblack.scala
@@ -0,0 +1,157 @@
+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)
+}
+