diff options
Diffstat (limited to 'src/library/scalax/collection/mutable/HashTable.scala')
-rw-r--r-- | src/library/scalax/collection/mutable/HashTable.scala | 172 |
1 files changed, 172 insertions, 0 deletions
diff --git a/src/library/scalax/collection/mutable/HashTable.scala b/src/library/scalax/collection/mutable/HashTable.scala new file mode 100644 index 0000000000..73ff61f3df --- /dev/null +++ b/src/library/scalax/collection/mutable/HashTable.scala @@ -0,0 +1,172 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://www.scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: HashTable.scala 16884 2009-01-09 16:52:09Z cunei $ + + +package scalax.collection.mutable + +/** This class can be used to construct data structures that are based + * on hashtables. Class <code>HashTable[A]</code> implements a hashtable + * that maps keys of type <code>A</code> to values of the fully abstract + * member type <code>Entry</code>. Classes that make use of <code>HashTable</code> + * have to provide an implementation for <code>Entry</code> + * + * There are mainly two parameters that affect the performance of a hashtable: + * the <i>initial size</i> and the <i>load factor</i>. The <i>size</i> + * refers to the number of <i>buckets</i> in the hashtable, and the <i>load + * factor</i> is a measure of how full the hashtable is allowed to get before + * its size is automatically doubled. Both parameters may be changed by + * overriding the corresponding values in class <code>HashTable</code>. + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.0, 31/12/2006 + */ +trait HashTable[A] extends AnyRef { + + protected type Entry >: Null <: HashEntry[A, Entry] + + /** The load factor for the hash table (in 0.001 step). + */ + protected def loadFactor: Int = 750 // corresponds to 75% + protected final val loadFactorDenum = 1000; + + /** The initial size of the hash table. + */ + protected def initialSize: Int = 16 + + /** The initial threshold + */ + protected def initialThreshold: Int = newThreshold(initialSize) + + /** The actual hash table. + */ + protected var table: scala.Array[HashEntry[A, Entry]] = + if (initialSize == 0) null else new scala.Array(initialSize) + + /** 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 = initialThreshold + + /** Returns the size of this hash table. + */ + def size = tableSize + + protected def findEntry(key: A): Entry = { + val h = index(elemHashCode(key)) + var e = table(h).asInstanceOf[Entry] + while (e != null && !elemEquals(e.key, key)) e = e.next + e + } + + protected def addEntry(e: Entry) { + val h = index(elemHashCode(e.key)) + e.next = table(h).asInstanceOf[Entry] + table(h) = e + tableSize = tableSize + 1 + if (tableSize > threshold) + resize(2 * table.length) + } + + protected def removeEntry(key: A) : Option[Entry] = { + val h = index(elemHashCode(key)) + var e = table(h).asInstanceOf[Entry] + if (e != null) { + if (elemEquals(e.key, key)) { + table(h) = e.next + tableSize = tableSize - 1 + return Some(e) + } else { + var e1 = e.next + while (e1 != null && !elemEquals(e1.key, key)) { + e = e1 + e1 = e1.next + } + if (e1 != null) { + e.next = e1.next + tableSize = tableSize - 1 + return Some(e1) + } + } + } + None + } + + protected def entries: Iterator[Entry] = new Iterator[Entry] { + val iterTable = table + var idx = table.length - 1 + var es = iterTable(idx).asInstanceOf[Entry] + scan() + def hasNext = es != null + def next = { + val res = es + es = es.next + scan() + res + } + def scan() { + while (es == null && idx > 0) { + idx = idx - 1 + es = iterTable(idx).asInstanceOf[Entry] + } + } + } + + def clear() { + var i = table.length - 1 + while (i >= 0) { table(i) = null; i = i - 1 } + tableSize = 0 + } + + private def newThreshold(size: Int) = + ((size.toLong * loadFactor)/loadFactorDenum).toInt + + private def resize(newSize: Int) = { + val oldTable = table + table = new scala.Array(newSize) + var i = oldTable.length - 1 + while (i >= 0) { + var e = oldTable(i) + while (e != null) { + val h = index(elemHashCode(e.key)) + val e1 = e.next + e.next = table(h).asInstanceOf[Entry] + table(h) = e + e = e1 + } + i = i - 1 + } + threshold = newThreshold(newSize) + } + + 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) +} + +trait HashEntry[A, E] { + val key: A + var next: E = _ +} + + + |