Merge remote-tracking branch 'erikrozendaal/SI-5331' into develop

4 files changed, 554 insertions, 32 deletions

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
+  }
+}