From 8cf889f06cb83f322ff3892175e978c25cd41d43 Mon Sep 17 00:00:00 2001 From: Lucien Pereira Date: Sat, 14 Jan 2012 09:52:41 +0100 Subject: syntactic error correction --- src/library/scala/collection/mutable/TreeSet.scala | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src') diff --git a/src/library/scala/collection/mutable/TreeSet.scala b/src/library/scala/collection/mutable/TreeSet.scala index 38fa0c953f..56b4b349cf 100644 --- a/src/library/scala/collection/mutable/TreeSet.scala +++ b/src/library/scala/collection/mutable/TreeSet.scala @@ -98,7 +98,7 @@ class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with S } /** - * Thanks to the nature immutable of the + * Thanks to the immutable nature of the * underlying AVL Tree, we can share it with * the clone. So clone complexity in time is O(1). * -- cgit v1.2.3 From b0fc4958a53500a329be4831f47e79f64074a5f1 Mon Sep 17 00:00:00 2001 From: Lucien Pereira Date: Sun, 15 Jan 2012 16:40:16 +0100 Subject: Getting rid of closure creation occuring for each rebalancing. Tail recursion is not necessary here. --- src/library/scala/collection/mutable/AVLTree.scala | 62 ++++++++++------------ 1 file changed, 28 insertions(+), 34 deletions(-) (limited to 'src') diff --git a/src/library/scala/collection/mutable/AVLTree.scala b/src/library/scala/collection/mutable/AVLTree.scala index 0cf6cb06e5..f0a6c690b6 100644 --- a/src/library/scala/collection/mutable/AVLTree.scala +++ b/src/library/scala/collection/mutable/AVLTree.scala @@ -9,7 +9,6 @@ package scala.collection package mutable -import annotation.tailrec /** * An immutable AVL Tree implementation used by mutable.TreeSet @@ -45,21 +44,16 @@ private[mutable] object AVLTree { * 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)))) - } - } + def insert[A](value: A, tree: AVLTree[A], ordering: Ordering[A]): AVLTree[A] = tree match { + case Leaf => Node(value, Leaf, Leaf) - insertTC(value, tree, x => rebalance(x)) + case Node(a, left, right) => if (0 == ordering.compare(value, a)) { + throw new IllegalArgumentException() + } else if (-1 == ordering.compare(value, a)) { + rebalance(Node(a, insert(value, left, ordering), right)) + } else { + rebalance(Node(a, left, insert(value, right, ordering))) + } } def contains[A](value: A, tree: AVLTree[A], ordering: Ordering[A]): Boolean = tree match { @@ -96,7 +90,7 @@ private[mutable] object AVLTree { rebalance(Node(a, left, remove(value, right, ordering))) } - case Node(a, left@Node(_, _, _), right) => if (0 == ordering.compare(value, a)) { + case Node(a, left: Node[A], right) => if (0 == ordering.compare(value, a)) { val (max, newLeft) = removeMax(left) rebalance(Node(max, newLeft, right)) } else if (-1 == ordering.compare(value, a)) { @@ -111,17 +105,17 @@ private[mutable] object AVLTree { * 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.") + def removeMax[A](tree: AVLTree[A]): (A, AVLTree[A]) = tree match { + case Node(a, Leaf, Leaf) => (a, Leaf) + + case Node(a, left, Leaf) => (a, left) + + case Node(a, left, right) => { + val (max, newRight) = removeMax(right) + (max, rebalance(Node(a, left, newRight))) } - removeMaxTC(tree, (a, b) => (a, b)) + case Leaf => sys.error("Should not happen.") } /** @@ -129,17 +123,17 @@ private[mutable] object AVLTree { * 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.") + def removeMin[A](tree: AVLTree[A]): (A, AVLTree[A]) = tree match { + case Node(a, Leaf, Leaf) => (a, Leaf) + + case Node(a, Leaf, right) => (a, right) + + case Node(a, left, right) => { + val (min, newLeft) = removeMin(left) + (min, rebalance(Node(a, newLeft, right))) } - removeMinTC(tree, (a, b) => (a, b)) + case Leaf => sys.error("Should not happen.") } /** -- cgit v1.2.3 From 1c963535daf42a636030f6e905c7c4529744e0c3 Mon Sep 17 00:00:00 2001 From: Lucien Pereira Date: Sat, 28 Jan 2012 14:13:17 +0100 Subject: Use of polymorphic dispatch instead of pattern matching. Use a specialized iterator. --- src/library/scala/collection/mutable/AVLTree.scala | 281 ++++++++++++--------- src/library/scala/collection/mutable/TreeSet.scala | 14 +- 2 files changed, 168 insertions(+), 127 deletions(-) (limited to 'src') diff --git a/src/library/scala/collection/mutable/AVLTree.scala b/src/library/scala/collection/mutable/AVLTree.scala index f0a6c690b6..ba2af8f120 100644 --- a/src/library/scala/collection/mutable/AVLTree.scala +++ b/src/library/scala/collection/mutable/AVLTree.scala @@ -21,180 +21,221 @@ private[mutable] sealed trait AVLTree[+A] extends Serializable { def depth: Int -} + def iterator[B >: A]: Iterator[B] = Iterator.empty -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 + def contains[B >: A](value: B, ordering: Ordering[B]): Boolean = false - override val depth: Int = math.max(left.depth, right.depth) + 1 + /** + * Returns a new tree containing the given element. + * Thows an IllegalArgumentException if element is already present. + * + */ + def insert[B >: A](value: B, ordering: Ordering[B]): AVLTree[B] = Node(value, Leaf, Leaf) + + /** + * Return a new tree which not contains given element. + * + */ + def remove[B >: A](value: B, ordering: Ordering[B]): AVLTree[A] = + throw new NoSuchElementException(String.valueOf(value)) + + /** + * Return a tuple containing the smallest element of the provided tree + * and a new tree from which this element has been extracted. + * + */ + def removeMin[B >: A]: (B, AVLTree[B]) = sys.error("Should not happen.") + + /** + * Return a tuple containing the biggest element of the provided tree + * and a new tree from which this element has been extracted. + * + */ + def removeMax[B >: A]: (B, AVLTree[B]) = sys.error("Should not happen.") + + def rebalance[B >: A]: AVLTree[B] = this + + def leftRotation[B >: A]: Node[B] = sys.error("Should not happen.") + + def rightRotation[B >: A]: Node[B] = sys.error("Should not happen.") + + def doubleLeftRotation[B >: A]: Node[B] = sys.error("Should not happen.") + def doubleRightRotation[B >: A]: Node[B] = sys.error("Should not happen.") } private case object Leaf extends AVLTree[Nothing] { override val balance: Int = 0 override val depth: Int = -1 - } -private[mutable] object AVLTree { +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 + + override def iterator[B >: A]: Iterator[B] = new AVLIterator(this) + + override def contains[B >: A](value: B, ordering: Ordering[B]) = { + val ord = ordering.compare(value, data) + if (0 == ord) + true + else if (ord < 0) + left.contains(value, ordering) + else + right.contains(value, ordering) + } /** * 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] = tree match { - case Leaf => Node(value, Leaf, Leaf) - - case Node(a, left, right) => if (0 == ordering.compare(value, a)) { + override def insert[B >: A](value: B, ordering: Ordering[B]) = { + val ord = ordering.compare(value, data) + if (0 == ord) throw new IllegalArgumentException() - } else if (-1 == ordering.compare(value, a)) { - rebalance(Node(a, insert(value, left, ordering), right)) - } else { - rebalance(Node(a, left, insert(value, right, ordering))) - } - } - - 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) - } + else if (ord < 0) + Node(data, left.insert(value, ordering), right).rebalance + else + Node(data, left, right.insert(value, ordering)).rebalance } /** * 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[A], 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)) + override def remove[B >: A](value: B, ordering: Ordering[B]): AVLTree[A] = { + val ord = ordering.compare(value, data) + if(ord == 0) { + if (Leaf == left) { + if (Leaf == right) { + Leaf + } else { + val (min, newRight) = right.removeMin + Node(min, left, newRight).rebalance + } + } else { + val (max, newLeft) = left.removeMax + Node(max, newLeft, right).rebalance + } + } else if (ord < 0) { + Node(data, left.remove(value, ordering), right).rebalance } else { - rebalance(Node(a, left, remove(value, right, ordering))) + Node(data, left, right.remove(value, ordering)).rebalance } } /** - * Return a tuple containing the biggest element of the provided tree + * Return a tuple containing the smallest element of the provided tree * and a new tree from which this element has been extracted. * */ - def removeMax[A](tree: AVLTree[A]): (A, AVLTree[A]) = tree match { - case Node(a, Leaf, Leaf) => (a, Leaf) - - case Node(a, left, Leaf) => (a, left) - - case Node(a, left, right) => { - val (max, newRight) = removeMax(right) - (max, rebalance(Node(a, left, newRight))) + override def removeMin[B >: A]: (B, AVLTree[B]) = { + if (Leaf == left) + (data, right) + else { + val (min, newLeft) = left.removeMin + (min, Node(data, newLeft, right).rebalance) } - - case Leaf => sys.error("Should not happen.") } /** - * Return a tuple containing the smallest element of the provided tree + * Return a tuple containing the biggest element of the provided tree * and a new tree from which this element has been extracted. * */ - def removeMin[A](tree: AVLTree[A]): (A, AVLTree[A]) = tree match { - case Node(a, Leaf, Leaf) => (a, Leaf) - - case Node(a, Leaf, right) => (a, right) - - case Node(a, left, right) => { - val (min, newLeft) = removeMin(left) - (min, rebalance(Node(a, newLeft, right))) + override def removeMax[B >: A]: (B, AVLTree[B]) = { + if (Leaf == right) + (data, left) + else { + val (max, newRight) = right.removeMax + (max, Node(data, left, newRight).rebalance) } - - case Leaf => sys.error("Should not happen.") } - - /** - * 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) + + override def rebalance[B >: A] = { + if (-2 == balance) { + if (1 == left.balance) + doubleRightRotation + else + rightRotation + } else if (2 == balance) { + if (-1 == right.balance) + doubleLeftRotation + else + leftRotation } else { - Stream.empty + this } } - /** - * 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) - } + override def leftRotation[B >: A] = { + if (Leaf != right) { + val r: Node[A] = right.asInstanceOf[Node[A]] + Node(r.data, Node(data, left, r.left), r.right) + } else sys.error("Should not happen.") + } - case _ => tree + override def rightRotation[B >: A] = { + if (Leaf != left) { + val l: Node[A] = left.asInstanceOf[Node[A]] + Node(l.data, l.left, Node(data, l.right, right)) + } else sys.error("Should not happen.") } - 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.") + override def doubleLeftRotation[B >: A] = { + if (Leaf != right) { + val r: Node[A] = right.asInstanceOf[Node[A]] + // Let's save an instanceOf by 'inlining' the left rotation + val rightRotated = r.rightRotation + Node(rightRotated.data, Node(data, left, rightRotated.left), rightRotated.right) + } else 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.") + override def doubleRightRotation[B >: A] = { + if (Leaf != left) { + val l: Node[A] = left.asInstanceOf[Node[A]] + // Let's save an instanceOf by 'inlining' the right rotation + val leftRotated = l.leftRotation + Node(leftRotated.data, leftRotated.left, Node(data, leftRotated.right, right)) + } else sys.error("Should not happen.") } +} + +private class AVLIterator[A](root: Node[A]) extends Iterator[A] { + val stack = mutable.ArrayStack[Node[A]](root) + diveLeft() - 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.") + private def diveLeft(): Unit = { + if (Leaf != stack.head.left) { + val left: Node[A] = stack.head.left.asInstanceOf[Node[A]] + stack.push(left) + diveLeft() + } } - 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.") + private def engageRight(): Unit = { + if (Leaf != stack.head.right) { + val right: Node[A] = stack.head.right.asInstanceOf[Node[A]] + stack.pop + stack.push(right) + diveLeft() + } else + stack.pop } + override def hasNext: Boolean = !stack.isEmpty + + override def next(): A = { + if (stack.isEmpty) + throw new NoSuchElementException() + else { + val result = stack.head.data + // Let's maintain stack for the next invocation + engageRight() + result + } + } } diff --git a/src/library/scala/collection/mutable/TreeSet.scala b/src/library/scala/collection/mutable/TreeSet.scala index 56b4b349cf..e0f1c3adfe 100644 --- a/src/library/scala/collection/mutable/TreeSet.scala +++ b/src/library/scala/collection/mutable/TreeSet.scala @@ -79,7 +79,7 @@ class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with S override def -=(elem: A): this.type = { try { - resolve.avl = AVLTree.remove(elem, resolve.avl, ordering) + resolve.avl = resolve.avl.remove(elem, ordering) resolve.cardinality = resolve.cardinality - 1 } catch { case e: NoSuchElementException => () @@ -89,7 +89,7 @@ class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with S override def +=(elem: A): this.type = { try { - resolve.avl = AVLTree.insert(elem, resolve.avl, ordering) + resolve.avl = resolve.avl.insert(elem, ordering) resolve.cardinality = resolve.cardinality + 1 } catch { case e: IllegalArgumentException => () @@ -113,11 +113,11 @@ class TreeSet[A](implicit val ordering: Ordering[A]) extends SortedSet[A] with S override def contains(elem: A): Boolean = { isLeftAcceptable(from, ordering)(elem) && isRightAcceptable(until, ordering)(elem) && - AVLTree.contains(elem, resolve.avl, ordering) + resolve.avl.contains(elem, ordering) } - override def iterator: Iterator[A] = - AVLTree.iterator(resolve.avl, - isLeftAcceptable(from, ordering), - isRightAcceptable(until, ordering)) + override def iterator: Iterator[A] = resolve.avl.iterator + .dropWhile(e => !isLeftAcceptable(from, ordering)(e)) + .takeWhile(e => isRightAcceptable(until, ordering)(e)) + } -- cgit v1.2.3