Bugfixes to Tree and TreeMap

5 files changed, 133 insertions, 141 deletions

diff --git a/sources/scala/collection/immutable/Order.scala b/sources/scala/collection/immutable/Order.scala
index eae120b76d..ee733e98f4 100644
--- a/sources/scala/collection/immutable/Order.scala
+++ b/sources/scala/collection/immutable/Order.scala
@@ -10,8 +10,8 @@
 package scala.collection.immutable;
 
 class Order[t](less:(t,t) => Boolean,equal:(t,t) => Boolean) {
-    def lt (e1:t, e2:t) = less(e1,e2);
+    def lt  (e1:t, e2:t) = less(e1,e2);
     def leq (e1:t, e2:t) = less(e1,e2) || equal(e1,e2);
-    def gt (e1:t, e2:t) = less(e2,e1);
+    def gt  (e1:t, e2:t) = less(e2,e1);
     def geq (e1:t, e2:t) = leq(e2,e1);
 }
diff --git a/sources/scala/collection/immutable/Tree.scala b/sources/scala/collection/immutable/Tree.scala
index 0f1b715512..4a3d8cc3d9 100644
--- a/sources/scala/collection/immutable/Tree.scala
+++ b/sources/scala/collection/immutable/Tree.scala
@@ -32,13 +32,11 @@
 ** USA
 **
 ** Author contact: erik.stenman@epfl.ch
-**                 (svenolof@csd.uu.se, richardc@csd.uu.se)
 ** ---------------------------------------------------------------------
 */
 
 package scala.collection.immutable;
 
-
 /** General Balanced Trees - highly efficient functional dictionaries.
 **
 ** An efficient implementation of Prof. Arne Andersson's General
@@ -56,64 +54,67 @@ package scala.collection.immutable;
 **  @version 1.0, 10/07/2003
 */
 
-class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) {
-    /* Data structure:
-    ** - Size:int - the number of elements in the tree.
-    ** - Tree:T, which is composed of nodes of the form:
-    **   - Node(Key, Value, Smaller, Bigger), and the "empty tree" node:
-    **   - Nil().
-    **
-    ** Original balance condition h(T) <= ceil(c * log(|T|)) has been
-    ** changed to the similar (but not quite equivalent) condition 2 ^ h(T)
-    ** <= |T| ^ c. I figure this should also be OK.
-    **
-    */
 
-    protected type aNode = Tree[KEY,Entry]#T;
-    protected type anInsertTree = Tree[KEY,Entry]#InsertTree;
-    protected val tree:aNode = Nil();
-
-    /** The size of the tree, returns 0 (zero) if the tree is empty.
-     ** @Returns The number of nodes in the tree as an integer.
-     **/
-    def size = 0;
-
-    /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-     * Factory method to create new trees.
-     */
-    private def mkTree(sz:int,t:aNode):Tree[KEY,Entry] =
-	new Tree[KEY,Entry](order,entryKey){
-	    override def size=sz;
-	    override protected val tree:aNode=t;
-	};
-    /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% */
-
-
-    /** Create a new balanced tree from the tree.
-     *  Might be useful to call after many deletions,
-     *  since deletion does not rebalance the tree.
-     **/
-    def balance = mkTree(size,tree.balance(size));
-
-
-
-    // The iterator structure is really just a list corresponding to
-    // the call stack of an in-order traversal.
-    //
-    // Note: The iterator has a state, i.e., it is not functional.
-    def entries:Iterator[Entry] =
-	new Iterator[Entry] {
-	    var iter = tree.mk_iter(scala.Nil);
-	    def hasNext = !iter.isEmpty;
-	    def next =
-	    iter.match {
-		case (Node(v,_,t)::iter_tail) =>
-		iter= iter_tail;
-		v;
-		case scala.Nil =>
-		error("next on empty iterator");
-	    }
+
+class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) {
+  /* Data structure:
+  ** - Size:int - the number of elements in the tree.
+  ** - Tree:T, which is composed of nodes of the form:
+  **   - Node(Key, Value, Smaller, Bigger), and the "empty tree" node:
+  **   - Nil().
+  **
+  ** Original balance condition h(T) <= ceil(c * log(|T|)) has been
+  ** changed to the similar (but not quite equivalent) condition 2 ^ h(T)
+  ** <= |T| ^ c. I figure this should also be OK.
+  **
+  */
+
+  protected type aNode = Tree[KEY,Entry]#T;
+  protected type anInsertTree = Tree[KEY,Entry]#InsertTree;
+  protected val tree:aNode = Nil();
+
+  /** The size of the tree, returns 0 (zero) if the tree is empty.
+  ** @Returns The number of nodes in the tree as an integer.
+  **/
+  def size = 0;
+
+  /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+  * Factory method to create new trees.
+  */
+  private def mkTree(sz:int,t:aNode):Tree[KEY,Entry] =
+    new Tree[KEY,Entry](order,entryKey){
+      override def size=sz;
+      override protected val tree:aNode=t;
+    };
+  /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% */
+
+
+  /** Create a new balanced tree from the tree.
+  *  Might be useful to call after many deletions,
+  *  since deletion does not rebalance the tree.
+  **/
+  def balance = mkTree(size,tree.balance(size));
+
+
+
+  // The iterator structure is really just a list corresponding to
+  // the call stack of an in-order traversal.
+  //
+  // Note: The iterator has a state, i.e., it is not functional.
+  def entries:Iterator[Entry] =
+    new Iterator[Entry] {
+      var iter = tree.mk_iter(scala.Nil);
+      def hasNext = !iter.isEmpty;
+      def next =
+	iter.match {
+	  case (Node(v,_,t)::iter_tail) => {
+	    iter= t.mk_iter(iter_tail);
+            v;
+	  }
+          case scala.Nil =>
+            error("next on empty iterator");
 	}
+    }
 
 
   private abstract class T() {
@@ -132,79 +133,75 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) {
     def balance(s:int) = balance_list(toList(scala.Nil), s);
 
     private def balance_list(list:List[Entry], s:int) = {
-	val Pair(t, _) = balance_list_1(list, s);
-	t;
+      val Pair(t, _) = balance_list_1(list, s);
+      t;
     }
 
     private def balance_list_1(list:List[Entry], s:int):
-	Pair[aNode,List[Entry]] = {
-	    if(s > 1) {
-		val sm = s - 1;
-		val s2 = div2(sm);
-		val s1 = sm - s2;
-		val Pair(t1,v::l1) = balance_list_1(list, s1);
-		val Pair(t2, l2) = balance_list_1(l1, s2);
-		val t = Node(v, t1, t2);
-		Pair(t, l2);
-	    } else
-	    if(s == 1) {
-		val v = list.head;
-		Pair(Node(v,Nil(),Nil()), list.tail);
-	    } else
-	    Pair(Nil(),list);
-	}
-
-
-
+    Pair[aNode,List[Entry]] = {
+      if(s > 1) {
+	val sm = s - 1;
+	val s2 = div2(sm);
+	val s1 = sm - s2;
+	val Pair(t1,v::l1) = balance_list_1(list, s1);
+	val Pair(t2, l2) = balance_list_1(l1, s2);
+	val t = Node(v, t1, t2);
+	Pair(t, l2);
+      } else
+	if(s == 1) {
+	  val v = list.head;
+	  Pair(Node(v,Nil(),Nil()), list.tail);
+	} else
+	  Pair(Nil(),list);
+    }
   }
 
 
 
-  private case class Node(value:Entry,smaller:aNode,bigger:aNode)
-	extends T {
-      def count:Info = {
-	  if (smaller == Nil() && bigger == Nil())
-	  Info(1,1);
-	  else {
-	      val sInfo = smaller.count;
-	      val bInfo = bigger.count;
-	      Info(mul2(max(sInfo.height,bInfo.height)),
-		       sInfo.size + bInfo.size +1);
-	  }
+  private case class Node(value:Entry,smaller:aNode,bigger:aNode) extends T {
+    def count:Info = {
+      if (smaller == Nil() && bigger == Nil()) Info(1,1);
+      else {
+	val sInfo = smaller.count;
+	val bInfo = bigger.count;
+	Info(mul2(max(sInfo.height,bInfo.height)),
+	     sInfo.size + bInfo.size +1);
       }
+    }
 
-      def is_defined(key:KEY):Boolean =
-	  if(order.lt(key,entryKey(value))) smaller.is_defined(key);
-	  else if (order.gt(key,entryKey(value))) bigger.is_defined(key);
-	  else true;
-
-      def get(key:KEY):Option[Entry] =
-	  if (order.lt(key,entryKey(value))) smaller.get(key);
-	  else if (order.gt(key,entryKey(value))) bigger.get(key);
-	  else Some(value);
-
-      def apply(key:KEY):Entry =
-	  if (order.lt(key,entryKey(value))) smaller.apply(key);
-	  else if (order.gt(key,entryKey(value))) bigger.apply(key);
-	  else value;
-
-      def update(key:KEY, newValue:Entry):aNode =
-	  if (order.lt(key,entryKey(value)))
-	      Node(value, smaller.update(key,newValue), bigger);
-	  else if (order.gt(key,entryKey(value)))
-	      Node(value, smaller, bigger.update(key,newValue));
-	  else
-	      this;
-
-      def insert(key:KEY, newValue:Entry, s:int):anInsertTree =
-	  if(order.lt(key,entryKey(value)))
-	      smaller.insert(key, newValue, div2(s)).insert_left(value,bigger);
-	  else if(order.gt(key,entryKey(value)))
-	      bigger.insert(key, value, div2(s)).insert_right(value,smaller);
-	  else error("Key exists" + key);
+    def is_defined(key:KEY):Boolean = {
+      if(order.lt(key,entryKey(value))) smaller.is_defined(key)
+      else if(order.gt(key,entryKey(value))) bigger.is_defined(key)
+      else true;
+    }
+    def get(key:KEY):Option[Entry] =
+      if (order.lt(key,entryKey(value))) smaller.get(key);
+      else if (order.gt(key,entryKey(value))) bigger.get(key);
+      else Some(value);
+
+    def apply(key:KEY):Entry =
+      if (order.lt(key,entryKey(value))) smaller.apply(key);
+      else if (order.gt(key,entryKey(value))) bigger.apply(key);
+      else value;
+
+    def update(key:KEY, newValue:Entry):aNode =
+      if (order.lt(key,entryKey(value)))
+	Node(value, smaller.update(key,newValue), bigger);
+      else if (order.gt(key,entryKey(value)))
+	Node(value, smaller, bigger.update(key,newValue));
+      else
+	Node(newValue, smaller, bigger);
+
+    def insert(key:KEY, newValue:Entry, s:int):anInsertTree = {
+      if(order.lt(key,entryKey(value)))
+	smaller.insert(key, newValue, div2(s)).insert_left(value,bigger);
+      else if(order.gt(key,entryKey(value)))
+	bigger.insert(key, newValue, div2(s)).insert_right(value,smaller);
+      else error("Key exists" + key);
+    }
 
-      def toList(acc:List[Entry]):List[Entry] =
-	  smaller.toList(value::bigger.toList(acc));
+    def toList(acc:List[Entry]):List[Entry] =
+      smaller.toList(value::bigger.toList(acc));
 
       def mk_iter(iter_tail:List[aNode]):List[aNode] =
 	  if (smaller == Nil()) this::iter_tail;
@@ -241,7 +238,7 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) {
 
     private case class Nil() extends T {
 	def count = Info(1,0);
-	def is_defined(_key:KEY) = false;
+	def is_defined(key:KEY) = false;
 	def get(_key:KEY) = None;
 	def apply(key:KEY) = error("key " + key + "not found");
 	def update(key:KEY, value:Entry) = error("key " + key + "not found");
@@ -264,10 +261,9 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) {
     */
     protected val p = 2; // It seems that p = 2 is optimal for sorted keys */
     protected def pow(a:int, b:int):int =
-      b.match {
+	b.match {
 	    case 2 => a * a;
 	    case 1 => a;
-            case 0 => 1;
 	    case x if x > 0 => a * pow(a, b-1);
 	};
     private def div2(x:int) = x >> 1;
@@ -289,17 +285,17 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) {
 	    ITree(Node(value,smaller,t));
 	def node = t;
     }
-    private case class INode(t1:aNode,height:int,size:int) extends InsertTree{
+    private case class INode(t1:aNode,height:int,siz:int) extends InsertTree{
 	def insert_left(value:Entry,bigger:aNode) = {
-	    insert(Node(value, t1, bigger), bigger);
+	    balance_p(Node(value, t1, bigger), bigger);
 	}
 	def insert_right(value:Entry,smaller:aNode) = {
-	    insert(Node(value, smaller, t1),smaller);
+	    balance_p(Node(value, smaller, t1),smaller);
 	}
-	private def insert(t:aNode,subtree:aNode):anInsertTree = {
+	private def balance_p(t:aNode,subtree:aNode):anInsertTree = {
 	    val info = subtree.count;
 	    val totalHeight = mul2(max(height, info.height));
-	    val totalSize = size + info.size + 1;
+	    val totalSize = siz + info.size + 1;
 	    val BalanceHeight = pow(totalSize, p);
 	    if(totalHeight > BalanceHeight) ITree(t.balance(totalSize));
 	    else INode(t, totalHeight, totalSize);
@@ -308,4 +304,3 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) {
     }
 
 }
-
diff --git a/sources/scala/collection/immutable/TreeMap.scala b/sources/scala/collection/immutable/TreeMap.scala
index 35437e80cc..d25657df92 100644
--- a/sources/scala/collection/immutable/TreeMap.scala
+++ b/sources/scala/collection/immutable/TreeMap.scala
@@ -25,13 +25,12 @@ class TreeMap[KEY,VALUE](order:Order[KEY]) extends
 	new TreeMap[KEY,VALUE](order){
 	    override def size=sz;
 	    override protected val tree:aNode=t;
-	};
-
+	}
 
     def update(key:KEY, value:VALUE):TreeMap[KEY,VALUE] = {
-	if(contains(key)) mkTreeMap(size,tree.update(key,Pair(key,value)))
+       if(contains(key)) mkTreeMap(size,tree.update(key,Pair(key,value)))
 	else insert(key,value);
-    }
+     }
 
     def insert(key:KEY,value:VALUE) = {
 	val newSize = size+1;
diff --git a/test/files/run/map_test.check b/test/files/run/map_test.check
index a8585769e8..a788c0fbca 100644
--- a/test/files/run/map_test.check
+++ b/test/files/run/map_test.check
@@ -1,3 +1,3 @@
-{42 -> The answer, 17 -> A small random number, 666 -> A bigger random number, 4711 -> A big random number}
+0->0 1->1 2->2 3->3 4->4 5->5 6->6 7->7 8->8 9->9 10->10 11->11 12->12 13->13 14->14 15->15 16->16 17->17 18->18 19->19 20->20 21->21 22->22 23->23 24->24 25->25 26->26 27->27 28->28 29->29 30->30 31->31 32->32 33->33 34->34 35->35 36->36 37->37 38->38 39->39 40->40 41->41 42->42 666->A bigger random number 4711->A big random number 
 0->0 1->1 2->2 3->3 4->4 5->5 6->6 7->7 8->8 9->9 10->10 11->11 12->12 13->13 14->14 15->15 16->16 17->17 18->18 19->19 20->20 21->21 22->22 23->23 24->24 25->25 26->26 27->27 28->28 29->29 30->30 31->31 32->32 33->33 34->34 35->35 36->36 37->37 38->38 39->39 40->40 41->41 42->42 666->A bigger random number 4711->A big random number 
 OK
diff --git a/test/files/run/map_test.scala b/test/files/run/map_test.scala
index 9c4bd2814e..7e91955317 100644
--- a/test/files/run/map_test.scala
+++ b/test/files/run/map_test.scala
@@ -9,14 +9,13 @@ object Test with Executable {
 
     test1();
     test2();
-
     Console.println("OK");
 
 
 
     def test1() = {
 	val myMap:TreeMap[int,String] = new TreeMap(intOrder);
-	test_map(myMap);
+        test_map(myMap);
     }
 
     def test2() = {
@@ -29,8 +28,7 @@ object Test with Executable {
 	val map2 = map1.update(17,"A small random number");
 	val map3 = map2.update(666,"A bigger random number");
 	val map4 = map3.update(4711,"A big random number");
-	//	val map1 = myMap + 42 -> "The answer";
-	Console.println(map4);
+	map1 == myMap + 42 -> "The answer";
 	var i = 0;
 	var map = map4;
 	while(i < 43) {