Merge pull request #4504 from ruippeixotog/mutable-treemap

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

7 files changed, 1129 insertions, 3 deletions

diff --git a/src/library/scala/collection/generic/MutableSortedMapFactory.scala b/src/library/scala/collection/generic/MutableSortedMapFactory.scala
new file mode 100644
index 0000000000..b6fa933ca8
--- /dev/null
+++ b/src/library/scala/collection/generic/MutableSortedMapFactory.scala
@@ -0,0 +1,24 @@
+package scala
+package collection
+package generic
+
+import scala.language.higherKinds
+
+/**
+ * A template for companion objects of `SortedMap` and subclasses thereof.
+ *
+ * @tparam CC the type of the collection.
+ *
+ * @author Rui Gonçalves
+ * @since 2.12
+ * @version 2.12
+ *
+ * @define Coll `mutable.SortedMap`
+ * @define coll mutable sorted map
+ * @define factoryInfo
+ *         This object provides a set of operations needed to create sorted maps of type `$Coll`.
+ * @define sortedMapCanBuildFromInfo
+ *         The standard `CanBuildFrom` instance for sorted maps
+ */
+abstract class MutableSortedMapFactory[CC[A, B] <: mutable.SortedMap[A, B] with SortedMapLike[A, B, CC[A, B]]]
+  extends SortedMapFactory[CC]
diff --git a/src/library/scala/collection/mutable/RedBlackTree.scala b/src/library/scala/collection/mutable/RedBlackTree.scala
new file mode 100644
index 0000000000..7f12264d45
--- /dev/null
+++ b/src/library/scala/collection/mutable/RedBlackTree.scala
@@ -0,0 +1,545 @@
+package scala.collection.mutable
+
+import scala.annotation.tailrec
+import scala.collection.Iterator
+
+/**
+ * An object containing the red-black tree implementation used by mutable `TreeMaps`.
+ *
+ * The trees implemented in this object are *not* thread safe.
+ *
+ * @author Rui Gonçalves
+ * @version 2.12
+ * @since 2.12
+ */
+private[collection] object RedBlackTree {
+
+  // ---- class structure ----
+
+  // For performance reasons, this implementation uses `null` references to represent leaves instead of a sentinel node.
+  // Currently, the internal nodes do not store their subtree size - only the tree object keeps track of their size.
+  // Therefore, while obtaining the size of the whole tree is O(1), knowing the number of entries inside a range is O(n)
+  // on the size of the range.
+
+  @SerialVersionUID(21575944040195605L)
+  final class Tree[A, B](var root: Node[A, B], var size: Int) extends Serializable
+
+  @SerialVersionUID(1950599696441054720L)
+  final class Node[A, B](var key: A, var value: B, var red: Boolean,
+                         var left: Node[A, B], var right: Node[A, B], var parent: Node[A, B]) extends Serializable {
+
+    override def toString: String = "Node(" + key + ", " + value + ", " + red + ", " + left + ", " + right + ")"
+  }
+
+  object Tree {
+    def empty[A, B]: Tree[A, B] = new Tree(null, 0)
+  }
+
+  object Node {
+
+    @inline def apply[A, B](key: A, value: B, red: Boolean,
+                            left: Node[A, B], right: Node[A, B], parent: Node[A, B]): Node[A, B] =
+      new Node(key, value, red, left, right, parent)
+
+    @inline def leaf[A, B](key: A, value: B, red: Boolean, parent: Node[A, B]): Node[A, B] =
+      new Node(key, value, red, null, null, parent)
+
+    def unapply[A, B](t: Node[A, B]) = Some((t.key, t.value, t.left, t.right, t.parent))
+  }
+
+  // ---- getters ----
+
+  def isRed(node: Node[_, _]) = (node ne null) && node.red
+  def isBlack(node: Node[_, _]) = (node eq null) || !node.red
+
+  // ---- size ----
+
+  def size(node: Node[_, _]): Int = if (node eq null) 0 else 1 + size(node.left) + size(node.right)
+  def isEmpty(tree: Tree[_, _]) = tree.root eq null
+
+  // ---- search ----
+
+  def get[A: Ordering, B](tree: Tree[A, B], key: A): Option[B] = getNode(tree.root, key) match {
+    case null => None
+    case node => Some(node.value)
+  }
+
+  @tailrec private[this] def getNode[A, B](node: Node[A, B], key: A)(implicit ord: Ordering[A]): Node[A, B] =
+    if (node eq null) null
+    else {
+      val cmp = ord.compare(key, node.key)
+      if (cmp < 0) getNode(node.left, key)
+      else if (cmp > 0) getNode(node.right, key)
+      else node
+    }
+
+  def contains[A: Ordering](tree: Tree[A, _], key: A) = getNode(tree.root, key) ne null
+
+  def min[A, B](tree: Tree[A, B]): Option[(A, B)] = minNode(tree.root) match {
+    case null => None
+    case node => Some((node.key, node.value))
+  }
+
+  private def minNode[A, B](node: Node[A, B]): Node[A, B] =
+    if (node eq null) null else minNodeNonNull(node)
+
+  @tailrec def minNodeNonNull[A, B](node: Node[A, B]): Node[A, B] =
+    if (node.left eq null) node else minNodeNonNull(node.left)
+
+  def max[A, B](tree: Tree[A, B]): Option[(A, B)] = maxNode(tree.root) match {
+    case null => None
+    case node => Some((node.key, node.value))
+  }
+
+  private def maxNode[A, B](node: Node[A, B]): Node[A, B] =
+    if (node eq null) null else maxNodeNonNull(node)
+
+  @tailrec def maxNodeNonNull[A, B](node: Node[A, B]): Node[A, B] =
+    if (node.right eq null) node else maxNodeNonNull(node.right)
+
+  /**
+   * Returns the first (lowest) map entry with a key equal or greater than `key`. Returns `None` if there is no such
+   * node.
+   */
+  def minAfter[A, B](tree: Tree[A, B], key: A)(implicit ord: Ordering[A]): Option[(A, B)] =
+    minNodeAfter(tree.root, key) match {
+      case null => None
+      case node => Some((node.key, node.value))
+    }
+
+  private[this] def minNodeAfter[A, B](node: Node[A, B], key: A)(implicit ord: Ordering[A]): Node[A, B] = {
+    if (node eq null) null
+    else {
+      var y: Node[A, B] = null
+      var x = node
+      var cmp = 1
+      while ((x ne null) && cmp != 0) {
+        y = x
+        cmp = ord.compare(key, x.key)
+        x = if (cmp < 0) x.left else x.right
+      }
+      if (cmp <= 0) y else successor(y)
+    }
+  }
+
+  /**
+   * Returns the last (highest) map entry with a key smaller than `key`. Returns `None` if there is no such node.
+   */
+  def maxBefore[A, B](tree: Tree[A, B], key: A)(implicit ord: Ordering[A]): Option[(A, B)] =
+    maxNodeBefore(tree.root, key) match {
+      case null => None
+      case node => Some((node.key, node.value))
+    }
+
+  private[this] def maxNodeBefore[A, B](node: Node[A, B], key: A)(implicit ord: Ordering[A]): Node[A, B] = {
+    if (node eq null) null
+    else {
+      var y: Node[A, B] = null
+      var x = node
+      var cmp = 1
+      while ((x ne null) && cmp != 0) {
+        y = x
+        cmp = ord.compare(key, x.key)
+        x = if (cmp < 0) x.left else x.right
+      }
+      if (cmp > 0) y else predecessor(y)
+    }
+  }
+
+  // ---- insertion ----
+
+  def insert[A, B](tree: Tree[A, B], key: A, value: B)(implicit ord: Ordering[A]): Unit = {
+    var y: Node[A, B] = null
+    var x = tree.root
+    var cmp = 1
+    while ((x ne null) && cmp != 0) {
+      y = x
+      cmp = ord.compare(key, x.key)
+      x = if (cmp < 0) x.left else x.right
+    }
+
+    if (cmp == 0) y.value = value
+    else {
+      val z = Node.leaf(key, value, red = true, y)
+
+      if (y eq null) tree.root = z
+      else if (cmp < 0) y.left = z
+      else y.right = z
+
+      fixAfterInsert(tree, z)
+      tree.size += 1
+    }
+  }
+
+  private[this] def fixAfterInsert[A, B](tree: Tree[A, B], node: Node[A, B]): Unit = {
+    var z = node
+    while (isRed(z.parent)) {
+      if (z.parent eq z.parent.parent.left) {
+        val y = z.parent.parent.right
+        if (isRed(y)) {
+          z.parent.red = false
+          y.red = false
+          z.parent.parent.red = true
+          z = z.parent.parent
+        } else {
+          if (z eq z.parent.right) {
+            z = z.parent
+            rotateLeft(tree, z)
+          }
+          z.parent.red = false
+          z.parent.parent.red = true
+          rotateRight(tree, z.parent.parent)
+        }
+      } else { // symmetric cases
+        val y = z.parent.parent.left
+        if (isRed(y)) {
+          z.parent.red = false
+          y.red = false
+          z.parent.parent.red = true
+          z = z.parent.parent
+        } else {
+          if (z eq z.parent.left) {
+            z = z.parent
+            rotateRight(tree, z)
+          }
+          z.parent.red = false
+          z.parent.parent.red = true
+          rotateLeft(tree, z.parent.parent)
+        }
+      }
+    }
+    tree.root.red = false
+  }
+
+  // ---- deletion ----
+
+  def delete[A, B](tree: Tree[A, B], key: A)(implicit ord: Ordering[A]): Unit = {
+    val z = getNode(tree.root, key)
+    if (z ne null) {
+      var y = z
+      var yIsRed = y.red
+      var x: Node[A, B] = null
+      var xParent: Node[A, B] = null
+
+      if (z.left eq null) {
+        x = z.right
+        transplant(tree, z, z.right)
+        xParent = z.parent
+      }
+      else if (z.right eq null) {
+        x = z.left
+        transplant(tree, z, z.left)
+        xParent = z.parent
+      }
+      else {
+        y = minNodeNonNull(z.right)
+        yIsRed = y.red
+        x = y.right
+
+        if (y.parent eq z) xParent = y
+        else {
+          xParent = y.parent
+          transplant(tree, y, y.right)
+          y.right = z.right
+          y.right.parent = y
+        }
+        transplant(tree, z, y)
+        y.left = z.left
+        y.left.parent = y
+        y.red = z.red
+      }
+
+      if (!yIsRed) fixAfterDelete(tree, x, xParent)
+      tree.size -= 1
+    }
+  }
+
+  private[this] def fixAfterDelete[A, B](tree: Tree[A, B], node: Node[A, B], parent: Node[A, B]): Unit = {
+    var x = node
+    var xParent = parent
+    while ((x ne tree.root) && isBlack(x)) {
+      if (x eq xParent.left) {
+        var w = xParent.right
+        // assert(w ne null)
+
+        if (w.red) {
+          w.red = false
+          xParent.red = true
+          rotateLeft(tree, xParent)
+          w = xParent.right
+        }
+        if (isBlack(w.left) && isBlack(w.right)) {
+          w.red = true
+          x = xParent
+        } else {
+          if (isBlack(w.right)) {
+            w.left.red = false
+            w.red = true
+            rotateRight(tree, w)
+            w = xParent.right
+          }
+          w.red = xParent.red
+          xParent.red = false
+          w.right.red = false
+          rotateLeft(tree, xParent)
+          x = tree.root
+        }
+      } else { // symmetric cases
+        var w = xParent.left
+        // assert(w ne null)
+
+        if (w.red) {
+          w.red = false
+          xParent.red = true
+          rotateRight(tree, xParent)
+          w = xParent.left
+        }
+        if (isBlack(w.right) && isBlack(w.left)) {
+          w.red = true
+          x = xParent
+        } else {
+          if (isBlack(w.left)) {
+            w.right.red = false
+            w.red = true
+            rotateLeft(tree, w)
+            w = xParent.left
+          }
+          w.red = xParent.red
+          xParent.red = false
+          w.left.red = false
+          rotateRight(tree, xParent)
+          x = tree.root
+        }
+      }
+      xParent = x.parent
+    }
+    if (x ne null) x.red = false
+  }
+
+  // ---- helpers ----
+
+  /**
+   * Returns the node that follows `node` in an in-order tree traversal. If `node` has the maximum key (and is,
+   * therefore, the last node), this method returns `null`.
+   */
+  private[this] def successor[A, B](node: Node[A, B]): Node[A, B] = {
+    if (node.right ne null) minNodeNonNull(node.right)
+    else {
+      var x = node
+      var y = x.parent
+      while ((y ne null) && (x eq y.right)) {
+        x = y
+        y = y.parent
+      }
+      y
+    }
+  }
+
+  /**
+   * Returns the node that precedes `node` in an in-order tree traversal. If `node` has the minimum key (and is,
+   * therefore, the first node), this method returns `null`.
+   */
+  private[this] def predecessor[A, B](node: Node[A, B]): Node[A, B] = {
+    if (node.left ne null) maxNodeNonNull(node.left)
+    else {
+      var x = node
+      var y = x.parent
+      while ((y ne null) && (x eq y.left)) {
+        x = y
+        y = y.parent
+      }
+      y
+    }
+  }
+
+  private[this] def rotateLeft[A, B](tree: Tree[A, B], x: Node[A, B]): Unit = if (x ne null) {
+    // assert(x.right ne null)
+    val y = x.right
+    x.right = y.left
+
+    if (y.left ne null) y.left.parent = x
+    y.parent = x.parent
+
+    if (x.parent eq null) tree.root = y
+    else if (x eq x.parent.left) x.parent.left = y
+    else x.parent.right = y
+
+    y.left = x
+    x.parent = y
+  }
+
+  private[this] def rotateRight[A, B](tree: Tree[A, B], x: Node[A, B]): Unit = if (x ne null) {
+    // assert(x.left ne null)
+    val y = x.left
+    x.left = y.right
+
+    if (y.right ne null) y.right.parent = x
+    y.parent = x.parent
+
+    if (x.parent eq null) tree.root = y
+    else if (x eq x.parent.right) x.parent.right = y
+    else x.parent.left = y
+
+    y.right = x
+    x.parent = y
+  }
+
+  /**
+   * Transplant the node `from` to the place of node `to`. This is done by setting `from` as a child of `to`'s previous
+   * parent and setting `from`'s parent to the `to`'s previous parent. The children of `from` are left unchanged.
+   */
+  private[this] def transplant[A, B](tree: Tree[A, B], to: Node[A, B], from: Node[A, B]): Unit = {
+    if (to.parent eq null) tree.root = from
+    else if (to eq to.parent.left) to.parent.left = from
+    else to.parent.right = from
+
+    if (from ne null) from.parent = to.parent
+  }
+
+  // ---- tree traversal ----
+
+  def foreach[A, B, U](tree: Tree[A, B], f: ((A, B)) => U): Unit = foreachNode(tree.root, f)
+
+  private[this] def foreachNode[A, B, U](node: Node[A, B], f: ((A, B)) => U): Unit =
+    if (node ne null) foreachNodeNonNull(node, f)
+
+  private[this] def foreachNodeNonNull[A, B, U](node: Node[A, B], f: ((A, B)) => U): Unit = {
+    if (node.left ne null) foreachNodeNonNull(node.left, f)
+    f((node.key, node.value))
+    if (node.right ne null) foreachNodeNonNull(node.right, f)
+  }
+
+  def transform[A, B](tree: Tree[A, B], f: (A, B) => B): Unit = transformNode(tree.root, f)
+
+  private[this] def transformNode[A, B, U](node: Node[A, B], f: (A, B) => B): Unit =
+    if (node ne null) transformNodeNonNull(node, f)
+
+  private[this] def transformNodeNonNull[A, B, U](node: Node[A, B], f: (A, B) => B): Unit = {
+    if (node.left ne null) transformNodeNonNull(node.left, f)
+    node.value = f(node.key, node.value)
+    if (node.right ne null) transformNodeNonNull(node.right, f)
+  }
+
+  def iterator[A: Ordering, B](tree: Tree[A, B], start: Option[A] = None, end: Option[A] = None): Iterator[(A, B)] =
+    new EntriesIterator(tree, start, end)
+
+  def keysIterator[A: Ordering](tree: Tree[A, _], start: Option[A] = None, end: Option[A] = None): Iterator[A] =
+    new KeysIterator(tree, start, end)
+
+  def valuesIterator[A: Ordering, B](tree: Tree[A, B], start: Option[A] = None, end: Option[A] = None): Iterator[B] =
+    new ValuesIterator(tree, start, end)
+
+  private[this] abstract class TreeIterator[A, B, R](tree: Tree[A, B], start: Option[A], end: Option[A])
+                                                    (implicit ord: Ordering[A]) extends Iterator[R] {
+
+    protected[this] def nextResult(node: Node[A, B]): R
+
+    def hasNext: Boolean = nextNode ne null
+
+    def next(): R = nextNode match {
+      case null => throw new NoSuchElementException("next on empty iterator")
+      case node =>
+        nextNode = successor(node)
+        setNullIfAfterEnd()
+        nextResult(node)
+    }
+
+    private[this] var nextNode: Node[A, B] = start match {
+      case None => minNode(tree.root)
+      case Some(from) => minNodeAfter(tree.root, from)
+    }
+
+    private[this] def setNullIfAfterEnd(): Unit =
+      if (end.isDefined && (nextNode ne null) && ord.compare(nextNode.key, end.get) >= 0)
+        nextNode = null
+
+    setNullIfAfterEnd()
+  }
+
+  private[this] final class EntriesIterator[A: Ordering, B](tree: Tree[A, B], start: Option[A], end: Option[A])
+    extends TreeIterator[A, B, (A, B)](tree, start, end) {
+
+    def nextResult(node: Node[A, B]) = (node.key, node.value)
+  }
+
+  private[this] final class KeysIterator[A: Ordering, B](tree: Tree[A, B], start: Option[A], end: Option[A])
+    extends TreeIterator[A, B, A](tree, start, end) {
+
+    def nextResult(node: Node[A, B]) = node.key
+  }
+
+  private[this] final class ValuesIterator[A: Ordering, B](tree: Tree[A, B], start: Option[A], end: Option[A])
+    extends TreeIterator[A, B, B](tree, start, end) {
+
+    def nextResult(node: Node[A, B]) = node.value
+  }
+
+  // ---- debugging ----
+
+  /**
+   * Checks if the tree is in a valid state. That happens if:
+   * - It is a valid binary search tree;
+   * - All red-black properties are satisfied;
+   * - All non-null nodes have their `parent` reference correct;
+   * - The size variable in `tree` corresponds to the actual size of the tree.
+   */
+  def isValid[A: Ordering, B](tree: Tree[A, B]): Boolean =
+    isValidBST(tree.root) && hasProperParentRefs(tree) && isValidRedBlackTree(tree) && size(tree.root) == tree.size
+
+  /**
+   * Returns true if all non-null nodes have their `parent` reference correct.
+   */
+  private[this] def hasProperParentRefs[A, B](tree: Tree[A, B]): Boolean = {
+
+    def hasProperParentRefs(node: Node[A, B]): Boolean = {
+      if (node eq null) true
+      else {
+        if ((node.left ne null) && (node.left.parent ne node) ||
+          (node.right ne null) && (node.right.parent ne node)) false
+        else hasProperParentRefs(node.left) && hasProperParentRefs(node.right)
+      }
+    }
+
+    if(tree.root eq null) true
+    else (tree.root.parent eq null) && hasProperParentRefs(tree.root)
+  }
+
+  /**
+   * Returns true if this node follows the properties of a binary search tree.
+   */
+  private[this] def isValidBST[A, B](node: Node[A, B])(implicit ord: Ordering[A]): Boolean = {
+    if (node eq null) true
+    else {
+      if ((node.left ne null) && (ord.compare(node.key, node.left.key) <= 0) ||
+        (node.right ne null) && (ord.compare(node.key, node.right.key) >= 0)) false
+      else isValidBST(node.left) && isValidBST(node.right)
+    }
+  }
+
+  /**
+   * Returns true if the tree has all the red-black tree properties: if the root node is black, if all children of red
+   * nodes are black and if the path from any node to any of its null children has the same number of black nodes.
+   */
+  private[this] def isValidRedBlackTree[A, B](tree: Tree[A, B]): Boolean = {
+
+    def noRedAfterRed(node: Node[A, B]): Boolean = {
+      if (node eq null) true
+      else if (node.red && (isRed(node.left) || isRed(node.right))) false
+      else noRedAfterRed(node.left) && noRedAfterRed(node.right)
+    }
+
+    def blackHeight(node: Node[A, B]): Int = {
+      if (node eq null) 1
+      else {
+        val lh = blackHeight(node.left)
+        val rh = blackHeight(node.right)
+
+        if (lh == -1 || lh != rh) -1
+        else if (isRed(node)) lh
+        else lh + 1
+      }
+    }
+
+    isBlack(tree.root) && noRedAfterRed(tree.root) && blackHeight(tree.root) >= 0
+  }
+}
diff --git a/src/library/scala/collection/mutable/SortedMap.scala b/src/library/scala/collection/mutable/SortedMap.scala
new file mode 100644
index 0000000000..806b30e79a
--- /dev/null
+++ b/src/library/scala/collection/mutable/SortedMap.scala
@@ -0,0 +1,57 @@
+package scala
+package collection
+package mutable
+
+import generic._
+
+/**
+ * A mutable map whose keys are sorted.
+ *
+ * @tparam A the type of the keys contained in this sorted map.
+ * @tparam B the type of the values associated with the keys.
+ *
+ * @author Rui Gonçalves
+ * @version 2.12
+ * @since 2.12
+ *
+ * @define Coll mutable.SortedMap
+ * @define coll mutable sorted map
+ */
+trait SortedMap[A, B]
+  extends Map[A, B]
+  with collection.SortedMap[A, B]
+  with MapLike[A, B, SortedMap[A, B]]
+  with SortedMapLike[A, B, SortedMap[A, B]] {
+
+  override protected[this] def newBuilder: Builder[(A, B), SortedMap[A, B]] = SortedMap.newBuilder[A, B]
+
+  override def empty: SortedMap[A, B] = SortedMap.empty
+
+  override def updated[B1 >: B](key: A, value: B1): SortedMap[A, B1] = this + ((key, value))
+
+  override def +[B1 >: B](kv: (A, B1)): SortedMap[A, B1] = clone().asInstanceOf[SortedMap[A, B1]] += kv
+
+  override def +[B1 >: B](elem1: (A, B1), elem2: (A, B1), elems: (A, B1)*): SortedMap[A, B1] =
+    clone().asInstanceOf[SortedMap[A, B1]] += elem1 += elem2 ++= elems
+
+  override def ++[B1 >: B](xs: GenTraversableOnce[(A, B1)]): SortedMap[A, B1] =
+    clone().asInstanceOf[SortedMap[A, B1]] ++= xs.seq
+}
+
+/**
+ * $factoryInfo
+ *
+ * @define Coll mutable.SortedMap
+ * @define coll mutable sorted map
+ */
+object SortedMap extends MutableSortedMapFactory[SortedMap] {
+
+  def empty[A, B](implicit ord: Ordering[A]): SortedMap[A, B] = TreeMap.empty[A, B]
+
+  /** $sortedMapCanBuildFromInfo */
+  implicit def canBuildFrom[A, B](implicit ord: Ordering[A]): CanBuildFrom[Coll, (A, B), SortedMap[A, B]] =
+    new SortedMapCanBuildFrom[A, B]
+}
+
+/** Explicit instantiation of the `SortedMap` trait to reduce class file size in subclasses. */
+abstract class AbstractSortedMap[A, B] extends scala.collection.mutable.AbstractMap[A, B] with SortedMap[A, B]
diff --git a/src/library/scala/collection/mutable/TreeMap.scala b/src/library/scala/collection/mutable/TreeMap.scala
new file mode 100644
index 0000000000..244cc18735
--- /dev/null
+++ b/src/library/scala/collection/mutable/TreeMap.scala
@@ -0,0 +1,166 @@
+package scala
+package collection
+package mutable
+
+import scala.collection.generic._
+import scala.collection.mutable.{RedBlackTree => RB}
+
+/**
+ * $factoryInfo
+ *
+ * @define Coll mutable.TreeMap
+ * @define coll mutable tree map
+ */
+object TreeMap extends MutableSortedMapFactory[TreeMap] {
+
+  def empty[A, B](implicit ord: Ordering[A]) = new TreeMap[A, B]()(ord)
+
+  /** $sortedMapCanBuildFromInfo */
+  implicit def canBuildFrom[A, B](implicit ord: Ordering[A]): CanBuildFrom[Coll, (A, B), TreeMap[A, B]] =
+    new SortedMapCanBuildFrom[A, B]
+}
+
+/**
+ * A mutable sorted map implemented using a mutable red-black tree as underlying data structure.
+ *
+ * @param ordering the implicit ordering used to compare objects of type `A`.
+ * @tparam A the type of the keys contained in this tree map.
+ * @tparam B the type of the values associated with the keys.
+ *
+ * @author Rui Gonçalves
+ * @version 2.12
+ * @since 2.12
+ *
+ * @define Coll mutable.TreeMap
+ * @define coll mutable tree map
+ */
+@SerialVersionUID(-2558985573956740112L)
+sealed class TreeMap[A, B] private (tree: RB.Tree[A, B])(implicit val ordering: Ordering[A])
+  extends AbstractSortedMap[A, B]
+  with SortedMap[A, B]
+  with MapLike[A, B, TreeMap[A, B]]
+  with SortedMapLike[A, B, TreeMap[A, B]]
+  with Serializable {
+
+  /**
+   * Creates an empty `TreeMap`.
+   * @param ord the implicit ordering used to compare objects of type `A`.
+   * @return an empty `TreeMap`.
+   */
+  def this()(implicit ord: Ordering[A]) = this(RB.Tree.empty)(ord)
+
+  override def empty = TreeMap.empty
+  override protected[this] def newBuilder = TreeMap.newBuilder[A, B]
+
+  def rangeImpl(from: Option[A], until: Option[A]): TreeMap[A, B] = new TreeMapView(from, until)
+
+  def -=(key: A): this.type = { RB.delete(tree, key); this }
+  def +=(kv: (A, B)): this.type = { RB.insert(tree, kv._1, kv._2); this }
+
+  def get(key: A) = RB.get(tree, key)
+
+  def iterator = RB.iterator(tree)
+  def iteratorFrom(start: A) = RB.iterator(tree, Some(start))
+  def keysIteratorFrom(start: A) = RB.keysIterator(tree, Some(start))
+  def valuesIteratorFrom(start: A) = RB.valuesIterator(tree, Some(start))
+
+  override def size = tree.size
+  override def isEmpty = RB.isEmpty(tree)
+  override def contains(key: A) = RB.contains(tree, key)
+
+  override def head = RB.min(tree).get
+  override def headOption = RB.min(tree)
+  override def last = RB.max(tree).get
+  override def lastOption = RB.max(tree)
+
+  override def keysIterator = RB.keysIterator(tree)
+  override def valuesIterator = RB.valuesIterator(tree)
+
+  override def foreach[U](f: ((A, B)) => U): Unit = RB.foreach(tree, f)
+  override def transform(f: (A, B) => B) = { RB.transform(tree, f); this }
+  override def clear(): Unit = tree.root = null
+
+  override def stringPrefix = "TreeMap"
+
+  /**
+   * A ranged projection of a [[TreeMap]]. Mutations on this map affect the original map and vice versa.
+   *
+   * Only entries with keys between this projection's key range will ever appear as elements of this map, independently
+   * of whether the entries are added through the original map or through this view. That means that if one inserts a
+   * key-value in a view whose key is outside the view's bounds, calls to `get` or `contains` will _not_ consider the
+   * newly added entry. Mutations are always reflected in the original map, though.
+   *
+   * @param from the lower bound (inclusive) of this projection wrapped in a `Some`, or `None` if there is no lower
+   *             bound.
+   * @param until the upper bound (exclusive) of this projection wrapped in a `Some`, or `None` if there is no upper
+   *              bound.
+   */
+  @SerialVersionUID(2219159283273389116L)
+  private[this] final class TreeMapView(from: Option[A], until: Option[A]) extends TreeMap[A, B](tree) {
+
+    /**
+     * Given a possible new lower bound, chooses and returns the most constraining one (the maximum).
+     */
+    private[this] def pickLowerBound(newFrom: Option[A]): Option[A] = (from, newFrom) match {
+      case (Some(fr), Some(newFr)) => Some(ordering.max(fr, newFr))
+      case (None, _) => newFrom
+      case _ => from
+    }
+
+    /**
+     * Given a possible new upper bound, chooses and returns the most constraining one (the minimum).
+     */
+    private[this] def pickUpperBound(newUntil: Option[A]): Option[A] = (until, newUntil) match {
+      case (Some(unt), Some(newUnt)) => Some(ordering.min(unt, newUnt))
+      case (None, _) => newUntil
+      case _ => until
+    }
+
+    /**
+     * Returns true if the argument is inside the view bounds (between `from` and `until`).
+     */
+    private[this] def isInsideViewBounds(key: A): Boolean = {
+      val afterFrom = from.isEmpty || ordering.compare(from.get, key) <= 0
+      val beforeUntil = until.isEmpty || ordering.compare(key, until.get) < 0
+      afterFrom && beforeUntil
+    }
+
+    override def rangeImpl(from: Option[A], until: Option[A]): TreeMap[A, B] =
+      new TreeMapView(pickLowerBound(from), pickUpperBound(until))
+
+    override def get(key: A) = if (isInsideViewBounds(key)) RB.get(tree, key) else None
+
+    override def iterator = RB.iterator(tree, from, until)
+    override def iteratorFrom(start: A) = RB.iterator(tree, pickLowerBound(Some(start)), until)
+    override def keysIteratorFrom(start: A) = RB.keysIterator(tree, pickLowerBound(Some(start)), until)
+    override def valuesIteratorFrom(start: A) = RB.valuesIterator(tree, pickLowerBound(Some(start)), until)
+
+    override def size = iterator.length
+    override def isEmpty = !iterator.hasNext
+    override def contains(key: A) = isInsideViewBounds(key) && RB.contains(tree, key)
+
+    override def head = headOption.get
+    override def headOption = {
+      val entry = if (from.isDefined) RB.minAfter(tree, from.get) else RB.min(tree)
+      (entry, until) match {
+        case (Some(e), Some(unt)) if ordering.compare(e._1, unt) >= 0 => None
+        case _ => entry
+      }
+    }
+
+    override def last = lastOption.get
+    override def lastOption = {
+      val entry = if (until.isDefined) RB.maxBefore(tree, until.get) else RB.max(tree)
+      (entry, from) match {
+        case (Some(e), Some(fr)) if ordering.compare(e._1, fr) < 0 => None
+        case _ => entry
+      }
+    }
+
+    override def foreach[U](f: ((A, B)) => U): Unit = iterator.foreach(f)
+    override def transform(f: (A, B) => B) = {
+      iterator.foreach { case (key, value) => update(key, f(key, value)) }
+      this
+    }
+  }
+}
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) } )
   }