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 | |
parent | e3e918acdb1225312f1d13f6fdc7b1073aae39b2 (diff) | |
download | scala-9e5f776d68efbd7b98865d6c2a67e3bbe33bc5c9.tar.gz scala-9e5f776d68efbd7b98865d6c2a67e3bbe33bc5c9.tar.bz2 scala-9e5f776d68efbd7b98865d6c2a67e3bbe33bc5c9.zip |
Diffstat (limited to 'src')
-rwxr-xr-x | src/library/scala/collection/immutable/EmptyMap.scala | 37 | ||||
-rwxr-xr-x | src/library/scala/collection/immutable/EmptySet.scala | 36 | ||||
-rwxr-xr-x | src/library/scala/collection/immutable/HashMap.scala | 154 | ||||
-rwxr-xr-x | src/library/scala/collection/immutable/HashSet.scala | 118 | ||||
-rwxr-xr-x | src/library/scala/collection/immutable/Map1.scala | 40 | ||||
-rwxr-xr-x | src/library/scala/collection/immutable/Map2.scala | 46 | ||||
-rwxr-xr-x | src/library/scala/collection/immutable/Map3.scala | 49 | ||||
-rwxr-xr-x | src/library/scala/collection/immutable/Map4.scala | 52 | ||||
-rwxr-xr-x | src/library/scala/collection/immutable/Set1.scala | 42 | ||||
-rwxr-xr-x | src/library/scala/collection/immutable/Set2.scala | 43 | ||||
-rwxr-xr-x | src/library/scala/collection/immutable/Set3.scala | 44 | ||||
-rwxr-xr-x | src/library/scala/collection/immutable/Set4.scala | 45 | ||||
-rwxr-xr-x | src/library/scala/collection/mutable/DefaultEntry.scala | 18 | ||||
-rwxr-xr-x | src/library/scala/collection/mutable/FlatHashTable.scala | 131 |
14 files changed, 855 insertions, 0 deletions
diff --git a/src/library/scala/collection/immutable/EmptyMap.scala b/src/library/scala/collection/immutable/EmptyMap.scala new file mode 100755 index 0000000000..764c066577 --- /dev/null +++ b/src/library/scala/collection/immutable/EmptyMap.scala @@ -0,0 +1,37 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListMap.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + + + +package scala.collection.immutable + +/** This class implements empty immutable maps + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +[serializable] +class EmptyMap[A, +B] extends Map[A, B] { + + def size: Int = 0 + + def get(key: A): Option[B] = None + + def elements: Iterator[{A, B}] = Iterator.empty + + def empty[C]: Map[A, C] = new EmptyMap[A, C] + + def update [B1 >: B](key: A, value: B1): Map[A, B1] = + new Map1(key, value) + + def - (key: A): Map[A, B] = this +} + + + diff --git a/src/library/scala/collection/immutable/EmptySet.scala b/src/library/scala/collection/immutable/EmptySet.scala new file mode 100755 index 0000000000..83a4f77813 --- /dev/null +++ b/src/library/scala/collection/immutable/EmptySet.scala @@ -0,0 +1,36 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListSet.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + + + +package scala.collection.immutable + +/** This class implements empty immutable maps + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +[serializable] +class EmptySet[A] extends Set[A] { + + def empty[C]: Set[C] = new EmptySet[C] + + def size: Int = 0 + + def contains(elem: A): Boolean = false + + def + (elem: A): Set[A] = new Set1(elem) + + def - (elem: A): Set[A] = this + + def elements: Iterator[A] = Iterator.empty +} + + + diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala new file mode 100755 index 0000000000..b11f76dcb9 --- /dev/null +++ b/src/library/scala/collection/immutable/HashMap.scala @@ -0,0 +1,154 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2006, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: HashMap.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + + +package scala.collection.immutable + +import Predef._ + +/** This class implements immutable maps using a hashtable. + * + * @author Martin Odersky + * @version 2.0, 19/01/2007 + */ +object HashMap { + + /** The empty map of this type */ + def empty[A, B] = new HashMap[A, B] + + /** The canonical factory for this type + */ + def apply[A, B](elems: {A, B}*) = empty[A, B] ++ elems +} + +[serializable] +class HashMap[A, B] extends Map[A,B] with mutable.HashTable[A] { + type Entry = mutable.DefaultEntry[A, Any] + + protected var later: HashMap[A, B] = null + protected var oldKey: A = _ + protected var oldValue: Option[B] = _ + protected var deltaSize: int = _ + + def empty[C] = new EmptyMap[A, C] + + def get(key: A): Option[B] = { + var m = this + var cnt = 0 + while (m.later != null) { + if (key == m.oldKey) return m.oldValue + cnt = cnt + 1 + m = m.later + } + if (cnt > logLimit) makeCopy(m) + val e = m.findEntry(key) + if (e == null) None + else Some(getValue(e)) + } + + def update [B1 >: B](key: A, value: B1): Map[A, B1] = { + makeCopyIfUpdated() + val e = findEntry(key) + if (e == null) { + markUpdated(key, None, 1) + later.addEntry(new Entry(key, value)) + } else { + markUpdated(key, Some(getValue(e)), 0) + e.value = value + } + later + } + + def - (key: A): Map[A, B] = { + makeCopyIfUpdated() + val e = findEntry(key) + if (e == null) this + else { + markUpdated(key, Some(getValue(e)), -1) + later removeEntry key + later + } + } + + override def size: int = { + var m = this + var cnt = 0 + var s = tableSize + while (m.later != null) { + s = s - m.deltaSize + cnt = cnt + 1 + m = m.later + } + if (cnt > logLimit) makeCopy(m) + s + } + + def elements = { + makeCopyIfUpdated() + entries map {e => {e.key, getValue(e)}} + } + + private def getValue(e: Entry) = + e.value.asInstanceOf[B] + + private def logLimit: int = Math.sqrt(table.length.toDouble).toInt + + private def markUpdated(key: A, ov: Option[B], delta: int) { + val lv = loadFactor + later = new HashMap[A, B] { + override def initialSize = 0 + override def loadFactor = lv + table = HashMap.this.table + tableSize = HashMap.this.tableSize + threshold = HashMap.this.threshold + } + oldKey = key + oldValue = ov + deltaSize = delta + } + + private def makeCopy(last: HashMap[A, B]) { + def undo(m: HashMap[A, B]) { + if (m ne last) { + undo(m.later) + if (m.deltaSize == 1) removeEntry(m.oldKey) + else if (m.deltaSize == 0) findEntry(m.oldKey).value = m.oldValue.get + else if (m.deltaSize == -1) addEntry(new Entry(m.oldKey, m.oldValue.get)) + } + } + def copy(e: Entry): Entry = + if (e == null) null + else { + val rest = copy(e.next) + val result = new Entry(e.key, e.value) + result.next = rest + result + } + val ltable = last.table + val s = ltable.length + table = new Array[Entry](s) + var i = 0 + while (i < s) { + table(i) = copy(ltable(i)) + i = i + 1 + } + 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) + } +} + 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) + } +} + diff --git a/src/library/scala/collection/immutable/Map1.scala b/src/library/scala/collection/immutable/Map1.scala new file mode 100755 index 0000000000..8310d40e7c --- /dev/null +++ b/src/library/scala/collection/immutable/Map1.scala @@ -0,0 +1,40 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListMap.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + + + +package scala.collection.immutable + +/** This class implements empty immutable maps + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +[serializable] +class Map1[A, +B](key1: A, value1: B) extends Map[A, B] { + + def size = 1 + + def get(key: A): Option[B] = + if (key == key1) Some(value1) else None + + def elements = Iterator.single({key1, value1}) + + def empty[B] = new EmptyMap[A, B] + + def update [B1 >: B](key: A, value: B1): Map[A, B1] = + if (key == key1) new Map1(key1, value) + else new Map2(key1, value1, key, value) + + def - (key: A): Map[A, B] = + if (key == key1) empty else this +} + + + diff --git a/src/library/scala/collection/immutable/Map2.scala b/src/library/scala/collection/immutable/Map2.scala new file mode 100755 index 0000000000..6082ca293b --- /dev/null +++ b/src/library/scala/collection/immutable/Map2.scala @@ -0,0 +1,46 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListMap.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + + + +package scala.collection.immutable + +/** This class implements empty immutable maps + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +[serializable] +class Map2[A, +B](key1: A, value1: B, key2: A, value2: B) extends Map[A, B] { + + def size = 2 + + def get(key: A): Option[B] = + if (key == key1) Some(value1) + else if (key == key2) Some(value2) + else None + + def elements = Iterator.fromValues( + {key1, value1}, {key2, value2}) + + def empty[C] = new EmptyMap[A, C] + + def update [B1 >: B](key: A, value: B1): Map[A, B1] = + if (key == key1) new Map2(key1, value, key2, value2) + else if (key == key2) new Map2(key1, value1, key2, value) + else new Map3(key1, value1, key2, value2, key, value) + + def - (key: A): Map[A, B] = + if (key == key1) new Map1(key2, value2) + else if (key == key2) new Map1(key1, value1) + else this +} + + + diff --git a/src/library/scala/collection/immutable/Map3.scala b/src/library/scala/collection/immutable/Map3.scala new file mode 100755 index 0000000000..e2320f55f5 --- /dev/null +++ b/src/library/scala/collection/immutable/Map3.scala @@ -0,0 +1,49 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListMap.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + + + +package scala.collection.immutable + +/** This class implements empty immutable maps + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +[serializable] +class Map3[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B) extends Map[A, B] { + + def size = 3 + + def get(key: A): Option[B] = + if (key == key1) Some(value1) + else if (key == key2) Some(value2) + else if (key == key3) Some(value3) + else None + + def elements = Iterator.fromValues( + {key1, value1}, {key2, value2}, {key3, value3}) + + def empty[C] = new EmptyMap[A, C] + + def update [B1 >: B](key: A, value: B1): Map[A, B1] = + if (key == key1) new Map3(key1, value, key2, value2, key3, value3) + else if (key == key2) new Map3(key1, value1, key2, value, key3, value3) + else if (key == key3) new Map3(key1, value1, key2, value2, key3, value) + else new Map4(key1, value1, key2, value2, key3, value3, key, value) + + def - (key: A): Map[A, B] = + if (key == key1) new Map2(key2, value2, key3, value3) + else if (key == key2) new Map2(key1, value1, key3, value3) + else if (key == key3) new Map2(key1, value1, key2, value2) + else this +} + + + diff --git a/src/library/scala/collection/immutable/Map4.scala b/src/library/scala/collection/immutable/Map4.scala new file mode 100755 index 0000000000..fa45f53b41 --- /dev/null +++ b/src/library/scala/collection/immutable/Map4.scala @@ -0,0 +1,52 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListMap.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + +package scala.collection.immutable + +import Predef._ + +/** This class implements empty immutable maps + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +[serializable] +class Map4[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B, key4: A, value4: B) extends Map[A, B] { + + def size = 4 + + def get(key: A): Option[B] = + if (key == key1) Some(value1) + else if (key == key2) Some(value2) + else if (key == key3) Some(value3) + else if (key == key4) Some(value4) + else None + + def elements = Iterator.fromValues( + {key1, value1}, {key2, value2}, {key3, value3}, {key4, value4}) + + def empty[C] = new EmptyMap[A, C] + + def update [B1 >: B](key: A, value: B1): Map[A, B1] = + if (key == key1) new Map4(key1, value, key2, value2, key3, value3, key4, value4) + else if (key == key2) new Map4(key1, value1, key2, value, key3, value3, key4, value4) + else if (key == key3) new Map4(key1, value1, key2, value2, key3, value, key4, value4) + else if (key == key4) new Map4(key1, value1, key2, value2, key3, value3, key4, value) + else HashMap(key1 -> value1, key2 -> value2, key3 -> value3, key4 -> value4, key -> value) + + def - (key: A): Map[A, B] = + if (key == key1) new Map3(key2, value2, key3, value3, key4, value4) + else if (key == key2) new Map3(key1, value1, key3, value3, key4, value4) + else if (key == key3) new Map3(key1, value1, key2, value2, key4, value4) + else if (key == key4) new Map3(key1, value1, key2, value2, key3, value3) + else this +} + + + diff --git a/src/library/scala/collection/immutable/Set1.scala b/src/library/scala/collection/immutable/Set1.scala new file mode 100755 index 0000000000..86d5c1d275 --- /dev/null +++ b/src/library/scala/collection/immutable/Set1.scala @@ -0,0 +1,42 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListSet.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + + + +package scala.collection.immutable + +/** This class implements empty immutable maps + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +[serializable] +class Set1[A](elem1: A) extends Set[A] { + + def empty[C]: Set[C] = new EmptySet[C] + + def size: Int = 1 + + def contains(elem: A): Boolean = + elem == elem1 + + def + (elem: A): Set[A] = + if (contains(elem)) this + else new Set2(elem1, elem) + + def - (elem: A): Set[A] = + if (elem == elem1) empty + else this + + def elements: Iterator[A] = + Iterator.fromValues(elem1) +} + + + diff --git a/src/library/scala/collection/immutable/Set2.scala b/src/library/scala/collection/immutable/Set2.scala new file mode 100755 index 0000000000..20ddd6a43d --- /dev/null +++ b/src/library/scala/collection/immutable/Set2.scala @@ -0,0 +1,43 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListSet.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + + + +package scala.collection.immutable + +/** This class implements empty immutable maps + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +[serializable] +class Set2[A](elem1: A, elem2: A) extends Set[A] { + + def empty[C]: Set[C] = new EmptySet[C] + + def size: Int = 2 + + def contains(elem: A): Boolean = + elem == elem1 || elem == elem2 + + def + (elem: A): Set[A] = + if (contains(elem)) this + else new Set3(elem1, elem2, elem) + + def - (elem: A): Set[A] = + if (elem == elem1) new Set1(elem2) + else if (elem == elem2) new Set1(elem1) + else this + + def elements: Iterator[A] = + Iterator.fromValues(elem1, elem2) +} + + + diff --git a/src/library/scala/collection/immutable/Set3.scala b/src/library/scala/collection/immutable/Set3.scala new file mode 100755 index 0000000000..1ffcc833df --- /dev/null +++ b/src/library/scala/collection/immutable/Set3.scala @@ -0,0 +1,44 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListSet.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + + + +package scala.collection.immutable + +/** This class implements empty immutable maps + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +[serializable] +class Set3[A](elem1: A, elem2: A, elem3: A) extends Set[A] { + + def empty[C]: Set[C] = new EmptySet[C] + + def size: Int = 3 + + def contains(elem: A): Boolean = + elem == elem1 || elem == elem2 || elem == elem3 + + def + (elem: A): Set[A] = + if (contains(elem)) this + else new Set4(elem1, elem2, elem3, elem) + + def - (elem: A): Set[A] = + if (elem == elem1) new Set2(elem2, elem3) + else if (elem == elem2) new Set2(elem1, elem3) + else if (elem == elem3) new Set2(elem1, elem2) + else this + + def elements: Iterator[A] = + Iterator.fromValues(elem1, elem2, elem3) +} + + + diff --git a/src/library/scala/collection/immutable/Set4.scala b/src/library/scala/collection/immutable/Set4.scala new file mode 100755 index 0000000000..a51ad8d546 --- /dev/null +++ b/src/library/scala/collection/immutable/Set4.scala @@ -0,0 +1,45 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2007, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: ListSet.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + + + +package scala.collection.immutable + +/** This class implements empty immutable maps + * @author Martin Oderskty + * @version 1.0, 019/01/2007 + */ +[serializable] +class Set4[A](elem1: A, elem2: A, elem3: A, elem4: A) extends Set[A] { + + def empty[C]: Set[C] = new EmptySet[C] + + def size: Int = 4 + + def contains(elem: A): Boolean = + elem == elem1 || elem == elem2 || elem == elem3 || elem == elem4 + + def + (elem: A): Set[A] = + if (contains(elem)) this + else HashSet(elem1, elem2, elem3, elem4, elem) + + def - (elem: A): Set[A] = + if (elem == elem1) new Set3(elem2, elem3, elem4) + else if (elem == elem2) new Set3(elem1, elem3, elem4) + else if (elem == elem3) new Set3(elem1, elem2, elem4) + else if (elem == elem4) new Set3(elem1, elem2, elem3) + else this + + def elements: Iterator[A] = + Iterator.fromValues(elem1, elem2, elem3, elem4) +} + + + diff --git a/src/library/scala/collection/mutable/DefaultEntry.scala b/src/library/scala/collection/mutable/DefaultEntry.scala new file mode 100755 index 0000000000..876319a15d --- /dev/null +++ b/src/library/scala/collection/mutable/DefaultEntry.scala @@ -0,0 +1,18 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2006, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +// $Id: DefaultMapModel.scala 9554 2007-01-04 16:30:16 +0000 (Thu, 04 Jan 2007) odersky $ + + +package scala.collection.mutable + +import Predef._ + +[serializable] +final class DefaultEntry[A, B](val key: A, var value: B) + extends HashEntry[A, DefaultEntry[A, B]] diff --git a/src/library/scala/collection/mutable/FlatHashTable.scala b/src/library/scala/collection/mutable/FlatHashTable.scala new file mode 100755 index 0000000000..98adc036ee --- /dev/null +++ b/src/library/scala/collection/mutable/FlatHashTable.scala @@ -0,0 +1,131 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2006 LAMP/EPFL + * @author Martin Odersky + */ +// $Id: HashSet.scala 9235 2006-11-13 14:59:18 +0000 (Mon, 13 Nov 2006) mihaylov $ + +package scala.collection.mutable + +trait FlatHashTable[A] { + + /** The load factor for the hash table. + */ + protected def loadFactor: Float = 0.5f + + /** The initial size of the hash table. + */ + protected def initialSize: Int = 16 + + /** The actual hash table. + */ + protected var table: Array[AnyRef] = + if (initialSize == 0) null else new Array(initialSize) + + /** The number of mappings contained in this hash table. + */ + protected var tableSize = 0 + + /** The next size value at which to resize (capacity * load factor). + */ + protected var threshold: Int = newThreshold(initialSize) + + /** Returns the number of entires in this hash table. + */ + def size: Int = tableSize + + def findEntry(elem: A): Option[A] = { + var h = index(elemHashCode(elem)) + var entry = table(h) + while (null != entry && entry != elem) { + h = (h + 1) % table.length + entry = table(h) + } + if (null == entry) None else Some(entry.asInstanceOf[A]) + } + + def containsEntry(elem: A): Boolean = { + var h = index(elemHashCode(elem)) + var entry = table(h) + while (null != entry && entry != elem) { + h = (h + 1) % table.length + entry = table(h) + } + null != entry + } + + def addEntry(elem: A) { + var h = index(elemHashCode(elem)) + var entry = table(h) + while (null != entry) { + if (entry == elem) return + h = (h + 1) % table.length + entry = table(h) + } + table(h) = elem.asInstanceOf[AnyRef] + tableSize = tableSize + 1 + if (tableSize >= threshold) growTable() + } + + def removeEntry(elem: A) { + var h = index(elemHashCode(elem)) + var entry = table(h) + while (null != entry) { + if (entry == elem) { + var h1 = (h + 1) % table.length + while (null != table(h1) && (index(elemHashCode(table(h1).asInstanceOf[A])) != h1)) { + table(h) = table(h1) + h = h1 + h1 = (h + 1) % table.length + } + table(h) = null + tableSize = tableSize - 1 + return + } + h = (h + 1) % table.length + entry = table(h) + } + } + + def elements = new Iterator[A] { + private var i = 0 + def hasNext: Boolean = { + while (i < table.length && (null == table(i))) i = i + 1; + i < table.length + } + def next: A = + if (hasNext) { i = i + 1; table(i - 1).asInstanceOf[A] } + else Iterator.empty.next + } + + private def growTable() { + val oldtable = table + table = new Array[AnyRef](table.length * 2) + threshold = newThreshold(table.length) + var i = 0 + while (i < oldtable.length) { + val entry = oldtable(i) + if (null != entry) addEntry(entry.asInstanceOf[A]) + i = i + 1 + } + } + + protected def elemHashCode(elem: A) = elem.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) + + private def newThreshold(size: Int) = + (size * loadFactor).asInstanceOf[Int] + + protected def clear() { + var i = table.length - 1 + while (i >= 0) { table(i) = null; i = i - 1 } + tableSize = 0 + } +} |