More comments and cleanups.

8 files changed, 227 insertions, 39 deletions

diff --git a/sources/scala/collection/Set.scala b/sources/scala/collection/Set.scala
index 705a3d24ad..8cec4c200c 100644
--- a/sources/scala/collection/Set.scala
+++ b/sources/scala/collection/Set.scala
@@ -25,10 +25,10 @@ package scala.collection;
  */
 trait Set[A] with Function1[A, Boolean] with Iterable[A] {
 
-	/** Returns the number of elements in this set.
-	 *
-	 *  @return number of set elements.
-	 */
+    /** Returns the number of elements in this set.
+    *
+    *  @return number of set elements.
+    */
     def size: Int;
 
     /** Checks if this set contains element <code>elem</code>.
diff --git a/sources/scala/collection/immutable/ListMap.scala b/sources/scala/collection/immutable/ListMap.scala
index 5e80447a3d..8089f6681e 100644
--- a/sources/scala/collection/immutable/ListMap.scala
+++ b/sources/scala/collection/immutable/ListMap.scala
@@ -33,6 +33,8 @@ object ListMap {
  *  @version 1.0, 09/07/2003
  */
 class ListMap[A, B] with Map[A, B] {
+  /** A factory to create empty maps of the same type of keys.
+  */
   val factory = new ListMapFactory[A];
 
   /** Returns the number of mappings in this map.
diff --git a/sources/scala/collection/immutable/ListSet.scala b/sources/scala/collection/immutable/ListSet.scala
index fa3582e31f..dd89906cec 100644
--- a/sources/scala/collection/immutable/ListSet.scala
+++ b/sources/scala/collection/immutable/ListSet.scala
@@ -24,18 +24,44 @@ object ListSet {
  */
 class ListSet[A] with Set[A] {
 
+    /** Returns the number of elements in this set.
+    *
+    *  @return number of set elements.
+    */
     def size: Int = 0;
 
+    /** Checks if this set contains element <code>elem</code>.
+    *
+    *  @param  elem    the element to check for membership.
+    *  @return true, iff <code>elem</code> is contained in this set.
+    */
     def contains(elem: A): Boolean = false;
 
+    /** This method creates a new set with an additional element.
+     */
     def +(elem: A): ListSet[A] = new Node(elem);
 
+    /** <code>-</code> can be used to remove a single element from
+     *  a set.
+     */
     def -(elem: A): ListSet[A] = this;
 
+    /** Creates a new iterator over all elements contained in this
+     *  object.
+     *
+     *  @return the new iterator
+     */
     def elements: Iterator[A] = toList.elements;
 
+    /** Transform this set into a list of all elements.
+     *
+     *  @return  a list which enumerates all elements of this set.
+     */
     override def toList: List[A] = Nil;
 
+    /** Compares two sets for equality.
+    *   Two set are equal iff they contain the same elements.
+    */
     override def equals(obj: Any): Boolean =
         if (obj.isInstanceOf[scala.collection.Set[A]]) {
             val that = obj.asInstanceOf[scala.collection.Set[A]];
@@ -46,14 +72,39 @@ class ListSet[A] with Set[A] {
     override def hashCode(): Int = 0;
 
     protected class Node(elem: A) extends ListSet[A] {
-        override def size = ListSet.this.size + 1;
-        override def isEmpty: Boolean = false;
-        override def contains(e: A) = (e == elem) || ListSet.this.contains(e);
-        override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e);
-        override def -(e: A): ListSet[A] = if (e == elem) ListSet.this else {
-            val tail = ListSet.this - e; new tail.Node(elem)
-        }
-        override def toList: List[A] = elem :: ListSet.this.toList;
-        override def hashCode(): Int = elem.hashCode() + ListSet.this.hashCode();
+      /** Returns the number of elements in this set.
+      *
+      *  @return number of set elements.
+      */
+      override def size = ListSet.this.size + 1;
+      /** Checks if this set is empty.
+      *
+      *  @return true, iff there is no element in the set.
+      */
+      override def isEmpty: Boolean = false;
+
+      /** Checks if this set contains element <code>elem</code>.
+      *
+      *  @param  elem    the element to check for membership.
+      *  @return true, iff <code>elem</code> is contained in this set.
+      */
+      override def contains(e: A) = (e == elem) || ListSet.this.contains(e);
+
+      /** This method creates a new set with an additional element.
+      */
+      override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e);
+      /** <code>-</code> can be used to remove a single element from
+      *  a set.
+      */
+      override def -(e: A): ListSet[A] = if (e == elem) ListSet.this else {
+        val tail = ListSet.this - e; new tail.Node(elem)
+      }
+
+      /** Transform this set into a list of all elements.
+      *
+      *  @return  a list which enumerates all elements of this set.
+      */
+      override def toList: List[A] = elem :: ListSet.this.toList;
+      override def hashCode(): Int = elem.hashCode() + ListSet.this.hashCode();
     }
 }
diff --git a/sources/scala/collection/immutable/Order.scala b/sources/scala/collection/immutable/Order.scala
index ee733e98f4..44ad1f2482 100644
--- a/sources/scala/collection/immutable/Order.scala
+++ b/sources/scala/collection/immutable/Order.scala
@@ -9,9 +9,104 @@
 
 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 leq (e1:t, e2:t) = less(e1,e2) || equal(e1,e2);
-    def gt  (e1:t, e2:t) = less(e2,e1);
-    def geq (e1:t, e2:t) = leq(e2,e1);
+/** The object Order provides constructors for orderings between
+*   objects.
+*/
+object Order {
+  /**
+  *  Creates an Order given a predicate
+  *  (<code>inferiority(e1,e2)</code>).
+  *  The predicate is true iff e1 is less than
+  *  e2. The ordinary equality operator == will be used for
+  *  equality by the order.
+  */
+  def make[A](inferiority:(A,A) => Boolean) =
+    new Order[A](inferiority,(e1:A,e2:A) => e1 == e2);
+  /**
+  *  Creates an Order given two predicates
+  * (<code>inferiority(e1,e2)</code> and
+  *  <code>equality(e1,e2)</code>). The first is true iff e1 is less than
+  *  e2 and the second predicate is true when e1 is equal to e2.
+  */
+  def make[A](inferiority:(A,A) => Boolean, equality:(A,A) => Boolean) =
+    new Order[A](inferiority,equality);
+  /**
+  *  Creates a 'standard' order between objects. <strong>NOTE:</strong>
+  *  The order is arbitrary and uses the <code>hashCode()</code> of
+  *  objects which might mean that the order is not really total
+  *  for some objects <code>(!(e1 &lt; e2) && !(e2 &lt; e1) && !(e1==e2))</code>
+  *  is true. This function should only be used when no other
+  *  comparision predicates can be defined.
+  */
+  def make =
+    new Order[Any](
+      (e1:Any,e2:Any) =>
+	e1.match {
+	  case x:Int => {
+	    e2.match {
+	      case y:Int => x < y;
+	      case y:Double => x < y;
+	      case y:Float => x < y;
+	      case y:Long => x < y;
+	      case _ => true;
+	    }
+	  }
+	  case x:Double => {
+	    e2.match {
+	      case y:Int => x < y;
+	      case y:Double => x < y;
+	      case y:Float => x < y;
+	      case y:Long => x < y;
+	      case _ => true;
+	    }
+	  }
+	  case x:Float => {
+	    e2.match {
+	      case y:Int => x < y;
+	      case y:Double => x < y
+	      case y:Float => x < y;;
+	      case y:Long => x < y;
+	      case _ => true;
+	    }
+	  }
+	  case x:Long => {
+	    e2.match {
+	      case y:Int => x < y;
+	      case y:Double => x < y
+	      case y:Float => x < y;;
+	      case y:Long => x < y;
+	      case _ => true;
+	    }
+	  }
+	  case x:AnyRef => {
+	    e2.match {
+	      case y:AnyVal => false;
+	      case y:AnyRef => x.hashCode() < y.hashCode();
+	    }
+	  }
+	},
+      (e1:Any,e2:Any) => e1 == e2);
+}
+
+
+/** The class Order[A] defines an order between objects of
+ *  type A, given two predicates (<code>inferiority(e1,e2)</code> and
+ *  <code>equality(e1,e2)</code>). The first is true iff e1 is less than
+ *  e2 and the second predicate is true when e1 is equal to e2.
+ *  An Order object can be used for ordered trees, maps, and sets.
+ *  In order to use the order with the given
+ *  TreeMap and TreeSet implementations the definition of the
+ *  predicates <code>inferiority</code> and <code>equality</code>
+ *  should be total. They predicate should
+ *  also define a true total ordering (i.e., inferiority should be
+ *  transitive, non-reflexive and asymmetric, and equality should be
+ *  transitive, reflexive and symetric.)
+ */
+class Order[A](inferiority:(A,A) => Boolean, equality:(A,A) => Boolean) {
+    def <  (e1:A, e2:A) = inferiority(e1,e2);
+    def <= (e1:A, e2:A) = inferiority(e1,e2) || equality(e1,e2);
+    def >  (e1:A, e2:A) = inferiority(e2,e1);
+    def >= (e1:A, e2:A) = ! inferiority(e1,e2);
+    def == (e1:A, e2:A) = equality(e1,e2);
+    def != (e1:A, e2:A) = ! equality(e1,e2);
 }
diff --git a/sources/scala/collection/immutable/Set.scala b/sources/scala/collection/immutable/Set.scala
index 2ed79d9e24..b613c7d86f 100644
--- a/sources/scala/collection/immutable/Set.scala
+++ b/sources/scala/collection/immutable/Set.scala
@@ -38,7 +38,7 @@ trait Set[A] with scala.collection.Set[A] {
         res;
     }
 
-    /** <code>-=</code> can be used to remove a single element from
+    /** <code>-</code> can be used to remove a single element from
      *  a set.
      */
      def -(elem: A): Set[A];
diff --git a/sources/scala/collection/immutable/Tree.scala b/sources/scala/collection/immutable/Tree.scala
index cdc2b2b669..a478e9a93b 100644
--- a/sources/scala/collection/immutable/Tree.scala
+++ b/sources/scala/collection/immutable/Tree.scala
@@ -124,13 +124,14 @@ abstract class Tree[KEY,Entry](order:Order[KEY]) {
   *  @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);
+  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 = {
+  */
+  def add(key:KEY,entry:Entry):This = {
     val newSize = size+1;
     New(newSize,
 	tree.insert(key,
@@ -149,6 +150,8 @@ abstract class Tree[KEY,Entry](order:Order[KEY]) {
   }
 
 
+  /** Removes the key from the tree.
+  */
   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.
@@ -225,33 +228,33 @@ abstract class Tree[KEY,Entry](order:Order[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)
+      if(order.<(key,entryKey(value))) smaller.is_defined(key)
+      else if(order.>(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);
+      if (order.<(key,entryKey(value))) smaller.get(key);
+      else if (order.>(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);
+      if (order.<(key,entryKey(value))) smaller.apply(key);
+	else if (order.>(key,entryKey(value))) bigger.apply(key);
 	else value;
 
     def update(key:KEY, newValue:Entry):aNode =
-      if (order.lt(key,entryKey(value)))
+      if (order.<(key,entryKey(value)))
 	GBNode(value, smaller.update(key,newValue), bigger);
-      else if (order.gt(key,entryKey(value)))
+      else if (order.>(key,entryKey(value)))
 	GBNode(value, smaller, bigger.update(key,newValue));
       else
 	GBNode(newValue, smaller, bigger);
 
     def insert(key:KEY, newValue:Entry, s:int):anInsertTree = {
-      if(order.lt(key,entryKey(value)))
+      if(order.<(key,entryKey(value)))
 	smaller.insert(key, newValue, div2(s)).insert_left(value,bigger);
-      else if(order.gt(key,entryKey(value)))
+      else if(order.>(key,entryKey(value)))
 	bigger.insert(key, newValue, div2(s)).insert_right(value,smaller);
       else error("Key exists" + key);
     }
@@ -265,10 +268,10 @@ abstract class Tree[KEY,Entry](order:Order[KEY]) {
 
 
     def delete(key:KEY):aNode = {
-      if (order.lt(key,entryKey(value)))
+      if (order.<(key,entryKey(value)))
 	GBNode(value, smaller.delete(key), bigger);
       else
-	if (order.gt(key,entryKey(value)))
+	if (order.>(key,entryKey(value)))
 	  GBNode(value, smaller, bigger.delete(key));
 	else
 	  smaller.merge(bigger)
@@ -357,8 +360,6 @@ abstract class Tree[KEY,Entry](order:Order[KEY]) {
 
 } // End of class Tree...
 
-case class Info(height:int, size:int);
-
 abstract class InsertTree[KEY,Entry]() {
   type aNode = GBTree[KEY,Entry];
   type anInsertTree = InsertTree[KEY,Entry];
@@ -368,10 +369,17 @@ abstract class InsertTree[KEY,Entry]() {
   def node:aNode;
 }
 
+/**
+*  GBTree is an internal class used by Tree.
+*/
+
 abstract class GBTree[KEY,Entry] {
   type aNode = GBTree[KEY,Entry];
   type anInsertTree = InsertTree[KEY,Entry];
 
+  /** Calculates 2^h, and size, where h is the height of the tree
+  *   and size is the number of nodes in the tree.
+  */
   def count:Info;
   def is_defined(Key:KEY):Boolean;
   def get(key:KEY):Option[Entry];
@@ -385,6 +393,9 @@ abstract class GBTree[KEY,Entry] {
   def take_smallest:Pair[Entry,aNode];
   def balance(s:int):GBTree[KEY,Entry];
 
+  case class Info(height:int, size:int);
+
+
 }
 
 
diff --git a/sources/scala/collection/immutable/TreeMap.scala b/sources/scala/collection/immutable/TreeMap.scala
index 878a4bdb24..c903721b6b 100644
--- a/sources/scala/collection/immutable/TreeMap.scala
+++ b/sources/scala/collection/immutable/TreeMap.scala
@@ -20,21 +20,39 @@ class TreeMapFactory[KEY](order:Order[KEY]) extends MapFactory[KEY] {
  */
  class TreeMap[KEY,VALUE](order:Order[KEY]) extends Tree[KEY,Pair[KEY,VALUE]](order) with Map[KEY, VALUE] {
    override type This = TreeMap[KEY,VALUE];
+   /** A factory to create empty maps of the same type of keys.
+   */
    val factory = new TreeMapFactory[KEY](order);
+
+  /** Returns the key of an entry.
+  *   This method has to be defined by concrete implementations
+  *   of the class.
+  */
    override def entryKey(entry:Pair[KEY,VALUE]) = entry._1;
 
+   /** Creates a new TreeMap from a GBTree and its size. */
    protected def New(sz:Int,t:aNode):This =
      new TreeMap[KEY,VALUE](order) {
        override def size=sz;
        override protected val tree:aNode=t;
      }
 
+   /**
+   *   A new TreeMap with the entry added is returned,
+   *   if key is <emph>not</emph> in the TreeMap, otherwise
+   *   the key is updated with the new entry.
+   */
    def update(key:KEY, value:VALUE) = update_or_add(key,Pair(key,value));
 
+   /**
+   *   A new TreeMap with the entry added is returned,
+   *   assuming that key is <emph>not</emph> in the TreeMap.
+   */
    def insert(key:KEY,value:VALUE) = add(key,Pair(key,value));
-   def -(key:KEY) = delete_any(key);
-
 
+   /** Removes the key from the TreeMap.
+   */
+   def -(key:KEY) = delete_any(key);
 
    /** Check if this map maps <code>key</code> to a value and return the
    *  value if it exists.
@@ -68,9 +86,20 @@ class TreeMapFactory[KEY](order:Order[KEY]) extends MapFactory[KEY] {
    */
    override def toList:List[Pair[KEY,VALUE]] = tree.toList(scala.Nil);
 
-   def elements:Iterator[Pair[KEY,VALUE]] = entries;
+   /** Creates a new iterator over all elements contained in this
+   *  object.
+   *
+   *  @return the new iterator
+   */
+    def elements:Iterator[Pair[KEY,VALUE]] = entries;
 
 
+   /** Compares two maps structurally; i.e. checks if all mappings
+   *  contained in this map are also contained in the other map,
+   *  and vice versa.
+   *
+   *  @return    true, iff both maps contain exactly the same mappings.
+   */
    override def equals(obj: Any): Boolean =
      if (obj.isInstanceOf[scala.collection.Map[KEY, VALUE]]) {
        val that = obj.asInstanceOf[scala.collection.Map[KEY, VALUE]];
diff --git a/test/files/run/map_test.scala b/test/files/run/map_test.scala
index 82a2c12e5a..709a7e0233 100644
--- a/test/files/run/map_test.scala
+++ b/test/files/run/map_test.scala
@@ -5,7 +5,7 @@ import scala.collection.immutable.Order;
 
 object Test with Executable {
     val intOrder =
-	new Order((x:int,y:int) => x < y, (x:int,y:int) => x == y);
+	Order.make((x:int,y:int) => x < y);
 
     test1();
     test2();