New collection class.

6 files changed, 488 insertions, 115 deletions

diff --git a/sources/scala/collection/immutable/Order.scala b/sources/scala/collection/immutable/Order.scala
deleted file mode 100644
index 3b3ca009c6..0000000000
--- a/sources/scala/collection/immutable/Order.scala
+++ /dev/null
@@ -1,115 +0,0 @@
-/*                     __                                               *\
-**     ________ ___   / /  ___     Scala API                            **
-**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
-**  __\ \/ /__/ __ |/ /__/ __ |                                         **
-** /____/\___/_/ |_/____/_/ | |                                         **
-**                          |/                                          **
-** $Id$
-\*                                                                      */
-
-package scala.collection.immutable;
-
-/** 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) &amp;&amp; !(e2 &lt; e1) &amp;&amp; !(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/mutable/PriorityQueue.scala b/sources/scala/collection/mutable/PriorityQueue.scala
new file mode 100644
index 0000000000..848069a918
--- /dev/null
+++ b/sources/scala/collection/mutable/PriorityQueue.scala
@@ -0,0 +1,150 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala.collection.mutable;
+
+
+/** This class implements priority queues using a heap. The
+ *  elements of the queue have to be ordered in terms of the
+ *  <code>Ordered[T]</code> trait.
+ *
+ *  @author  Matthias Zenger
+ *  @version 1.0, 03/05/2004
+ */
+class PriorityQueue[A <% Ordered[A]] extends ResizableArray[A] {
+  	size = size + 1; // we do not use array(0)
+
+  	protected def fixUp(as: Array[A], m: Int): Unit = {
+  		var k: Int = m;
+  	    while ((k > 1) && (as(k / 2) < as(k))) {
+  	    	swap(k, k / 2);
+  	    	k = k / 2;
+  	    }
+  	}
+
+  	protected def fixDown(as: Array[A], m: Int, n: Int): Unit = {
+  	    var k: Int = m;
+  	    var loop: Boolean = true;
+  	    while (loop && (n >= 2 * k)) {
+  	    	var j = 2 * k;
+  	    	if ((j < n) && (as(j) < as(j + 1)))
+  	    		j = j + 1;
+  	    	if (!(as(k) < as(j)))
+  	    	    loop = false;
+  	    	else {
+  	    	    val h = as(k);
+  	    	    as(k) = as(j);
+  	    	    as(j) = h;
+  	    		k = j;
+  	    	}
+  	    }
+  	}
+
+  	/** Checks if the queue is empty.
+     *
+     *  @return true, iff there is no element in the queue.
+     */
+  	def isEmpty: Boolean = size < 2;
+
+  	/** Inserts a single element into the priority queue.
+     *
+     *  @param  elem        the element to insert
+     */
+  	def +=(elem: A): Unit = {
+  		ensureSize(1);
+  		array(size) = elem;
+  		fixUp(array, size);
+  		size = size + 1;
+  	}
+
+    /** Adds all elements provided by an <code>Iterable</code> object
+     *  into the priority queue.
+     *
+     *  @param  iter        an iterable object
+     */
+    def ++=(iter: Iterable[A]): Unit = iter.elements.foreach(e => this += e);
+
+    /** Adds all elements to the queue.
+     *
+     *  @param  elems       the elements to add.
+     */
+    def enqueue(elems: A*): Unit = (this ++= elems);
+
+  	/** Returns the element with the highest priority in the queue,
+  	 *  and removes this element from the queue.
+     *
+     *  @return   the element with the highest priority.
+     */
+  	def dequeue: A = {
+  		if (size > 1) {
+  		    size = size - 1;
+  			swap(1, size);
+  			fixDown(array, 1, size - 1);
+  			array(size)
+  		} else
+  			error("no element to remove from heap");
+  	}
+
+    /** Returns the element with the highest priority in the queue,
+     *  or throws an error if there is no element contained in the queue.
+     *
+     *  @return   the element with the highest priority.
+     */
+  	def max: A = if (size > 1) array(1) else error("queue is empty");
+
+    /** Removes all elements from the queue. After this operation is completed,
+     *  the queue will be empty.
+     */
+    def clear: Unit = {
+        size = 1;
+    }
+
+    /** Returns an iterator which yiels all the elements of the priority
+     *  queue in descending priority order.
+     *
+     *  @return  an iterator over all elements sorted in descending order.
+     */
+  	override def elements: Iterator[A] = new Iterator[A] {
+  		val as: Array[A] = new Array[A](size);
+  		java.lang.System.arraycopy(array, 0, as, 0, size);
+  		var i = size - 1;
+  		def hasNext: Boolean = i > 0;
+        def next: A = {
+            val res = as(1);
+            as(1) = as(i);
+            i = i - 1;
+  			fixDown(as, 1, i);
+  			res
+        }
+  	}
+
+    /** Checks if two queues are structurally identical.
+     *
+     *  @return true, iff both queues contain the same sequence of elements.
+     */
+    override def equals(that: Any): Boolean =
+        that.isInstanceOf[PriorityQueue[A]] &&
+        { val other = that.asInstanceOf[PriorityQueue[A]];
+          elements.zip(other.elements).forall {
+            case Pair(thiselem, thatelem) => thiselem == thatelem;
+        }};
+
+    /** The hashCode method always yields an error, since it is not
+     *  safe to use mutable queues as keys in hash tables.
+     *
+     *  @return never.
+     */
+    override def hashCode(): Int = error("unsuitable as hash key");
+
+    /** Returns a textual representation of a queue as a string.
+     *
+     *  @return the string representation of this queue.
+     */
+    override def toString() = toList.mkString("PriorityQueue(", ", ", ")");
+}
diff --git a/sources/scala/collection/mutable/ResizableArray.scala b/sources/scala/collection/mutable/ResizableArray.scala
new file mode 100644
index 0000000000..08ff972fc0
--- /dev/null
+++ b/sources/scala/collection/mutable/ResizableArray.scala
@@ -0,0 +1,61 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala.collection.mutable;
+
+
+/** This class is used internally to implement data structures that
+ *  are based on resizable arrays.
+ *
+ *  @author  Matthias Zenger
+ *  @version 1.0, 03/05/2004
+ */
+abstract class ResizableArray[A] with Iterable[A] {
+	import java.lang.System.arraycopy;
+
+   	protected val initialSize: Int = 16;
+	protected var array: Array[A] = new Array[A](initialSize);
+	protected var size: Int = 0;
+
+	/** Extends the internal array if more elements are needed.
+	 */
+ 	protected def ensureSize(n: Int): Unit = {
+	    if ((size + n) > array.length) {
+	        val newar: Array[A] = new Array(array.length * 2);
+	        arraycopy(array, 0, newar, 0, size);
+	        array = newar;
+	    }
+	}
+
+	/** Swap two elements of this array.
+	 */
+  	protected def swap(a: Int, b: Int): Unit = {
+    	val h = array(a);
+    	array(a) = array(b);
+    	array(b) = h;
+  	}
+
+  	/** Move parts of the array.
+  	 */
+  	protected def copy(m: Int, n: Int, len: Int) = {
+  		arraycopy(array, m, array, n, len);
+  	}
+
+	/** Returns the length of this resizable array.
+	 */
+	def length: Int = size;
+
+	/** Returns a new iterator over all elements of this resizable array.
+     */
+    def elements: Iterator[A] = new Iterator[A] {
+        var i = 0;
+        def hasNext: Boolean = i < size;
+        def next: A = { i = i + 1; array(i - 1) }
+    }
+}
diff --git a/sources/scala/collection/mutable/SynchronizedPriorityQueue.scala b/sources/scala/collection/mutable/SynchronizedPriorityQueue.scala
new file mode 100644
index 0000000000..1afcb8171a
--- /dev/null
+++ b/sources/scala/collection/mutable/SynchronizedPriorityQueue.scala
@@ -0,0 +1,91 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala.collection.mutable;
+
+
+/** This class implements synchronized priority queues using a heap.
+ *  The elements of the queue have to be ordered in terms of the
+ *  <code>Ordered[T]</code> trait.
+ *
+ *  @author  Matthias Zenger
+ *  @version 1.0, 03/05/2004
+ */
+class SynchronizedPriorityQueue[A <% Ordered[A]] extends PriorityQueue[A] {
+
+  	/** Checks if the queue is empty.
+     *
+     *  @return true, iff there is no element in the queue.
+     */
+  	override def isEmpty: Boolean = synchronized { super.isEmpty; }
+
+  	/** Inserts a single element into the priority queue.
+     *
+     *  @param  elem        the element to insert
+     */
+  	override def +=(elem: A): Unit = synchronized { super.+=(elem); }
+
+    /** Adds all elements provided by an <code>Iterable</code> object
+     *  into the priority queue.
+     *
+     *  @param  iter        an iterable object
+     */
+    override def ++=(iter: Iterable[A]): Unit = synchronized { super.++=(iter); }
+
+    /** Adds all elements to the queue.
+     *
+     *  @param  elems       the elements to add.
+     */
+    override def enqueue(elems: A*): Unit = synchronized { super.++=(elems); }
+
+  	/** Returns the element with the highest priority in the queue,
+  	 *  and removes this element from the queue.
+     *
+     *  @return   the element with the highest priority.
+     */
+  	override def dequeue: A = synchronized { super.dequeue; }
+
+    /** Returns the element with the highest priority in the queue,
+     *  or throws an error if there is no element contained in the queue.
+     *
+     *  @return   the element with the highest priority.
+     */
+  	override def max: A = synchronized { super.max; }
+
+    /** Removes all elements from the queue. After this operation is completed,
+     *  the queue will be empty.
+     */
+    override def clear: Unit = synchronized { super.clear; }
+
+    /** Returns an iterator which yiels all the elements of the priority
+     *  queue in descending priority order.
+     *
+     *  @return  an iterator over all elements sorted in descending order.
+     */
+  	override def elements: Iterator[A] = synchronized { super.elements; }
+
+    /** Checks if two queues are structurally identical.
+     *
+     *  @return true, iff both queues contain the same sequence of elements.
+     */
+    override def equals(that: Any): Boolean = synchronized { super.equals(that); }
+
+    /** The hashCode method always yields an error, since it is not
+     *  safe to use mutable queues as keys in hash tables.
+     *
+     *  @return never.
+     */
+    override def hashCode(): Int = synchronized { super.hashCode(); }
+
+    /** Returns a textual representation of a queue as a string.
+     *
+     *  @return the string representation of this queue.
+     */
+    override def toString(): String = synchronized { super.toString(); }
+}
diff --git a/sources/scala/collection/mutable/SynchronizedQueue.scala b/sources/scala/collection/mutable/SynchronizedQueue.scala
new file mode 100644
index 0000000000..caf17d91d2
--- /dev/null
+++ b/sources/scala/collection/mutable/SynchronizedQueue.scala
@@ -0,0 +1,85 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala.collection.mutable;
+
+
+/** This is a synchronized version of the <code>Queue[T]</code> class. It
+ *  implements a data structure that allows one to insert and retrieve
+ *  elements in a first-in-first-out (FIFO) manner.
+ *
+ *  @author  Matthias Zenger
+ *  @version 1.0, 03/05/2004
+ */
+class SynchronizedQueue[A] extends Queue[A] {
+
+    /** Checks if the queue is empty.
+     *
+     *  @return true, iff there is no element in the queue.
+     */
+    override def isEmpty: Boolean = synchronized { super.isEmpty; }
+
+    /** Inserts a single element at the end of the queue.
+     *
+     *  @param  elem        the element to insert
+     */
+    override def +=(elem: A): Unit = synchronized { super.+=(elem); }
+
+    /** Adds all elements provided by an <code>Iterable</code> object
+     *  at the end of the queue. The elements are prepended in the order they
+     *  are given out by the iterator.
+     *
+     *  @param  iter        an iterable object
+     */
+    override def ++=(iter: Iterable[A]): Unit = synchronized { super.++=(iter); }
+
+    /** Adds all elements to the queue.
+     *
+     *  @param  elems       the elements to add.
+     */
+    override def enqueue(elems: A*): Unit = synchronized { super.++=(elems); }
+
+    /** Returns the first element in the queue, and removes this element
+     *  from the queue.
+     *
+     *  @return the first element of the queue.
+     */
+    override def dequeue: A = synchronized { super.dequeue; }
+
+    /** Returns the first element in the queue, or throws an error if there
+     *  is no element contained in the queue.
+     *
+     *  @return the first element.
+     */
+    override def front: A = synchronized { super.front; }
+
+    /** Removes all elements from the queue. After this operation is completed,
+     *  the queue will be empty.
+     */
+    override def clear: Unit = synchronized { super.clear; }
+
+    /** Checks if two queues are structurally identical.
+     *
+     *  @return true, iff both queues contain the same sequence of elements.
+     */
+    override def equals(that: Any): Boolean = synchronized { super.equals(that); }
+
+    /** The hashCode method always yields an error, since it is not
+     *  safe to use mutable queues as keys in hash tables.
+     *
+     *  @return never.
+     */
+    override def hashCode(): Int = synchronized { super.hashCode(); }
+
+    /** Returns a textual representation of a queue as a string.
+     *
+     *  @return the string representation of this queue.
+     */
+    override def toString() = synchronized { super.toString(); }
+}
diff --git a/sources/scala/collection/mutable/SynchronizedStack.scala b/sources/scala/collection/mutable/SynchronizedStack.scala
new file mode 100644
index 0000000000..2469b20d67
--- /dev/null
+++ b/sources/scala/collection/mutable/SynchronizedStack.scala
@@ -0,0 +1,101 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala.collection.mutable;
+
+
+/** This is a synchronized version of the <code>Stack[T]</code> class. It
+ *  implements a data structure which allows to store and retrieve
+ *  objects in a last-in-first-out (LIFO) fashion.
+ *
+ *  @author  Matthias Zenger
+ *  @version 1.0, 03/05/2004
+ */
+class SynchronizedStack[A] extends Stack[A] {
+
+    /** Checks if the stack is empty.
+     *
+     *  @return true, iff there is no element on the stack
+     */
+    override def isEmpty: Boolean = synchronized { super.isEmpty }
+
+    /** Pushes a single element on top of the stack.
+     *
+     *  @param  elem        the element to push onto the stack
+     */
+    override def +=(elem: A): Unit = synchronized { super.+=(elem); }
+
+    /** Pushes all elements provided by an <code>Iterable</code> object
+     *  on top of the stack. The elements are pushed in the order they
+     *  are given out by the iterator.
+     *
+     *  @param  iter        an iterable object
+     */
+    override def ++=(iter: Iterable[A]): Unit = synchronized { super.++=(iter); }
+
+    /** Pushes a sequence of elements on top of the stack. The first element
+     *  is pushed first, etc.
+     *
+     *  @param  elems       a sequence of elements
+     */
+    override def push(elems: A*): Unit = synchronized { super.++=(elems); }
+
+    /** Returns the top element of the stack. This method will not remove
+     *  the element from the stack. An error is signaled if there is no
+     *  element on the stack.
+     *
+     *  @return the top element
+     */
+    override def top: A = synchronized { super.top; }
+
+    /** Removes the top element from the stack.
+     */
+    override def pop: A = synchronized { super.pop; }
+
+    /**
+     * Removes all elements from the stack. After this operation completed,
+     * the stack will be empty.
+     */
+    override def clear: Unit = synchronized { super.clear; }
+
+    /** Returns an iterator over all elements on the stack. This iterator
+     *  is stable with respect to state changes in the stack object; i.e.
+     *  such changes will not be reflected in the iterator. The iterator
+     *  issues elements in the order they were inserted into the stack
+     *  (FIFO order).
+     *
+     *  @return an iterator over all stack elements.
+     */
+    override def elements: Iterator[A] = synchronized { super.elements; }
+
+    /** Creates a list of all stack elements in FIFO order.
+     *
+     *  @return the created list.
+     */
+    override def toList: List[A] = synchronized { super.toList; }
+
+    /** Checks if two stacks are structurally identical.
+     *
+     *  @return true, iff both stacks contain the same sequence of elements.
+     */
+    override def equals(that: Any): Boolean = synchronized { super.equals(that); }
+
+    /** The hashCode method always yields an error, since it is not
+     *  safe to use mutable stacks as keys in hash tables.
+     *
+     *  @return never.
+     */
+    override def hashCode(): Int = synchronized { super.hashCode(); }
+
+    /** Returns a textual representation of a stack as a string.
+     *
+     *  @return the string representation of this stack.
+     */
+    override def toString() = synchronized { super.toString(); }
+}