diff options
author | Matthias Zenger <mzenger@gmail.com> | 2003-07-09 17:05:37 +0000 |
---|---|---|
committer | Matthias Zenger <mzenger@gmail.com> | 2003-07-09 17:05:37 +0000 |
commit | c2b559a9b27de3cc8e45097ea952b170b9e0a703 (patch) | |
tree | bbfd762a221660c23a32a01172082183235cdcc4 /sources | |
parent | 796f281527acf0bc5aa9d5468dd46385d284ec86 (diff) | |
download | scala-c2b559a9b27de3cc8e45097ea952b170b9e0a703.tar.gz scala-c2b559a9b27de3cc8e45097ea952b170b9e0a703.tar.bz2 scala-c2b559a9b27de3cc8e45097ea952b170b9e0a703.zip |
Basic implementation of maps and sets.
Diffstat (limited to 'sources')
-rw-r--r-- | sources/scala/collection/immutable/ListMap.scala | 65 | ||||
-rw-r--r-- | sources/scala/collection/immutable/ListSet.scala | 16 |
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; } |