diff options
| -rw-r--r-- | src/library/scala/collection/mutable/RedBlackTree.scala | 33 | ||||
| -rw-r--r-- | src/library/scala/collection/mutable/SortedSet.scala | 3 | ||||
| -rw-r--r-- | src/library/scala/collection/mutable/TreeMap.scala | 19 | ||||
| -rw-r--r-- | src/library/scala/collection/mutable/TreeSet.scala | 181 | ||||
| -rw-r--r-- | test/files/run/t8549.scala | 5 | ||||
| -rw-r--r-- | test/files/scalacheck/MutableTreeMap.scala | 20 | ||||
| -rw-r--r-- | test/files/scalacheck/MutableTreeSet.scala | 216 | ||||
| -rw-r--r-- | test/junit/scala/collection/SetMapConsistencyTest.scala | 6 |
8 files changed, 424 insertions, 59 deletions
diff --git a/src/library/scala/collection/mutable/RedBlackTree.scala b/src/library/scala/collection/mutable/RedBlackTree.scala index a3be011ae2..e4793242bf 100644 --- a/src/library/scala/collection/mutable/RedBlackTree.scala +++ b/src/library/scala/collection/mutable/RedBlackTree.scala @@ -82,6 +82,11 @@ private[collection] object RedBlackTree { case node => Some((node.key, node.value)) } + def minKey[A](tree: Tree[A, _]): Option[A] = minNode(tree.root) match { + case null => None + case node => Some(node.key) + } + private def minNode[A, B](node: Node[A, B]): Node[A, B] = if (node eq null) null else minNodeNonNull(node) @@ -93,6 +98,11 @@ private[collection] object RedBlackTree { case node => Some((node.key, node.value)) } + def maxKey[A](tree: Tree[A, _]): Option[A] = maxNode(tree.root) match { + case null => None + case node => Some(node.key) + } + private def maxNode[A, B](node: Node[A, B]): Node[A, B] = if (node eq null) null else maxNodeNonNull(node) @@ -109,6 +119,12 @@ private[collection] object RedBlackTree { case node => Some((node.key, node.value)) } + def minKeyAfter[A](tree: Tree[A, _], key: A)(implicit ord: Ordering[A]): Option[A] = + minNodeAfter(tree.root, key) match { + case null => None + case node => Some(node.key) + } + private[this] def minNodeAfter[A, B](node: Node[A, B], key: A)(implicit ord: Ordering[A]): Node[A, B] = { if (node eq null) null else { @@ -133,6 +149,12 @@ private[collection] object RedBlackTree { case node => Some((node.key, node.value)) } + def maxKeyBefore[A](tree: Tree[A, _], key: A)(implicit ord: Ordering[A]): Option[A] = + maxNodeBefore(tree.root, key) match { + case null => None + case node => Some(node.key) + } + private[this] def maxNodeBefore[A, B](node: Node[A, B], key: A)(implicit ord: Ordering[A]): Node[A, B] = { if (node eq null) null else { @@ -411,6 +433,17 @@ private[collection] object RedBlackTree { if (node.right ne null) foreachNodeNonNull(node.right, f) } + def foreachKey[A, U](tree: Tree[A, _], f: A => U): Unit = foreachNodeKey(tree.root, f) + + private[this] def foreachNodeKey[A, U](node: Node[A, _], f: A => U): Unit = + if (node ne null) foreachNodeKeyNonNull(node, f) + + private[this] def foreachNodeKeyNonNull[A, U](node: Node[A, _], f: A => U): Unit = { + if (node.left ne null) foreachNodeKeyNonNull(node.left, f) + f(node.key) + if (node.right ne null) foreachNodeKeyNonNull(node.right, f) + } + def transform[A, B](tree: Tree[A, B], f: (A, B) => B): Unit = transformNode(tree.root, f) private[this] def transformNode[A, B, U](node: Node[A, B], f: (A, B) => B): Unit = diff --git a/src/library/scala/collection/mutable/SortedSet.scala b/src/library/scala/collection/mutable/SortedSet.scala index 0f2fa75abd..3dee57eb6d 100644 --- a/src/library/scala/collection/mutable/SortedSet.scala +++ b/src/library/scala/collection/mutable/SortedSet.scala @@ -48,3 +48,6 @@ object SortedSet extends MutableSortedSetFactory[SortedSet] { def empty[A](implicit ord: Ordering[A]): SortedSet[A] = TreeSet.empty[A] } + +/** Explicit instantiation of the `SortedSet` trait to reduce class file size in subclasses. */ +abstract class AbstractSortedSet[A] extends scala.collection.mutable.AbstractSet[A] with SortedSet[A] diff --git a/src/library/scala/collection/mutable/TreeMap.scala b/src/library/scala/collection/mutable/TreeMap.scala index b96cef5bee..dc7d5d750e 100644 --- a/src/library/scala/collection/mutable/TreeMap.scala +++ b/src/library/scala/collection/mutable/TreeMap.scala @@ -52,6 +52,20 @@ sealed class TreeMap[A, B] private (tree: RB.Tree[A, B])(implicit val ordering: override def empty = TreeMap.empty override protected[this] def newBuilder = TreeMap.newBuilder[A, B] + /** + * Creates a ranged projection of this map. Any mutations in the ranged projection will update the original map and + * vice versa. + * + * Only entries with keys between this projection's key range will ever appear as elements of this map, independently + * of whether the entries are added through the original map or through this view. That means that if one inserts a + * key-value in a view whose key is outside the view's bounds, calls to `get` or `contains` will _not_ consider the + * newly added entry. Mutations are always reflected in the original map, though. + * + * @param from the lower bound (inclusive) of this projection wrapped in a `Some`, or `None` if there is no lower + * bound. + * @param until the upper bound (exclusive) of this projection wrapped in a `Some`, or `None` if there is no upper + * bound. + */ def rangeImpl(from: Option[A], until: Option[A]): TreeMap[A, B] = new TreeMapView(from, until) def -=(key: A): this.type = { RB.delete(tree, key); this } @@ -157,10 +171,15 @@ sealed class TreeMap[A, B] private (tree: RB.Tree[A, B])(implicit val ordering: } } + // Using the iterator should be efficient enough; if performance is deemed a problem later, specialized + // `foreach(f, from, until)` and `transform(f, from, until)` methods can be created in `RedBlackTree`. See + // https://github.com/scala/scala/pull/4608#discussion_r34307985 for a discussion about this. override def foreach[U](f: ((A, B)) => U): Unit = iterator.foreach(f) override def transform(f: (A, B) => B) = { iterator.foreach { case (key, value) => update(key, f(key, value)) } this } + + override def clone() = super.clone().rangeImpl(from, until) } } diff --git a/src/library/scala/collection/mutable/TreeSet.scala b/src/library/scala/collection/mutable/TreeSet.scala index f849eea569..ada6f145ad 100644 --- a/src/library/scala/collection/mutable/TreeSet.scala +++ b/src/library/scala/collection/mutable/TreeSet.scala @@ -11,8 +11,7 @@ package collection package mutable import generic._ -import scala.collection.immutable.{RedBlackTree => RB} -import scala.runtime.ObjectRef +import scala.collection.mutable.{RedBlackTree => RB} /** * @define Coll `mutable.TreeSet` @@ -29,88 +28,162 @@ object TreeSet extends MutableSortedSetFactory[TreeSet] { */ def empty[A](implicit ordering: Ordering[A]) = new TreeSet[A]() + /** $sortedMapCanBuildFromInfo */ + implicit def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, TreeSet[A]] = + new SortedSetCanBuildFrom[A] } /** - * A mutable SortedSet using an immutable RedBlack Tree as underlying data structure. + * A mutable sorted set implemented using a mutable red-black tree as underlying data structure. * - * @author Lucien Pereira + * @param ordering the implicit ordering used to compare objects of type `A`. + * @tparam A the type of the keys contained in this tree set. + * + * @author Rui Gonçalves + * @version 2.12 + * @since 2.10 * + * @define Coll mutable.TreeSet + * @define coll mutable tree set */ -@deprecatedInheritance("TreeSet is not designed to enable meaningful subclassing.", "2.11.0") -class TreeSet[A] private (treeRef: ObjectRef[RB.Tree[A, Null]], from: Option[A], until: Option[A])(implicit val ordering: Ordering[A]) - extends SortedSet[A] with SetLike[A, TreeSet[A]] - with SortedSetLike[A, TreeSet[A]] with Set[A] with Serializable { +// Original API designed in part by Lucien Pereira +@SerialVersionUID(-3642111301929493640L) +sealed class TreeSet[A] private (tree: RB.Tree[A, Null])(implicit val ordering: Ordering[A]) + extends AbstractSortedSet[A] + with SortedSet[A] + with SetLike[A, TreeSet[A]] + with SortedSetLike[A, TreeSet[A]] + with Serializable { if (ordering eq null) throw new NullPointerException("ordering must not be null") - def this()(implicit ordering: Ordering[A]) = this(new ObjectRef(null), None, None) + /** + * Creates an empty `TreeSet`. + * @param ord the implicit ordering used to compare objects of type `A`. + * @return an empty `TreeSet`. + */ + def this()(implicit ord: Ordering[A]) = this(RB.Tree.empty)(ord) - override def size: Int = RB.countInRange(treeRef.elem, from, until) + override def empty = TreeSet.empty + override protected[this] def newBuilder = TreeSet.newBuilder[A] - override def stringPrefix = "TreeSet" + /** + * Creates a ranged projection of this set. Any mutations in the ranged projection affect will update the original set + * and vice versa. + * + * Only keys between this projection's key range will ever appear as elements of this set, independently of whether + * the elements are added through the original set or through this view. That means that if one inserts an element in + * a view whose key is outside the view's bounds, calls to `contains` will _not_ consider the newly added element. + * Mutations are always reflected in the original set, though. + * + * @param from the lower bound (inclusive) of this projection wrapped in a `Some`, or `None` if there is no lower + * bound. + * @param until the upper bound (exclusive) of this projection wrapped in a `Some`, or `None` if there is no upper + * bound. + */ + def rangeImpl(from: Option[A], until: Option[A]): TreeSet[A] = new TreeSetView(from, until) - override def empty: TreeSet[A] = TreeSet.empty + def -=(key: A): this.type = { RB.delete(tree, key); this } + def +=(elem: A): this.type = { RB.insert(tree, elem, null); this } - private def pickBound(comparison: (A, A) => A, oldBound: Option[A], newBound: Option[A]) = (newBound, oldBound) match { - case (Some(newB), Some(oldB)) => Some(comparison(newB, oldB)) - case (None, _) => oldBound - case _ => newBound - } + def contains(elem: A) = RB.contains(tree, elem) - override def rangeImpl(fromArg: Option[A], untilArg: Option[A]): TreeSet[A] = { - val newFrom = pickBound(ordering.max, fromArg, from) - val newUntil = pickBound(ordering.min, untilArg, until) + def iterator = RB.keysIterator(tree) + def keysIteratorFrom(start: A) = RB.keysIterator(tree, Some(start)) + override def iteratorFrom(start: A) = RB.keysIterator(tree, Some(start)) - new TreeSet(treeRef, newFrom, newUntil) - } + override def size = RB.size(tree) + override def isEmpty = RB.isEmpty(tree) - override def -=(elem: A): this.type = { - treeRef.elem = RB.delete(treeRef.elem, elem) - this - } + override def head = RB.minKey(tree).get + override def headOption = RB.minKey(tree) + override def last = RB.maxKey(tree).get + override def lastOption = RB.maxKey(tree) - override def +=(elem: A): this.type = { - treeRef.elem = RB.update(treeRef.elem, elem, null, overwrite = false) - this - } + override def foreach[U](f: A => U): Unit = RB.foreachKey(tree, f) + override def clear(): Unit = RB.clear(tree) + + override def stringPrefix = "TreeSet" /** - * Thanks to the immutable nature of the - * underlying Tree, we can share it with - * the clone. So clone complexity in time is O(1). + * A ranged projection of a [[TreeSet]]. Mutations on this set affect the original set and vice versa. * + * Only keys between this projection's key range will ever appear as elements of this set, independently of whether + * the elements are added through the original set or through this view. That means that if one inserts an element in + * a view whose key is outside the view's bounds, calls to `contains` will _not_ consider the newly added element. + * Mutations are always reflected in the original set, though. + * + * @param from the lower bound (inclusive) of this projection wrapped in a `Some`, or `None` if there is no lower + * bound. + * @param until the upper bound (exclusive) of this projection wrapped in a `Some`, or `None` if there is no upper + * bound. */ - override def clone(): TreeSet[A] = - new TreeSet[A](new ObjectRef(treeRef.elem), from, until) - - private val notProjection = !(from.isDefined || until.isDefined) + @SerialVersionUID(7087824939194006086L) + private[this] final class TreeSetView(from: Option[A], until: Option[A]) extends TreeSet[A](tree) { + + /** + * Given a possible new lower bound, chooses and returns the most constraining one (the maximum). + */ + private[this] def pickLowerBound(newFrom: Option[A]): Option[A] = (from, newFrom) match { + case (Some(fr), Some(newFr)) => Some(ordering.max(fr, newFr)) + case (None, _) => newFrom + case _ => from + } - override def contains(elem: A): Boolean = { - def leftAcceptable: Boolean = from match { - case Some(lb) => ordering.gteq(elem, lb) - case _ => true + /** + * Given a possible new upper bound, chooses and returns the most constraining one (the minimum). + */ + private[this] def pickUpperBound(newUntil: Option[A]): Option[A] = (until, newUntil) match { + case (Some(unt), Some(newUnt)) => Some(ordering.min(unt, newUnt)) + case (None, _) => newUntil + case _ => until } - def rightAcceptable: Boolean = until match { - case Some(ub) => ordering.lt(elem, ub) - case _ => true + /** + * Returns true if the argument is inside the view bounds (between `from` and `until`). + */ + private[this] def isInsideViewBounds(key: A): Boolean = { + val afterFrom = from.isEmpty || ordering.compare(from.get, key) <= 0 + val beforeUntil = until.isEmpty || ordering.compare(key, until.get) < 0 + afterFrom && beforeUntil } - (notProjection || (leftAcceptable && rightAcceptable)) && - RB.contains(treeRef.elem, elem) - } + override def rangeImpl(from: Option[A], until: Option[A]): TreeSet[A] = + new TreeSetView(pickLowerBound(from), pickUpperBound(until)) + + override def contains(key: A) = isInsideViewBounds(key) && RB.contains(tree, key) + + override def iterator = RB.keysIterator(tree, from, until) + override def keysIteratorFrom(start: A) = RB.keysIterator(tree, pickLowerBound(Some(start)), until) + override def iteratorFrom(start: A) = RB.keysIterator(tree, pickLowerBound(Some(start)), until) - override def iterator: Iterator[A] = iteratorFrom(None) + override def size = iterator.length + override def isEmpty = !iterator.hasNext - override def keysIteratorFrom(start: A) = iteratorFrom(Some(start)) + override def head = headOption.get + override def headOption = { + val elem = if (from.isDefined) RB.minKeyAfter(tree, from.get) else RB.minKey(tree) + (elem, until) match { + case (Some(e), Some(unt)) if ordering.compare(e, unt) >= 0 => None + case _ => elem + } + } - private def iteratorFrom(start: Option[A]) = { - val it = RB.keysIterator(treeRef.elem, pickBound(ordering.max, from, start)) - until match { - case None => it - case Some(ub) => it takeWhile (k => ordering.lt(k, ub)) + override def last = lastOption.get + override def lastOption = { + val elem = if (until.isDefined) RB.maxKeyBefore(tree, until.get) else RB.maxKey(tree) + (elem, from) match { + case (Some(e), Some(fr)) if ordering.compare(e, fr) < 0 => None + case _ => elem + } } + + // Using the iterator should be efficient enough; if performance is deemed a problem later, a specialized + // `foreachKey(f, from, until)` method can be created in `RedBlackTree`. See + // https://github.com/scala/scala/pull/4608#discussion_r34307985 for a discussion about this. + override def foreach[U](f: A => U): Unit = iterator.foreach(f) + + override def clone() = super.clone().rangeImpl(from, until) } } diff --git a/test/files/run/t8549.scala b/test/files/run/t8549.scala index 2d3f33537d..0f2be6a4cd 100644 --- a/test/files/run/t8549.scala +++ b/test/files/run/t8549.scala @@ -79,7 +79,7 @@ object Test extends App { } } - // Generated on 20150330-15:20:14 with Scala version 2.12.0-20150330-143836-a91b76ea6c) + // Generated on 20150627-00:51:59 with Scala version 2.12.0-20150626-225838-66bdc5200f) overwrite.foreach(updateComment) check(Some(1))("rO0ABXNyAApzY2FsYS5Tb21lESLyaV6hi3QCAAFMAAF4dAASTGphdmEvbGFuZy9PYmplY3Q7eHIADHNjYWxhLk9wdGlvbv5pN/3bDmZ0AgAAeHBzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAQ==") @@ -179,6 +179,9 @@ object Test extends App { check(mutable.TreeMap())( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZU1hcNx8qC229ZvwAgACTAAIb3JkZXJpbmd0ABVMc2NhbGEvbWF0aC9PcmRlcmluZztMACZzY2FsYSRjb2xsZWN0aW9uJG11dGFibGUkVHJlZU1hcCQkdHJlZXQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJFRyZWU7eHBzcgAYc2NhbGEubWF0aC5PcmRlcmluZyRJbnQkC4BMdr1Z51wCAAB4cHNyACpzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuUmVkQmxhY2tUcmVlJFRyZWUATKc08DWmFQIAAkkABHNpemVMAARyb290dAAsTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9SZWRCbGFja1RyZWUkTm9kZTt4cAAAAABw") check(mutable.TreeMap(1 -> 1, 3 -> 6))( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZU1hcNx8qC229ZvwAgACTAAIb3JkZXJpbmd0ABVMc2NhbGEvbWF0aC9PcmRlcmluZztMACZzY2FsYSRjb2xsZWN0aW9uJG11dGFibGUkVHJlZU1hcCQkdHJlZXQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJFRyZWU7eHBzcgAYc2NhbGEubWF0aC5PcmRlcmluZyRJbnQkC4BMdr1Z51wCAAB4cHNyACpzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuUmVkQmxhY2tUcmVlJFRyZWUATKc08DWmFQIAAkkABHNpemVMAARyb290dAAsTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9SZWRCbGFja1RyZWUkTm9kZTt4cAAAAAJzcgAqc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlJlZEJsYWNrVHJlZSROb2RlGxHsFtValgACAAZaAANyZWRMAANrZXl0ABJMamF2YS9sYW5nL09iamVjdDtMAARsZWZ0cQB+AAdMAAZwYXJlbnRxAH4AB0wABXJpZ2h0cQB+AAdMAAV2YWx1ZXEAfgAKeHAAc3IAEWphdmEubGFuZy5JbnRlZ2VyEuKgpPeBhzgCAAFJAAV2YWx1ZXhyABBqYXZhLmxhbmcuTnVtYmVyhqyVHQuU4IsCAAB4cAAAAAFwcHNxAH4ACQFzcQB+AAwAAAADcHEAfgALcHNxAH4ADAAAAAZxAH4ADg==") check(mutable.TreeMap(1 -> 1, 3 -> 6).range(1, 2))( "rO0ABXNyACxzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZU1hcCRUcmVlTWFwVmlldx7MCZxLhVQ8AgADTAAGJG91dGVydAAiTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9UcmVlTWFwO0wABGZyb210AA5Mc2NhbGEvT3B0aW9uO0wABXVudGlscQB+AAJ4cgAgc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlRyZWVNYXDcfKgttvWb8AIAAkwACG9yZGVyaW5ndAAVTHNjYWxhL21hdGgvT3JkZXJpbmc7TAAmc2NhbGEkY29sbGVjdGlvbiRtdXRhYmxlJFRyZWVNYXAkJHRyZWV0ACxMc2NhbGEvY29sbGVjdGlvbi9tdXRhYmxlL1JlZEJsYWNrVHJlZSRUcmVlO3hwc3IAGHNjYWxhLm1hdGguT3JkZXJpbmckSW50JAuATHa9WedcAgAAeHBzcgAqc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlJlZEJsYWNrVHJlZSRUcmVlAEynNPA1phUCAAJJAARzaXplTAAEcm9vdHQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJE5vZGU7eHAAAAACc3IAKnNjYWxhLmNvbGxlY3Rpb24ubXV0YWJsZS5SZWRCbGFja1RyZWUkTm9kZRsR7BbVWpYAAgAGWgADcmVkTAADa2V5dAASTGphdmEvbGFuZy9PYmplY3Q7TAAEbGVmdHEAfgAKTAAGcGFyZW50cQB+AApMAAVyaWdodHEAfgAKTAAFdmFsdWVxAH4ADXhwAHNyABFqYXZhLmxhbmcuSW50ZWdlchLioKT3gYc4AgABSQAFdmFsdWV4cgAQamF2YS5sYW5nLk51bWJlcoaslR0LlOCLAgAAeHAAAAABcHBzcQB+AAwBc3EAfgAPAAAAA3BxAH4ADnBzcQB+AA8AAAAGcQB+ABFzcQB+AANxAH4ACHEAfgALc3IACnNjYWxhLlNvbWURIvJpXqGLdAIAAUwAAXhxAH4ADXhyAAxzY2FsYS5PcHRpb27+aTf92w5mdAIAAHhwcQB+ABFzcQB+ABZzcQB+AA8AAAAC") + check(mutable.TreeSet())( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZVNldM10nxFQDpt4AgACTAAIb3JkZXJpbmd0ABVMc2NhbGEvbWF0aC9PcmRlcmluZztMACZzY2FsYSRjb2xsZWN0aW9uJG11dGFibGUkVHJlZVNldCQkdHJlZXQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJFRyZWU7eHBzcgAYc2NhbGEubWF0aC5PcmRlcmluZyRJbnQkC4BMdr1Z51wCAAB4cHNyACpzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuUmVkQmxhY2tUcmVlJFRyZWUATKc08DWmFQIAAkkABHNpemVMAARyb290dAAsTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9SZWRCbGFja1RyZWUkTm9kZTt4cAAAAABw") + check(mutable.TreeSet(1, 3))( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZVNldM10nxFQDpt4AgACTAAIb3JkZXJpbmd0ABVMc2NhbGEvbWF0aC9PcmRlcmluZztMACZzY2FsYSRjb2xsZWN0aW9uJG11dGFibGUkVHJlZVNldCQkdHJlZXQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJFRyZWU7eHBzcgAYc2NhbGEubWF0aC5PcmRlcmluZyRJbnQkC4BMdr1Z51wCAAB4cHNyACpzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuUmVkQmxhY2tUcmVlJFRyZWUATKc08DWmFQIAAkkABHNpemVMAARyb290dAAsTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9SZWRCbGFja1RyZWUkTm9kZTt4cAAAAAJzcgAqc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlJlZEJsYWNrVHJlZSROb2RlGxHsFtValgACAAZaAANyZWRMAANrZXl0ABJMamF2YS9sYW5nL09iamVjdDtMAARsZWZ0cQB+AAdMAAZwYXJlbnRxAH4AB0wABXJpZ2h0cQB+AAdMAAV2YWx1ZXEAfgAKeHAAc3IAEWphdmEubGFuZy5JbnRlZ2VyEuKgpPeBhzgCAAFJAAV2YWx1ZXhyABBqYXZhLmxhbmcuTnVtYmVyhqyVHQuU4IsCAAB4cAAAAAFwcHNxAH4ACQFzcQB+AAwAAAADcHEAfgALcHBw") + check(mutable.TreeSet(1, 3).range(1, 2))( "rO0ABXNyACxzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuVHJlZVNldCRUcmVlU2V0Vmlld2JdAzqy0DpGAgADTAAGJG91dGVydAAiTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9UcmVlU2V0O0wABGZyb210AA5Mc2NhbGEvT3B0aW9uO0wABXVudGlscQB+AAJ4cgAgc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlRyZWVTZXTNdJ8RUA6beAIAAkwACG9yZGVyaW5ndAAVTHNjYWxhL21hdGgvT3JkZXJpbmc7TAAmc2NhbGEkY29sbGVjdGlvbiRtdXRhYmxlJFRyZWVTZXQkJHRyZWV0ACxMc2NhbGEvY29sbGVjdGlvbi9tdXRhYmxlL1JlZEJsYWNrVHJlZSRUcmVlO3hwc3IAGHNjYWxhLm1hdGguT3JkZXJpbmckSW50JAuATHa9WedcAgAAeHBzcgAqc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLlJlZEJsYWNrVHJlZSRUcmVlAEynNPA1phUCAAJJAARzaXplTAAEcm9vdHQALExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUmVkQmxhY2tUcmVlJE5vZGU7eHAAAAACc3IAKnNjYWxhLmNvbGxlY3Rpb24ubXV0YWJsZS5SZWRCbGFja1RyZWUkTm9kZRsR7BbVWpYAAgAGWgADcmVkTAADa2V5dAASTGphdmEvbGFuZy9PYmplY3Q7TAAEbGVmdHEAfgAKTAAGcGFyZW50cQB+AApMAAVyaWdodHEAfgAKTAAFdmFsdWVxAH4ADXhwAHNyABFqYXZhLmxhbmcuSW50ZWdlchLioKT3gYc4AgABSQAFdmFsdWV4cgAQamF2YS5sYW5nLk51bWJlcoaslR0LlOCLAgAAeHAAAAABcHBzcQB+AAwBc3EAfgAPAAAAA3BxAH4ADnBwcHNxAH4AA3EAfgAIcQB+AAtzcgAKc2NhbGEuU29tZREi8mleoYt0AgABTAABeHEAfgANeHIADHNjYWxhLk9wdGlvbv5pN/3bDmZ0AgAAeHBxAH4AEXNxAH4AFXNxAH4ADwAAAAI=") // TODO SI-8576 Uninitialized field under -Xcheckinit // check(new mutable.History())( "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuSGlzdG9yeUhuXxDIFJrsAgACSQAKbWF4SGlzdG9yeUwAA2xvZ3QAIExzY2FsYS9jb2xsZWN0aW9uL211dGFibGUvUXVldWU7eHAAAAPoc3IAHnNjYWxhLmNvbGxlY3Rpb24ubXV0YWJsZS5RdWV1ZbjMURVfOuHHAgAAeHIAJHNjYWxhLmNvbGxlY3Rpb24ubXV0YWJsZS5NdXRhYmxlTGlzdFJpnjJ+gFbAAgADSQADbGVuTAAGZmlyc3QwdAAlTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9MaW5rZWRMaXN0O0wABWxhc3QwcQB+AAV4cAAAAABzcgAjc2NhbGEuY29sbGVjdGlvbi5tdXRhYmxlLkxpbmtlZExpc3Sak+nGCZHaUQIAAkwABGVsZW10ABJMamF2YS9sYW5nL09iamVjdDtMAARuZXh0dAAeTHNjYWxhL2NvbGxlY3Rpb24vbXV0YWJsZS9TZXE7eHBwcQB+AApxAH4ACg==") check(mutable.LinkedHashMap(1 -> 2))( "rO0ABXNyACZzY2FsYS5jb2xsZWN0aW9uLm11dGFibGUuTGlua2VkSGFzaE1hcAAAAAAAAAABAwAAeHB3DQAAAu4AAAABAAAABABzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAXNxAH4AAgAAAAJ4") 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 { diff --git a/test/files/scalacheck/MutableTreeSet.scala b/test/files/scalacheck/MutableTreeSet.scala new file mode 100644 index 0000000000..bcb1d0ed94 --- /dev/null +++ b/test/files/scalacheck/MutableTreeSet.scala @@ -0,0 +1,216 @@ +import java.io._ + +import org.scalacheck._ +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 + +package scala.collection.mutable { + + object MutableTreeSetProperties extends Properties("mutable.TreeSet") { + type K = String + + property("size, isEmpty") = forAll { (elems: Set[K]) => + val set = mutable.TreeSet[K]() + set ++= elems + set.size == elems.size && set.isEmpty == elems.isEmpty + } + + property("+=") = forAll { (set: mutable.TreeSet[K], k: K) => + val oldSize = set.size + val containedKeyBefore = set.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize else oldSize + 1 + + set += k + set.contains(k) && set.size == newExpectedSize + } + + property("++=") = forAll { (set: mutable.TreeSet[K], ks: Seq[K]) => + val oldElems = set.toList + set ++= ks + (oldElems ++ ks).forall(set.contains) + } + + property("-=") = forAll { (set: mutable.TreeSet[K], k: K) => + val oldSize = set.size + val containedKeyBefore = set.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize - 1 else oldSize + + set -= k + !set.contains(k) && set.size == newExpectedSize + } + + property("--=") = forAll { (set: mutable.TreeSet[K], ks: Seq[K]) => + val oldElems = set.toList + set --= ks + val deletedElems = ks.toSet + oldElems.forall { e => set.contains(e) == !deletedElems(e) } + } + + property("iterator") = forAll { (ks: Set[K]) => + val set = mutable.TreeSet[K]() + set ++= ks + + set.iterator.toSeq == ks.toSeq.sorted + } + + property("iteratorFrom, keysIteratorFrom") = forAll { (ks: Set[K], k: K) => + val set = mutable.TreeSet[K]() + set ++= ks + + set.iteratorFrom(k).toSeq == ks.filter(_ >= k).toSeq.sorted + set.keysIteratorFrom(k).toSeq == ks.filter(_ >= k).toSeq.sorted + } + + property("headOption") = forAll { (set: mutable.TreeSet[K]) => + set.headOption == Try(set.iterator.next()).toOption + } + + property("lastOption") = forAll { (set: mutable.TreeSet[K]) => + set.lastOption == Try(set.iterator.max).toOption + } + + property("clear") = forAll { (set: mutable.TreeSet[K]) => + set.clear() + set.isEmpty && set.size == 0 + } + + property("serializable") = forAll { (set: mutable.TreeSet[K]) => + val bytesOut = new ByteArrayOutputStream() + val out = new ObjectOutputStream(bytesOut) + out.writeObject(set) + val bytes = bytesOut.toByteArray + + val in = new ObjectInputStream(new ByteArrayInputStream(bytes)) + val sameSet = in.readObject().asInstanceOf[mutable.TreeSet[K]] + set.iterator.toSeq == sameSet.iterator.toSeq + } + + property("same behavior as immutable.TreeMap") = forAll { ops: Seq[Either[K, K]] => + var iset = immutable.TreeSet[K]() + val mset = mutable.TreeSet[K]() + + ops.foreach { + case Left(k) => iset += k; mset += k + case Right(k) => iset -= k; mset -= k + } + + iset.toList == mset.toList + } + } + + object MutableTreeSetViewProperties extends Properties("mutable.TreeSetView") { + type K = String + + implicit val ord = implicitly[Ordering[K]] + + def in(key: K, from: Option[K], until: Option[K]) = + from.fold(true)(_ <= key) && until.fold(true)(_ > key) + + def keysInView[This <: TraversableOnce[K], That](keys: This, from: Option[K], until: Option[K])(implicit bf: CanBuildFrom[This, K, That]) = { + (bf.apply(keys) ++= keys.filter(in(_, from, until))).result() + } + + property("size, isEmpty") = forAll { (keys: Set[K], from: Option[K], until: Option[K]) => + val map = mutable.TreeSet[K]() + map ++= keys + + val mapView = map.rangeImpl(from, until) + mapView.size == keysInView(keys, from, until).size && + mapView.isEmpty == !keys.exists(in(_, from, until)) + } + + property("+=") = forAll { (set: mutable.TreeSet[K], k: K, from: Option[K], until: Option[K]) => + val oldSize = set.size + val containedKeyBefore = set.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize else oldSize + 1 + val isInRange = in(k, from, until) + + val setView = set.rangeImpl(from, until) + setView += k + + set.contains(k) && set.size == newExpectedSize && setView.contains(k) == isInRange + } + + property("++=") = forAll { (set: mutable.TreeSet[K], ks: Seq[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + setView ++= ks + ks.toSet.forall { k => + set.contains(k) && setView.contains(k) == in(k, from, until) + } + } + + property("-=") = forAll { (set: mutable.TreeSet[K], k: K, from: Option[K], until: Option[K]) => + val oldSize = set.size + val containedKeyBefore = set.contains(k) + val newExpectedSize = if(containedKeyBefore) oldSize - 1 else oldSize + + val setView = set.rangeImpl(from, until) + setView -= k + + !set.contains(k) && set.size == newExpectedSize && !setView.contains(k) + } + + property("--=") = forAll { (set: mutable.TreeSet[K], ks: Seq[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + setView --= ks + ks.toSet.forall { k => !set.contains(k) && !setView.contains(k) } + } + + property("iterator") = forAll { (ks: Set[K], from: Option[K], until: Option[K]) => + val set = mutable.TreeSet[K]() + set ++= ks + + val setView = set.rangeImpl(from, until) + setView.iterator.toSeq == keysInView(ks, from, until).toSeq.sorted + } + + property("iteratorFrom, keysIteratorFrom") = forAll { (ks: Set[K], k: K, from: Option[K], until: Option[K]) => + val set = mutable.TreeSet[K]() + set ++= ks + + val setView = set.rangeImpl(from, until) + val newLower = Some(from.fold(k)(ord.max(_, k))) + setView.iteratorFrom(k).toSeq == keysInView(ks, newLower, until).toSeq.sorted + } + + property("headOption") = forAll { (set: mutable.TreeSet[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + setView.headOption == Try(keysInView(set.iterator, from, until).next()).toOption + } + + property("lastOption") = forAll { (set: mutable.TreeSet[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + setView.lastOption == Try(keysInView(set.iterator, from, until).max).toOption + } + + property("clear") = forAll { (set: mutable.TreeSet[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + setView.clear() + set.isEmpty && setView.isEmpty && set.size == 0 && setView.size == 0 + } + + property("serializable") = forAll { (set: mutable.TreeSet[K], from: Option[K], until: Option[K]) => + val setView = set.rangeImpl(from, until) + + val bytesOut = new ByteArrayOutputStream() + val out = new ObjectOutputStream(bytesOut) + out.writeObject(setView) + val bytes = bytesOut.toByteArray + + val in = new ObjectInputStream(new ByteArrayInputStream(bytes)) + val sameSetView = in.readObject().asInstanceOf[mutable.TreeSet[K]] + setView.iterator.toSeq == sameSetView.iterator.toSeq + } + } +} + +object Test extends Properties("mutable.TreeSet") { + import scala.collection.mutable._ + include(MutableTreeSetProperties) + include(MutableTreeSetViewProperties) +} diff --git a/test/junit/scala/collection/SetMapConsistencyTest.scala b/test/junit/scala/collection/SetMapConsistencyTest.scala index 5f14af7c37..eb864a8449 100644 --- a/test/junit/scala/collection/SetMapConsistencyTest.scala +++ b/test/junit/scala/collection/SetMapConsistencyTest.scala @@ -190,7 +190,9 @@ class SetMapConsistencyTest { def boxMbs = new BoxMutableSet[Int, cm.BitSet](new cm.BitSet, "mutable.BitSet") def boxMhs[A] = new BoxMutableSet[A, cm.HashSet[A]](new cm.HashSet[A], "mutable.HashSet") - + + def boxMts[A: Ordering] = new BoxMutableSet[A, cm.TreeSet[A]](new cm.TreeSet[A], "mutable.TreeSet") + def boxJavaS[A] = new BoxMutableSet[A, cm.Set[A]]((new java.util.HashSet[A]).asScala, "java.util.HashSet") { override def adders = 3 override def subbers = 1 @@ -354,7 +356,7 @@ class SetMapConsistencyTest { def churnIntSets() { val sets = Array[() => MapBox[Int]]( () => boxMhm[Int], () => boxIhm[Int], () => boxJavaS[Int], - () => boxMbs, () => boxMhs[Int], () => boxIbs, () => boxIhs[Int], () => boxIls[Int], () => boxIts[Int] + () => boxMbs, () => boxMhs[Int], () => boxMts[Int], () => boxIbs, () => boxIhs[Int], () => boxIls[Int], () => boxIts[Int] ) assert( sets.sliding(2).forall{ ms => churn(ms(0)(), ms(1)(), smallKeys, 1000, valuer = _ => 0) } ) } |