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.

6 files changed, 247 insertions, 1 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
+    }
+  }
+  
+}
diff --git a/test/files/jvm/serialization.check b/test/files/jvm/serialization.check
index 15708f0c3b..bc56387f81 100644
--- a/test/files/jvm/serialization.check
+++ b/test/files/jvm/serialization.check
@@ -188,6 +188,10 @@ x = WrappedArray(1, 2, 3)
 y = WrappedArray(1, 2, 3)
 x equals y: true, y equals x: true
 
+x = TreeSet(1, 2, 3)
+y = TreeSet(1, 2, 3)
+x equals y: true, y equals x: true
+
 x =  xml:src="hello"
 y =  xml:src="hello"
 x equals y: true, y equals x: true
diff --git a/test/files/jvm/serialization.scala b/test/files/jvm/serialization.scala
index 9391b60e46..73bed2d46b 100644
--- a/test/files/jvm/serialization.scala
+++ b/test/files/jvm/serialization.scala
@@ -286,7 +286,7 @@ object Test3_mutable {
   import scala.collection.mutable.{
     ArrayBuffer, ArrayBuilder, ArraySeq, ArrayStack, BitSet, DoubleLinkedList,
     HashMap, HashSet, History, LinkedList, ListBuffer, Publisher, Queue,
-    Stack, StringBuilder, WrappedArray}
+    Stack, StringBuilder, WrappedArray, TreeSet}
 
   // in alphabetic order
   try {
@@ -380,6 +380,11 @@ object Test3_mutable {
     val wa1 = WrappedArray.make(Array(1, 2, 3))
     val _wa1: WrappedArray[Int] = read(write(wa1))
     check(wa1, _wa1)
+    
+    // TreeSet
+    val ts1 = TreeSet[Int]() ++= Array(1, 2, 3)
+    val _ts1: TreeSet[Int] = read(write(ts1))
+    check(ts1, _ts1)
   }
   catch {
     case e: Exception =>
diff --git a/test/files/run/si4147.scala b/test/files/run/si4147.scala
new file mode 100644
index 0000000000..c1e2d746a9
--- /dev/null
+++ b/test/files/run/si4147.scala
@@ -0,0 +1,36 @@
+
+
+
+import scala.collection._
+
+
+
+object Test {
+
+  def main(args: Array[String]) {
+    checkElementsAreSorted()
+    checkRangedImpl()
+  }
+
+  def checkElementsAreSorted() {
+    val tree = mutable.SortedSet[Int]()
+    tree ++= List(4, 3, 1, 6, 7, 5, 2)
+    assert(tree == immutable.SortedSet(1, 2, 3, 4, 5, 6, 7))
+    assert(tree.size == 7)
+  }
+
+  def checkRangedImpl() {
+    val tree = mutable.SortedSet[Int](3, 1, 6, 7, 5, 2)
+    val projection = tree.rangeImpl(Some(3), Some(6))
+    assert(projection == immutable.SortedSet(3, 5))
+    assert(projection.size == 2)
+
+    // Let's check that modification are taken into account
+    tree add 4
+    assert(tree == immutable.SortedSet(1, 2, 3, 4, 5, 6, 7))
+    assert(projection == immutable.SortedSet(3, 4, 5))
+    assert(tree.size == 7)
+    assert(projection.size == 3)
+  }
+
+}
diff --git a/test/files/scalacheck/si4147.scala b/test/files/scalacheck/si4147.scala
new file mode 100644
index 0000000000..1453440ef1
--- /dev/null
+++ b/test/files/scalacheck/si4147.scala
@@ -0,0 +1,67 @@
+import org.scalacheck.Prop.forAll
+import org.scalacheck.Properties
+import org.scalacheck.ConsoleReporter.testStatsEx
+import org.scalacheck.Gen
+import org.scalacheck.ConsoleReporter
+
+
+import collection.mutable
+
+
+object Test extends Properties("Mutable TreeSet") {
+
+  val generator = Gen.listOfN(1000, Gen.chooseNum(0, 1000))
+
+  val denseGenerator = Gen.listOfN(1000, Gen.chooseNum(0, 200))
+
+  property("Insertion doesn't allow duplicates values.") = forAll(generator) { (s: List[Int]) =>
+    {
+      val t = mutable.TreeSet[Int](s: _*)
+      t == s.toSet
+    }
+  }
+
+  property("Verification of size method validity") = forAll(generator) { (s: List[Int]) =>
+    {
+      val t = mutable.TreeSet[Int](s: _*)
+      for (a <- s) {
+        t -= a
+      }
+      t.size == 0
+    }
+  }
+
+  property("All inserted elements are removed") = forAll(generator) { (s: List[Int]) =>
+    {
+      val t = mutable.TreeSet[Int](s: _*)
+      for (a <- s) {
+        t -= a
+      }
+      t == Set()
+    }
+  }
+
+  property("Elements are sorted.") = forAll(generator) { (s: List[Int]) =>
+    {
+      val t = mutable.TreeSet[Int](s: _*)
+      t.toList == s.distinct.sorted
+    }
+  }
+
+  property("Implicit CanBuildFrom resolution succeeds as well as the \"same-result-type\" principle.") =
+    forAll(generator) { (s: List[Int]) =>
+      {
+        val t = mutable.TreeSet[Int](s: _*)
+        val t2 = t.map(_ * 2)
+        t2.isInstanceOf[collection.mutable.TreeSet[Int]]
+      }
+    }
+
+  property("A view doesn't expose off bounds elements") = forAll(denseGenerator) { (s: List[Int]) =>
+    {
+      val t = mutable.TreeSet[Int](s: _*)
+      val view = t.rangeImpl(Some(50), Some(150))
+      view.filter(_ < 50) == Set[Int]() && view.filter(_ >= 150) == Set[Int]()
+    }
+  }
+}