diff options
author | aleksandar <aleksandar@lampmac14.epfl.ch> | 2012-01-12 15:28:25 +0100 |
---|---|---|
committer | aleksandar <aleksandar@lampmac14.epfl.ch> | 2012-01-12 15:30:42 +0100 |
commit | 51ddeb372b3f0b22041d9a51f3faee17acd7b749 (patch) | |
tree | 5f1156ed34f7cc429189e18cc88782f13a3bfc86 | |
parent | 178d49df450904330c06cfea9955f120ba04d34c (diff) | |
download | scala-51ddeb372b3f0b22041d9a51f3faee17acd7b749.tar.gz scala-51ddeb372b3f0b22041d9a51f3faee17acd7b749.tar.bz2 scala-51ddeb372b3f0b22041d9a51f3faee17acd7b749.zip |
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.
-rw-r--r-- | .gitignore | 2 | ||||
-rw-r--r-- | src/library/scala/collection/generic/MutableSortedSetFactory.scala | 33 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/AVLTree.scala | 206 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/SortedSet.scala | 49 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/TreeSet.scala | 130 | ||||
-rw-r--r-- | test/benchmarking/AVL-insert-random.scala | 67 | ||||
-rw-r--r-- | test/benchmarking/AVL-insert.scala | 67 | ||||
-rw-r--r-- | test/files/jvm/serialization.check | 4 | ||||
-rw-r--r-- | test/files/jvm/serialization.scala | 7 | ||||
-rw-r--r-- | test/files/run/si4147.scala | 36 | ||||
-rw-r--r-- | test/files/scalacheck/si4147.scala | 67 |
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]() + } + } +} |