From 8290fa5c459dcee0f74008fdeb7e7cc94a6058b9 Mon Sep 17 00:00:00 2001 From: Matthias Zenger Date: Mon, 9 Jun 2003 20:10:25 +0000 Subject: New collection classes. --- sources/scala/HashMap.scala | 180 +++-------------------------------------- sources/scala/HashSet.scala | 33 ++++++++ sources/scala/HashTable.scala | 131 ++++++++++++++++++++++++++++++ sources/scala/Iterable.scala | 14 ++++ sources/scala/ListSet.scala | 30 +++++++ sources/scala/Map.scala | 73 +++++++++++++++-- sources/scala/MutableMap.scala | 38 ++++++++- sources/scala/Set.scala | 87 ++++++++++++++++++++ 8 files changed, 408 insertions(+), 178 deletions(-) create mode 100644 sources/scala/HashSet.scala create mode 100644 sources/scala/HashTable.scala create mode 100644 sources/scala/Iterable.scala create mode 100644 sources/scala/ListSet.scala create mode 100644 sources/scala/Set.scala diff --git a/sources/scala/HashMap.scala b/sources/scala/HashMap.scala index 9427108f00..ed6519a383 100644 --- a/sources/scala/HashMap.scala +++ b/sources/scala/HashMap.scala @@ -11,129 +11,30 @@ package scala; /** I promise, there will be some documentation soon! :-) Matthias */ -class HashMap[A, B] extends MutableMap[A, B] { +class HashMap[A, B] extends MutableMap[A, B] with HashTable[A] { - /** 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 true 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) = findEntry(key) match { + case None => None + case Some(e) => Some(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) = findEntry(key) match { + case None => addEntry(new Entry(key, value)); + case Some(e) => e.value = 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) = { + def remove(key: A) = { val old = apply(key); - update(key, value); + removeEntry(key); 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; @@ -141,66 +42,5 @@ class HashMap[A, B] extends MutableMap[A, B] { 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); + protected def entryKey(e: Entry) = e.key; } diff --git a/sources/scala/HashSet.scala b/sources/scala/HashSet.scala new file mode 100644 index 0000000000..08d4b95d5b --- /dev/null +++ b/sources/scala/HashSet.scala @@ -0,0 +1,33 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala; + +/** I promise, there will be some documentation soon! :-) Matthias + */ +class HashSet[A] extends Set[A] with HashTable[A] { + + def contains(elem: A): Boolean = findEntry(elem) match { + case None => false + case Some(_) => true + } + + def add(elem: A): Unit = findEntry(elem) match { + case None => addEntry(elem); + case Some(_) => + } + + def remove(elem: A): Unit = removeEntry(elem); + + def iterator = entries; + + protected type Entry = A; + + protected def entryKey(e: Entry) = e; +} diff --git a/sources/scala/HashTable.scala b/sources/scala/HashTable.scala new file mode 100644 index 0000000000..00edab3947 --- /dev/null +++ b/sources/scala/HashTable.scala @@ -0,0 +1,131 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala; + +/** I promise, there will be some documentation soon! :-) Matthias + */ +abstract class HashTable[A] { + + /** 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; + + protected def findEntry(key: A): Option[Entry] = + table(index(elemHashCode(key))).find(entryFor(key)); + + protected def addEntry(e: Entry): Unit = { + val h = index(elemHashCode(entryKey(e))); + table(h) = e :: table(h); + tableSize = tableSize + 1; + if (tableSize > threshold) + resize(2 * table.length); + } + + protected def removeEntry(key: A): Unit = { + val old = findEntry(key); + old match { + case None => + case Some(e) => { + val idx = index(elemHashCode(key)); + table(idx) = table(idx).filter(e => !elemEquals(entryKey(e), key)); + tableSize = tableSize - 1; + } + } + } + + def clear = { + initTable(table.length - 1); + tableSize = 0; + } + + protected type Entry; + + protected def entryKey(e: Entry): A; + + 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 => elemEquals(entryKey(e), key)); + + private def initTable(n: Int): Unit = { + table(n) = Nil; + if (n > 0) initTable(n - 1); + } + + 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 = improve(elemHashCode(entryKey(e))) & (newSize - 1); + newTable(idx) = e :: newTable(idx); + rehashList(es); + } + } + rehash(table.length - 1); + table = newTable; + threshold = ((initialSize as Float) * loadFactor) as Int; + } + + protected def elemEquals(key1: A, key2: A): Boolean = (key1 == key2); + + protected def elemHashCode(key: A) = key.hashCode(); + + protected final def improve(hcode: Int) = { + var h: Int = hcode + ~(hcode << 9); + h = h ^ (h >>> 14); + h = h + (h << 4); + h ^ (h >>> 10); + } + + protected final def index(hcode: Int) = improve(hcode) & (table.length - 1); +} diff --git a/sources/scala/Iterable.scala b/sources/scala/Iterable.scala new file mode 100644 index 0000000000..a0edf1a7f3 --- /dev/null +++ b/sources/scala/Iterable.scala @@ -0,0 +1,14 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala; + +trait Iterable[+A] { + def iterator: Iterator[A]; +} diff --git a/sources/scala/ListSet.scala b/sources/scala/ListSet.scala new file mode 100644 index 0000000000..d5abe5406a --- /dev/null +++ b/sources/scala/ListSet.scala @@ -0,0 +1,30 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala; + +/** I promise, there will be some documentation soon! :-) Matthias + */ +class ListSet[A] extends Set[A] { + protected var elems: List[A] = Nil; + + def size: Int = elems.length; + + def contains(elem: A): Boolean = elems.contains(elem); + + def add(elem: A): Unit = if (!elems.contains(elem)) elems = elem :: elems; + + def remove(elem: A): Unit = { elems = elems.filter(e => e != elem); } + + def clear: Unit = { elems = Nil; } + + def iterator: Iterator[A] = elems.iterator; + + override def toList: List[A] = elems; +} diff --git a/sources/scala/Map.scala b/sources/scala/Map.scala index 236bf767b3..fb1c235486 100644 --- a/sources/scala/Map.scala +++ b/sources/scala/Map.scala @@ -11,14 +11,75 @@ package scala; /** I promise, there will be some documentation soon! :-) Matthias */ -trait Map[A, +B] with Function1[A, B] with PartialFunction[A, B] { +trait Map[A, +B] with Function1[A, B] + with PartialFunction[A, B] + with Iterable[Pair[A, B]] { + def size: Int; - def isEmpty: Boolean; + + def isEmpty: Boolean = (size == 0); + + def apply(key: A): B = get(key) match { + case None => null + case Some(value) => value + } + def get(key: A): Option[B]; + def remove(key: A): B; - def contains(key: A): Boolean; + + def contains(key: A): Boolean = get(key) match { + case None => false + case Some(_) => true + } + + def isDefinedAt(key: A) = contains(key); + def clear: Unit; - def keys: Iterator[A]; - def values: Iterator[B]; - def iterator: Iterator[Pair[A, B]]; + + def keys: Iterator[A] = new Iterator[A] { + val iter = iterator; + def hasNext = iter.hasNext; + def next = iter.next._1; + } + + def values: Iterator[B] = new Iterator[B] { + val iter = iterator; + def hasNext = iter.hasNext; + def next = iter.next._2; + } + + def foreach(f: (A, B) => Unit) = { + val iter = iterator; + while (iter.hasNext) { + val Pair(key, value) = iter.next; + f(key, value); + } + } + + def filter(p: (A, B) => Boolean): Unit = toList foreach { + case Pair(key, value) => if (p(key, value)) { val old = remove(key); } + } + + def toList: List[Pair[A, B]] = { + var res: List[Pair[A, B]] = Nil; + val iter = iterator; + while (iter.hasNext) { + res = iter.next :: res; + } + res; + } + + override def toString() = + if (size == 0) + "{}" + else + "{" + { + val iter = iterator; + var res = iter.next.toString(); + while (iter.hasNext) { + res = res + ", " + iter.next; + } + res; + } + "}"; } diff --git a/sources/scala/MutableMap.scala b/sources/scala/MutableMap.scala index 818f10f843..861a9f6b60 100644 --- a/sources/scala/MutableMap.scala +++ b/sources/scala/MutableMap.scala @@ -11,7 +11,41 @@ package scala; /** I promise, there will be some documentation soon! :-) Matthias */ -trait MutableMap[A, B] extends Map[A, B] { +trait MutableMap[A, B] with Map[A, B] { + def update(key: A, value: B): Unit; - def put(key: A, value: B): B; + + def put(key: A, value: B): B = { + val old = apply(key); + update(key, value); + old; + } + + def putAll(mappings: Pair[A, B]*) = { + val ys = mappings as List[Pair[A, B]]; + ys foreach { case Pair(key, value) => update(key, value); }; + } + + def putMap(map: Iterable[Pair[A, B]]): Unit = map.iterator foreach { + case Pair(key, value) => update(key, value); + } + + def map(f: (A, B) => B): Unit = iterator foreach { + case Pair(key, value) => update(key, f(key, value)); + } + + override def toString() = + if (size == 0) + "{}" + else + "{" + { + val iter = iterator; + var res = mappingToString(iter.next); + while (iter.hasNext) { + res = res + ", " + mappingToString(iter.next); + } + res; + } + "}"; + + def mappingToString(p: Pair[A, B]) = p._1.toString() + " -> " + p._2; } diff --git a/sources/scala/Set.scala b/sources/scala/Set.scala new file mode 100644 index 0000000000..17ca20015f --- /dev/null +++ b/sources/scala/Set.scala @@ -0,0 +1,87 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala; + +/** I promise, there will be some documentation soon! :-) Matthias + */ +trait Set[A] with Iterable[A] { + + def size: Int; + + def isEmpty: Boolean = (size == 0); + + def contains(elem: A): Boolean; + + def add(elem: A): Unit; + + def addAll(elems: A*): Unit = { + val ys = elems as List[A]; + ys foreach { y => add(y); }; + } + + def addSet(that: Iterable[A]): Unit = + that.iterator.foreach(elem => add(elem)); + + def remove(elem: A): Unit; + + def removeAll(elems: A*): Unit = { + val ys = elems as List[A]; + ys foreach { y => remove(y); }; + } + + def removeSet(that: Iterable[A]): Unit = + that.iterator.foreach(elem => remove(elem)); + + def intersect(that: Set[A]): Unit = filter(that.contains); + + def clear: Unit; + + def subsetOf(that: Set[A]): Boolean = { + val iter = iterator; + var res = true; + while (res && iter.hasNext) { + res = that.contains(iter.next); + } + res + } + + def foreach(f: A => Unit) = { + val iter = iterator; + while (iter.hasNext) { + f(iter.next); + } + } + + def filter(p: A => Boolean): Unit = toList foreach { + elem => if (p(elem)) remove(elem); + } + + def toList: List[A] = { + var res: List[A] = Nil; + val iter = iterator; + while (iter.hasNext) { + res = iter.next :: res; + } + res; + } + + override def toString() = + if (size == 0) + "{}" + else + "{" + { + val iter = iterator; + var res = iter.next.toString(); + while (iter.hasNext) { + res = res + ", " + iter.next; + } + res; + } + "}"; +} -- cgit v1.2.3