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
+  }
+}