added SynchronizedMap; changed Set.put to Set.a...

added SynchronizedMap; changed Set.put to Set.add, implemented
LinkedHashMap/Set more efficiently.

9 files changed, 191 insertions, 200 deletions

diff --git a/src/library/scala/collection/mutable/BitSet.scala b/src/library/scala/collection/mutable/BitSet.scala
index 996130766c..66d5baac54 100644
--- a/src/library/scala/collection/mutable/BitSet.scala
+++ b/src/library/scala/collection/mutable/BitSet.scala
@@ -35,13 +35,13 @@ class BitSet (protected var elems: Array[Long]) extends Set[Int]
   /** Adds element to bitset,
    *  @return element was already present.
    */
-  override def put (elem: Int): Boolean = {
+  override def add (elem: Int): Boolean = {
     require(elem >= 0)
-    if (contains(elem)) true
+    if (contains(elem)) false
     else {
       val idx = elem >> LogWL
       updateWord(idx, word(idx) | (1L << elem))
-      false
+      true
     }
   }
 
@@ -57,7 +57,7 @@ class BitSet (protected var elems: Array[Long]) extends Set[Int]
     } else false
   }
 
-  def += (elem: Int): this.type = { put(elem); this }
+  def += (elem: Int): this.type = { add(elem); this }
   def -= (elem: Int): this.type = { remove(elem); this }
 
   def toImmutable = immutable.BitSet.fromArray(elems)
diff --git a/src/library/scala/collection/mutable/FlatHashTable.scala b/src/library/scala/collection/mutable/FlatHashTable.scala
index c4ea42a3dd..dd09af381e 100644
--- a/src/library/scala/collection/mutable/FlatHashTable.scala
+++ b/src/library/scala/collection/mutable/FlatHashTable.scala
@@ -62,6 +62,9 @@ trait FlatHashTable[A] {
     null != entry
   }
 
+  /** Add entry if not yet in table
+   *  Return whether a new entry was added
+   */
   def addEntry(elem: A) : Boolean = {
     var h = index(elemHashCode(elem))
     var entry = table(h)
diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala
index d80e514ac8..f8ba594d4c 100644
--- a/src/library/scala/collection/mutable/HashMap.scala
+++ b/src/library/scala/collection/mutable/HashMap.scala
@@ -15,20 +15,46 @@ import generic._
 
 
 @serializable
-class HashMap[A, B] extends Map[A, B] with MutableMapTemplate[A, B, HashMap[A, B]] with HashTable[A] with DefaultMapModel[A, B] {
+class HashMap[A, B] extends Map[A, B]
+                       with MutableMapTemplate[A, B, HashMap[A, B]]
+                       with HashTable[A] {
 
   override def empty: HashMap[A, B] = HashMap.empty[A, B]
+  override def clear() = super.clear()
+  override def size: Int = super[HashTable].size
+
+  type Entry = DefaultEntry[A, B]
 
-  override def remove(key: A): Option[B] = removeEntry(key) match {
-    case Some(e) => Some(e.value)
-    case None => None
+  def get(key: A): Option[B] = {
+    val e = findEntry(key)
+    if (e == null) None
+    else Some(e.value)
   }
 
-  override def -=(key: A): this.type = { remove(key); this }
+  override def put(key: A, value: B): Option[B] = {
+    val e = findEntry(key)
+    if (e == null) { addEntry(new Entry(key, value)); None }
+    else { val v = e.value; e.value = value; Some(v) }
+  }
 
-  override def clear() = super.clear()
+  override def update(key: A, value: B): Unit = put(key, value)
 
-  override def size: Int = super[HashTable].size
+  override def remove(key: A): Option[B] = {
+    val e = removeEntry(key)
+    if (e ne null) Some(e.value)
+    else None
+  }
+
+  def += (kv: (A, B)): this.type = {
+    val e = findEntry(kv._1)
+    if (e == null) addEntry(new Entry(kv._1, kv._2))
+    else e.value = kv._2
+    this
+  }
+
+  def -=(key: A): this.type = { removeEntry(key); this }
+
+  def elements = entries map {e => (e.key, e.value)}
 }
 
 /** This class implements mutable maps using a hashtable.
diff --git a/src/library/scala/collection/mutable/HashSet.scala b/src/library/scala/collection/mutable/HashSet.scala
index 5c93ff96eb..d5eba30552 100644
--- a/src/library/scala/collection/mutable/HashSet.scala
+++ b/src/library/scala/collection/mutable/HashSet.scala
@@ -33,8 +33,8 @@ class HashSet[A] extends Set[A]
   def += (elem: A): this.type = { addEntry(elem); this }
   def -= (elem: A): this.type = { removeEntry(elem); this }
 
-  override def put(elem: A): Boolean = addEntry(elem)
-  override def remove(elem: A): Boolean = !removeEntry(elem).isEmpty
+  override def add(elem: A): Boolean = addEntry(elem)
+  override def remove(elem: A): Boolean = removeEntry(elem).isDefined
 
   override def clear() = super.clear()
 
diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala
index ce00ac6c8a..ada2df83b3 100644
--- a/src/library/scala/collection/mutable/HashTable.scala
+++ b/src/library/scala/collection/mutable/HashTable.scala
@@ -62,6 +62,8 @@ trait HashTable[A] extends AnyRef {
    */
   def size = tableSize
 
+  /** Find entry with given key in table, null if not found
+   */
   protected def findEntry(key: A): Entry = {
     val h = index(elemHashCode(key))
     var e = table(h).asInstanceOf[Entry]
@@ -69,6 +71,9 @@ trait HashTable[A] extends AnyRef {
     e
   }
 
+  /** Add entry to table
+   *  pre: no entry with same key exists
+   */
   protected def addEntry(e: Entry) {
     val h = index(elemHashCode(e.key))
     e.next = table(h).asInstanceOf[Entry]
@@ -78,14 +83,16 @@ trait HashTable[A] extends AnyRef {
       resize(2 * table.length)
   }
 
-  protected def removeEntry(key: A) : Option[Entry] = {
+  /** Remove entry from table if present
+   */
+  protected def removeEntry(key: A) : Entry = {
     val h = index(elemHashCode(key))
     var e = table(h).asInstanceOf[Entry]
     if (e != null) {
       if (elemEquals(e.key, key)) {
         table(h) = e.next
         tableSize = tableSize - 1
-        return Some(e)
+        return e
       } else {
         var e1 = e.next
         while (e1 != null && !elemEquals(e1.key, key)) {
@@ -95,13 +102,15 @@ trait HashTable[A] extends AnyRef {
         if (e1 != null) {
           e.next = e1.next
           tableSize = tableSize - 1
-          return Some(e1)
+          return e1
         }
       }
     }
-    None
+    null
   }
 
+  /** An iterator returning all entries
+   */
   protected def entries: Iterator[Entry] = new Iterator[Entry] {
     val iterTable = table
     var idx = table.length - 1
@@ -122,6 +131,8 @@ trait HashTable[A] extends AnyRef {
     }
   }
 
+  /** Remove all entries from table
+   */
   def clear() {
     var i = table.length - 1
     while (i >= 0) { table(i) = null; i = i - 1 }
diff --git a/src/library/scala/collection/mutable/LinkedHashMap.scala b/src/library/scala/collection/mutable/LinkedHashMap.scala
index f2cdf99c5b..29e77fb01c 100644
--- a/src/library/scala/collection/mutable/LinkedHashMap.scala
+++ b/src/library/scala/collection/mutable/LinkedHashMap.scala
@@ -18,7 +18,7 @@ import generic._
  *
  *  @author  Matthias Zenger
  *  @author  Martin Odersky
- *  @version 2.0, 31/12/2006
+ *  @version 2.8
  */
 object LinkedHashMap extends MutableMapFactory[LinkedHashMap] {
   implicit def builderFactory[A, B]: BuilderFactory[(A, B), LinkedHashMap[A, B], Coll] = new MapBuilderFactory[A, B]
@@ -28,45 +28,89 @@ object LinkedHashMap extends MutableMapFactory[LinkedHashMap] {
 @serializable
 class LinkedHashMap[A, B] extends Map[A, B]
                              with MutableMapTemplate[A, B, LinkedHashMap[A, B]]
-                             with HashTable[A]
-                             with DefaultMapModel[A,B] {
-
-  override def empty = LinkedHashMap.empty
+                             with HashTable[A] {
 
+  override def empty = LinkedHashMap.empty[A, B]
   override def size = super[HashTable].size
 
-  private var ordered = List[Entry]()
+  type Entry = LinkedEntry[A, B]
 
-  def -= (key: A): this.type = { remove(key); this }
+  protected var firstEntry: Entry = null
+  protected var lastEntry: Entry = null
 
-  override def remove(key: A): Option[B] = removeEntry(key) match {
-    case None => None
-    case Some(e) =>
-      ordered = ordered.filter(_ ne e)
-      Some(e.value)
-    }
+  def get(key: A): Option[B] = {
+    val e = findEntry(key)
+    if (e == null) None
+    else Some(e.value)
+  }
 
   override def put(key: A, value: B): Option[B] = {
     val e = findEntry(key)
     if (e == null) {
       val e = new Entry(key, value)
-      ordered = e :: ordered
       addEntry(e)
+      if (firstEntry == null) firstEntry = e
+      else { lastEntry.later = e; e.earlier = lastEntry }
+      lastEntry = e
       None
     } else {
-      val ret = Some(e.value)
+      val v = e.value
       e.value = value
-      ret
+      Some(v)
     }
   }
-  override def update(key: A, value: B) { put(key, value) }
 
-  override def clear() {
-    ordered = Nil
-    super.clear()
+  override def remove(key: A): Option[B] = {
+    val e = removeEntry(key)
+    if (e eq null) None
+    else {
+      if (e.earlier eq null) firstEntry = e.later
+      else e.earlier.later = e.later
+      if (e.later eq null) lastEntry = e.earlier
+      else e.later.earlier = e.earlier
+      Some(e.value)
+    }
+  }
+
+  def += (kv: (A, B)): this.type = { put(kv._1, kv._2); this }
+  def -=(key: A): this.type = { remove(key); this }
+
+  def elements: Iterator[(A, B)] = new Iterator[(A, B)] {
+    private var cur = firstEntry
+    def hasNext = cur ne null
+    def next =
+      if (hasNext) { val res = (cur.key, cur.value); cur = cur.later; res }
+      else Iterator.empty.next
+  }
+
+  override def keys: Iterator[A] = new Iterator[A] {
+    private var cur = firstEntry
+    def hasNext = cur ne null
+    def next =
+      if (hasNext) { val res = cur.key; cur = cur.later; res }
+      else Iterator.empty.next
+  }
+
+  override def values: Iterator[B] = new Iterator[B] {
+    private var cur = firstEntry
+    def hasNext = cur ne null
+    def next = { val res = cur.value; cur = cur.later; res }
+      if (hasNext) { val res = cur.value; cur = cur.later; res }
+      else Iterator.empty.next
   }
 
-  override def elements = ordered.reverse.elements map {e => (e.key, e.value)}
+  override def foreach[U](f: ((A, B)) => U) = {
+    var cur = firstEntry
+    while (cur ne null) {
+      f((cur.key, cur.value))
+      cur = cur.later
+    }
+  }
+
+  override def clear() {
+    super[HashTable].clear()
+    firstEntry = null
+  }
 
   // debug NoSuchElementException in Pickler
   var previousTables: List[(String, Int)] = Nil
diff --git a/src/library/scala/collection/mutable/LinkedHashSet.scala b/src/library/scala/collection/mutable/LinkedHashSet.scala
index 089419ccbd..14f6b18722 100644
--- a/src/library/scala/collection/mutable/LinkedHashSet.scala
+++ b/src/library/scala/collection/mutable/LinkedHashSet.scala
@@ -12,46 +12,49 @@ package scala.collection.mutable
 
 import generic._
 
-//!!! todo make inherit from HashSet.
-object LinkedHashSet {
-  /** The empty map of this type */
-  def empty[A] = new LinkedHashSet[A]
-
-  /** The canonical factory for this type
-   */
-  def apply[A](elems: A*) = empty[A] ++= elems
-}
-
+/** Todo: this has O(n) cost for element removal.
+ *  Should be rewritten to be more efficient.
+ */
 @serializable
-class LinkedHashSet[A] extends Set[A] with MutableSetTemplate[A, LinkedHashSet[A]] with FlatHashTable[A] {
+class LinkedHashSet[A] extends Set[A]
+                          with SetClass[A, LinkedHashSet]
+                          with MutableSetTemplate[A, LinkedHashSet[A]]
+                          with FlatHashTable[A]
+{
+  override def companion: Companion[LinkedHashSet] = LinkedHashSet
 
-  override def empty = LinkedHashSet.empty
+  protected val ordered = new ListBuffer[A]
 
   override def size = super.size
 
-  private var ordered = List[A]()
-
   def contains(elem: A): Boolean = containsEntry(elem)
 
-  def += (elem: A): this.type = { put(elem); this }
+  def += (elem: A): this.type = { add(elem); this }
   def -= (elem: A): this.type = { remove(elem); this }
 
-  override def put(elem: A): Boolean =
-    if (addEntry(elem)) {
-      ordered = elem :: ordered
-      true
-    } else false
+  override def add(elem: A): Boolean =
+    if (addEntry(elem)) { ordered += elem; true }
+    else false
 
-  override def remove(elem: A): Boolean = removeEntry(elem) match {
-    case None => false
-    case Some(elem) => ordered = ordered.filter(_ != elem); true
-  }
+  override def remove(elem: A): Boolean =
+    removeEntry(elem) match {
+      case None => false
+      case _ => ordered -= elem; true
+    }
 
   override def clear() {
-    ordered = Nil
+    ordered.clear()
     super.clear()
   }
 
-  override def elements = ordered.reverse.elements
+  override def elements = ordered.elements
+
+  override def foreach[U](f: A => U) = ordered foreach f
+}
+
+/** Factory object for `LinkedHashSet` class */
+object LinkedHashSet extends SetFactory[LinkedHashSet] {
+  implicit def builderFactory[A]: BuilderFactory[A, LinkedHashSet[A], Coll] = setBuilderFactory[A]
+  override def empty[A]: LinkedHashSet[A] = new LinkedHashSet[A]
 }
 
diff --git a/src/library/scala/collection/mutable/SynchronizedMap.scala b/src/library/scala/collection/mutable/SynchronizedMap.scala
index 838b987e9b..4b30ce5d4b 100644
--- a/src/library/scala/collection/mutable/SynchronizedMap.scala
+++ b/src/library/scala/collection/mutable/SynchronizedMap.scala
@@ -1,4 +1,3 @@
-/* TODO: Reintegrate
 /*                     __                                               *\
 **     ________ ___   / /  ___     Scala API                            **
 **    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
@@ -21,135 +20,32 @@ package scala.collection.mutable
  */
 trait SynchronizedMap[A, B] extends Map[A, B] {
 
-  import collection.Traversable
-
-
-  abstract override def size: Int = synchronized {
-    super.size
-  }
-
-  abstract override def get(key: A): Option[B] = synchronized {
-    super.get(key)
-  }
-
-  override def isEmpty: Boolean = synchronized {
-    super.isEmpty
-  }
-
-  override def apply(key: A): B = synchronized {
-    super.apply(key)
-  }
-
-  override def contains(key: A): Boolean = synchronized {
-    super.contains(key)
-  }
-
-  override def isDefinedAt(key: A) = synchronized {
-    super.isDefinedAt(key)
-  }
-
-  override def keys: Iterator[A] = synchronized {
-    super.keys
-  }
-
-  override def keySet: collection.Set[A] = synchronized {
-    super.keySet
-  }
-
-  override def values: Iterator[B] = synchronized {
-    super.values
-  }
-
-  abstract override def elements: Iterator[(A, B)] = synchronized {
-    super.elements
-  }
-
-  override def toList: List[(A, B)] = synchronized {
-    super.toList
-  }
-
-  abstract override def update(key: A, value: B): Unit = synchronized {
-    super.update(key, value)
-  }
-
-  override def += (kv: (A, B)): Unit = synchronized {
-    super.+=(kv)
-  }
-
-  /** Add two or more key/value pairs to this map.
-   *  @param    kv1 the key/first value pair.
-   *  @param    kv2 the second key/first value pair.
-   *  @param    kvs the remaining key/first value pairs.
-   */
-  override def += (kv1: (A, B), kv2: (A, B), kvs: (A, B)*): Unit = synchronized {
-    super.+=(kv1, kv2, kvs: _*)
-  }
-
-  override def ++=(map: Traversable[(A, B)]): Unit = synchronized {
-    super.++=(map)
-  }
-
-  override def ++=(it: Iterator[(A, B)]): Unit = synchronized {
-    super.++=(it)
-  }
-
-  abstract override def -=(key: A): Unit = synchronized {
-    super.-=(key)
-  }
-
-  override def -= (key1: A, key2: A, keys: A*): Unit = synchronized {
-    super.-=(key1, key2, keys: _*)
-  }
-
-  override def --=(keys: Traversable[A]): Unit = synchronized {
-    super.--=(keys)
-  }
-
-  override def --=(it: Iterator[A]): Unit = synchronized {
-    super.--=(it)
-  }
-
-  override def clear(): Unit = synchronized {
-    super.clear
-  }
-/* TODO: Reintegrate
-  override def getOrElseUpdate(key: A, default: => B): B = synchronized {
-    super.getOrElseUpdate(key, default)
-  }
-*/
-  override def transform(f: (A, B) => B): this.type = synchronized[this.type] {
-    super.transform(f)
-  }
-
-  override def retain(p: (A, B) => Boolean): this.type = synchronized[this.type] {
-    super.retain(p)
-  }
-
-  override def toString() = synchronized {
-    super.toString()
-  }
-
-  override def equals(that: Any): Boolean = synchronized {
-    super.equals(that)
-  }
-
-/* TODO: Reintegrate
-  override def <<(cmd: Message[(A, B)]): Unit = synchronized {
-    super.<<(cmd)
-  }
-*/
-  override def clone(): Map[A, B] = synchronized {
-    super.clone()
-  }
-}
-
-/* Factory object for `Map` class
- * Currently this returns a HashMap.
- */
-object SynchronizedMap extends MutableMapFactory[SynchronizedMap] {
-  type Coll = Map[_, _]
-  implicit def implicitBuilder[A, B]: Builder[(A, B), Map[A, B]] = from.mapBuilder[A, B]
-  def empty[A, B]: Map[A, B] = new HashMap[A, B] with SynchronizeddMap[A, B]
+  abstract override def get(key: A): Option[B] = synchronized { super.get(key) }
+  abstract override def elements: Iterator[(A, B)] = synchronized { super.elements }
+  abstract override def += (kv: (A, B)): this.type = synchronized[this.type] { super.+=(kv) }
+  abstract override def -= (key: A): this.type = synchronized[this.type] { super.-=(key) }
+
+  override def size: Int = synchronized { super.size }
+  override def put(key: A, value: B): Option[B] = synchronized { super.put(key, value) }
+  override def update(key: A, value: B): Unit = synchronized { super.update(key, value) }
+  override def remove(key: A): Option[B] = synchronized { super.remove(key) }
+  override def clear(): Unit = synchronized { super.clear() }
+  override def getOrElseUpdate(key: A, default: => B): B = synchronized { super.getOrElseUpdate(key, default) }
+  override def transform(f: (A, B) => B): this.type = synchronized[this.type] { super.transform(f) }
+  override def retain(p: (A, B) => Boolean): this.type = synchronized[this.type] { super.retain(p) }
+  override def valueSet = synchronized { super.valueSet }
+  override def clone() = synchronized { super.clone() }
+  override def foreach[U](f: ((A, B)) => U) = synchronized { super.foreach(f) }
+  override def apply(key: A): B = synchronized { super.apply(key) }
+  override def keys: Iterator[A] = synchronized { super.keys }
+  override def isEmpty: Boolean = synchronized { super.isEmpty }
+  override def contains(key: A): Boolean = synchronized {super.contains(key) }
+  override def isDefinedAt(key: A) = synchronized { super.isDefinedAt(key) }
+
+  @deprecated override def +(kv: (A, B)): this.type = synchronized[this.type] { super.+(kv) }
+  // can't override -, -- same type!
+  // @deprecated override def -(key: A): This = synchronized { super.-(key) }
+
+  // !!! todo: also add all other methods
 }
 
-*/
diff --git a/src/library/scala/collection/mutable/SynchronizedSet.scala b/src/library/scala/collection/mutable/SynchronizedSet.scala
index 0c57996019..e3ab544974 100644
--- a/src/library/scala/collection/mutable/SynchronizedSet.scala
+++ b/src/library/scala/collection/mutable/SynchronizedSet.scala
@@ -7,7 +7,7 @@
 \*                                                                      */
 
 // $Id$
-
+// !!! check whether we have all methods */
 
 package scala.collection.mutable
 
@@ -33,10 +33,6 @@ trait SynchronizedSet[A] extends Set[A] {
     super.contains(elem)
   }
 
-  abstract override def update(elem: A, included: Boolean): Unit = synchronized {
-    super.update(elem, included)
-  }
-
   abstract override def +=(elem: A): this.type = synchronized[this.type] {
     super.+=(elem)
   }
@@ -61,6 +57,18 @@ trait SynchronizedSet[A] extends Set[A] {
     super.--=(it)
   }
 
+  override def update(elem: A, included: Boolean): Unit = synchronized {
+    super.update(elem, included)
+  }
+
+  override def add(elem: A): Boolean = synchronized {
+    super.add(elem)
+  }
+
+  override def remove(elem: A): Boolean = synchronized {
+    super.remove(elem)
+  }
+
   override def intersect(that: collection.Set[A]) = synchronized {
     super.intersect(that)
   }