1 files changed, 337 insertions, 0 deletions
diff --git a/test/scalacheck/scala/collection/mutable/MutableTreeMap.scala b/test/scalacheck/scala/collection/mutable/MutableTreeMap.scala
new file mode 100644
index 0000000000..e3c19b8841
--- /dev/null
+++ b/test/scalacheck/scala/collection/mutable/MutableTreeMap.scala
@@ -0,0 +1,337 @@
+package scala.collection.mutable
+
+import java.io._
+
+import org.scalacheck._
+import org.scalacheck.Arbitrary._
+import org.scalacheck.Prop.forAll
+
+import scala.collection.generic.CanBuildFrom
+import scala.collection.immutable
+import scala.collection.mutable
+import scala.util.Try
+import scala.collection.mutable.{RedBlackTree => RB}
+
+trait Generators {
+
+  def genRedBlackTree[A: Arbitrary: Ordering, B: Arbitrary]: Gen[RB.Tree[A, B]] = {
+    import org.scalacheck.Gen._
+    for { entries <- listOf(arbitrary[(A, B)]) } yield {
+      val tree = RB.Tree.empty[A, B]
+      entries.foreach { case (k, v) => RB.insert(tree, k, v) }
+      tree
+    }
+  }
+
+  // Note: in scalacheck 1.12.2 tree maps can be automatically generated without the need for custom
+  // machinery
+  def genTreeMap[A: Arbitrary: Ordering, B: Arbitrary]: Gen[mutable.TreeMap[A, B]] = {
+    import org.scalacheck.Gen._
+    for {
+      keys <- listOf(arbitrary[A])
+      values <- listOfN(keys.size, arbitrary[B])
+    } yield mutable.TreeMap(keys zip values: _*)
+  }
+
+  implicit def arbRedBlackTree[A: Arbitrary: Ordering, B: Arbitrary] = Arbitrary(genRedBlackTree[A, B])
+  implicit def arbTreeMap[A: Arbitrary: Ordering, B: Arbitrary] = Arbitrary(genTreeMap[A, B])
+}
+
+object RedBlackTreeProperties extends Properties("mutable.RedBlackTree") with Generators {
+  type K = String
+  type V = Int
+
+  property("initial invariants") = forAll { (tree: RB.Tree[K, V]) =>
+    RB.isValid(tree)
+  }
+
+  property("insert") = forAll { (tree: RB.Tree[K, V], entries: Seq[(K, V)]) =>
+    entries.foreach { case (k, v) => RB.insert(tree, k, v) }
+    RB.isValid(tree) && entries.toMap.forall { case (k, v) => RB.get(tree, k) == Some(v) }
+  }
+
+  property("delete") = forAll { (tree: RB.Tree[K, V], ks: Seq[K]) =>
+    ks.foreach { k => RB.delete(tree, k) }
+    RB.isValid(tree) && ks.toSet.forall { k => RB.get(tree, k) == None }
+  }
+
+  property("insert & delete") = forAll { (tree: RB.Tree[K, V], ops: Seq[Either[(K, V), K]]) =>
+    ops.foreach {
+      case Left((k, v)) => RB.insert(tree, k, v)
+      case Right(k) => RB.delete(tree, k)
+    }
+    RB.isValid(tree)
+  }
+
+  property("min") = forAll { (entries: Seq[(K, V)]) =>
+    val tree = RB.Tree.empty[K, V]
+    entries.foreach { case (k, v) => RB.insert(tree, k, v) }
+    RB.min(tree) == (if (entries.isEmpty) None else Some(entries.toMap.min))
+  }
+
+  property("max") = forAll { (entries: Seq[(K, V)]) =>
+    val tree = RB.Tree.empty[K, V]
+    entries.foreach { case (k, v) => RB.insert(tree, k, v) }
+    RB.max(tree) == (if (entries.isEmpty) None else Some(entries.toMap.max))
+  }
+}
+
+object MutableTreeMapProperties extends Properties("mutable.TreeMap") with Generators {
+  type K = String
+  type V = Int
+
+  property("get, contains") = forAll { (allEntries: Map[K, V]) =>
+    val entries = allEntries.take(allEntries.size / 2)
+
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+
+    allEntries.forall { case (k, v) =>
+      map.contains(k) == entries.contains(k) &&
+        map.get(k) == entries.get(k)
+    }
+  }
+
+  property("size, isEmpty") = forAll { (entries: Map[K, V]) =>
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+    map.size == entries.size && map.isEmpty == entries.isEmpty
+  }
+
+  property("+=") = forAll { (map: mutable.TreeMap[K, V], k: K, v: V) =>
+    val oldSize = map.size
+    val containedKeyBefore = map.contains(k)
+    val newExpectedSize = if(containedKeyBefore) oldSize else oldSize + 1
+
+    map += (k -> v)
+    map.contains(k) && map.get(k) == Some(v) && map.size == newExpectedSize
+  }
+
+  property("++=") = forAll { (map: mutable.TreeMap[K, V], entries: Seq[(K, V)]) =>
+    val oldEntries = map.toMap
+    map ++= entries
+    (oldEntries ++ entries).forall { case (k, v) => map.get(k) == Some(v) }
+  }
+
+  property("-=") = forAll { (map: mutable.TreeMap[K, V], k: K) =>
+    val oldSize = map.size
+    val containedKeyBefore = map.contains(k)
+    val newExpectedSize = if(containedKeyBefore) oldSize - 1 else oldSize
+
+    map -= k
+    !map.contains(k) && map.get(k) == None && map.size == newExpectedSize
+  }
+
+  property("--=") = forAll { (map: mutable.TreeMap[K, V], ks: Seq[K]) =>
+    val oldElems = map.toList
+    map --= ks
+    val deletedElems = ks.toSet
+    oldElems.forall { case (k, v) => map.get(k) == (if(deletedElems(k)) None else Some(v)) }
+  }
+
+  property("iterator") = forAll { (entries: Map[K, V]) =>
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+
+    map.iterator.toSeq == entries.toSeq.sorted
+  }
+
+  property("iteratorFrom") = forAll { (entries: Map[K, V], k: K) =>
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+
+    map.iteratorFrom(k).toSeq == entries.filterKeys(_ >= k).toSeq.sorted
+  }
+
+  property("keysIteratorFrom") = forAll { (entries: Map[K, V], k: K) =>
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+
+    map.keysIteratorFrom(k).toSeq == entries.keysIterator.filter(_ >= k).toSeq.sorted
+  }
+
+  property("valuesIteratorFrom") = forAll { (entries: Map[K, V], k: K) =>
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+
+    map.valuesIteratorFrom(k).toSeq == entries.filterKeys(_ >= k).toSeq.sorted.map(_._2)
+  }
+
+  property("headOption") = forAll { (map: mutable.TreeMap[K, V]) =>
+    map.headOption == Try(map.iterator.next()).toOption
+  }
+
+  property("lastOption") = forAll { (map: mutable.TreeMap[K, V]) =>
+    map.lastOption == Try(map.iterator.max).toOption
+  }
+
+  property("clear") = forAll { (map: mutable.TreeMap[K, V]) =>
+    map.clear()
+    map.isEmpty && map.size == 0
+  }
+
+  property("serializable") = forAll { (map: mutable.TreeMap[K, V]) =>
+    val bytesOut = new ByteArrayOutputStream()
+    val out = new ObjectOutputStream(bytesOut)
+    out.writeObject(map)
+    val bytes = bytesOut.toByteArray
+
+    val in = new ObjectInputStream(new ByteArrayInputStream(bytes))
+    val sameMap = in.readObject().asInstanceOf[mutable.TreeMap[K, V]]
+    map.iterator.toSeq == sameMap.iterator.toSeq
+  }
+
+  property("same behavior as immutable.TreeMap") = forAll { ops: Seq[Either[(K, V), K]] =>
+    var imap = immutable.TreeMap[K, V]()
+    val mmap = mutable.TreeMap[K, V]()
+
+    ops.foreach {
+      case Left((k, v)) => imap += k -> v; mmap += k -> v
+      case Right(k) => imap -= k; mmap -= k
+    }
+
+    imap.toList == mmap.toList
+  }
+}
+
+object MutableTreeMapViewProperties extends Properties("mutable.TreeMapView") with Generators {
+  type K = String
+  type V = Int
+
+  implicit val ord = implicitly[Ordering[K]]
+
+  def in(key: K, from: Option[K], until: Option[K]) =
+    from.fold(true)(_ <= key) && until.fold(true)(_ > key)
+
+  def entriesInView[This <: TraversableOnce[(K, V)], That](entries: This, from: Option[K], until: Option[K])(implicit bf: CanBuildFrom[This, (K, V), That]) = {
+    (bf.apply(entries) ++= entries.filter { case (k, _) => in(k, from, until) }).result()
+  }
+
+  property("get, contains") = forAll { (allEntries: Map[K, V], from: Option[K], until: Option[K]) =>
+    val entries = allEntries.take(allEntries.size / 2)
+
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+
+    val mapView = map.rangeImpl(from, until)
+    allEntries.forall { case (k, v) =>
+      mapView.contains(k) == (in(k, from, until) && entries.contains(k)) &&
+        mapView.get(k) == (if(in(k, from, until)) entries.get(k) else None)
+    }
+  }
+
+  property("size, isEmpty") = forAll { (entries: Map[K, V], from: Option[K], until: Option[K]) =>
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+
+    val mapView = map.rangeImpl(from, until)
+    mapView.size == entriesInView(entries, from, until).size &&
+      mapView.isEmpty == !entries.exists { kv => in(kv._1, from, until) }
+  }
+
+  property("+=") = forAll { (map: mutable.TreeMap[K, V], k: K, v: V, from: Option[K], until: Option[K]) =>
+    val oldSize = map.size
+    val containedKeyBefore = map.contains(k)
+    val newExpectedSize = if(containedKeyBefore) oldSize else oldSize + 1
+    val isInRange = in(k, from, until)
+
+    val mapView = map.rangeImpl(from, until)
+    mapView += (k -> v)
+
+    map.contains(k) && map.get(k) == Some(v) && map.size == newExpectedSize &&
+      mapView.contains(k) == isInRange &&
+      mapView.get(k) == (if(isInRange) Some(v) else None)
+  }
+
+  property("++=") = forAll { (map: mutable.TreeMap[K, V], entries: Seq[(K, V)], from: Option[K], until: Option[K]) =>
+    val mapView = map.rangeImpl(from, until)
+    mapView ++= entries
+    entries.toMap.forall { case (k, v) =>
+      map.get(k) == Some(v) &&
+        mapView.get(k) == (if (in(k, from, until)) Some(v) else None)
+    }
+  }
+
+  property("-=") = forAll { (map: mutable.TreeMap[K, V], k: K, from: Option[K], until: Option[K]) =>
+    val oldSize = map.size
+    val containedKeyBefore = map.contains(k)
+    val newExpectedSize = if(containedKeyBefore) oldSize - 1 else oldSize
+
+    val mapView = map.rangeImpl(from, until)
+    mapView -= k
+
+    !map.contains(k) && map.get(k) == None && map.size == newExpectedSize &&
+      !mapView.contains(k) &&
+      mapView.get(k) == None
+  }
+
+  property("--=") = forAll { (map: mutable.TreeMap[K, V], ks: Seq[K], from: Option[K], until: Option[K]) =>
+    val mapView = map.rangeImpl(from, until)
+    mapView --= ks
+    ks.toSet.forall { k => map.get(k) == None && mapView.get(k) == None }
+  }
+
+  property("iterator") = forAll { (entries: Map[K, V], from: Option[K], until: Option[K]) =>
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+
+    val mapView = map.rangeImpl(from, until)
+    mapView.iterator.toSeq == entriesInView(entries, from, until).toSeq.sorted
+  }
+
+  property("iteratorFrom") = forAll { (entries: Map[K, V], k: K, from: Option[K], until: Option[K]) =>
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+
+    val mapView = map.rangeImpl(from, until)
+    val newLower = Some(from.fold(k)(ord.max(_, k)))
+    mapView.iteratorFrom(k).toSeq == entriesInView(entries, newLower, until).toSeq.sorted
+  }
+
+  property("keysIteratorFrom") = forAll { (entries: Map[K, V], k: K, from: Option[K], until: Option[K]) =>
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+
+    val mapView = map.rangeImpl(from, until)
+    val newLower = Some(from.fold(k)(ord.max(_, k)))
+    mapView.keysIteratorFrom(k).toSeq == entriesInView(entries, newLower, until).toSeq.sorted.map(_._1)
+  }
+
+  property("valuesIteratorFrom") = forAll { (entries: Map[K, V], k: K, from: Option[K], until: Option[K]) =>
+    val map = mutable.TreeMap[K, V]()
+    map ++= entries
+
+    val mapView = map.rangeImpl(from, until)
+    val newLower = Some(from.fold(k)(ord.max(_, k)))
+    mapView.valuesIteratorFrom(k).toSeq == entriesInView(entries, newLower, until).toSeq.sorted.map(_._2)
+  }
+
+  property("headOption") = forAll { (map: mutable.TreeMap[K, V], from: Option[K], until: Option[K]) =>
+    val mapView = map.rangeImpl(from, until)
+    mapView.headOption == Try(entriesInView(map.iterator, from, until).next()).toOption
+  }
+
+  property("lastOption") = forAll { (map: mutable.TreeMap[K, V], from: Option[K], until: Option[K]) =>
+    val mapView = map.rangeImpl(from, until)
+    mapView.lastOption == Try(entriesInView(map.iterator, from, until).max).toOption
+  }
+
+  property("clear") = forAll { (map: mutable.TreeMap[K, V], from: Option[K], until: Option[K]) =>
+    val mapView = map.rangeImpl(from, until)
+    mapView.clear()
+    map.isEmpty && mapView.isEmpty && map.size == 0 && mapView.size == 0
+  }
+
+  property("serializable") = forAll { (map: mutable.TreeMap[K, V], from: Option[K], until: Option[K]) =>
+    val mapView = map.rangeImpl(from, until)
+
+    val bytesOut = new ByteArrayOutputStream()
+    val out = new ObjectOutputStream(bytesOut)
+    out.writeObject(mapView)
+    val bytes = bytesOut.toByteArray
+
+    val in = new ObjectInputStream(new ByteArrayInputStream(bytes))
+    val sameMapView = in.readObject().asInstanceOf[mutable.TreeMap[K, V]]
+    mapView.iterator.toSeq == sameMapView.iterator.toSeq
+  }
+}