SI-4147 Add an implementation of `mutable.TreeMap`

This commit contains an implementation of a mutable red-black tree with focus on performance. It also contains a new `mutable.TreeMap` Scala collection that is backed by the aforementioned tree. The common generic factories and traits related to mutable sorted maps didn't exist yet, so this commit also adds them.

Regarding performance, `TreeMap` overrides (from `MapLike` and `SortedMapLike`) all of the most common methods for maps and also those whose default implementations are asymptotically worse than direct red-black tree algorithms (e.g. `last`, `clear`).

The `rangeImpl` method of `TreeMap` returns an instance of `TreeMapView`, an inner class of `TreeMap`. This view is backed by the same `RedBlackTree.Tree` instance, and therefore changes to the original map are reflected in the view and vice-versa. The semantics of mutating a view by adding and removing keys outside the view's range are the same of the current `mutable.TreeSet`. A bit less focus was given on the performance of views - in particular, getting the `size` of a `TreeMapView` is O(n) on the number of elements inside the view bounds. That can be improved in the future.

In a future commit, `mutable.TreeSet` can be changed to be backed by this red-black tree implementation.

3 files changed, 337 insertions, 3 deletions

diff --git a/test/files/run/t8549.scala b/test/files/run/t8549.scala
index cb254e3810..da1a9d58c1 100644
--- a/test/files/run/t8549.scala
+++ b/test/files/run/t8549.scala
@@ -79,7 +79,7 @@ object Test extends App {
     }
   }
 
-  // Generated on 20141010-14:01:28 with Scala version 2.11.2)
+  // Generated on 20150519-10:11:14 with Scala version 2.12.0-20150517-213212-4c1ce60ef9)
   overwrite.foreach(updateComment)
 
   check(Some(1))("rO0ABXNyAApzY2FsYS5Tb21lESLyaV6hi3QCAAFMAAF4dAASTGphdmEvbGFuZy9PYmplY3Q7eHIADHNjYWxhLk9wdGlvbv5pN/3bDmZ0AgAAeHBzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAQ==")
@@ -163,6 +163,9 @@ object Test extends App {
   check(mutable.HashMap())( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuSGFzaE1hcAAAAAAAAAABAwAAeHB3DQAAAu4AAAAAAAAABAB4")
   check(mutable.HashMap(1 -> 1))( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuSGFzaE1hcAAAAAAAAAABAwAAeHB3DQAAAu4AAAABAAAABABzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAXEAfgAEeA==")
   check(mutable.HashSet(1, 2, 3))( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuSGFzaFNldAAAAAAAAAABAwAAeHB3DQAAAcIAAAADAAAABQBzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAXNxAH4AAgAAAAJzcQB+AAIAAAADeA==")
+  check(mutable.TreeMap())( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZU1hcNx8qC229ZvwAgACTAAIb3JkZXJpbmd0ABVMc2NhbGEvbWF0aC9PcmRlcmluZztMACZzY2FsYSRjb2xsZWN0aW9uJG11dGFibGUkVHJlZU1hcCQkdHJlZXQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJFRyZWU7eHBzcgAYc2NhbGEubWF0aC5PcmRlcmluZyRJbnQkC4BMdr1Z51wCAAB4cHNyACpzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuUmVkQmxhY2tUcmVlJFRyZWUATKc08DWmFQIAAkkABHNpemVMAARyb290dAAsTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9SZWRCbGFja1RyZWUkTm9kZTt4cAAAAABw")
+  check(mutable.TreeMap(1 -> 1, 3 -> 6))( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZU1hcNx8qC229ZvwAgACTAAIb3JkZXJpbmd0ABVMc2NhbGEvbWF0aC9PcmRlcmluZztMACZzY2FsYSRjb2xsZWN0aW9uJG11dGFibGUkVHJlZU1hcCQkdHJlZXQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJFRyZWU7eHBzcgAYc2NhbGEubWF0aC5PcmRlcmluZyRJbnQkC4BMdr1Z51wCAAB4cHNyACpzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuUmVkQmxhY2tUcmVlJFRyZWUATKc08DWmFQIAAkkABHNpemVMAARyb290dAAsTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9SZWRCbGFja1RyZWUkTm9kZTt4cAAAAAJzcgAqc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlJlZEJsYWNrVHJlZSROb2RlGxHsFtValgACAAZaAANyZWRMAANrZXl0ABJMamF2YS9sYW5nL09iamVjdDtMAARsZWZ0cQB+AAdMAAZwYXJlbnRxAH4AB0wABXJpZ2h0cQB+AAdMAAV2YWx1ZXEAfgAKeHAAc3IAEWphdmEubGFuZy5JbnRlZ2VyEuKgpPeBhzgCAAFJAAV2YWx1ZXhyABBqYXZhLmxhbmcuTnVtYmVyhqyVHQuU4IsCAAB4cAAAAAFwcHNxAH4ACQFzcQB+AAwAAAADcHEAfgALcHNxAH4ADAAAAAZxAH4ADg==")
+  check(mutable.TreeMap(1 -> 1, 3 -> 6).range(1, 2))( "rO0ABXNyACxzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZU1hcCRUcmVlTWFwVmlldx7MCZxLhVQ8AgADTAAGJG91dGVydAAiTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9UcmVlTWFwO0wABGZyb210AA5Mc2NhbGEvT3B0aW9uO0wABXVudGlscQB+AAJ4cgAgc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlRyZWVNYXDcfKgttvWb8AIAAkwACG9yZGVyaW5ndAAVTHNjYWxhL21hdGgvT3JkZXJpbmc7TAAmc2NhbGEkY29sbGVjdGlvbiRtdXRhYmxlJFRyZWVNYXAkJHRyZWV0ACxMc2NhbGEvY29sbGVjdGlvbi9tdXRhYmxlL1JlZEJsYWNrVHJlZSRUcmVlO3hwc3IAGHNjYWxhLm1hdGguT3JkZXJpbmckSW50JAuATHa9WedcAgAAeHBzcgAqc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlJlZEJsYWNrVHJlZSRUcmVlAEynNPA1phUCAAJJAARzaXplTAAEcm9vdHQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJE5vZGU7eHAAAAACc3IAKnNjYWxhLmNvbGxlY3Rpb24ubXV0YWJsZS5SZWRCbGFja1RyZWUkTm9kZRsR7BbVWpYAAgAGWgADcmVkTAADa2V5dAASTGphdmEvbGFuZy9PYmplY3Q7TAAEbGVmdHEAfgAKTAAGcGFyZW50cQB+AApMAAVyaWdodHEAfgAKTAAFdmFsdWVxAH4ADXhwAHNyABFqYXZhLmxhbmcuSW50ZWdlchLioKT3gYc4AgABSQAFdmFsdWV4cgAQamF2YS5sYW5nLk51bWJlcoaslR0LlOCLAgAAeHAAAAABcHBzcQB+AAwBc3EAfgAPAAAAA3BxAH4ADnBzcQB+AA8AAAAGcQB+ABFzcQB+AANxAH4ACHEAfgALc3IACnNjYWxhLlNvbWURIvJpXqGLdAIAAUwAAXhxAH4ADXhyAAxzY2FsYS5PcHRpb27+aTf92w5mdAIAAHhwcQB+ABFzcQB+ABZzcQB+AA8AAAAC")
   // TODO SI-8576 Uninitialized field under -Xcheckinit
   // check(new mutable.History())( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuSGlzdG9yeUhuXxDIFJrsAgACSQAKbWF4SGlzdG9yeUwAA2xvZ3QAIExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUXVldWU7eHAAAAPoc3IAHnNjYWxhLmNvbGxlY3Rpb24ubXV0YWJsZS5RdWV1ZbjMURVfOuHHAgAAeHIAJHNjYWxhLmNvbGxlY3Rpb24ubXV0YWJsZS5NdXRhYmxlTGlzdFJpnjJ+gFbAAgADSQADbGVuTAAGZmlyc3QwdAAlTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9MaW5rZWRMaXN0O0wABWxhc3QwcQB+AAV4cAAAAABzcgAjc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLkxpbmtlZExpc3Sak+nGCZHaUQIAAkwABGVsZW10ABJMamF2YS9sYW5nL09iamVjdDtMAARuZXh0dAAeTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9TZXE7eHBwcQB+AApxAH4ACg==")
   check(mutable.LinkedHashMap(1 -> 2))( "rO0ABXNyACZzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuTGlua2VkSGFzaE1hcAAAAAAAAAABAwAAeHB3DQAAAu4AAAABAAAABABzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAXNxAH4AAgAAAAJ4")
diff --git a/test/files/scalacheck/MutableTreeMap.scala b/test/files/scalacheck/MutableTreeMap.scala
new file mode 100644
index 0000000000..ac073b1c42
--- /dev/null
+++ b/test/files/scalacheck/MutableTreeMap.scala
@@ -0,0 +1,329 @@
+import java.io._
+
+import org.scalacheck._
+import org.scalacheck.Arbitrary._
+import org.scalacheck.Prop.forAll
+
+import scala.collection.generic.CanBuildFrom
+import scala.collection.mutable
+import scala.util.Try
+import scala.collection.mutable.{RedBlackTree => RB}
+
+package scala.collection.mutable {
+
+  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)]) =>
+      map ++= entries
+      entries.toMap.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]) =>
+      map --= ks
+      ks.toSet.forall { k => map.get(k) == None }
+    }
+
+    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
+    }
+
+    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
+    }
+  }
+
+  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
+    }
+
+    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
+    }
+  }
+}
+
+object Test extends Properties("mutable.TreeMap") {
+  import scala.collection.mutable._
+  include(RedBlackTreeProperties)
+  include(MutableTreeMapProperties)
+  include(MutableTreeMapViewProperties)
+}
diff --git a/test/junit/scala/collection/SetMapConsistencyTest.scala b/test/junit/scala/collection/SetMapConsistencyTest.scala
index 0749e61c09..5f14af7c37 100644
--- a/test/junit/scala/collection/SetMapConsistencyTest.scala
+++ b/test/junit/scala/collection/SetMapConsistencyTest.scala
@@ -66,6 +66,8 @@ class SetMapConsistencyTest {
   def boxMhm[A] = new BoxMutableMap[A, cm.HashMap[A, Int]](new cm.HashMap[A, Int], "mutable.HashMap")
   
   def boxMohm[A] = new BoxMutableMap[A, cm.OpenHashMap[A, Int]](new cm.OpenHashMap[A, Int], "mutable.OpenHashMap")
+
+  def boxMtm[A: Ordering] = new BoxMutableMap[A, cm.TreeMap[A, Int]](new cm.TreeMap[A, Int], "mutable.TreeMap")
   
   def boxMarm[A <: AnyRef] = new BoxMutableMap[A, cm.AnyRefMap[A, Int]](new cm.AnyRefMap[A, Int](_ => -1), "mutable.AnyRefMap") {
     private def arm: cm.AnyRefMap[A, Int] = m.asInstanceOf[cm.AnyRefMap[A, Int]]
@@ -315,7 +317,7 @@ class SetMapConsistencyTest {
   @Test
   def churnIntMaps() {
     val maps = Array[() => MapBox[Int]](
-      () => boxMlm[Int], () => boxMhm[Int], () => boxMohm[Int], () => boxJavaM[Int],
+      () => boxMlm[Int], () => boxMhm[Int], () => boxMohm[Int], () => boxMtm[Int], () => boxJavaM[Int],
       () => boxIim, () => boxIhm[Int], () => boxIlm[Int], () => boxItm[Int]
     )
     assert( maps.sliding(2).forall{ ms => churn(ms(0)(), ms(1)(), intKeys, 2000) } )
@@ -325,7 +327,7 @@ class SetMapConsistencyTest {
   def churnLongMaps() {
     val maps = Array[() => MapBox[Long]](
       () => boxMjm, () => boxIjm, () => boxJavaM[Long],
-      () => boxMlm[Long], () => boxMhm[Long], () => boxMohm[Long], () => boxIhm[Long], () => boxIlm[Long]
+      () => boxMlm[Long], () => boxMhm[Long], () => boxMtm[Long], () => boxMohm[Long], () => boxIhm[Long], () => boxIlm[Long]
     )
     assert( maps.sliding(2).forall{ ms => churn(ms(0)(), ms(1)(), longKeys, 10000) } )
   }