Cleanup and commenting of library

5 files changed, 552 insertions, 295 deletions

diff --git a/sources/scala/collection/immutable/ListMap.scala b/sources/scala/collection/immutable/ListMap.scala
index a0e7339b69..5e80447a3d 100644
--- a/sources/scala/collection/immutable/ListMap.scala
+++ b/sources/scala/collection/immutable/ListMap.scala
@@ -9,6 +9,9 @@
 
 package scala.collection.immutable;
 
+class ListMapFactory[A] with MapFactory[A] {
+  def Empty[B] = ListMap.Empty[A,B];
+}
 
 object ListMap {
   def Empty[A, B] = new ListMap[A, B];
@@ -30,54 +33,123 @@ object ListMap {
  *  @version 1.0, 09/07/2003
  */
 class ListMap[A, B] with Map[A, B] {
+  val factory = new ListMapFactory[A];
 
-    def size: Int = 0;
+  /** Returns the number of mappings in this map.
+  *
+  *  @return number of mappings.
+  */
+  def size: Int = 0;
 
-    def get(key: A): Option[B] = None;
+  /** Check if this map maps <code>key</code> to a value and return the
+  *  value if it exists.
+  *
+  *  @param  key     the key of the mapping of interest
+  *  @return the value of the mapping, if it exists
+  */
+  def get(key: A): Option[B] = None;
 
-    def update(key: A, value: B): ListMap[A, B] = new Node(key, value);
+  /** This method allows one to create a new map with an
+  *  additional mapping from <code>key</code>
+  *  to <code>value</code>. If the map contains already a
+  *  mapping for <code>key</code>, it will be overridden by this
+  *  function.
+  */
+  def update(key: A, value: B): ListMap[A, B] = new Node(key, value);
 
-    def -(key: A): ListMap[A, B] = this;
+  /** This creates a new mapping without the given <code>key</code>.
+  *  If the map does not contain a mapping for the given key, the
+  *  method returns the same map.
+  */
+  def -(key: A): ListMap[A, B] = this;
 
-    def elements: Iterator[Pair[A, B]] = toList.elements;
+  /** This returns an iterator over key-value pairs.
+  */
+  def elements: Iterator[Pair[A, B]] = toList.elements;
 
-    override def toList: List[Pair[A, B]] = Nil;
+  /** This return a list of key-value pairs.
+  */
+  override def toList: List[Pair[A, B]] = Nil;
 
-    override def equals(obj: Any): Boolean =
-        if (obj.isInstanceOf[scala.collection.Map[A, B]]) {
-            val that = obj.asInstanceOf[scala.collection.Map[A, B]];
-            if (size != that.size) false else toList.forall {
-                case Pair(key, value) => that.get(key) match {
-                    case None => false;
-                    case Some(v) => v == value;
-                }
-            };
-        } else
-            false;
+  /** Compares two maps for equality.
+  *   Two maps are equal iff they contain exactly the
+  *   same key-value pairs.
+  */
+  override def equals(obj: Any): Boolean =
+    if (obj.isInstanceOf[scala.collection.Map[A, B]]) {
+      val that = obj.asInstanceOf[scala.collection.Map[A, B]];
+      if (size != that.size) false else toList.forall {
+        case Pair(key, value) => that.get(key) match {
+          case None => false;
+          case Some(v) => v == value;
+        }
+      };
+    } else
+      false;
 
     override def hashCode(): Int = 0;
 
     protected class Node(key: A, value: B) extends ListMap[A, B] {
-        override def size: Int = ListMap.this.size + 1;
-        override def isEmpty: Boolean = false;
-        override def apply(k: A): B = if (k == key) value else ListMap.this(k);
-        override def get(k: A): Option[B] =
-            if (k == key) Some(value) else ListMap.this.get(k);
-        override def update(k: A, v: B): ListMap[A, B] =
-            if (k == key) {
-                new ListMap.this.Node(k, v);
-            } else {
-                val tail = ListMap.this.update(k,v); new tail.Node(key, value)
-            }
-        override def -(k: A): ListMap[A, B] =
-            if (k == key)
-                ListMap.this
-            else {
-                val tail = ListMap.this - k; new tail.Node(key, value)
-            }
-        override def toList: List[Pair[A, B]] = Pair(key, value) :: ListMap.this.toList;
-        override def hashCode(): Int =
-            (key.hashCode() ^ value.hashCode()) + ListMap.this.hashCode();
+      /** Returns the number of mappings in this map.
+      *
+      *  @return number of mappings.
+      */
+      override def size: Int = ListMap.this.size + 1;
+
+      /** Is this an empty map?
+      *
+      *  @return true, iff the map is empty.
+      */
+      override def isEmpty: Boolean = false;
+
+      /** Retrieve the value which is associated with the given key. This
+      *  method throws an exception if there is no mapping from the given
+      *  key to a value.
+      *
+      *  @param  key     the key
+      *  @return the value associated with the given key.
+      */
+      override def apply(k: A): B = if (k == key) value else ListMap.this(k);
+
+      /** Check if this map maps <code>key</code> to a value and return the
+      *  value if it exists.
+      *
+      *  @param  key     the key of the mapping of interest
+      *  @return the value of the mapping, if it exists
+      */
+      override def get(k: A): Option[B] =
+        if (k == key) Some(value) else ListMap.this.get(k);
+
+      /** This method allows one to create a new map with an
+      *  additional mapping from <code>key</code>
+      *  to <code>value</code>. If the map contains already a
+      *  mapping for <code>key</code>, it will be overridden by this
+      *  function.
+      */
+	override def update(k: A, v: B): ListMap[A, B] =
+          if (k == key) {
+            new ListMap.this.Node(k, v);
+          } else {
+            val tail = ListMap.this.update(k,v); new tail.Node(key, value)
+          }
+
+      /** This creates a new mapping without the given <code>key</code>.
+      *  If the map does not contain a mapping for the given key, the
+      *  method returns the same map.
+      */
+      override def -(k: A): ListMap[A, B] =
+        if (k == key)
+          ListMap.this
+        else {
+          val tail = ListMap.this - k; new tail.Node(key, value)
+        }
+
+      /** This return a list of key-value pairs.
+      */
+      override def toList: List[Pair[A, B]] = Pair(key, value) :: ListMap.this.toList;
+
+      override def hashCode(): Int =
+        (key.hashCode() ^ value.hashCode()) + ListMap.this.hashCode();
     }
 }
 
diff --git a/sources/scala/collection/immutable/Map.scala b/sources/scala/collection/immutable/Map.scala
index 2d67d907cb..84b79bd813 100644
--- a/sources/scala/collection/immutable/Map.scala
+++ b/sources/scala/collection/immutable/Map.scala
@@ -9,30 +9,78 @@
 
 package scala.collection.immutable;
 
+/** This trait extends the Map interface of collections that unambiguously map
+ *  keys to values (i.e. a key is mapped to at least one value).
+ *  This trait defines the interface for functional map implementations
+ *  relying on immutable data structures.
+ *  Concrete map implementations have to provide functionality for the
+ *  abstract methods in scala.collection.Map as well as for
+ *  <code>factory</code>, <code>update</code>, and -.
 
-trait Map[A, B] with scala.collection.Map[A, B] {
+ *  @author  Matthias Zenger, Erik Stenman
+ *  @version 1.0, 03/12/2003
+ */
+trait Map[KEY, VALUE] with scala.collection.Map[KEY, VALUE] {
 
-    def update(key: A, value: B): Map[A, B];
+  /** A factory to create empty maps of the same type of keys.
+  */
+  val factory:MapFactory[KEY];
 
-    def -(key: A): Map[A, B];
 
-    def +(key: A): MapTo = new MapTo(key);
+  /** This method allows one to create a new map with an
+  *  additional mapping from <code>key</code>
+  *  to <code>value</code>. If the map contains already a
+  *  mapping for <code>key</code>, it will be overridden by this
+  *  function.
+  */
+  def update(key: KEY, value: VALUE): Map[KEY, VALUE];
 
-    def incl(mappings: Pair[A, B]*): Map[A, B] = incl(mappings);
+  /** This creates a new mapping without the given <code>key</code>.
+  *  If the map does not contain a mapping for the given key, the
+  *  method returns the same map.
+  */
+  def -(key: KEY): Map[KEY, VALUE];
 
-    def incl(map: Iterable[Pair[A, B]]): Map[A, B] = {
-        val iter = map.elements;
-        var res = this;
-        while (iter.hasNext) {
-            val Pair(key, value) = iter.next;
-            res = res.update(key, value);
-        }
-        res;
+  /** This method defines syntactic sugar for adding a
+  *  mapping. It is typically used in the following way:
+  *  <pre>
+  *  map + key -> value;
+  *  </pre>
+  */
+  def +(key: KEY): MapTo = new MapTo(key);
+
+
+  /** <code>incl</code> can be used to add many mappings at the same time
+  *  to the map. The method assumes that a mapping is represented
+  *  by a <code>Pair</code> object who's first component denotes the
+  *  key, and who's second component refers to the value.
+  */
+  def incl(mappings: Pair[KEY, VALUE]*): Map[KEY, VALUE] = incl(mappings);
+
+  /** <code>incl</code> can be used to add many mappings at the same time
+  *  to the map. The method assumes that each mapping is represented
+  *  by an Iterator over <code>Pair</code> objects who's first component
+  *  denotes the key, and who's second component refers to the value.
+  */
+  def incl(map: Iterable[Pair[KEY, VALUE]]): Map[KEY, VALUE] = {
+    val iter = map.elements;
+    var res = this;
+    while (iter.hasNext) {
+      val Pair(key, value) = iter.next;
+      res = res.update(key, value);
     }
+    res;
+  }
 
-    def excl(keys: A*): Map[A, B] = excl(keys);
+  /** This method will return a map where all the mappings
+  *  for the given sequence of keys are removed from the map.
+  */
+  def excl(keys: KEY*): Map[KEY, VALUE] = excl(keys);
 
-    def excl(keys: Iterable[A]): Map[A, B] = {
+  /** This method removes all the mappings for keys provided by an
+  *  iterator over the elements of the <code>keys</code> object.
+  */
+    def excl(keys: Iterable[KEY]): Map[KEY, VALUE] = {
         val iter = keys.elements;
         var res = this;
         while (iter.hasNext) {
@@ -41,15 +89,21 @@ trait Map[A, B] with scala.collection.Map[A, B] {
         res;
     }
 
-    def map(f: (A, B) => B): Map[A, B] = {
-        var res = this;
+     /** This function transforms all the values of mappings contained
+     *  in this map with function <code>f</code>.
+     */
+    def map[C <: Any](f: (KEY, VALUE) => C): Map[KEY, C] = {
+        var res = factory.Empty[C];
         elements foreach {
             case Pair(key, value) => res = res.update(key, f(key, value));
         }
         res;
     }
 
-    def filter(p: (A, B) => Boolean): Map[A, B] = {
+    /** This method removes all the mappings for which the predicate
+     *  <code>p</code> returns <code>false</code>.
+     */
+    def filter(p: (KEY, VALUE) => Boolean): Map[KEY, VALUE] = {
         var res = this;
         toList foreach {
             case Pair(key, value) => if (p(key, value)) { res = res.excl(key); }
@@ -57,6 +111,9 @@ trait Map[A, B] with scala.collection.Map[A, B] {
         res;
     }
 
+    /** Returns a string representation of this map which shows
+     *  all the mappings.
+     */
     override def toString() =
         if (size == 0)
             "{}"
@@ -70,9 +127,32 @@ trait Map[A, B] with scala.collection.Map[A, B] {
                 res;
             } + "}";
 
-    def mappingToString(p: Pair[A, B]) = p._1.toString() + " -> " + p._2;
+  /** Compares two maps for equality.
+  *   Two maps are equal iff they contain exactly the
+  *   same key-value pairs.
+  */
+  override def equals(obj: Any): Boolean =
+    if (obj.isInstanceOf[scala.collection.Map[KEY, VALUE]]) {
+      val that = obj.asInstanceOf[scala.collection.Map[KEY, VALUE]];
+      if (size != that.size) false else elements.forall {
+        case Pair(key, value) => that.get(key) match {
+          case None => false;
+          case Some(v) => v == value;
+        }
+      };
+    } else
+      false;
+
+  /** This method controls how a mapping is represented in the string
+  *  representation provided by method <code>toString</code>.
+  */
+  def mappingToString(p: Pair[KEY, VALUE]) = p._1.toString() + " -> " + p._2;
 
-    class MapTo(key: A) {
-        def ->(value: B): Map[A, B] = update(key, value);
+    class MapTo(key: KEY) {
+        def ->(value: VALUE): Map[KEY, VALUE] = update(key, value);
     }
 }
+
+abstract class MapFactory[KEY] {
+  def Empty[VALUE]:Map[KEY,VALUE];
+}
diff --git a/sources/scala/collection/immutable/Set.scala b/sources/scala/collection/immutable/Set.scala
index 896ed5daf5..2ed79d9e24 100644
--- a/sources/scala/collection/immutable/Set.scala
+++ b/sources/scala/collection/immutable/Set.scala
@@ -20,29 +20,51 @@ package scala.collection.immutable;
  */
 trait Set[A] with scala.collection.Set[A] {
 
+    /** This method creates a new set with an additional element.
+     */
     def +(elem: A): Set[A];
 
-    def incl(elems: A*): Set[A] = incl(elems);
+    /** <code>incl</code> can be used to add many elements to the set
+     *  at the same time.
+     */
+     def incl(elems: A*): Set[A] = incl(elems);
 
-    def incl(that: Iterable[A]): Set[A] = {
+     /** This method will add all the elements provided by an iterator
+     *  of the iterable object <code>that</code> to the set.
+     */
+   def incl(that: Iterable[A]): Set[A] = {
         var res = this;
         that.elements.foreach(elem => res = res + elem);
         res;
     }
 
-    def -(elem: A): Set[A];
+    /** <code>-=</code> can be used to remove a single element from
+     *  a set.
+     */
+     def -(elem: A): Set[A];
 
+    /** <code>excl</code> removes many elements from the set.
+     */
     def excl(elems: A*): Set[A] = excl(elems);
 
-    def excl(that: Iterable[A]): Set[A] = {
+    /** This method removes all the elements provided by an iterator
+     *  of the iterable object <code>that</code> from the set.
+     */
+     def excl(that: Iterable[A]): Set[A] = {
         var res = this;
         that.elements.foreach(elem => res = res - elem);
         res;
     }
 
+    /** This method computes an intersection with set <code>that</code>.
+     *  It removes all the elements that are not present in <code>that</code>.
+     */
     def intersect(that: scala.collection.Set[A]): Set[A] = filter(that.contains);
 
-    def filter(p: A => Boolean): Set[A] = {
+     /** Method <code>filter</code> removes all elements from the set for
+     *  which the predicate <code>p</code> yields the value <code>false</code>.
+     */
+   def filter(p: A => Boolean): Set[A] = {
         var res = this;
         toList foreach {
             elem => if (p(elem)) { res = res - elem; }
diff --git a/sources/scala/collection/immutable/Tree.scala b/sources/scala/collection/immutable/Tree.scala
index 205f0b926a..cdc2b2b669 100644
--- a/sources/scala/collection/immutable/Tree.scala
+++ b/sources/scala/collection/immutable/Tree.scala
@@ -47,67 +47,139 @@ package scala.collection.immutable;
 ** This implementation does not balance the trees after deletions.
 ** Since deletions
 ** don't increase the height of a tree, this should be OK in most
-** applications. A balance method is provided for dose cases
+** applications. A balance method is provided for those cases
 ** where rebalancing is needed.
+** <p>
+** The tree consists of entries conatining a key with an order.
+** Concrete implementations of the tree class has to suply the
+** function entryKey that given an entry in the tree return
+** its key.
+** <p>
+** When instanciating the tree an order for the keys has to be
+** supplied.
 **
 **  @author  Erik Stenman
 **  @version 1.0, 10/07/2003
 */
-
-
-
-class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) {
+abstract class Tree[KEY,Entry](order:Order[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().
+  ** - size:Int - the number of elements in the tree.
+  ** - tree:T, which is composed of nodes of the form:
+  **   - GBNode(entry:Entry, smaller:T, bigger:T), and the "empty tree" node:
+  **   - GBNil.
   **
   ** 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.
+  ** changed to the similar (but not quite equivalent) condition
+  ** 2 ^ h(T) <= |T| ^ c.
   **
   */
 
-  protected type aNode = Tree[KEY,Entry]#T;
-  protected type anInsertTree = Tree[KEY,Entry]#InsertTree;
-  protected val tree:aNode = Nil();
+  /** The type returned when creating a new tree.
+  *   This type should be defined by concrete implementations
+  *   e.g. <pre>
+  *   class C[T](...) extends Tree[A,B](...) {
+  *     type This = C[T];
+  *   </pre>
+  */
+  type This <: Tree[KEY,Entry];
+
+  /**
+  *  The type of nodes that the tree is build from.
+  */
+  protected type aNode = GBTree[KEY,Entry];
+
+  /** The nodes in the tree.
+  */
+  protected val tree:aNode = GBNil;
+
+  /** This abstract method should be defined by a concrete implementation
+  **   C[T] as something like:
+  **    <pre>
+  **     override def New(sz:Int,t:aNode):This {
+  **       new C[T](order) {
+  **        override def size=sz;
+  **        override protected val tree:aNode=t;
+  **     }
+  **    </pre>
+  **   The concrete implementation should also override the def of This
+  **   <code>override type This = C[T];</code>
+  **
+  */
+  protected def New(sz:Int,t:aNode):This;
 
   /** The size of the tree, returns 0 (zero) if the tree is empty.
-  ** @Returns The number of nodes in the tree as an integer.
+  **  @Returns The number of nodes in the tree as an integer.
   **/
   def size = 0;
 
-  /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-  * Factory method to create new trees.
+  /** Returns the key of an entry.
+  *   This method has to be defined by concrete implementations
+  *   of the class.
   */
-  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;
-    };
-  /* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% */
+  def entryKey(entry:Entry):KEY;
 
 
-  /** 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));
+  /** Is the given key mapped to a value by this map?
+  *
+  *  @param   key        the key
+  *  @return true, iff there is a mapping for key in this map
+  */
+   def is_defined(key:KEY) = tree.is_defined(key);
+
+
+  /**
+  *   A new tree with the entry added is returned,
+  *   assuming that key is <emph>not</emph> in the tree.
+  */  def add(key:KEY,entry:Entry):This = {
+    val newSize = size+1;
+    New(newSize,
+	tree.insert(key,
+		    entry,
+		    pow(newSize, p)).node);
+  }
 
+  /**
+  *   A new tree with the entry added is returned,
+  *   if key is <emph>not</emph> in the tree, otherwise
+  *   the key is updated with the new entry.
+  */
+  def update_or_add(key:KEY, entry:Entry):This = {
+    if(is_defined(key)) New(size,tree.update(key,entry))
+    else add(key,entry);
+  }
 
 
-  // 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 delete_any(key:KEY) =
+    if(is_defined(key)) delete(key) else
+      // TODO: Avoid this creation by convincing the type system that this has type This.
+      New(size,tree);
+
+  /** Removes the key from the tree, assumimg that key is present.
+  */
+  private def delete(key:KEY) = New(size - 1, tree.delete(key));
+
+  /** Check if this map maps <code>key</code> to a value and return the
+  *  value if it exists.
+  *
+  *  @param  key     the key of the mapping of interest
+  *  @return the value of the mapping, if it exists
+  */
+  def find(key:KEY) =  tree.get(key);
+
+  /**
+  *  Gives you an iterator over all elements in the tree.
+  *  The iterator structure corresponds to
+  *  the call stack of an in-order traversal.
+  *
+  * Note: The iterator itself 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) => {
+	  case (GBNode(v,_,t)::iter_tail) => {
 	    iter= t.mk_iter(iter_tail);
             v;
 	  }
@@ -116,51 +188,34 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) {
 	}
     }
 
-
-  private abstract class T() {
-    def count:Info;
-    def is_defined(Key:KEY):Boolean;
-    def get(key:KEY):Option[Entry];
-    def apply(key:KEY):Entry;
-    def update(key:KEY, value:Entry):aNode;
-    def insert(key:KEY, value:Entry, size:int):anInsertTree;
-    def toList(acc:List[Entry]):List[Entry];
-    def mk_iter(iter_tail:List[aNode]):List[aNode];
-    def delete(key:KEY):aNode;
-    def merge(t:aNode):aNode;
-    def take_smallest:Pair[Entry,aNode];
-
-    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;
-    }
-
-    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);
-    }
+  /** 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 = New(size,tree.balance(size));
+
+
+  case object GBNil extends GBTree[KEY,Entry] {
+    def count = Info(1,0);
+    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");
+    def insert(key:KEY, value:Entry, s:int):anInsertTree =
+      if (s == 0) INode(GBNode(value, GBNil, GBNil), 1, 1);
+      else ITree(GBNode(value, GBNil, GBNil));
+    def toList(acc:List[Entry]) = acc;
+    def mk_iter(iter_tail:List[GBTree[KEY,Entry]]) = iter_tail;
+    def merge(larger:GBTree[KEY,Entry]) = larger;
+    def take_smallest:Pair[Entry,GBTree[KEY,Entry]] = error("Take Smallest on empty tree");
+    def delete(_key:KEY) = error("Delete on empty tree.");
+    def balance(s:int) = this;
+    override def hashCode() = 0;
   }
 
-
-
-  private case class Node(value:Entry,smaller:aNode,bigger:aNode) extends T {
+  private case class GBNode(value:Entry,smaller:GBTree[KEY,Entry],bigger:GBTree[KEY,Entry]) extends GBTree[KEY,Entry] {
     def count:Info = {
-      if (smaller == Nil() && bigger == Nil()) Info(1,1);
+      if (smaller == GBNil && bigger == GBNil) Info(1,1);
       else {
 	val sInfo = smaller.count;
 	val bInfo = bigger.count;
@@ -174,23 +229,24 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>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);
+	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;
+	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);
+	GBNode(value, smaller.update(key,newValue), bigger);
       else if (order.gt(key,entryKey(value)))
-	Node(value, smaller, bigger.update(key,newValue));
+	GBNode(value, smaller, bigger.update(key,newValue));
       else
-	Node(newValue, smaller, bigger);
+	GBNode(newValue, smaller, bigger);
 
     def insert(key:KEY, newValue:Entry, s:int):anInsertTree = {
       if(order.lt(key,entryKey(value)))
@@ -203,104 +259,134 @@ class Tree[KEY,Entry](order:Order[KEY],entryKey:Entry=>KEY) {
     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;
-	  else smaller.mk_iter(this::iter_tail);
+    def mk_iter(iter_tail:List[aNode]):List[aNode] =
+      if (smaller == GBNil) this::iter_tail;
+      else smaller.mk_iter(this::iter_tail);
 
 
-      def delete(key:KEY):aNode = {
-	  if (order.lt(key,entryKey(value)))
-	  Node(value, smaller.delete(key), bigger);
-	  else
-	  if (order.gt(key,entryKey(value)))
-	  Node(value, smaller, bigger.delete(key));
-	  else
+    def delete(key:KEY):aNode = {
+      if (order.lt(key,entryKey(value)))
+	GBNode(value, smaller.delete(key), bigger);
+      else
+	if (order.gt(key,entryKey(value)))
+	  GBNode(value, smaller, bigger.delete(key));
+	else
 	  smaller.merge(bigger)
-	}
+    }
 
-      def merge(larger:aNode) = {
-	if(larger==Nil()) this;
-	else {
-	    val Pair(value,larger1) = larger.take_smallest;
-	    Node(value,smaller,larger1);
-	}
+    def merge(larger:aNode) = {
+      if(larger==GBNil) this;
+      else {
+	val Pair(value,larger1) = larger.take_smallest;
+	GBNode(value,smaller,larger1);
       }
+    }
 
-      def take_smallest:Pair[Entry,aNode] = {
-	  if (smaller == Nil) Pair(value,bigger);
-	  else {
-	      val Pair(value1, smaller1) = smaller.take_smallest;
-	      Pair(value1, Node(value, smaller1, bigger));
-	  }
+    def take_smallest:Pair[Entry,aNode] = {
+      if (smaller == GBNil) Pair(value,bigger);
+      else {
+	val Pair(value1, smaller1) = smaller.take_smallest;
+	Pair(value1, GBNode(value, smaller1, bigger));
       }
+    }
+
+    def balance(s:int):GBTree[KEY,Entry] = balance_list(toList(scala.Nil), s);
+
+    override def hashCode() =
+      value.hashCode() + smaller.hashCode() + bigger.hashCode();
+
+  }
+
+
+  protected def balance_list(list:List[Entry], s:int) = balance_list_1(list, s)._1;
+
+  protected 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 = GBNode(v, t1, t2);
+      Pair(t, l2);
+    } else
+      if(s == 1) {
+	val v = list.head;
+	Pair(GBNode(v,GBNil,GBNil), list.tail);
+      } else
+	Pair(GBNil,list);
   }
 
 
-    private case class Nil() extends T {
-	def count = Info(1,0);
-	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");
-	def insert(key:KEY, value:Entry, s:int) =
-	    if (s == 0) INode(Node(value, Nil(), Nil()), 1, 1);
-	    else ITree(Node(value, Nil(), Nil()));
-	def toList(acc:List[Entry]) = acc;
-	def mk_iter(iter_tail:List[aNode]) = iter_tail;
-	def merge(larger:aNode) = larger;
-	def take_smallest:Pair[Entry,aNode] = error("Take Smallest on empty tree");
-	def delete(_key:KEY) = error("Delete on empty tree.");
+
+  // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% */
+
+  protected case class ITree(t:aNode) extends InsertTree[KEY,Entry] {
+    def insert_left(value:Entry,bigger:aNode) = ITree(GBNode(value,t,bigger));
+    def insert_right(value:Entry,smaller:aNode) = ITree(GBNode(value,smaller,t));
+    def node = t;
+  }
+  protected case class INode(t1:aNode,height:int,siz:int) extends InsertTree[KEY,Entry]{
+    def insert_left(value:Entry,bigger:aNode) = balance_p(GBNode(value, t1, bigger), bigger);
+    def insert_right(value:Entry,smaller:aNode) = balance_p(GBNode(value, smaller, t1),smaller);
+    protected def balance_p(t:aNode,subtree:aNode):anInsertTree = {
+      val info = subtree.count;
+      val totalHeight = mul2(max(height, info.height));
+      val totalSize = siz + info.size + 1;
+      val BalanceHeight = pow(totalSize, p);
+      if(totalHeight > BalanceHeight) ITree(t.balance(totalSize));
+      else INode(t, totalHeight, totalSize);
     }
+    def node = t1;
+  }
 
+  /* -----------------------------------------------------------
+  // Some helpful definitions.
+  */
+  private val p = 2; // It seems that p = 2 is optimal for sorted keys */
+  private def pow(a:int, b:int):int =
+    b.match {
+      case 2 => a * a;
+      case 1 => a;
+      case x if x > 0 => a * pow(a, b-1);
+    };
+  private def div2(x:int) = x >> 1;
+  private def mul2(x:int) = x << 1;
+  private def max(x:int, y:int):int = if(x>y) x else y;
 
-    private case class Info(height:int, size:int) {}
 
+} // End of class Tree...
 
-    /* -----------------------------------------------------------
-    // Some helpful definitions.
-    */
-    protected val p = 2; // It seems that p = 2 is optimal for sorted keys */
-    protected def pow(a:int, b:int):int =
-	b.match {
-	    case 2 => a * a;
-	    case 1 => a;
-	    case x if x > 0 => a * pow(a, b-1);
-	};
-    private def div2(x:int) = x >> 1;
-    private def mul2(x:int) = x << 1;
-    private def max(x:int, y:int) = if(x<y) y; else x;
+case class Info(height:int, size:int);
 
+abstract class InsertTree[KEY,Entry]() {
+  type aNode = GBTree[KEY,Entry];
+  type anInsertTree = InsertTree[KEY,Entry];
 
+  def insert_left(v:Entry,t:aNode):anInsertTree;
+  def insert_right(v:Entry,t:aNode):anInsertTree;
+  def node:aNode;
+}
 
-    // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% */
-    protected abstract class InsertTree() {
-	def insert_left(v:Entry,t:aNode):anInsertTree;
-	def insert_right(v:Entry,t:aNode):anInsertTree;
-	def node:aNode;
-    }
-    private case class ITree(t:aNode) extends InsertTree {
-	def insert_left(value:Entry,bigger:aNode) =
-	    ITree(Node(value,t,bigger));
-	def insert_right(value:Entry,smaller:aNode) =
-	    ITree(Node(value,smaller,t));
-	def node = t;
-    }
-    private case class INode(t1:aNode,height:int,siz:int) extends InsertTree{
-	def insert_left(value:Entry,bigger:aNode) = {
-	    balance_p(Node(value, t1, bigger), bigger);
-	}
-	def insert_right(value:Entry,smaller:aNode) = {
-	    balance_p(Node(value, smaller, t1),smaller);
-	}
-	private def balance_p(t:aNode,subtree:aNode):anInsertTree = {
-	    val info = subtree.count;
-	    val totalHeight = mul2(max(height, info.height));
-	    val totalSize = siz + info.size + 1;
-	    val BalanceHeight = pow(totalSize, p);
-	    if(totalHeight > BalanceHeight) ITree(t.balance(totalSize));
-	    else INode(t, totalHeight, totalSize);
-	}
-	def node = t1;
-    }
+abstract class GBTree[KEY,Entry] {
+  type aNode = GBTree[KEY,Entry];
+  type anInsertTree = InsertTree[KEY,Entry];
+
+  def count:Info;
+  def is_defined(Key:KEY):Boolean;
+  def get(key:KEY):Option[Entry];
+  def apply(key:KEY):Entry;
+  def update(key:KEY, value:Entry):aNode;
+  def insert(key:KEY, value:Entry, size:int):anInsertTree;
+  def toList(acc:List[Entry]):List[Entry];
+  def mk_iter(iter_tail:List[aNode]):List[aNode];
+  def delete(key:KEY):aNode;
+  def merge(t:aNode):aNode;
+  def take_smallest:Pair[Entry,aNode];
+  def balance(s:int):GBTree[KEY,Entry];
 
 }
+
+
+
+
diff --git a/sources/scala/collection/immutable/TreeMap.scala b/sources/scala/collection/immutable/TreeMap.scala
index 9e409f0336..878a4bdb24 100644
--- a/sources/scala/collection/immutable/TreeMap.scala
+++ b/sources/scala/collection/immutable/TreeMap.scala
@@ -9,81 +9,78 @@
 
 package scala.collection.immutable;
 
+class TreeMapFactory[KEY](order:Order[KEY]) extends MapFactory[KEY] {
+  def Empty[VALUE] = new TreeMap[KEY,VALUE](order);
+}
+
 /** This class implements immutable maps using a tree.
  *
  *  @author  Erik Stenman, Matthias Zenger
  *  @version 1.0, 23/07/2003
  */
-class TreeMap[KEY,VALUE](order:Order[KEY])
-    extends Map[KEY, VALUE]
-    with Tree[KEY,Pair[KEY,VALUE]](order,
-	{(entry:Pair[KEY,VALUE]) =>
-	    entry.match {case Pair(key,_value)=> key:KEY}
-	}) {
-
-    private def mkTreeMap(sz:int,t:aNode):TreeMap[KEY,VALUE] =
-	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)))
-	else insert(key,value);
+ class TreeMap[KEY,VALUE](order:Order[KEY]) extends Tree[KEY,Pair[KEY,VALUE]](order) with Map[KEY, VALUE] {
+   override type This = TreeMap[KEY,VALUE];
+   val factory = new TreeMapFactory[KEY](order);
+   override def entryKey(entry:Pair[KEY,VALUE]) = entry._1;
+
+   protected def New(sz:Int,t:aNode):This =
+     new TreeMap[KEY,VALUE](order) {
+       override def size=sz;
+       override protected val tree:aNode=t;
+     }
+
+   def update(key:KEY, value:VALUE) = update_or_add(key,Pair(key,value));
+
+   def insert(key:KEY,value:VALUE) = add(key,Pair(key,value));
+   def -(key:KEY) = delete_any(key);
+
+
+
+   /** Check if this map maps <code>key</code> to a value and return the
+   *  value if it exists.
+   *
+   *  @param  key     the key of the mapping of interest
+   *  @return the value of the mapping, if it exists
+   */
+   override def get(key:KEY) =
+     find(key).match {
+       case Some(Pair(_,value:VALUE)) => Some(value);
+       case _ => None;
      }
 
-    def insert(key:KEY,value:VALUE) = {
-	val newSize = size+1;
-	mkTreeMap(newSize,tree.insert(key, Pair(key,value),
-				    pow(newSize, p)).node);
-    }
-
-
-    /** Check if this map maps <code>key</code> to a value and return the
-     *  value if it exists.
-     *
-     *  @param  key     the key of the mapping of interest
-     *  @return the value of the mapping, if it exists
-     */
-     def get(key:KEY) =
-	tree.get(key).match {
-	    case Some(Pair(_,value:VALUE)) => Some(value);
-	    case _ => None;
-	}
-
-
-    def -(key:KEY) = delete_any(key);
-
-    def delete_any(key:KEY) =
-	if(contains(key)) delete(key)
-			      else this;
-
-    // delete. Assumes that key is present.
-    def delete(key:KEY) =
-	mkTreeMap(size - 1, tree.delete(key));
-
-    /** Retrieve the value which is associated with the given key. This
-     *  method throws an exception if there is no mapping from the given
-     *  key to a value.
-     *
-     *  @param  key     the key
-     *  @return the value associated with the given key.
-     *  @throws Error("key not found").
-     */
-    override def apply(key:KEY):VALUE = tree.apply(key)._2;
-
-    /** Is the given key mapped to a value by this map?
-     *
-     *  @param   key        the key
-     *  @return true, iff there is a mapping for key in this map
-     */
-    override def contains(key:KEY) = tree.is_defined(key);
-
-    /** Creates a list of all (key, value) mappings.
-     *
-     *  @return    the list of all mappings
-     */
-    override def toList:List[Pair[KEY,VALUE]] = tree.toList(scala.Nil);
-
-    def elements:Iterator[Pair[KEY,VALUE]] = entries;
+
+
+
+   /** Retrieve the value which is associated with the given key. This
+   *  method throws an exception if there is no mapping from the given
+   *  key to a value.
+   *
+   *  @param  key     the key
+   *  @return the value associated with the given key.
+   *  @throws Error("key not found").
+   */
+   override def apply(key:KEY):VALUE = tree.apply(key)._2;
+
+
+   /** Creates a list of all (key, value) mappings.
+   *
+   *  @return    the list of all mappings
+   */
+   override def toList:List[Pair[KEY,VALUE]] = tree.toList(scala.Nil);
+
+   def elements:Iterator[Pair[KEY,VALUE]] = entries;
+
+
+   override def equals(obj: Any): Boolean =
+     if (obj.isInstanceOf[scala.collection.Map[KEY, VALUE]]) {
+       val that = obj.asInstanceOf[scala.collection.Map[KEY, VALUE]];
+       if (size != that.size) false else elements.forall {
+         case Pair(key, value) => that.get(key) match {
+           case None => false;
+           case Some(v) => v == value;
+         }
+       };
+     } else
+       false;
+
 }