From 5d1b310ad7880c0e67a28a91c0597ab754f3ffc7 Mon Sep 17 00:00:00 2001 From: Matthias Zenger Date: Thu, 19 Jun 2003 10:57:56 +0000 Subject: Refactored some list code and implemented Stack... Refactored some list code and implemented Stacks and Queues. --- sources/scala/DefaultMapModel.scala | 50 +++++++++++++++++++++++++++++ sources/scala/DoubleLinkedList.scala | 41 ++++++++++++++++++++++++ sources/scala/HashMap.scala | 2 +- sources/scala/LinkedList.scala | 42 ++----------------------- sources/scala/ListMap.scala | 2 +- sources/scala/MutableList.scala | 61 ++++++++++++++++++++++++++++++++++++ sources/scala/Queue.scala | 32 +++++++++++++++++++ sources/scala/SingleLinkedList.scala | 55 ++++++++++++++++++++++++++++++++ sources/scala/Stack.scala | 30 ++++++++++++++++++ 9 files changed, 274 insertions(+), 41 deletions(-) create mode 100644 sources/scala/DefaultMapModel.scala create mode 100644 sources/scala/DoubleLinkedList.scala create mode 100644 sources/scala/MutableList.scala create mode 100644 sources/scala/Queue.scala create mode 100644 sources/scala/SingleLinkedList.scala create mode 100644 sources/scala/Stack.scala (limited to 'sources') 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; +} -- cgit v1.2.3