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, 329 insertions, 0 deletions

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