diff options
author | Rui Gonçalves <ruippeixotog@gmail.com> | 2015-07-06 22:56:02 +0100 |
---|---|---|
committer | Rui Gonçalves <ruippeixotog@gmail.com> | 2015-07-28 10:12:44 +0100 |
commit | c15259091d43c82053bcacf206eba5da6bc56fe5 (patch) | |
tree | 235d06ba881014d47c70b5e381b1c615d84e47b0 /test/files/scalacheck/MutableTreeMap.scala | |
parent | 462e22d2f25bb9432c5a1e7bf20f391e6424f7a9 (diff) | |
download | scala-c15259091d43c82053bcacf206eba5da6bc56fe5.tar.gz scala-c15259091d43c82053bcacf206eba5da6bc56fe5.tar.bz2 scala-c15259091d43c82053bcacf206eba5da6bc56fe5.zip |
SI-6938 Use mutable red-black tree in TreeSet
The previous implementation of `mutable.TreeSet` uses a mutable reference to an immutable red-black tree as its underlying data structure. That leads to unnecessary objects being created, which can be a problem in systems with limited resources. It also has reduced performance when compared with common mutable implementations.
In this commit `mutable.TreeSet` is changed so that it uses the recently created `mutable.RedBlackTree` as its underlying data structure. Specialized red-black tree methods were created for working with keys for efficiency reasons. The new implementation is source-compatible with the previous one, although its serialized representation obviously changes.
Closes [SI-6938](https://issues.scala-lang.org/browse/SI-6938).
Diffstat (limited to 'test/files/scalacheck/MutableTreeMap.scala')
-rw-r--r-- | test/files/scalacheck/MutableTreeMap.scala | 20 |
1 files changed, 18 insertions, 2 deletions
diff --git a/test/files/scalacheck/MutableTreeMap.scala b/test/files/scalacheck/MutableTreeMap.scala index b072307a63..42b88c56a7 100644 --- a/test/files/scalacheck/MutableTreeMap.scala +++ b/test/files/scalacheck/MutableTreeMap.scala @@ -5,6 +5,7 @@ import org.scalacheck.Arbitrary._ import org.scalacheck.Prop.forAll import scala.collection.generic.CanBuildFrom +import scala.collection.immutable import scala.collection.mutable import scala.util.Try import scala.collection.mutable.{RedBlackTree => RB} @@ -107,8 +108,9 @@ package scala.collection.mutable { } property("++=") = forAll { (map: mutable.TreeMap[K, V], entries: Seq[(K, V)]) => + val oldEntries = map.toMap map ++= entries - entries.toMap.forall { case (k, v) => map.get(k) == Some(v) } + (oldEntries ++ entries).forall { case (k, v) => map.get(k) == Some(v) } } property("-=") = forAll { (map: mutable.TreeMap[K, V], k: K) => @@ -121,8 +123,10 @@ package scala.collection.mutable { } property("--=") = forAll { (map: mutable.TreeMap[K, V], ks: Seq[K]) => + val oldElems = map.toList map --= ks - ks.toSet.forall { k => map.get(k) == None } + val deletedElems = ks.toSet + oldElems.forall { case (k, v) => map.get(k) == (if(deletedElems(k)) None else Some(v)) } } property("iterator") = forAll { (entries: Map[K, V]) => @@ -176,6 +180,18 @@ package scala.collection.mutable { val sameMap = in.readObject().asInstanceOf[mutable.TreeMap[K, V]] map.iterator.toSeq == sameMap.iterator.toSeq } + + property("same behavior as immutable.TreeMap") = forAll { ops: Seq[Either[(K, V), K]] => + var imap = immutable.TreeMap[K, V]() + val mmap = mutable.TreeMap[K, V]() + + ops.foreach { + case Left((k, v)) => imap += k -> v; mmap += k -> v + case Right(k) => imap -= k; mmap -= k + } + + imap.toList == mmap.toList + } } object MutableTreeMapViewProperties extends Properties("mutable.TreeMapView") with Generators { |