diff options
author | Martin Odersky <odersky@gmail.com> | 2012-12-06 14:06:00 +0100 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2012-12-06 14:06:00 +0100 |
commit | 90962407e72d88f8f3249ade0f6bd60ff15af5ce (patch) | |
tree | 6b2fc0ba13bad7c4532ebf1df39b0b2f5d7e70b6 /src/dotty/tools/dotc/util/HashSet.scala | |
parent | 2308509d2651ee78e1122b5d61b798c984c96c4d (diff) | |
download | dotty-90962407e72d88f8f3249ade0f6bd60ff15af5ce.tar.gz dotty-90962407e72d88f8f3249ade0f6bd60ff15af5ce.tar.bz2 dotty-90962407e72d88f8f3249ade0f6bd60ff15af5ce.zip |
Initial commit
Diffstat (limited to 'src/dotty/tools/dotc/util/HashSet.scala')
-rw-r--r-- | src/dotty/tools/dotc/util/HashSet.scala | 108 |
1 files changed, 108 insertions, 0 deletions
diff --git a/src/dotty/tools/dotc/util/HashSet.scala b/src/dotty/tools/dotc/util/HashSet.scala new file mode 100644 index 000000000..589cc1f41 --- /dev/null +++ b/src/dotty/tools/dotc/util/HashSet.scala @@ -0,0 +1,108 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2012 LAMP/EPFL + * @author Martin Odersky + */ + +package dotty.tools.dotc.util + +object HashSet { + def apply[T >: Null <: AnyRef](): HashSet[T] = this(16) + def apply[T >: Null <: AnyRef](label: String): HashSet[T] = this(label, 16) + def apply[T >: Null <: AnyRef](initialCapacity: Int): HashSet[T] = this("No Label", initialCapacity) + def apply[T >: Null <: AnyRef](label: String, initialCapacity: Int): HashSet[T] = + new HashSet[T](label, initialCapacity) +} + +class HashSet[T >: Null <: AnyRef](val label: String, initialCapacity: Int) extends Set[T] with scala.collection.generic.Clearable { + private var used = 0 + private var table = new Array[AnyRef](initialCapacity) + private def index(x: Int): Int = math.abs(x % table.length) + + def hash(x: T): Int = x.hashCode + + def size: Int = used + def clear() { + used = 0 + table = new Array[AnyRef](initialCapacity) + } + + def findEntryOrUpdate(x: T): T = { + var h = index(hash(x)) + var entry = table(h) + while (entry ne null) { + if (x == entry) + return entry.asInstanceOf[T] + + h = index(h + 1) + entry = table(h) + } + table(h) = x + used += 1 + if (used > (table.length >> 2)) growTable() + x + } + + def findEntry(x: T): T = { + var h = index(hash(x)) + var entry = table(h) + while ((entry ne null) && x != entry) { + h = index(h + 1) + entry = table(h) + } + entry.asInstanceOf[T] + } + + def addEntry(x: T) { + var h = index(hash(x)) + var entry = table(h) + while (entry ne null) { + if (x == entry) return + h = index(h + 1) + entry = table(h) + } + table(h) = x + used += 1 + if (used > (table.length >> 2)) growTable() + } + def addEntries(xs: TraversableOnce[T]) { + xs foreach addEntry + } + + def iterator = new Iterator[T] { + private var i = 0 + def hasNext: Boolean = { + while (i < table.length && (table(i) eq null)) i += 1 + i < table.length + } + def next(): T = + if (hasNext) { i += 1; table(i - 1).asInstanceOf[T] } + else null + } + + private def addOldEntry(x: T) { + var h = index(hash(x)) + var entry = table(h) + while (entry ne null) { + h = index(h + 1) + entry = table(h) + } + table(h) = x + } + + private def growTable() { + val oldtable = table + val growthFactor = + if (table.length <= initialCapacity) 8 + else if (table.length <= (initialCapacity * 8)) 4 + else 2 + + table = new Array[AnyRef](table.length * growthFactor) + var i = 0 + while (i < oldtable.length) { + val entry = oldtable(i) + if (entry ne null) addOldEntry(entry.asInstanceOf[T]) + i += 1 + } + } + override def toString() = "HashSet %s(%d / %d)".format(label, used, table.length) +} |