diff options
author | Martin Odersky <odersky@gmail.com> | 2007-01-22 22:35:02 +0000 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2007-01-22 22:35:02 +0000 |
commit | 9e5f776d68efbd7b98865d6c2a67e3bbe33bc5c9 (patch) | |
tree | 86a3b52400413b21f3cc4e65722930e466953d1d /src/library/scala/collection/immutable/HashSet.scala | |
parent | e3e918acdb1225312f1d13f6fdc7b1073aae39b2 (diff) | |
download | scala-9e5f776d68efbd7b98865d6c2a67e3bbe33bc5c9.tar.gz scala-9e5f776d68efbd7b98865d6c2a67e3bbe33bc5c9.tar.bz2 scala-9e5f776d68efbd7b98865d6c2a67e3bbe33bc5c9.zip |
Diffstat (limited to 'src/library/scala/collection/immutable/HashSet.scala')
-rwxr-xr-x | src/library/scala/collection/immutable/HashSet.scala | 118 |
1 files changed, 118 insertions, 0 deletions
diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala new file mode 100755 index 0000000000..aa4d832537 --- /dev/null +++ b/src/library/scala/collection/immutable/HashSet.scala @@ -0,0 +1,118 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2006, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: HashSet.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ +package scala.collection.immutable + +object HashSet { + + /** The empty set of this type. + */ + def empty[A] = new HashSet[A] + + /** The canonical factory for this type + */ + def apply[A, B](elems: A*) = empty[A] ++ elems +} + +[serializable] +class HashSet[A] extends Set[A] with mutable.FlatHashTable[A] { + protected var later: HashSet[A] = null + protected var changedElem: A = _ + protected var deleted: Boolean = _ + + def empty[C]: Set[C] = new EmptySet[C] + + def contains(elem: A): Boolean = { + var m = this + var cnt = 0 + while (m.later != null) { + if (elem == m.changedElem) return m.deleted + cnt = cnt + 1 + m = m.later + } + if (cnt > logLimit) makeCopy(m) + m.containsEntry(elem) + } + + def + (elem: A): Set[A] = { + makeCopyIfUpdated() + if (containsEntry(elem)) this + else { + markUpdated(elem, false) + later addEntry elem + later + } + } + + def - (elem: A): Set[A] = { + makeCopyIfUpdated() + if (!containsEntry(elem)) this + else { + markUpdated(elem, true) + later removeEntry elem + later + } + } + + override def size: Int = { + var m = this + var cnt = 0 + var s = tableSize + while (m.later != null) { + if (m.deleted) s = s + 1 else s = s - 1 + cnt = cnt + 1 + m = m.later + } + if (cnt > logLimit) makeCopy(m) + s + } + + override def elements = { + makeCopyIfUpdated() + super.elements + } + + private def logLimit: Int = Math.sqrt(table.length.toDouble).toInt + + private def markUpdated(elem: A, del: Boolean) { + val lv = loadFactor + later = new HashSet[A] { + override def initialSize = 0 + override def loadFactor = lv + table = HashSet.this.table + tableSize = HashSet.this.tableSize + threshold = HashSet.this.threshold + } + changedElem = elem + deleted = del + } + + private def makeCopy(last: HashSet[A]) { + def undo(m: HashSet[A]) { + if (m ne last) { + undo(m.later) + if (m.deleted) addEntry(changedElem) + else removeEntry(changedElem) + } + } + table = new Array[AnyRef](last.table.length) + Array.copy(last.table, 0, table, 0, table.length) + tableSize = last.tableSize + threshold = last.threshold + undo(this) + later = null + } + + private def makeCopyIfUpdated() { + var m = this + while (m.later != null) m = m.later + if (m ne this) makeCopy(m) + } +} + |