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, 24 insertions, 0 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]