diff options
Diffstat (limited to 'src/library/scalax/collection/immutable/HashSet.scala')
-rw-r--r-- | src/library/scalax/collection/immutable/HashSet.scala | 138 |
1 files changed, 138 insertions, 0 deletions
diff --git a/src/library/scalax/collection/immutable/HashSet.scala b/src/library/scalax/collection/immutable/HashSet.scala new file mode 100644 index 0000000000..56394b9bc6 --- /dev/null +++ b/src/library/scalax/collection/immutable/HashSet.scala @@ -0,0 +1,138 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: HashSet.scala 16884 2009-01-09 16:52:09Z cunei $ + +package scalax.collection.immutable + +import generic.{SetTemplate, SetFactory, AddableBuilder} + +/** The canonical factory methods for <a href="HashSet.html">immutable HashSet's<la>. + * + * @author Martin Odersky + * @version 2.8 + */ +object HashSet extends SetFactory[HashSet] { + + /** The empty set of this type. + */ + def empty[A] = new HashSet[A] + +} + +/** This class implements immutable maps/sets using a hash table. + * It is optimized for sequential accesses where the last updated table is accessed most often. + * It supports with reasonable efficiency accesses to previous versions of the table by keeping + * a change log that's regularly compacted. + * It needs to synchronize most methods, so it is less suitable for highly concurrent accesses. + * + * @author Martin Odersky + * @version 2.0, 19/01/2007 + */ +@serializable +class HashSet[A] extends Set[A] + with SetTemplate[HashSet, A] + with mutable.FlatHashTable[A] { + protected var later: HashSet[A] = null + protected var changedElem: A = _ + protected var deleted: Boolean = _ + + def contains(elem: A): Boolean = synchronized { + var m = this + var cnt = 0 + while (m.later != null) { + if (elem == m.changedElem) return m.deleted + cnt += 1 + m = m.later + } + if (cnt > logLimit) makeCopy(m) + m.containsEntry(elem) + } + + def + (elem: A): HashSet[A] = synchronized { + makeCopyIfUpdated() + if (containsEntry(elem)) this + else { + markUpdated(elem, false) + later addEntry elem + later + } + } + + def - (elem: A): HashSet[A] = synchronized { + makeCopyIfUpdated() + if (!containsEntry(elem)) this + else { + markUpdated(elem, true) + later removeEntry elem + later + } + } + + override def size: Int = synchronized { + var m = this + var cnt = 0 + var s = 0 + while (m.later != null) { + if (m.deleted) s += 1 else s -= 1 + cnt += 1 + m = m.later + } + s += m.tableSize + if (cnt > logLimit) makeCopy(m) + s + } + + override def elements = synchronized { + makeCopyIfUpdated() + // note need to cache because (later versions of) set might be mutated while elements are traversed. + val cached = new mutable.ArrayBuffer() ++ super.elements + cached.elements + } + + override def newBuilder[B]: generic.Builder[HashSet, B] = + new AddableBuilder[HashSet, B](HashSet.empty) + + private def logLimit: Int = Math.sqrt(table.length).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(m.changedElem) + else removeEntry(m.changedElem) + } + } + table = new scala.Array[AnyRef](last.table.length) + scala.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) + } +} + |