Add mutable tree sets to the standard library.

This implementation is based on AVL trees.
The current implementation is contributed by Lucien Pereira.

Fixes #4147.

2 files changed, 134 insertions, 0 deletions

diff --git a/test/benchmarking/AVL-insert-random.scala b/test/benchmarking/AVL-insert-random.scala
new file mode 100644
index 0000000000..7299e330f5
--- /dev/null
+++ b/test/benchmarking/AVL-insert-random.scala
@@ -0,0 +1,67 @@
+package scala.collection
+
+
+
+
+
+class Dummy(val a: Int) extends math.Ordered[Dummy] {
+  def compare(other: Dummy) = this.a - other.a
+  override def toString = a.toString
+}
+
+
+object RandomGlobal {
+  val sz = 500000
+  val data = util.Random.shuffle((0 until sz) map { new Dummy(_) }) toArray;
+}
+
+
+import RandomGlobal._
+
+
+object RandomAVL extends testing.Benchmark {
+  
+  def run() {
+    val avl = new collection.mutable.TreeSet[Dummy]
+    
+    var i = 0
+    while (i < sz) {
+      val elem = data(i)
+      avl += elem
+      i += 1
+    }
+  }
+  
+}
+
+
+object RandomImmutableTreeSet extends testing.Benchmark {
+  
+  def run() {
+    var tree = new collection.immutable.TreeSet[Dummy]
+    
+    var i = 0
+    while (i < sz) {
+      val elem = data(i)
+      tree += elem
+      i += 1
+    }
+  }
+  
+}
+
+
+object RandomJavaTreeSet extends testing.Benchmark {
+  
+  def run() {
+    val tree = new java.util.TreeSet[Dummy]
+    
+    var i = 0
+    while (i < sz) {
+      val elem = data(i)
+      tree add elem
+      i += 1
+    }
+  }
+  
+}
diff --git a/test/benchmarking/AVL-insert.scala b/test/benchmarking/AVL-insert.scala
new file mode 100644
index 0000000000..4f3ab390c9
--- /dev/null
+++ b/test/benchmarking/AVL-insert.scala
@@ -0,0 +1,67 @@
+package scala.collection
+
+
+
+
+
+class Dummy(val a: Int) extends math.Ordered[Dummy] {
+  def compare(other: Dummy) = this.a - other.a
+  override def toString = a.toString
+}
+
+
+object Global {
+  val sz = 500000
+  val data = (0 until sz) map { new Dummy(_) } toArray
+}
+
+
+import Global._
+
+
+object AVL extends testing.Benchmark {
+  
+  def run() {
+    val avl = new collection.mutable.TreeSet[Dummy]
+    
+    var i = 0
+    while (i < sz) {
+      val elem = data(i)
+      avl += elem
+      i += 1
+    }
+  }
+  
+}
+
+
+object ImmutableTreeSet extends testing.Benchmark {
+  
+  def run() {
+    var tree = new collection.immutable.TreeSet[Dummy]
+    
+    var i = 0
+    while (i < sz) {
+      val elem = data(i)
+      tree += elem
+      i += 1
+    }
+  }
+  
+}
+
+
+object JavaTreeSet extends testing.Benchmark {
+  
+  def run() {
+    val tree = new java.util.TreeSet[Dummy]
+    
+    var i = 0
+    while (i < sz) {
+      val elem = data(i)
+      tree add elem
+      i += 1
+    }
+  }
+  
+}