Added support for structural equality in mutabl...

Added support for structural equality in mutable data structures. Added
documentation. Cleaned up code.

11 files changed, 317 insertions, 121 deletions

diff --git a/sources/scala/Cell.scala b/sources/scala/Cell.scala
index 8336704eb7..8a5146a3a3 100644
--- a/sources/scala/Cell.scala
+++ b/sources/scala/Cell.scala
@@ -1,2 +1,20 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
 package scala;
+
+
+/** A <code>Cell</code> is a generic wrapper which completely
+ *  hides the functionality of the wrapped object. The wrapped
+ *  object is accessible via the <code>elem</code> accessor method.
+ *
+ *  @author  Martin Odersky
+ *  @version 1.0, 08/08/2003
+ */
 case class Cell[+T](elem: T);
diff --git a/sources/scala/Iterator.scala b/sources/scala/Iterator.scala
index adcc2cf746..58b2c399fa 100644
--- a/sources/scala/Iterator.scala
+++ b/sources/scala/Iterator.scala
@@ -65,6 +65,18 @@ trait Iterator[+a] with Iterable[a] {
   def foreach(f: a => Unit): Unit =
     while (hasNext) { f(next) }
 
+  def forall(p: a => Boolean): Boolean = {
+    var res = true;
+    while (res && hasNext) { res = p(next); }
+    res;
+  }
+
+  def exists(p: a => Boolean): Boolean = {
+    var res = false;
+    while (!res && hasNext) { res = p(next); }
+    res;
+  }
+
   def take(n: Int) = new Iterator[a] {
     var remaining = n;
     def hasNext = remaining > 0 && Iterator.this.hasNext;
diff --git a/sources/scala/List.scala b/sources/scala/List.scala
index a952b05ac5..cda726f112 100644
--- a/sources/scala/List.scala
+++ b/sources/scala/List.scala
@@ -71,7 +71,7 @@ object List {
  *  @author  Martin Odersky
  *  @version 1.0, 16/07/2003
  */
-trait List[+a] extends Seq[a] {
+trait List[+a] extends Seq[a] with StructuralEquality[List[a]] {
 
   /** Tests if this list is empty.
    *  @return true, iff the list contains no element.
diff --git a/sources/scala/Ord.scala b/sources/scala/Ord.scala
index bfe845c615..aa55504c39 100644
--- a/sources/scala/Ord.scala
+++ b/sources/scala/Ord.scala
@@ -1,3 +1,12 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
 package scala;
 
 trait Ord[t <: Ord[t]]: t {
@@ -6,3 +15,13 @@ trait Ord[t <: Ord[t]]: t {
   def > (that: t): Boolean = that < this;
   def >=(that: t): Boolean = that <= this;
 }
+
+/* Shall we use a covariant Ord?
+
+trait Ord[+T <: Ord[T]] {
+  def < [S >: T <: Ord[S]](that: S): Boolean;
+  def <=[S >: T <: Ord[S]](that: S): Boolean = this < that || this == that;
+  def > [S >: T <: Ord[S]](that: S): Boolean = that < this;
+  def >=[S >: T <: Ord[S]](that: S): Boolean = that <= this;
+}
+*/
diff --git a/sources/scala/Stream.scala b/sources/scala/Stream.scala
index aa7fe82db7..6fe7ab1aa5 100644
--- a/sources/scala/Stream.scala
+++ b/sources/scala/Stream.scala
@@ -1,5 +1,15 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
 package scala;
 
+
 trait Stream[+a] extends Seq[a] {
 
   def isEmpty: Boolean;
diff --git a/sources/scala/StructuralEquality.scala b/sources/scala/StructuralEquality.scala
new file mode 100644
index 0000000000..38e0b6a44c
--- /dev/null
+++ b/sources/scala/StructuralEquality.scala
@@ -0,0 +1,41 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+
+/** Collection classes supporting this trait provide a method
+ *  <code>elements</code> which returns an iterator over all the
+ *  elements contained in the collection.
+ *
+ *  @author  Matthias Zenger
+ *  @version 1.0, 16/07/2003
+ */
+trait StructuralEquality[+A <: StructuralEquality[A]] {
+
+    /** Compares this object with the provided object structurally;
+     *  i.e. by looking at the internal structure of aggregated objects.
+     *  <code>===</code> does not have to be compatible with the
+     *  <code>hashCode</code> method.
+     *
+     *  @param   that	the other object
+     *  @returns true, iff <code>this</code> and <code>that</code> are
+     *           structurally equivalent.
+     */
+    def ===[B >: A](that: B): Boolean = (this == that);
+
+    /** Compares this object with the provided object structurally
+     *  and returns true, iff the two objects differ.
+     *
+     *  @param   that	the other object
+     *  @returns false, iff <code>this</code> and <code>that</code> are
+     *           structurally equivalent.
+     */
+    def !==[B >: A](that: B): Boolean = !(this === that);
+}
diff --git a/sources/scala/Symbol.scala b/sources/scala/Symbol.scala
index a02abaffa3..7df7099ae1 100644
--- a/sources/scala/Symbol.scala
+++ b/sources/scala/Symbol.scala
@@ -1,6 +1,24 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
 package scala;
 
+
+/** Instances of <code>Symbol</code> can be created easily with
+ *  Scala's built-in quote mechanism. For instance, the Scala term
+ *  <code>'mysym</code> will invoke the constructor of the
+ *  <code>Symbol</code> class in the following way:
+ *  <code>new Symbol("mysym")</code>.
+ *
+ *  @author  Martin Odersky
+ *  @version 1.0, 08/08/2003
+ */
 case class Symbol(name: String) {
   override def toString() = "'" + name;
 }
-
diff --git a/sources/scala/collection/Map.scala b/sources/scala/collection/Map.scala
index f478146190..14c2f3ef1a 100644
--- a/sources/scala/collection/Map.scala
+++ b/sources/scala/collection/Map.scala
@@ -25,38 +25,83 @@ package scala.collection;
  *  @version 1.0, 08/07/2003
  */
 trait Map[A, +B] with PartialFunction[A, B]
-                 with Iterable[Pair[A, B]] {
+                 with Iterable[Pair[A, B]]
+                 with StructuralEquality[Map[A, B]]{
 
+    /** Compute the number of key-to-value mappings.
+     *
+     *  @returns the number of mappings
+     */
     def size: Int;
 
+    /** 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
+     *  @returns the value of the mapping, if it exists
+     */
     def get(key: A): Option[B];
 
+    /** Is this an empty map?
+     *
+     *  @returns true, iff the map is empty.
+     */
     def isEmpty: Boolean = (size == 0);
 
+    /** 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
+     *  @returns the value associated with the given key.
+     */
     def apply(key: A): B = get(key) match {
         case None => error("key not found")
         case Some(value) => value
     }
 
+    /** Is the given key mapped to a value by this map?
+     *
+     *  @param	 key		the key
+     *  @returns true, iff there is a mapping for key in this map
+     */
     def contains(key: A): Boolean = get(key) match {
         case None => false
         case Some(_) => true
     }
 
+    /** Does this map contain a mapping from the given key to a value?
+     *
+     *  @param	 key		the key
+     *  @returns true, iff there is a mapping for key in this map
+     */
     def isDefinedAt(key: A) = contains(key);
 
+    /** Creates an iterator for all keys.
+     *
+     *  @returns an iterator over all keys.
+     */
     def keys: Iterator[A] = new Iterator[A] {
         val iter = Map.this.elements;
         def hasNext = iter.hasNext;
         def next = iter.next._1;
     }
 
+    /** Creates an iterator for a contained values.
+     *
+     *  @returns an iterator over all values.
+     */
     def values: Iterator[B] = new Iterator[B] {
         val iter = Map.this.elements;
         def hasNext = iter.hasNext;
         def next = iter.next._2;
     }
 
+    /** Executes the given function for all (key, value) pairs
+     *  contained in this map.
+     *
+     *  @param		f	the function to execute.
+     */
     def foreach(f: (A, B) => Unit) = {
         val iter = elements;
         while (iter.hasNext) {
@@ -65,15 +110,60 @@ trait Map[A, +B] with PartialFunction[A, B]
         }
     }
 
+	/** Applies the given predicate to all (key, value) mappings
+	 *  contained in this map and returns true if this predicate
+	 *  yields true for all mappings.
+	 *
+	 *  @param		p	the predicate
+	 *  @returns	true, iff p yields true for all mappings.
+	 */
+	def forall(p: (A, B) => Boolean): Boolean = elements.forall {
+		case Pair(key, value) => p(key, value)
+	}
+
+    /** Applies the given predicate to all (key, value) mappings
+	 *  contained in this map and returns true if there is at least
+	 *  one mapping for which this predicate yields true.
+	 *
+	 *  @param		p	the predicate
+	 *  @returns	true, iff there is at least one mapping for which
+	 *              p yields true.
+	 */
+    def exists(p: (A, B) => Boolean): Boolean = elements.exists {
+		case Pair(key, value) => p(key, value)
+	}
+
+	/** Creates a list of all (key, value) mappings.
+	 *
+	 *  @returns	the list of all mappings
+	 */
     def toList: List[Pair[A, B]] = {
         var res: List[Pair[A, B]] = Nil;
-        val iter = elements;
-        while (iter.hasNext) {
-            res = iter.next :: res;
-        }
+        elements.foreach { mapping => res = mapping :: res; };
         res;
     }
 
+    /** Compares two maps structurally; i.e. checks if all mappings
+     *  contained in this map are also contained in the other map,
+     *  and vice versa.
+     *
+     *  @returns	true, iff both maps contain exactly the same mappings.
+     */
+	override def ===[C >: Map[A, B]](that: C): Boolean =
+    	that.isInstanceOf[Map[A, B]] &&
+    	{ val other = that.asInstanceOf[Map[A, B]];
+    	  this.size == other.size &&
+    	  this.elements.forall {
+    	      case Pair(key, value) => other.get(key) match {
+    	          case None => false;
+    	          case Some(otherval) => value == otherval;
+    	      }
+    	  }};
+
+    /** Creates a string representation for this map.
+     *
+     *  @returns	a string showing all mappings
+     */
     override def toString() =
         if (size == 0)
             "{}"
diff --git a/sources/scala/collection/Set.scala b/sources/scala/collection/Set.scala
index 4e5b020167..76dd891f47 100644
--- a/sources/scala/collection/Set.scala
+++ b/sources/scala/collection/Set.scala
@@ -23,49 +23,36 @@ package scala.collection;
  *  @author  Matthias Zenger
  *  @version 1.0, 08/07/2003
  */
-trait Set[A] with Iterable[A] {
+trait Set[A] with Iterable[A]
+             with StructuralEquality[Set[A]] {
 
     def size: Int;
 
+    def contains(elem: A): Boolean;
+
     def isEmpty: Boolean = (size == 0);
 
-    def contains(elem: A): Boolean;
+    def subsetOf(that: Set[A]): Boolean = forall(that.contains);
 
-    def subsetOf(that: Set[A]): Boolean = {
-        val iter = elements;
-        var res = true;
-        while (res && iter.hasNext) {
-            res = that.contains(iter.next);
-        }
-        res
-    }
+    def foreach(f: A => Unit): Unit = elements.foreach(f);
 
-    def foreach(f: A => Unit): Unit = {
-        val iter = elements;
-        while (iter.hasNext) {
-            f(iter.next);
-        }
-    }
+    def forall(p: A => Boolean): Boolean = elements.forall(p);
 
-    def exists(p: A => Boolean): Boolean = {
-        val iter = elements;
-        var res = false;
-        while (!res && iter.hasNext) {
-            if (p(iter.next)) { res = true; }
-        }
-        res;
-    }
+    def exists(p: A => Boolean): Boolean = elements.exists(p);
 
     def toList: List[A] = {
         var res: List[A] = Nil;
-        val iter = elements;
-        while (iter.hasNext) {
-            res = iter.next :: res;
-        }
+        elements.foreach { elem => res = elem :: res; }
         res;
     }
 
-    override def toString() =
+    override def ===[B >: Set[A]](that: B): Boolean =
+    	that.isInstanceOf[Set[A]] &&
+    	{ val other = that.asInstanceOf[Set[A]];
+    	  this.size == other.size &&
+    	  this.elements.forall(other.contains) };
+
+    override def toString(): String =
         if (size == 0)
             "{}"
         else
diff --git a/sources/scala/collection/immutable/Queue.scala b/sources/scala/collection/immutable/Queue.scala
index 99171e1497..a3291d46e4 100644
--- a/sources/scala/collection/immutable/Queue.scala
+++ b/sources/scala/collection/immutable/Queue.scala
@@ -20,16 +20,19 @@ object Queue {
     val Empty:Queue[All] = new Queue(Nil, Nil);
 }
 
-class Queue[+A](in:List[A],out:List[A]) extends Seq[A] {
-  /** Returns the <code>n</code>-th element of this queue.
-   * The first element is at position 0.
-   * @param n index of the element to return
-   * @return the element at position <code>n</code> in this list.
-   * @throws java.lang.RuntimeException if the list is too short.
-   */
+class Queue[+A](in: List[A], out: List[A]) extends Seq[A]
+                                           with StructuralEquality[Queue[A]] {
+
+    /** Returns the <code>n</code>-th element of this queue.
+     *  The first element is at position 0.
+     *
+     *  @param n index of the element to return
+     *  @return the element at position <code>n</code> in this list.
+     *  @throws java.lang.RuntimeException if the list is too short.
+     */
     def apply(n: Int): A =
-	if (n < out.length) out.apply(n)
-	    else (in.reverse).apply(n - out.length);
+    	if (n < out.length) out.apply(n)
+	    else in.reverse.apply(n - out.length);
 
     /** Returns the elements in the list as an iterator
      */
@@ -50,9 +53,7 @@ class Queue[+A](in:List[A],out:List[A]) extends Seq[A] {
      *
      *  @param  elem        the element to insert
      */
-    def +[B >: A](elem: B):Queue[B] = {
-	new Queue(elem::in,out);
-    }
+    def +[B >: A](elem: B):Queue[B] = new Queue(elem::in,out);
 
     /** Returns a new que with all all elements provided by
      *  an <code>Iterable</code> object added at the end of
@@ -63,9 +64,9 @@ class Queue[+A](in:List[A],out:List[A]) extends Seq[A] {
      *  @param  iter        an iterable object
      */
     def +[B >: A](iter: Iterable[B]) = {
-	var q:List[B] = in;
-	iter.elements.foreach(e => q = (e::q));
-	new Queue(q,out);
+		var q:List[B] = in;
+		iter.elements.foreach(e => q = (e::q));
+		new Queue(q,out);
     }
 
     /** Returns a new queue with all elements added.
@@ -80,81 +81,79 @@ class Queue[+A](in:List[A],out:List[A]) extends Seq[A] {
      *  @returns the first element of the queue.
      */
     def dequeue: Pair[A,Queue[A]] = {
-	var newOut:List[A]=Nil;
-	var newIn:List[A]=Nil;
-        if (out.isEmpty) {
-	    newOut = in.reverse;
-	    newIn = Nil;
-	} else {
-	    newOut = out;
-	    newIn = in;
-	}
-	if (newOut.isEmpty)
-  	  error("queue empty");
-        else {
+		var newOut:List[A]=Nil;
+		var newIn:List[A]=Nil;
+        	if (out.isEmpty) {
+	    	newOut = in.reverse;
+	    	newIn = Nil;
+		} else {
+	    	newOut = out;
+	    	newIn = in;
+		}
+		if (newOut.isEmpty)
+  	  		error("queue empty");
+        else
             Pair(newOut.head,new Queue(newIn,newOut.tail));
-        }
     }
 
-   /** Returns the first element in the queue, or throws an error if there
+    /** Returns the first element in the queue, or throws an error if there
      *  is no element contained in the queue.
      *
      *  @returns the first element.
      */
-    def front: A = {
-	if (out.isEmpty) {
-	    if (in.isEmpty) {
-		error("queue empty");
-	    } else {in.last;}
-	} else
-	out.head;
-    }
+    def front: A =
+		if (out.isEmpty) {
+	    	if (in.isEmpty) error("queue empty") else in.last;
+		} else
+			out.head;
+
+    /** Returns a string representation of this queue. The resulting string
+     * begins with the string <code>start</code> and is finished by the string
+     *   <code>end</code>. Inside, the string representations of elements (w.r.t.
+     * the method <code>toString()</code>) are separated by the string
+     * <code>sep</code>.
+     * <p>
+     * Ex: <br>
+     * <code>Queue(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code>
+     * @param start starting string.
+     * @param sep separator string.
+     * @param end ending string.
+     * @return a string representation of this list.
+     */
+	def mkString(start: String, sep: String, end: String): String =
+        (out ::: (in.reverse)).mkString(start,sep,end);
 
-  /** Returns a string representation of this queue. The resulting string
-  * begins with the string <code>start</code> and is finished by the string
-  * <code>end</code>. Inside, the string representations of elements (w.r.t.
-  * the method <code>toString()</code>) are separated by the string
-  * <code>sep</code>.
-  * <p>
-  * Ex: <br>
-  * <code>Queue(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code>
-  * @param start starting string.
-  * @param sep separator string.
-  * @param end ending string.
-  * @return a string representation of this list.
-  */
-  def mkString(start: String, sep: String, end: String): String =
-      (out:::(in.reverse)).mkString(start,sep,end);
-
-  /** Returns a string representation of this queue.
-   */
-  override def toString() = (out:::(in.reverse)).mkString("Queue(", ",", ")");
-
-  /** Compares two queues for equality by comparing
-   *  each element in the queues.
-   */
-  override def equals(o :Any) = o match {
-    case q: Queue[Any] =>
-      /* A function that compares the element at
-         position index in q with the element at
-         the same position in this (queue).
-         If they are equal the next element is
-         compared. */
-      def eqe(index: int):Boolean = {
-	/* If all elements are compared
-	the queues are equal. */
-	index >= this.length ||
-	/* Otherwise: compare the elements */
-	(q.apply(index) == this.apply(index) &&
-	 /* if they are equal compare the rest. */
-	   eqe(index+1))
-      }
-      /* If the length of the ques are the same,
-         compare each element, starting at index 0. */
-      (q.length == this.length) && eqe(0);
-
-    case _ => false; /* o is not a queue: not equal to this. */
-  }
+    /** Returns a string representation of this queue.
+     */
+    override def toString() = (out ::: (in.reverse)).mkString("Queue(", ",", ")");
+
+    /** Compares two queues for equality by comparing
+     *  each element in the queues.
+     *
+     *  @returns true, iff the two queues are structurally equal.
+     */
+    override def equals(o: Any): Boolean = o match {
+		case q: Queue[Any] =>
+		  /* A function that compares the element at
+			 position index in q with the element at
+			 the same position in this (queue).
+			 If they are equal the next element is
+			 compared. */
+		  def eqe(index: int):Boolean = {
+		/* If all elements are compared
+		the queues are equal. */
+		index >= this.length ||
+		/* Otherwise: compare the elements */
+		(q.apply(index) == this.apply(index) &&
+		 /* if they are equal compare the rest. */
+		   eqe(index+1))
+		  }
+		  /* If the length of the ques are the same,
+			 compare each element, starting at index 0. */
+		  (q.length == this.length) && eqe(0);
+
+		case _ => false; /* o is not a queue: not equal to this. */
+    }
 }
 
 
diff --git a/sources/scala/collection/immutable/Stack.scala b/sources/scala/collection/immutable/Stack.scala
index fdb9b03b37..1c63d3d69d 100644
--- a/sources/scala/collection/immutable/Stack.scala
+++ b/sources/scala/collection/immutable/Stack.scala
@@ -22,7 +22,7 @@ object Stack {
  *  @author  Matthias Zenger
  *  @version 1.0, 10/07/2003
  */
-class Stack[+A] with Seq[A] {
+class Stack[+A] with Seq[A] with StructuralEquality[Stack[A]] {
 
     /** Checks if this stack is empty.
      *
@@ -105,8 +105,10 @@ class Stack[+A] with Seq[A] {
      *           same elements in the same order.
      */
     override def equals(obj: Any): Boolean =
-        if (obj is Stack[A]) toList.equals((obj as Stack[A]).toList);
-        else false;
+        if (obj.isInstanceOf[Stack[A]])
+        	toList.equals((obj.asInstanceOf[Stack[A]]).toList);
+        else
+        	false;
 
     /** Returns the hash code for this stack.
      *