Basic implementation of maps and sets.

2 files changed, 60 insertions, 21 deletions

diff --git a/sources/scala/collection/immutable/ListMap.scala b/sources/scala/collection/immutable/ListMap.scala
index ce21acbfc4..21c50bdd96 100644
--- a/sources/scala/collection/immutable/ListMap.scala
+++ b/sources/scala/collection/immutable/ListMap.scala
@@ -4,28 +4,57 @@
 **  __\ \/ /__/ __ |/ /__/ __ |                                         **
 ** /____/\___/_/ |_/____/_/ | |                                         **
 **                          |/                                          **
+** $Id$
 \*                                                                      */
 
-// $Id$
+package scala.collection.immutable;
 
 
-package scala.collections.immutable;
-
-
-class ListMap[A, B] extends Map[A, B] with DefaultMapModel[A, B] {
-
-    var xs: List[Entry] = Nil;
-
-    def size: Int = xs.length;
-
-    override def clear: Unit = { xs = Nil; }
-
-    protected def findEntry(key: A) = xs find {e => e.key == key};
-
-    protected def addEntry(e: Entry) = { xs = e :: xs; }
-
-    def remove(key: A) = { xs = xs filter {e => e.key != key}; }
+object ListMap {
+	def Empty[A, B] = new ListMap[A, B];
+}
 
-    protected def entries = xs.elements;
 
+/** This class implements immutable maps using a list-based data
+ *  structure. Instances of <code>ListMap</code> represent
+ *  empty maps; they can be either created by calling the constructor
+ *  directly, or by applying the function <code>ListMap.Empty</code>.
+ *
+ *  @author  Matthias Zenger
+ *  @version 1.0, 09/07/2003
+ */
+class ListMap[A, B] with Map[A, B, ListMap[A, B]] {
+
+    def size: Int = 0;
+
+    def get(key: A): Option[B] = None;
+
+	def update(key: A, value: B): ListMap[A, B] = new Node(key, value);
+
+    def -(key: A): ListMap[A, B] = this;
+
+    def elements: Iterator[Pair[A, B]] = toList.elements;
+
+    override def toList: List[Pair[A, B]] = Nil;
+
+    protected class Node(key: A, value: B) extends ListMap[A, B] {
+        override def size: Int = ListMap.this.size + 1;
+       	override def isEmpty: Boolean = true;
+		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 y = ListMap.this.update(k, v); (new y.Node(key, value)): ListMap[A, B]
+			}
+		override def -(k: A): ListMap[A, B] =
+			if (k == key)
+				ListMap.this
+			else {
+				val y = ListMap.this - k; (new y.Node(key, value)): ListMap[A, B]
+			}
+		override def toList: List[Pair[A, B]] = Pair(key, value) :: ListMap.this.toList;
+    }
 }
diff --git a/sources/scala/collection/immutable/ListSet.scala b/sources/scala/collection/immutable/ListSet.scala
index e9a7ccd6b5..f9ca0df1d9 100644
--- a/sources/scala/collection/immutable/ListSet.scala
+++ b/sources/scala/collection/immutable/ListSet.scala
@@ -10,12 +10,22 @@
 package scala.collection.immutable;
 
 
+object ListSet {
+	def Empty[A] = new ListSet[A];
+}
+
+/** This class implements immutable sets using a list-based data
+ *  structure. Instances of <code>ListSet</code> represent
+ *  empty sets; they can be either created by calling the constructor
+ *  directly, or by applying the function <code>ListSet.Empty</code>.
+ *
+ *  @author  Matthias Zenger
+ *  @version 1.0, 09/07/2003
+ */
 class ListSet[A] with Set[A, ListSet[A]] {
 
 	def size: Int = 0;
 
-    override def isEmpty: Boolean = true;
-
 	def contains(elem: A): Boolean = false;
 
 	def +(elem: A): ListSet[A] = new Node(elem);
@@ -32,7 +42,7 @@ class ListSet[A] with Set[A, ListSet[A]] {
 		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 y = ListSet.this - e; (new y.Node(e)) : ListSet[A]
+			val y = ListSet.this - e; (new y.Node(elem)): ListSet[A]
 		}
 		override def toList: List[A] = elem :: ListSet.this.toList;
 	}