diff options
author | Seth Tisue <seth@tisue.net> | 2015-08-06 15:40:10 -0700 |
---|---|---|
committer | Seth Tisue <seth@tisue.net> | 2015-08-06 15:40:10 -0700 |
commit | 2f7a622e2de688f6b79bb6270020bc99445bada8 (patch) | |
tree | 43ced2d6076f1959a3d05e220567aa4f464e4c92 /src | |
parent | 466821defd57f1d99cf4852e2b9c374979a05f98 (diff) | |
parent | c15259091d43c82053bcacf206eba5da6bc56fe5 (diff) | |
download | scala-2f7a622e2de688f6b79bb6270020bc99445bada8.tar.gz scala-2f7a622e2de688f6b79bb6270020bc99445bada8.tar.bz2 scala-2f7a622e2de688f6b79bb6270020bc99445bada8.zip |
Merge pull request #4608 from ruippeixotog/improve-mutable-treeset
SI-6938 Use mutable red-black tree in `mutable.TreeSet`
Diffstat (limited to 'src')
4 files changed, 182 insertions, 54 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) } } |