New collection classes.

8 files changed, 408 insertions, 178 deletions

diff --git a/sources/scala/HashMap.scala b/sources/scala/HashMap.scala
index 9427108f00..ed6519a383 100644
--- a/sources/scala/HashMap.scala
+++ b/sources/scala/HashMap.scala
@@ -11,129 +11,30 @@ package scala;
 
 /** I promise, there will be some documentation soon! :-) Matthias
  */
-class HashMap[A, B] extends MutableMap[A, B] {
+class HashMap[A, B] extends MutableMap[A, B] with HashTable[A] {
 
-    /** The load factor for the hash table.
-     */
-    protected val loadFactor: Float = 0.75f;
-
-    /** The initial size of the hash table.
-     */
-   	protected val initialSize: Int = 16;
-
-    /** The actual hash table.
-     */
-  	protected var table: Array[List[Entry]] = new Array(initialSize);
-  	initTable(initialSize - 1);
-
-    /** The number of mappings contained in this hash table.
-     */
-    protected var tableSize: Int = 0;
-
-    /** The next size value at which to resize (capacity * load factor).
-     */
-    protected var threshold: Int = ((initialSize as Float) * loadFactor) as Int;
-
-    /** Returns the size of this hash map.
-     */
-    def size = tableSize;
-
-    /** Returns <tt>true</tt> if this map contains no mappings.
-     */
-    def isEmpty = (tableSize == 0);
-
-    def apply(key: A) = table(index(key)).find(entryFor(key)) match {
-      case None => null
-      case Some(e) => e.value
+    def get(key: A) = findEntry(key) match {
+		case None => None
+		case Some(e) => Some(e.value);
     }
 
-    def get(key: A) = table(index(key)).find(entryFor(key)) match {
-      case None => None
-      case Some(e) => Some(e.value);
+    def update(key: A, value: B) = findEntry(key) match {
+ 		case None => addEntry(new Entry(key, value));
+		case Some(e) => e.value = value;
     }
 
-    def update(key: A, value: B) = {
-        val h = index(key);
-        System.out.println("update(" + key + "<" + h + ">, " + value + ")");
-        table(h).find(entryFor(key)) match {
-            case None => addEntry(key, value, h);
-            case Some(e) => e.value = value;
-       	}
-    }
-
-    def put(key: A, value: B) = {
+    def remove(key: A) = {
     	val old = apply(key);
-    	update(key, value);
+    	removeEntry(key);
     	old;
     }
 
-    /*
-    def +=(key: A) = new AssignValue(key);
-
-    def +=(map: Map[A, B]) = {
-    	val iter = map.iterator;
-    	while (iter.hasNext) {
-    		val Pair(key, value) = iter.next;
-    		this(key) = value;
-    	}
-    }
-    */
-
-    def remove(key: A) = {
-    	val old = get(key);
-    	old match {
-    		case None => null
-    		case Some(value) => {
-    			val idx = index(key);
-    			table(idx) = table(idx).filter(e => e.key != key);
-    			tableSize = tableSize - 1;
-    			value;
-    		}
-    	}
-    }
-
-    def isDefinedAt(key: A) = table(index(key)).exists(entryFor(key));
-
-    def contains(key: A) = isDefinedAt(key);
-
-    def clear = {
-    	initTable(table.length - 1);
-    	tableSize = 0;
-    }
-
-    def keys = new Iterator[A] {
-    	val iter = entries;
-  		def hasNext = iter.hasNext;
-    	def next = iter.next.key;
-  	}
-
-  	def values = new Iterator[B] {
-  		val iter = entries;
-  		def hasNext = iter.hasNext;
-    	def next = iter.next.value;
-  	}
-
   	def iterator = new Iterator[Pair[A, B]] {
   		val iter = entries;
   		def hasNext = iter.hasNext;
     	def next = iter.next.toPair;
   	}
 
-  	override def toString() =
-  		if (tableSize == 0) "{}"
-  		else "{" + {
-  			val iter = entries;
-  			var res = iter.next.toString();
-  			while (iter.hasNext) {
-  				res = res + ", " + iter.next;
-  			}
-  			res;
-  		} + "}";
-
-  	class AssignValue(key: A) {
-  		def ->(value: B) = update(key, value);
- 	}
-
     protected class Entry(k: A, v: B) {
     	def key = k;
     	var value = v;
@@ -141,66 +42,5 @@ class HashMap[A, B] extends MutableMap[A, B] {
     	override def toString() = k.toString() + " -> " + value;
     }
 
-  	protected def entries = new Iterator[Entry] {
-  		val iterTable = table;
-  		var idx = table.length - 1;
-  		var xs = iterTable(idx);
-  		scan();
-  		def hasNext = !xs.isEmpty;
-  		def next = {
-  			val res = xs.head;
-  			xs = xs.tail;
-  			scan();
-  			res;
-  		}
-  		def scan(): Unit = if (xs.isEmpty && (idx > 0)) {
-  			idx = idx - 1;
-  			xs = iterTable(idx);
-  			scan();
-  		}
-  	}
-
-    private def entryFor(key: A) = (e: Entry => e.key == key);
-
-    private def initTable(n: Int): Unit = {
-        table(n) = Nil;
-        if (n > 0) initTable(n - 1);
-    }
-
-    private def addEntry(key: A, value: B, hash: Int) = {
-    	table(hash) = (new Entry(key, value)) :: table(hash);
-    	tableSize = tableSize + 1;
-    	if (tableSize > threshold)
-    	    resize(2 * table.length);
-    }
-
-    private def resize(newSize: Int) = {
-        val newTable: Array[List[Entry]] = new Array(newSize);
-        initTable(newSize - 1);
-        def rehash(i: Int) = {
-        	if (i >= 0)
-        		rehashList(table(i));
-        }
-        def rehashList(xs: List[Entry]): Unit = xs.match {
-            case Nil => ()
-            case e :: es => {
-                val idx = hash(e.key) & (newSize - 1);
-                newTable(idx) = e :: newTable(idx);
-                rehashList(es);
-            }
-        }
-        rehash(table.length - 1);
-        table = newTable;
-        threshold = ((initialSize as Float) * loadFactor) as Int;
-    }
-
-    private def hash(x: A) = {
-		var h: Int = x.hashCode();
-        h = h + ~(h << 9);
-        h = h ^ (h >>> 14);
-        h = h + (h << 4);
-        h ^ (h >>> 10);
-    }
-
-    private def index(x: A) = hash(x) & (table.length - 1);
+ 	protected def entryKey(e: Entry) = e.key;
 }
diff --git a/sources/scala/HashSet.scala b/sources/scala/HashSet.scala
new file mode 100644
index 0000000000..08d4b95d5b
--- /dev/null
+++ b/sources/scala/HashSet.scala
@@ -0,0 +1,33 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+/** I promise, there will be some documentation soon! :-) Matthias
+ */
+class HashSet[A] extends Set[A] with HashTable[A] {
+
+	def contains(elem: A): Boolean = findEntry(elem) match {
+		case None => false
+		case Some(_) => true
+	}
+
+	def add(elem: A): Unit = findEntry(elem) match {
+		case None => addEntry(elem);
+		case Some(_) =>
+	}
+
+	def remove(elem: A): Unit = removeEntry(elem);
+
+  	def iterator = entries;
+
+	protected type Entry = A;
+
+	protected def entryKey(e: Entry) = e;
+}
diff --git a/sources/scala/HashTable.scala b/sources/scala/HashTable.scala
new file mode 100644
index 0000000000..00edab3947
--- /dev/null
+++ b/sources/scala/HashTable.scala
@@ -0,0 +1,131 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+/** I promise, there will be some documentation soon! :-) Matthias
+ */
+abstract class HashTable[A] {
+
+    /** The load factor for the hash table.
+     */
+    protected val loadFactor: Float = 0.75f;
+
+    /** The initial size of the hash table.
+     */
+   	protected val initialSize: Int = 16;
+
+    /** The actual hash table.
+     */
+  	protected var table: Array[List[Entry]] = new Array(initialSize);
+  	initTable(initialSize - 1);
+
+    /** The number of mappings contained in this hash table.
+     */
+    protected var tableSize: Int = 0;
+
+    /** The next size value at which to resize (capacity * load factor).
+     */
+    protected var threshold: Int = ((initialSize as Float) * loadFactor) as Int;
+
+    /** Returns the size of this hash map.
+     */
+    def size = tableSize;
+
+    protected def findEntry(key: A): Option[Entry] =
+    	table(index(elemHashCode(key))).find(entryFor(key));
+
+    protected def addEntry(e: Entry): Unit = {
+    	val h = index(elemHashCode(entryKey(e)));
+    	table(h) = e :: table(h);
+    	tableSize = tableSize + 1;
+    	if (tableSize > threshold)
+    	    resize(2 * table.length);
+    }
+
+    protected def removeEntry(key: A): Unit = {
+    	val old = findEntry(key);
+    	old match {
+    		case None =>
+    		case Some(e) => {
+    			val idx = index(elemHashCode(key));
+    			table(idx) = table(idx).filter(e => !elemEquals(entryKey(e), key));
+    			tableSize = tableSize - 1;
+    		}
+    	}
+    }
+
+    def clear = {
+    	initTable(table.length - 1);
+    	tableSize = 0;
+    }
+
+  	protected type Entry;
+
+  	protected def entryKey(e: Entry): A;
+
+  	protected def entries = new Iterator[Entry] {
+  		val iterTable = table;
+  		var idx = table.length - 1;
+  		var xs = iterTable(idx);
+  		scan();
+  		def hasNext = !xs.isEmpty;
+  		def next = {
+  			val res = xs.head;
+  			xs = xs.tail;
+  			scan();
+  			res;
+  		}
+  		def scan(): Unit = if (xs.isEmpty && (idx > 0)) {
+  			idx = idx - 1;
+  			xs = iterTable(idx);
+  			scan();
+  		}
+  	}
+
+    private def entryFor(key: A) = (e: Entry => elemEquals(entryKey(e), key));
+
+    private def initTable(n: Int): Unit = {
+        table(n) = Nil;
+        if (n > 0) initTable(n - 1);
+    }
+
+    private def resize(newSize: Int) = {
+        val newTable: Array[List[Entry]] = new Array(newSize);
+        initTable(newSize - 1);
+        def rehash(i: Int) = {
+        	if (i >= 0)
+        		rehashList(table(i));
+        }
+        def rehashList(xs: List[Entry]): Unit = xs.match {
+            case Nil => ()
+            case e :: es => {
+                val idx = improve(elemHashCode(entryKey(e))) & (newSize - 1);
+                newTable(idx) = e :: newTable(idx);
+                rehashList(es);
+            }
+        }
+        rehash(table.length - 1);
+        table = newTable;
+        threshold = ((initialSize as Float) * loadFactor) as Int;
+    }
+
+    protected def elemEquals(key1: A, key2: A): Boolean = (key1 == key2);
+
+    protected def elemHashCode(key: A) = key.hashCode();
+
+    protected final def improve(hcode: Int) = {
+		var h: Int = hcode + ~(hcode << 9);
+        h = h ^ (h >>> 14);
+        h = h + (h << 4);
+        h ^ (h >>> 10);
+    }
+
+    protected final def index(hcode: Int) = improve(hcode) & (table.length - 1);
+}
diff --git a/sources/scala/Iterable.scala b/sources/scala/Iterable.scala
new file mode 100644
index 0000000000..a0edf1a7f3
--- /dev/null
+++ b/sources/scala/Iterable.scala
@@ -0,0 +1,14 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+trait Iterable[+A] {
+	def iterator: Iterator[A];
+}
diff --git a/sources/scala/ListSet.scala b/sources/scala/ListSet.scala
new file mode 100644
index 0000000000..d5abe5406a
--- /dev/null
+++ b/sources/scala/ListSet.scala
@@ -0,0 +1,30 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+/** I promise, there will be some documentation soon! :-) Matthias
+ */
+class ListSet[A] extends Set[A] {
+	protected var elems: List[A] = Nil;
+
+	def size: Int = elems.length;
+
+	def contains(elem: A): Boolean = elems.contains(elem);
+
+	def add(elem: A): Unit = if (!elems.contains(elem)) elems = elem :: elems;
+
+	def remove(elem: A): Unit = { elems = elems.filter(e => e != elem); }
+
+	def clear: Unit = { elems = Nil; }
+
+	def iterator: Iterator[A] = elems.iterator;
+
+	override def toList: List[A] = elems;
+}
diff --git a/sources/scala/Map.scala b/sources/scala/Map.scala
index 236bf767b3..fb1c235486 100644
--- a/sources/scala/Map.scala
+++ b/sources/scala/Map.scala
@@ -11,14 +11,75 @@ package scala;
 
 /** I promise, there will be some documentation soon! :-) Matthias
  */
-trait Map[A, +B] with Function1[A, B] with PartialFunction[A, B] {
+trait Map[A, +B] with Function1[A, B]
+                 with PartialFunction[A, B]
+                 with Iterable[Pair[A, B]] {
+
 	def size: Int;
-    def isEmpty: Boolean;
+
+    def isEmpty: Boolean = (size == 0);
+
+    def apply(key: A): B = get(key) match {
+    	case None => null
+    	case Some(value) => value
+    }
+
 	def get(key: A): Option[B];
+
 	def remove(key: A): B;
-	def contains(key: A): Boolean;
+
+	def contains(key: A): Boolean = get(key) match {
+		case None => false
+		case Some(_) => true
+	}
+
+	def isDefinedAt(key: A) = contains(key);
+
 	def clear: Unit;
-	def keys: Iterator[A];
-	def values: Iterator[B];
-	def iterator: Iterator[Pair[A, B]];
+
+	def keys: Iterator[A] = new Iterator[A] {
+		val iter = iterator;
+  		def hasNext = iter.hasNext;
+    	def next = iter.next._1;
+	}
+
+	def values: Iterator[B] = new Iterator[B] {
+		val iter = iterator;
+  		def hasNext = iter.hasNext;
+    	def next = iter.next._2;
+	}
+
+	def foreach(f: (A, B) => Unit) = {
+		val iter = iterator;
+		while (iter.hasNext) {
+			val Pair(key, value) = iter.next;
+			f(key, value);
+		}
+	}
+
+	def filter(p: (A, B) => Boolean): Unit = toList foreach {
+		case Pair(key, value) => if (p(key, value)) { val old = remove(key); }
+	}
+
+	def toList: List[Pair[A, B]] = {
+		var res: List[Pair[A, B]] = Nil;
+		val iter = iterator;
+		while (iter.hasNext) {
+			res = iter.next :: res;
+		}
+		res;
+	}
+
+	override def toString() =
+  		if (size == 0)
+  			"{}"
+  		else
+  			"{" + {
+				val iter = iterator;
+				var res = iter.next.toString();
+				while (iter.hasNext) {
+					res = res + ", " + iter.next;
+				}
+				res;
+  			} + "}";
 }
diff --git a/sources/scala/MutableMap.scala b/sources/scala/MutableMap.scala
index 818f10f843..861a9f6b60 100644
--- a/sources/scala/MutableMap.scala
+++ b/sources/scala/MutableMap.scala
@@ -11,7 +11,41 @@ package scala;
 
 /** I promise, there will be some documentation soon! :-) Matthias
  */
-trait MutableMap[A, B] extends Map[A, B] {
+trait MutableMap[A, B] with Map[A, B] {
+
 	def update(key: A, value: B): Unit;
-	def put(key: A, value: B): B;
+
+	def put(key: A, value: B): B = {
+		val old = apply(key);
+		update(key, value);
+    	old;
+	}
+
+	def putAll(mappings: Pair[A, B]*) = {
+		val ys = mappings as List[Pair[A, B]];
+    	ys foreach { case Pair(key, value) => update(key, value); };
+	}
+
+	def putMap(map: Iterable[Pair[A, B]]): Unit = map.iterator foreach {
+		case Pair(key, value) => update(key, value);
+	}
+
+	def map(f: (A, B) => B): Unit = iterator foreach {
+		case Pair(key, value) => update(key, f(key, value));
+	}
+
+	override def toString() =
+  		if (size == 0)
+  			"{}"
+  		else
+  			"{" + {
+				val iter = iterator;
+				var res = mappingToString(iter.next);
+				while (iter.hasNext) {
+					res = res + ", " + mappingToString(iter.next);
+				}
+				res;
+  			} + "}";
+
+	def mappingToString(p: Pair[A, B]) = p._1.toString() + " -> " + p._2;
 }
diff --git a/sources/scala/Set.scala b/sources/scala/Set.scala
new file mode 100644
index 0000000000..17ca20015f
--- /dev/null
+++ b/sources/scala/Set.scala
@@ -0,0 +1,87 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+/** I promise, there will be some documentation soon! :-) Matthias
+ */
+trait Set[A] with Iterable[A] {
+
+	def size: Int;
+
+    def isEmpty: Boolean = (size == 0);
+
+	def contains(elem: A): Boolean;
+
+	def add(elem: A): Unit;
+
+	def addAll(elems: A*): Unit = {
+		val ys = elems as List[A];
+    	ys foreach { y => add(y); };
+	}
+
+	def addSet(that: Iterable[A]): Unit =
+		that.iterator.foreach(elem => add(elem));
+
+	def remove(elem: A): Unit;
+
+	def removeAll(elems: A*): Unit = {
+		val ys = elems as List[A];
+    	ys foreach { y => remove(y); };
+	}
+
+	def removeSet(that: Iterable[A]): Unit =
+		that.iterator.foreach(elem => remove(elem));
+
+	def intersect(that: Set[A]): Unit = filter(that.contains);
+
+	def clear: Unit;
+
+	def subsetOf(that: Set[A]): Boolean = {
+		val iter = iterator;
+		var res = true;
+		while (res && iter.hasNext) {
+			res = that.contains(iter.next);
+		}
+		res
+	}
+
+	def foreach(f: A => Unit) = {
+		val iter = iterator;
+		while (iter.hasNext) {
+			f(iter.next);
+		}
+	}
+
+	def filter(p: A => Boolean): Unit = toList foreach {
+		elem => if (p(elem)) remove(elem);
+	}
+
+	def toList: List[A] = {
+		var res: List[A] = Nil;
+		val iter = iterator;
+		while (iter.hasNext) {
+			res = iter.next :: res;
+		}
+		res;
+	}
+
+	override def toString() =
+  		if (size == 0)
+  			"{}"
+  		else
+  			"{" + {
+				val iter = iterator;
+				var res = iter.next.toString();
+				while (iter.hasNext) {
+					res = res + ", " + iter.next;
+				}
+				res;
+  			} + "}";
+}