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.

1 files changed, 4 insertions, 2 deletions

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