diff options
author | Matthias Zenger <mzenger@gmail.com> | 2003-06-05 15:31:08 +0000 |
---|---|---|
committer | Matthias Zenger <mzenger@gmail.com> | 2003-06-05 15:31:08 +0000 |
commit | 6a6b914be91942eec2ef5536ae76195cb81979b8 (patch) | |
tree | 9027a77189864bf89aba3ef046ebbd66ef74b12f /sources | |
parent | be858b38fe6527378948ad94b1db9e11143bcdfa (diff) | |
download | scala-6a6b914be91942eec2ef5536ae76195cb81979b8.tar.gz scala-6a6b914be91942eec2ef5536ae76195cb81979b8.tar.bz2 scala-6a6b914be91942eec2ef5536ae76195cb81979b8.zip |
Some collection classes.
welcome.
Diffstat (limited to 'sources')
-rw-r--r-- | sources/scala/HashMap.scala | 206 | ||||
-rw-r--r-- | sources/scala/Map.scala | 24 | ||||
-rw-r--r-- | sources/scala/MutableMap.scala | 17 |
3 files changed, 247 insertions, 0 deletions
diff --git a/sources/scala/HashMap.scala b/sources/scala/HashMap.scala new file mode 100644 index 0000000000..9427108f00 --- /dev/null +++ b/sources/scala/HashMap.scala @@ -0,0 +1,206 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala; + +/** I promise, there will be some documentation soon! :-) Matthias + */ +class HashMap[A, B] extends MutableMap[A, B] { + + /** 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) = table(index(key)).find(entryFor(key)) match { + case None => None + case Some(e) => Some(e.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) = { + val old = apply(key); + update(key, value); + 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; + def toPair = Pair(k, value); + 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); +} diff --git a/sources/scala/Map.scala b/sources/scala/Map.scala new file mode 100644 index 0000000000..236bf767b3 --- /dev/null +++ b/sources/scala/Map.scala @@ -0,0 +1,24 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala; + +/** I promise, there will be some documentation soon! :-) Matthias + */ +trait Map[A, +B] with Function1[A, B] with PartialFunction[A, B] { + def size: Int; + def isEmpty: Boolean; + def get(key: A): Option[B]; + def remove(key: A): B; + def contains(key: A): Boolean; + def clear: Unit; + def keys: Iterator[A]; + def values: Iterator[B]; + def iterator: Iterator[Pair[A, B]]; +} diff --git a/sources/scala/MutableMap.scala b/sources/scala/MutableMap.scala new file mode 100644 index 0000000000..818f10f843 --- /dev/null +++ b/sources/scala/MutableMap.scala @@ -0,0 +1,17 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala; + +/** I promise, there will be some documentation soon! :-) Matthias + */ +trait MutableMap[A, B] extends Map[A, B] { + def update(key: A, value: B): Unit; + def put(key: A, value: B): B; +} |