Refactored some list code and implemented Stack...

Refactored some list code and implemented Stacks and Queues.

9 files changed, 274 insertions, 41 deletions

diff --git a/sources/scala/DefaultMapModel.scala b/sources/scala/DefaultMapModel.scala
new file mode 100644
index 0000000000..61913e542a
--- /dev/null
+++ b/sources/scala/DefaultMapModel.scala
@@ -0,0 +1,50 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+
+trait DefaultMapModel[A, B] extends MutableMap[A, B] {
+
+	protected def findEntry(key: A): Option[Entry];
+
+	protected def addEntry(e: Entry): Unit;
+
+    protected def removeEntry(key: A): Unit;
+
+    protected def entries: Iterator[Entry];
+
+    def get(key: A) = findEntry(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 remove(key: A) = findEntry(key) match {
+    	case None => null;
+    	case Some(e) => removeEntry(key); e.value;
+    }
+
+    def elements = new Iterator[Pair[A, B]] {
+        val iter = entries;
+        def hasNext = iter.hasNext;
+        def next = iter.next.toPair;
+    }
+
+    protected class Entry(k: A, v: B) {
+        def key = k;
+        var value = v;
+        def toPair = Pair(k, value);
+        override def toString() = k.toString() + " -> " + value;
+    }
+}
diff --git a/sources/scala/DoubleLinkedList.scala b/sources/scala/DoubleLinkedList.scala
new file mode 100644
index 0000000000..800db9d158
--- /dev/null
+++ b/sources/scala/DoubleLinkedList.scala
@@ -0,0 +1,41 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+
+abstract class DoubleLinkedList[A, This <: DoubleLinkedList[A, This]]: This
+	extends SingleLinkedList[A, This] {
+
+	var prev: This = _;
+
+	override def append(that: This): Unit =
+		if (that == null)
+			()
+		else if (next == null) {
+			next = that;
+			that.prev = this;
+		} else
+			next.append(that);
+
+	override def insert(that: This): Unit = if (that != null) {
+		that.append(next);
+		next = that;
+		that.prev = this;
+	}
+
+	def remove: Unit = {
+		if (next != null)
+			next.prev = prev;
+		if (prev != null)
+			prev.next = next;
+		prev = null;
+		next = null;
+	}
+}
diff --git a/sources/scala/HashMap.scala b/sources/scala/HashMap.scala
index 18af2a174e..f9b2a07fac 100644
--- a/sources/scala/HashMap.scala
+++ b/sources/scala/HashMap.scala
@@ -13,7 +13,7 @@ package scala;
  */
 class HashMap[A, B] extends MutableMap[A, B]
                     with HashTable[A]
-                    with MapImpl[A, B] {
+                    with DefaultMapModel[A, B] {
 
     protected def entryKey(e: Entry) = e.key;
 }
diff --git a/sources/scala/LinkedList.scala b/sources/scala/LinkedList.scala
index bd500e13e2..380acdb1be 100644
--- a/sources/scala/LinkedList.scala
+++ b/sources/scala/LinkedList.scala
@@ -9,43 +9,7 @@
 
 package scala;
 
-class LinkedList[A] with Seq[A] {
-    var elem: A = _;
-    var next: LinkedList[A] = null;
-
-    def append(x: A): LinkedList[A] = {
-        val l = new LinkedList[A]();
-        l.elem = x;
-        this.next = l;
-        l
-    }
-
-    def length: Int = 1 + (if (next == null) 0 else next.length);
-
-    def apply(n: Int): A = {
-        if (n == 0) elem
-        else if (next == null) null
-        else next.apply(n - 1);
-    }
-
-    def at(n: Int): A = apply(n);
-
-    def get(n: Int): Option[A] = {
-        if (n == 0) Some(elem)
-        else if (next == null) None
-        else next.get(n - 1);
-    }
-
-    def elements: Iterator[A] = new Iterator[A] {
-        var elems = LinkedList.this;
-        def hasNext = (elems != null);
-        def next = {
-            val res = elems.elem;
-            elems = elems.next;
-            res;
-        }
-    }
-
-    def toList: List[A] =
-        if (next == null) (elem :: Nil) else (elem :: next.toList);
+class LinkedList[A](head: A, tail: LinkedList[A]) extends SingleLinkedList[A, LinkedList[A]] {
+	elem = head;
+	next = tail;
 }
diff --git a/sources/scala/ListMap.scala b/sources/scala/ListMap.scala
index fa4a556607..bdf316b22d 100644
--- a/sources/scala/ListMap.scala
+++ b/sources/scala/ListMap.scala
@@ -11,7 +11,7 @@ package scala;
 
 
 class ListMap[A, B] extends MutableMap[A, B]
-                    with MapImpl[A, B] {
+                    with DefaultMapModel[A, B] {
 
 	var xs: List[Entry] = Nil;
 
diff --git a/sources/scala/MutableList.scala b/sources/scala/MutableList.scala
new file mode 100644
index 0000000000..d540221284
--- /dev/null
+++ b/sources/scala/MutableList.scala
@@ -0,0 +1,61 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+
+class MutableList[A] with Seq[A] with PartialFunction[Int, A] {
+
+    protected var first: LinkedList[A] = null;
+    protected var last: LinkedList[A] = null;
+    protected var len: Int = 0;
+
+    def length: Int = len;
+
+    def isDefinedAt(n: Int) = (n >= 0) && (n < len);
+
+    def apply(n: Int): A = get(n) match {
+        case None => null
+        case Some(value) => value
+    }
+
+    def get(n: Int): Option[A] = first.get(n);
+
+    def at(n: Int): A = apply(n);
+
+    protected def prependElem(elem: A) = {
+    	first = new LinkedList[A](elem, first);
+        if (len == 0)
+            last = first;
+        len = len + 1;
+    }
+
+    protected def appendElem(elem: A) = {
+        if (len == 0)
+            prependElem(elem);
+        else {
+            last.next = new LinkedList[A](elem, null);
+            last = last.next;
+            len = len + 1;
+        }
+    }
+
+    protected def reset: Unit = {
+    	first = null;
+    	last = null;
+    	len = 0;
+    }
+
+    def elements: Iterator[A] =
+    	if (first == null) Nil.elements else first.elements;
+
+    def toList: List[A] = if (first == null) Nil else first.toList;
+
+    override def toString() = toList.toString();
+}
diff --git a/sources/scala/Queue.scala b/sources/scala/Queue.scala
new file mode 100644
index 0000000000..2d885c2856
--- /dev/null
+++ b/sources/scala/Queue.scala
@@ -0,0 +1,32 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+
+class Queue[A] with MutableList[A] {
+
+    def +=(elem: A) = appendElem(elem);
+
+    def +=(iter: Iterable[A]) = iter.elements.foreach(e => appendElem(e));
+
+    def enqueue(elems: A*): Unit = (this += elems);
+
+    def dequeue(): A = {
+    	if (first == null)
+    		error("queue empty");
+    	else {
+    		val res = first.elem;
+    		first = first.next;
+    		res;
+    	}
+    }
+
+    def clear: Unit = reset;
+}
diff --git a/sources/scala/SingleLinkedList.scala b/sources/scala/SingleLinkedList.scala
new file mode 100644
index 0000000000..b7e4934de0
--- /dev/null
+++ b/sources/scala/SingleLinkedList.scala
@@ -0,0 +1,55 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+
+abstract class SingleLinkedList[A, This <: SingleLinkedList[A, This]]: This with Seq[A] {
+
+	var elem: A = _;
+
+	var next: This = _;
+
+	def length: Int = 1 + (if (next == null) 0 else next.length);
+
+	def append(that: This): Unit =
+		if (next == null) { next = that; } else next.append(that);
+
+	def insert(that: This): Unit = if (that != null) {
+		that.append(next);
+		next = that;
+	}
+
+    def apply(n: Int): A = {
+        if (n == 0) elem
+        else if (next == null) null
+        else next.apply(n - 1);
+    }
+
+    def at(n: Int): A = apply(n);
+
+    def get(n: Int): Option[A] = {
+        if (n == 0) Some(elem)
+        else if (next == null) None
+        else next.get(n - 1);
+    }
+
+    def elements: Iterator[A] = new Iterator[A] {
+        var elems = SingleLinkedList.this;
+        def hasNext = (elems != null);
+        def next = {
+            val res = elems.elem;
+            elems = elems.next;
+            res;
+        }
+    }
+
+    def toList: List[A] =
+        if (next == null) (elem :: Nil) else (elem :: next.toList);
+}
diff --git a/sources/scala/Stack.scala b/sources/scala/Stack.scala
new file mode 100644
index 0000000000..67f1065aef
--- /dev/null
+++ b/sources/scala/Stack.scala
@@ -0,0 +1,30 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003, LAMP/EPFL                  **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+** $Id$
+\*                                                                      */
+
+package scala;
+
+
+class Stack[A] with MutableList[A] {
+
+    def +=(elem: A) = prependElem(elem);
+
+    def +=(iter: Iterable[A]) = iter.elements.foreach(e => prependElem(e));
+
+    def push(elems: A*): Unit = (this += elems);
+
+    def top: A = if (first == null) error("stack empty"); else first.elem;
+
+    def pop: Unit = if (first != null) { first = first.next; }
+
+    def clear: Unit = reset;
+
+    override def elements: Iterator[A] = toList.elements;
+
+    override def toList: List[A] = super.toList.reverse;
+}