From 51ddeb372b3f0b22041d9a51f3faee17acd7b749 Mon Sep 17 00:00:00 2001 From: aleksandar Date: Thu, 12 Jan 2012 15:28:25 +0100 Subject: 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. --- test/benchmarking/AVL-insert-random.scala | 67 +++++++++++++++++++++++++++++++ test/benchmarking/AVL-insert.scala | 67 +++++++++++++++++++++++++++++++ test/files/jvm/serialization.check | 4 ++ test/files/jvm/serialization.scala | 7 +++- test/files/run/si4147.scala | 36 +++++++++++++++++ test/files/scalacheck/si4147.scala | 67 +++++++++++++++++++++++++++++++ 6 files changed, 247 insertions(+), 1 deletion(-) create mode 100644 test/benchmarking/AVL-insert-random.scala create mode 100644 test/benchmarking/AVL-insert.scala create mode 100644 test/files/run/si4147.scala create mode 100644 test/files/scalacheck/si4147.scala (limited to 'test') 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]() + } + } +} -- cgit v1.2.3