summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore2
-rw-r--r--src/library/scala/collection/generic/MutableSortedSetFactory.scala33
-rw-r--r--src/library/scala/collection/mutable/AVLTree.scala206
-rw-r--r--src/library/scala/collection/mutable/SortedSet.scala49
-rw-r--r--src/library/scala/collection/mutable/TreeSet.scala130
-rw-r--r--test/benchmarking/AVL-insert-random.scala67
-rw-r--r--test/benchmarking/AVL-insert.scala67
-rw-r--r--test/files/jvm/serialization.check4
-rw-r--r--test/files/jvm/serialization.scala7
-rw-r--r--test/files/run/si4147.scala36
-rw-r--r--test/files/scalacheck/si4147.scala67
11 files changed, 667 insertions, 1 deletions
diff --git a/.gitignore b/.gitignore
index d392f0e82c..2121e38a7e 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1 +1,3 @@
*.jar
+build
+*.*~
diff --git a/src/library/scala/collection/generic/MutableSortedSetFactory.scala b/src/library/scala/collection/generic/MutableSortedSetFactory.scala
new file mode 100644
index 0000000000..b235379575
--- /dev/null
+++ b/src/library/scala/collection/generic/MutableSortedSetFactory.scala
@@ -0,0 +1,33 @@
+/* __ *\
+** ________ ___ / / ___ Scala API **
+** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL **
+** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
+** /____/\___/_/ |_/____/_/ | | **
+** |/ **
+\* */
+
+package scala.collection
+package generic
+
+import scala.collection.mutable.{ Builder, GrowingBuilder }
+
+/**
+ * @define Coll mutable.SortedSet
+ * @define coll mutable sorted
+ *
+ * @author Lucien Pereira
+ *
+ */
+abstract class MutableSortedSetFactory[CC[A] <: mutable.SortedSet[A] with SortedSetLike[A, CC[A]] with mutable.Set[A] with mutable.SetLike[A, CC[A]]] extends SortedSetFactory[CC] {
+
+ /**
+ * mutable.SetBuilder uses '+' which is not a primitive for anything extending mutable.SetLike,
+ * this causes serious perfomances issues since each time 'elems = elems + x'
+ * is evaluated elems is cloned (which is O(n)).
+ *
+ * Fortunately GrowingBuilder comes to rescue.
+ *
+ */
+ override def newBuilder[A](implicit ord: Ordering[A]): Builder[A, CC[A]] = new GrowingBuilder[A, CC[A]](empty)
+
+}
diff --git a/src/library/scala/collection/mutable/AVLTree.scala b/src/library/scala/collection/mutable/AVLTree.scala
new file mode 100644
index 0000000000..0cf6cb06e5
--- /dev/null
+++ b/src/library/scala/collection/mutable/AVLTree.scala
@@ -0,0 +1,206 @@
+/* __ *\
+** ________ ___ / / ___ Scala API **
+** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL **
+** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
+** /____/\___/_/ |_/____/_/ | | **
+** |/ **
+\* */
+
+package scala.collection
+package mutable
+
+import annotation.tailrec
+
+/**
+ * An immutable AVL Tree implementation used by mutable.TreeSet
+ *
+ * @author Lucien Pereira
+ *
+ */
+private[mutable] sealed trait AVLTree[+A] extends Serializable {
+ def balance: Int
+
+ def depth: Int
+
+}
+
+private case class Node[A](val data: A, val left: AVLTree[A], val right: AVLTree[A]) extends AVLTree[A] {
+ override val balance: Int = right.depth - left.depth
+
+ override val depth: Int = math.max(left.depth, right.depth) + 1
+
+}
+
+private case object Leaf extends AVLTree[Nothing] {
+ override val balance: Int = 0
+
+ override val depth: Int = -1
+
+}
+
+private[mutable] object AVLTree {
+
+ /**
+ * Returns a new tree containing the given element.
+ * Thows an IllegalArgumentException if element is already present.
+ *
+ */
+ def insert[A](value: A, tree: AVLTree[A], ordering: Ordering[A]): AVLTree[A] = {
+ @tailrec
+ def insertTC(value: A, tree: AVLTree[A], reassemble: AVLTree[A] => AVLTree[A]): AVLTree[A] = tree match {
+ case Leaf => reassemble(Node(value, Leaf, Leaf))
+
+ case Node(a, left, right) => if (0 == ordering.compare(value, a)) {
+ throw new IllegalArgumentException()
+ } else if (-1 == ordering.compare(value, a)) {
+ insertTC(value, left, x => reassemble(rebalance(Node(a, x, right))))
+ } else {
+ insertTC(value, right, x => reassemble(rebalance(Node(a, left, x))))
+ }
+ }
+
+ insertTC(value, tree, x => rebalance(x))
+ }
+
+ def contains[A](value: A, tree: AVLTree[A], ordering: Ordering[A]): Boolean = tree match {
+ case Leaf => false
+
+ case Node(a, left, right) => if (0 == ordering.compare(value, a)) {
+ true
+ } else if (-1 == ordering.compare(value, a)) {
+ contains(value, left, ordering)
+ } else {
+ contains(value, right, ordering)
+ }
+ }
+
+ /**
+ * Return a new tree which not contains given element.
+ *
+ */
+ def remove[A](value: A, tree: AVLTree[A], ordering: Ordering[A]): AVLTree[A] = tree match {
+ case Leaf => throw new NoSuchElementException()
+
+ case Node(a, Leaf, Leaf) => if (0 == ordering.compare(value, a)) {
+ Leaf
+ } else {
+ throw new NoSuchElementException()
+ }
+
+ case Node(a, left, right@Node(_, _, _)) => if (0 == ordering.compare(value, a)) {
+ val (min, newRight) = removeMin(right)
+ rebalance(Node(min, left, newRight))
+ } else if (-1 == ordering.compare(value, a)) {
+ rebalance(Node(a, remove(value, left, ordering), right))
+ } else {
+ rebalance(Node(a, left, remove(value, right, ordering)))
+ }
+
+ case Node(a, left@Node(_, _, _), right) => if (0 == ordering.compare(value, a)) {
+ val (max, newLeft) = removeMax(left)
+ rebalance(Node(max, newLeft, right))
+ } else if (-1 == ordering.compare(value, a)) {
+ rebalance(Node(a, remove(value, left, ordering), right))
+ } else {
+ rebalance(Node(a, left, remove(value, right, ordering)))
+ }
+ }
+
+ /**
+ * Return a tuple containing the biggest element of the provided tree
+ * and a new tree from which this element has been extracted.
+ *
+ */
+ def removeMax[A](tree: Node[A]): (A, AVLTree[A]) = {
+ @tailrec
+ def removeMaxTC(tree: AVLTree[A], assemble: (A, AVLTree[A]) => (A, AVLTree[A])): (A, AVLTree[A]) = tree match {
+ case Node(a, Leaf, Leaf) => assemble(a, Leaf)
+ case Node(a, left, Leaf) => assemble(a, left)
+ case Node(a, left, right) => removeMaxTC(right,
+ (max: A, avl: AVLTree[A]) => assemble(max, rebalance(Node(a, left, avl))))
+ case Leaf => sys.error("Should not happen.")
+ }
+
+ removeMaxTC(tree, (a, b) => (a, b))
+ }
+
+ /**
+ * Return a tuple containing the smallest element of the provided tree
+ * and a new tree from which this element has been extracted.
+ *
+ */
+ def removeMin[A](tree: Node[A]): (A, AVLTree[A]) = {
+ @tailrec
+ def removeMinTC(tree: AVLTree[A], assemble: (A, AVLTree[A]) => (A, AVLTree[A])): (A, AVLTree[A]) = tree match {
+ case Node(a, Leaf, Leaf) => assemble(a, Leaf)
+ case Node(a, Leaf, right) => assemble(a, right)
+ case Node(a, left, right) => removeMinTC(left,
+ (min: A, avl: AVLTree[A]) => assemble(min, rebalance(Node(a, avl, right))))
+ case Leaf => sys.error("Should not happen.")
+ }
+
+ removeMinTC(tree, (a, b) => (a, b))
+ }
+
+ /**
+ * Returns a bounded stream of elements in the tree.
+ *
+ */
+ def toStream[A](tree: AVLTree[A], isLeftAcceptable: A => Boolean, isRightAcceptable: A => Boolean): Stream[A] = tree match {
+ case Leaf => Stream.empty
+
+ case Node(a, left, right) => if (isLeftAcceptable(a)) {
+ if (isRightAcceptable(a)) {
+ toStream(left, isLeftAcceptable, isRightAcceptable) ++ Stream(a) ++ toStream(right, isLeftAcceptable, isRightAcceptable)
+ } else {
+ toStream(left, isLeftAcceptable, isRightAcceptable)
+ }
+ } else if (isRightAcceptable(a)) {
+ toStream(right, isLeftAcceptable, isRightAcceptable)
+ } else {
+ Stream.empty
+ }
+ }
+
+ /**
+ * Returns a bounded iterator of elements in the tree.
+ *
+ */
+ def iterator[A](tree: AVLTree[A], isLeftAcceptable: A => Boolean, isRightAcceptable: A => Boolean): Iterator[A] =
+ toStream(tree, isLeftAcceptable, isRightAcceptable).iterator
+
+ def rebalance[A](tree: AVLTree[A]): AVLTree[A] = (tree, tree.balance) match {
+ case (node@Node(_, left, _), -2) => left.balance match {
+ case 1 => doubleRightRotation(node)
+ case _ => rightRotation(node)
+ }
+
+ case (node@Node(_, _, right), 2) => right.balance match {
+ case -1 => doubleLeftRotation(node)
+ case _ => leftRotation(node)
+ }
+
+ case _ => tree
+ }
+
+ def leftRotation[A](tree: Node[A]): AVLTree[A] = tree.right match {
+ case Node(b, left, right) => Node(b, Node(tree.data, tree.left, left), right)
+ case _ => sys.error("Should not happen.")
+ }
+
+ def rightRotation[A](tree: Node[A]): AVLTree[A] = tree.left match {
+ case Node(b, left, right) => Node(b, left, Node(tree.data, right, tree.right))
+ case _ => sys.error("Should not happen.")
+ }
+
+ def doubleLeftRotation[A](tree: Node[A]): AVLTree[A] = tree.right match {
+ case right@Node(b, l, r) => leftRotation(Node(tree.data, tree.left, rightRotation(right)))
+ case _ => sys.error("Should not happen.")
+ }
+
+ def doubleRightRotation[A](tree: Node[A]): AVLTree[A] = tree.left match {
+ case left@Node(b, l, r) => rightRotation(Node(tree.data, leftRotation(left), tree.right))
+ case _ => sys.error("Should not happen.")
+ }
+
+}
diff --git a/src/library/scala/collection/mutable/SortedSet.scala b/src/library/scala/collection/mutable/SortedSet.scala
new file mode 100644
index 0000000000..d87fc0b4a2
--- /dev/null
+++ b/src/library/scala/collection/mutable/SortedSet.scala
@@ -0,0 +1,49 @@
+/* __ *\
+** ________ ___ / / ___ Scala API **
+** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL **
+** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
+** /____/\___/_/ |_/____/_/ | | **
+** |/ **
+\* */
+
+package scala.collection
+package mutable
+
+import generic._
+
+/**
+ * Base trait for mutable sorted set.
+ *
+ * @define Coll mutable.SortedSet
+ * @define coll mutable sorted set
+ *
+ * @author Lucien Pereira
+ *
+ */
+trait SortedSet[A] extends collection.SortedSet[A] with collection.SortedSetLike[A,SortedSet[A]]
+ with mutable.Set[A] with mutable.SetLike[A, SortedSet[A]] {
+
+ /** Needs to be overridden in subclasses. */
+ override def empty: SortedSet[A] = SortedSet.empty[A]
+
+}
+
+/**
+ * A template for mutable sorted set companion objects.
+ *
+ * @define Coll mutable.SortedSet
+ * @define coll mutable sorted set
+ * @define factoryInfo
+ * This object provides a set of operations needed to create sorted sets of type mutable.SortedSet.
+ * @define sortedSetCanBuildFromInfo
+ * Standard `CanBuildFrom` instance for sorted sets.
+ *
+ * @author Lucien Pereira
+ *
+ */
+object SortedSet extends MutableSortedSetFactory[SortedSet] {
+ implicit def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, SortedSet[A]] = new SortedSetCanBuildFrom[A]
+
+ def empty[A](implicit ord: Ordering[A]): SortedSet[A] = TreeSet.empty[A]
+
+}
diff --git a/src/library/scala/collection/mutable/TreeSet.scala b/src/library/scala/collection/mutable/TreeSet.scala
new file mode 100644
index 0000000000..8039db7cc9
--- /dev/null
+++ b/src/library/scala/collection/mutable/TreeSet.scala
@@ -0,0 +1,130 @@
+/* __ *\
+** ________ ___ / / ___ Scala API **
+** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL **
+** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
+** /____/\___/_/ |_/____/_/ | | **
+** |/ **
+\* */
+
+package scala.collection
+package mutable
+
+
+
+import generic._
+
+
+
+/**
+ * @define Coll mutable.TreeSet
+ * @define coll mutable tree set
+ * @factoryInfo
+ * Companion object of TreeSet providing factory related utilities.
+ *
+ * @author Lucien Pereira
+ *
+ */
+object TreeSet extends MutableSortedSetFactory[TreeSet] {
+ /**
+ * The empty set of this type
+ */
+ def empty[A](implicit ordering: Ordering[A]) = new TreeSet[A]()
+
+}
+
+/**
+ * A mutable SortedSet using an immutable AVL Tree as underlying data structure.
+ *
+ * @author Lucien Pereira
+ *
+ */
+class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with SetLike[A, TreeSet[A]]
+ with SortedSetLike[A, TreeSet[A]] with Set[A] with Serializable {
+
+ // Projection constructor
+ private def this(base: Option[TreeSet[A]], from: Option[A], until: Option[A])(implicit ordering: Ordering[A]) {
+ this();
+ this.base = base
+ this.from = from
+ this.until = until
+ }
+
+ private var base: Option[TreeSet[A]] = None
+
+ private var from: Option[A] = None
+
+ private var until: Option[A] = None
+
+ private var avl: AVLTree[A] = Leaf
+
+ private var cardinality: Int = 0
+
+ def resolve: TreeSet[A] = base.getOrElse(this)
+
+ private def isLeftAcceptable(from: Option[A], ordering: Ordering[A])(a: A): Boolean =
+ from.map(x => ordering.gteq(a, x)).getOrElse(true)
+
+ private def isRightAcceptable(until: Option[A], ordering: Ordering[A])(a: A): Boolean =
+ until.map(x => ordering.lt(a, x)).getOrElse(true)
+
+ /**
+ * Cardinality store the set size, unfortunately a
+ * set view (given by rangeImpl)
+ * cannot take advantage of this optimisation
+ *
+ */
+ override def size: Int = base.map(_ => super.size).getOrElse(cardinality)
+
+ override def stringPrefix = "TreeSet"
+
+ override def empty: TreeSet[A] = TreeSet.empty
+
+ override def rangeImpl(from: Option[A], until: Option[A]): TreeSet[A] = new TreeSet(Some(this), from, until)
+
+ override def -=(elem: A): this.type = {
+ try {
+ resolve.avl = AVLTree.remove(elem, resolve.avl, ordering)
+ resolve.cardinality = resolve.cardinality - 1
+ } catch {
+ case e: NoSuchElementException => ()
+ case a: Any => a.printStackTrace
+ }
+ this
+ }
+
+ override def +=(elem: A): this.type = {
+ try {
+ resolve.avl = AVLTree.insert(elem, resolve.avl, ordering)
+ resolve.cardinality = resolve.cardinality + 1
+ } catch {
+ case e: IllegalArgumentException => ()
+ case a: Any => a.printStackTrace
+ }
+ this
+ }
+
+ /**
+ * Thanks to the nature immutable of the
+ * underlying AVL Tree, we can share it with
+ * the clone. So clone complexity in time is O(1).
+ *
+ */
+ override def clone: TreeSet[A] = {
+ val clone = new TreeSet[A](base, from, until)
+ clone.avl = resolve.avl
+ clone.cardinality = resolve.cardinality
+ clone
+ }
+
+ override def contains(elem: A): Boolean = {
+ isLeftAcceptable(from, ordering)(elem) &&
+ isRightAcceptable(until, ordering)(elem) &&
+ AVLTree.contains(elem, resolve.avl, ordering)
+ }
+
+ override def iterator: Iterator[A] =
+ AVLTree.iterator(resolve.avl,
+ isLeftAcceptable(from, ordering),
+ isRightAcceptable(until, ordering))
+
+}
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]()
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-04 15:02:30 +0000