Getting rid of closure creation occuring for each rebalancing. Tail recursion is not necessary here.

1 files changed, 28 insertions, 34 deletions

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.")
   }
 
   /**