new version of collection libraries

14 files changed, 594 insertions, 44 deletions

diff --git a/src/library/scalax/collection/mutable/Array.scala b/src/library/scalax/collection/mutable/Array.scala
index c2b4d19101..cf1e02008b 100755
--- a/src/library/scalax/collection/mutable/Array.scala
+++ b/src/library/scalax/collection/mutable/Array.scala
@@ -253,7 +253,7 @@ object Array extends SequenceFactory[Array] {
  *  @author Martin Odersky
  *  @version 1.0
  */
-final class Array[A](_length: Int) extends Vector[A] with mutable.VectorTemplate[Array, A] {
+final class Array[A](_length: Int) extends Vector[A] with MutableVectorTemplate[Array, A] {
 
    /** Multidimensional array creation
     *  @deprecated use Array.ofDim instead
diff --git a/src/library/scalax/collection/mutable/ArrayBuffer.scala b/src/library/scalax/collection/mutable/ArrayBuffer.scala
index dbdb96e004..daf514c485 100644
--- a/src/library/scalax/collection/mutable/ArrayBuffer.scala
+++ b/src/library/scalax/collection/mutable/ArrayBuffer.scala
@@ -11,7 +11,7 @@
 
 package scalax.collection.mutable
 
-import generic.SequenceFactory
+import generic.{SequenceFactory, MutableVectorTemplate, Builder}
 
 /* Factory object for `ArrayBuffer` class */
 object ArrayBuffer extends SequenceFactory[ArrayBuffer] {
@@ -31,7 +31,7 @@ object ArrayBuffer extends SequenceFactory[ArrayBuffer] {
 class ArrayBuffer[A](override protected val initialSize: Int)
   extends Buffer[A]
      with Vector[A]
-     with generic.mutable.VectorTemplate[ArrayBuffer, A]
+     with MutableVectorTemplate[ArrayBuffer, A]
      with Builder[ArrayBuffer, A]
      with ResizableArray[A] {
 
diff --git a/src/library/scalax/collection/mutable/Buffer.scala b/src/library/scalax/collection/mutable/Buffer.scala
index 502f99758a..3d0eaec84e 100644
--- a/src/library/scalax/collection/mutable/Buffer.scala
+++ b/src/library/scalax/collection/mutable/Buffer.scala
@@ -11,8 +11,7 @@
 
 package scalax.collection.mutable
 
-import generic.{SequenceFactory, SequenceTemplate}
-import generic.mutable.{Growable, Shrinkable}
+import generic._
 
 /* Factory object for `Buffer` trait */
 object Buffer extends SequenceFactory[Buffer] {
@@ -29,12 +28,14 @@ object Buffer extends SequenceFactory[Buffer] {
  *  @version 2.8
   */
 @cloneable
-trait Buffer[A] extends mutable.Sequence[A]
+trait Buffer[A] extends Sequence[A]
                    with SequenceTemplate[Buffer, A]
+                   with Addable[Buffer[A], A]
+                   with Subtractable[Buffer[A], A]
                    with Growable[A]
                    with Shrinkable[A]
 //      with Scriptable[Message[(Location, A)]]
-                   with CloneableCollection
+                   with Cloneable[Buffer[A]]
 {
 
 // Abstract methods from Vector:
@@ -83,6 +84,10 @@ trait Buffer[A] extends mutable.Sequence[A]
    */
   def +:(elem: A): this.type
 
+  /** Append a single element to this buffer and return the identity of the buffer
+   */
+  def +(elem: A): this.type = { +=(elem); this }
+
   /** Inserts new elements at the index <code>n</code>. Opposed to method
    *  <code>update</code>, this method will not replace an element with a
    *  one. Instead, it will insert a new element at index <code>n</code>.
@@ -114,7 +119,7 @@ trait Buffer[A] extends mutable.Sequence[A]
   }
 
   /** Removes a single element from this buffer, at its first occurrence.
-   *  If the list does not contain that element, it is unchanged
+   *  If the buffer does not contain that element, it is unchanged.
    *
    *  @param x  the element to remove.
    */
@@ -123,6 +128,13 @@ trait Buffer[A] extends mutable.Sequence[A]
     if (i != -1) remove(i)
   }
 
+  /** Removes a single element from this buffer and returns the identity
+   *  of the buffer. If the buffer does not contain that element, it is unchanged.
+   *
+   *  @param x  the element to remove.
+   */
+  def -(elem: A): this.type = { -=(elem); this }
+
   /** Prepend two ore more elements to this buffer and return
    *  the identity of the buffer.
    *  @param elem  the element to prepend.
@@ -235,12 +247,6 @@ trait Buffer[A] extends mutable.Sequence[A]
   }
    */
 
-  /** Return a clone of this buffer.
-   *
-   *  @return a buffer with the same elements.
-   */
-  override def clone(): Buffer[A] = super.clone().asInstanceOf[Buffer[A]]
-
   /** Defines the prefix of the string representation.
    */
   override def stringPrefix: String = "Buffer"
diff --git a/src/library/scalax/collection/mutable/CloneableCollection.scala b/src/library/scalax/collection/mutable/DefaultEntry.scala
index 465995ac7e..2fb0f62226 100644
--- a/src/library/scalax/collection/mutable/CloneableCollection.scala
+++ b/src/library/scalax/collection/mutable/DefaultEntry.scala
@@ -6,14 +6,11 @@
 **                          |/                                          **
 \*                                                                      */
 
-// $Id: CloneableCollection.scala 12003 2007-06-13 12:14:15Z mihaylov $
+// $Id: DefaultEntry.scala 16893 2009-01-13 13:09:22Z cunei $
 
 
 package scalax.collection.mutable
 
-/** The J2ME version of the library defined this trait with a clone method
- * to substitute for the lack of Object.clone there
- */
-trait CloneableCollection {
-  override def clone(): AnyRef = super.clone()
-}
+@serializable
+final class DefaultEntry[A, B](val key: A, var value: B)
+      extends HashEntry[A, DefaultEntry[A, B]]
diff --git a/src/library/scalax/collection/mutable/DefaultMapModel.scala b/src/library/scalax/collection/mutable/DefaultMapModel.scala
new file mode 100644
index 0000000000..fda7798e26
--- /dev/null
+++ b/src/library/scalax/collection/mutable/DefaultMapModel.scala
@@ -0,0 +1,44 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |                                         **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: DefaultMapModel.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+package scalax.collection.mutable
+
+/** This class is used internally. It implements the mutable <code>Map</code>
+ *  class in terms of three functions: <code>findEntry</code>,
+ *  <code>addEntry</code>, and <code>entries</code>.
+ *
+ *  @author  Matthias Zenger
+ *  @version 1.0, 08/07/2003
+ */
+trait DefaultMapModel[A, B] extends Map[A, B] {
+
+  type Entry = DefaultEntry[A, B]
+
+  protected def findEntry(key: A): Entry
+  protected def addEntry(e: Entry)
+  protected def entries: Iterator[Entry]
+
+  def get(key: A): Option[B] = {
+    val e = findEntry(key)
+    if (e == null) None
+    else Some(e.value);
+  }
+
+  def update(key: A, value: B): this.type = {
+    val e = findEntry(key)
+    if (e == null) addEntry(new Entry(key, value))
+    else e.value = value
+    this
+  }
+
+  def elements = entries map {e => (e.key, e.value)}
+}
+
diff --git a/src/library/scalax/collection/mutable/FlatHashTable.scala b/src/library/scalax/collection/mutable/FlatHashTable.scala
new file mode 100644
index 0000000000..c8fe2cede3
--- /dev/null
+++ b/src/library/scalax/collection/mutable/FlatHashTable.scala
@@ -0,0 +1,164 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: FlatHashTable.scala 16893 2009-01-13 13:09:22Z cunei $
+
+package scalax.collection.mutable
+
+trait FlatHashTable[A] {
+
+  /** The load factor for the hash table; must be < 500 (0.5)
+   */
+  protected def loadFactor: Int = 450
+  protected final def loadFactorDenum = 1000
+
+  /** The initial size of the hash table.
+   */
+  protected def initialSize: Int = 16
+
+  private final val tableDebug = false
+
+  /** The actual hash table.
+   */
+  protected var table: scala.Array[AnyRef] =
+    if (initialSize == 0) null else new scala.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) : Boolean = {
+    var h = index(elemHashCode(elem))
+    var entry = table(h)
+    while (null != entry) {
+      if (entry == elem) return false
+      h = (h + 1) % table.length
+      entry = table(h)
+    }
+    table(h) = elem.asInstanceOf[AnyRef]
+    tableSize = tableSize + 1
+    if (tableSize >= threshold) growTable()
+    true
+  }
+
+  def removeEntry(elem: A) : Option[A] = {
+    if (tableDebug) checkConsistent()
+    def precedes(i: Int, j: Int) = {
+      val d = table.length >> 1
+      if (i <= j) j - i < d
+      else i - j > d
+    }
+    var h = index(elemHashCode(elem))
+    var entry = table(h)
+    while (null != entry) {
+      if (entry == elem) {
+        var h0 = h
+        var h1 = (h0 + 1) % table.length
+        while (null != table(h1)) {
+          val h2 = index(elemHashCode(table(h1).asInstanceOf[A]))
+          //Console.println("shift at "+h1+":"+table(h1)+" with h2 = "+h2+"? "+(h2 != h1)+precedes(h2, h0)+table.length)
+          if (h2 != h1 && precedes(h2, h0)) {
+            //Console.println("shift "+h1+" to "+h0+"!")
+            table(h0) = table(h1)
+            h0 = h1
+          }
+          h1 = (h1 + 1) % table.length
+        }
+        table(h0) = null
+        tableSize -= 1
+        if (tableDebug) checkConsistent()
+        return Some(entry.asInstanceOf[A])
+      }
+      h = (h + 1) % table.length
+      entry = table(h)
+    }
+    None
+  }
+
+  def elements = new Iterator[A] {
+    private var i = 0
+    def hasNext: Boolean = {
+      while (i < table.length && (null == table(i))) i += 1;
+      i < table.length
+    }
+    def next(): A =
+      if (hasNext) { i += 1; table(i - 1).asInstanceOf[A] }
+      else Iterator.empty.next
+  }
+
+  private def growTable() {
+    val oldtable = table
+    table = new scala.Array[AnyRef](table.length * 2)
+    tableSize = 0
+    threshold = newThreshold(table.length)
+    var i = 0
+    while (i < oldtable.length) {
+      val entry = oldtable(i)
+      if (null != entry) addEntry(entry.asInstanceOf[A])
+      i += 1
+    }
+    if (tableDebug) checkConsistent()
+  }
+
+  private def checkConsistent() {
+    for (i <- 0 until table.length)
+      if (table(i) != null && !containsEntry(table(i).asInstanceOf[A]))
+        assert(false, i+" "+table(i)+" "+table.toString)
+  }
+
+  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) = {
+    val lf = loadFactor
+    assert(lf < (loadFactorDenum / 2), "loadFactor too large; must be < 0.5")
+    (size.toLong * lf / loadFactorDenum ).toInt
+  }
+
+  protected def clear() {
+    var i = table.length - 1
+    while (i >= 0) { table(i) = null; i -= 1 }
+    tableSize = 0
+  }
+}
diff --git a/src/library/scalax/collection/mutable/HashMap.scala b/src/library/scalax/collection/mutable/HashMap.scala
new file mode 100644
index 0000000000..4d3342636c
--- /dev/null
+++ b/src/library/scalax/collection/mutable/HashMap.scala
@@ -0,0 +1,43 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: HashMap.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+package scalax.collection.mutable
+
+import generic._
+
+/** This class implements mutable maps using a hashtable.
+ *
+ *  @author  Matthias Zenger
+ *  @author  Martin Odersky
+ *  @version 2.8
+ */
+object HashMap  extends MapFactory[HashMap] {
+
+  /** The empty map of this type */
+  def empty[A, B] = new HashMap[A, B]
+
+}
+
+@serializable
+class HashMap[A, B]
+  extends Map[A, B]
+     with MapTemplate[A, B, HashMap]
+     with HashTable[A]
+     with DefaultMapModel[A, B] {
+
+  def empty[B] = HashMap.empty[A, B]
+
+  def -= (key: A) { removeEntry(key) }
+
+  override def clear() = super.clear()
+
+  override def clone(): Map[A, B] = new HashMap[A, B] ++ this
+}
diff --git a/src/library/scalax/collection/mutable/HashSet.scala b/src/library/scalax/collection/mutable/HashSet.scala
new file mode 100644
index 0000000000..601d0885c0
--- /dev/null
+++ b/src/library/scalax/collection/mutable/HashSet.scala
@@ -0,0 +1,48 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: HashSet.scala 16893 2009-01-13 13:09:22Z cunei $
+
+
+package scalax.collection.mutable
+
+import generic.{SetTemplate, SetFactory, AddableBuilder}
+
+/** Factory object for `HashSet` class */
+object HashSet extends SetFactory[HashSet] {
+  /** The empty set of this type */
+  def empty[A] = new HashSet[A]
+}
+
+/** This class implements mutable sets using a hashtable.
+ *
+ *  @author  Matthias Zenger
+ *  @author  Martin Odersky
+ *  @version 2.0, 31/12/2006
+ */
+@serializable
+class HashSet[A]
+  extends Set[A]
+     with SetTemplate[HashSet, A]
+     with FlatHashTable[A] {
+
+  def contains(elem: A): Boolean = containsEntry(elem)
+
+  def +=(elem: A) { addEntry(elem) }
+
+  def -=(elem: A) { removeEntry(elem) }
+
+  override def clear() = super.clear()
+
+  override def newBuilder[B]: generic.Builder[HashSet, B] =
+    new AddableBuilder[HashSet, B](HashSet.empty)
+
+  override def clone(): HashSet[A] = new HashSet[A] ++ this
+}
+
+
diff --git a/src/library/scalax/collection/mutable/HashTable.scala b/src/library/scalax/collection/mutable/HashTable.scala
new file mode 100644
index 0000000000..73ff61f3df
--- /dev/null
+++ b/src/library/scalax/collection/mutable/HashTable.scala
@@ -0,0 +1,172 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://www.scala-lang.org/           **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: HashTable.scala 16884 2009-01-09 16:52:09Z cunei $
+
+
+package scalax.collection.mutable
+
+/** This class can be used to construct data structures that are based
+ *  on hashtables. Class <code>HashTable[A]</code> implements a hashtable
+ *  that maps keys of type <code>A</code> to values of the fully abstract
+ *  member type <code>Entry</code>. Classes that make use of <code>HashTable</code>
+ *  have to provide an implementation for <code>Entry</code>
+ *
+ *  There are mainly two parameters that affect the performance of a hashtable:
+ *  the <i>initial size</i> and the <i>load factor</i>. The <i>size</i>
+ *  refers to the number of <i>buckets</i> in the hashtable, and the <i>load
+ *  factor</i> is a measure of how full the hashtable is allowed to get before
+ *  its size is automatically doubled. Both parameters may be changed by
+ *  overriding the corresponding values in class <code>HashTable</code>.
+ *
+ *  @author  Matthias Zenger
+ *  @author  Martin Odersky
+ *  @version 2.0, 31/12/2006
+ */
+trait HashTable[A] extends AnyRef {
+
+  protected type Entry >: Null <: HashEntry[A, Entry]
+
+  /** The load factor for the hash table (in 0.001 step).
+   */
+  protected def loadFactor: Int = 750 // corresponds to 75%
+  protected final val loadFactorDenum = 1000;
+
+  /** The initial size of the hash table.
+   */
+  protected def initialSize: Int = 16
+
+  /** The initial threshold
+   */
+  protected def initialThreshold: Int = newThreshold(initialSize)
+
+  /** The actual hash table.
+   */
+  protected var table: scala.Array[HashEntry[A, Entry]] =
+    if (initialSize == 0) null else new scala.Array(initialSize)
+
+  /** The number of mappings contained in this hash table.
+   */
+  protected var tableSize: Int = 0
+
+  /** The next size value at which to resize (capacity * load factor).
+   */
+  protected var threshold: Int = initialThreshold
+
+  /** Returns the size of this hash table.
+   */
+  def size = tableSize
+
+  protected def findEntry(key: A): Entry = {
+    val h = index(elemHashCode(key))
+    var e = table(h).asInstanceOf[Entry]
+    while (e != null && !elemEquals(e.key, key)) e = e.next
+    e
+  }
+
+  protected def addEntry(e: Entry) {
+    val h = index(elemHashCode(e.key))
+    e.next = table(h).asInstanceOf[Entry]
+    table(h) = e
+    tableSize = tableSize + 1
+    if (tableSize > threshold)
+      resize(2 * table.length)
+  }
+
+  protected def removeEntry(key: A) : Option[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)
+      } else {
+        var e1 = e.next
+        while (e1 != null && !elemEquals(e1.key, key)) {
+          e = e1
+          e1 = e1.next
+        }
+        if (e1 != null) {
+          e.next = e1.next
+          tableSize = tableSize - 1
+          return Some(e1)
+        }
+      }
+    }
+    None
+  }
+
+  protected def entries: Iterator[Entry] = new Iterator[Entry] {
+    val iterTable = table
+    var idx = table.length - 1
+    var es = iterTable(idx).asInstanceOf[Entry]
+    scan()
+    def hasNext = es != null
+    def next = {
+      val res = es
+      es = es.next
+      scan()
+      res
+    }
+    def scan() {
+      while (es == null && idx > 0) {
+        idx = idx - 1
+        es = iterTable(idx).asInstanceOf[Entry]
+      }
+    }
+  }
+
+  def clear() {
+    var i = table.length - 1
+    while (i >= 0) { table(i) = null; i = i - 1 }
+    tableSize = 0
+  }
+
+  private def newThreshold(size: Int) =
+    ((size.toLong * loadFactor)/loadFactorDenum).toInt
+
+  private def resize(newSize: Int) = {
+    val oldTable = table
+    table = new scala.Array(newSize)
+    var i = oldTable.length - 1
+    while (i >= 0) {
+      var e = oldTable(i)
+      while (e != null) {
+        val h = index(elemHashCode(e.key))
+        val e1 = e.next
+        e.next = table(h).asInstanceOf[Entry]
+        table(h) = e
+        e = e1
+      }
+      i = i - 1
+    }
+    threshold = newThreshold(newSize)
+  }
+
+  protected def elemEquals(key1: A, key2: A): Boolean = (key1 == key2)
+
+  protected def elemHashCode(key: A) = key.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)
+}
+
+trait HashEntry[A, E] {
+  val key: A
+  var next: E = _
+}
+
+
+
diff --git a/src/library/scalax/collection/mutable/ListBuffer.scala b/src/library/scalax/collection/mutable/ListBuffer.scala
index dff29f6453..4d0ad7ec80 100644
--- a/src/library/scalax/collection/mutable/ListBuffer.scala
+++ b/src/library/scalax/collection/mutable/ListBuffer.scala
@@ -11,7 +11,7 @@
 
 package scalax.collection.mutable
 
-import generic.{SequenceForwarder, SequenceFactory, SequenceTemplate}
+import generic._
 import immutable.List
 import collection.immutable.{List, Nil, ::}
 
@@ -31,6 +31,8 @@ object ListBuffer extends SequenceFactory[ListBuffer] {
 final class ListBuffer[A]
       extends Buffer[A]
          with SequenceTemplate[ListBuffer, A]
+         with Addable[ListBuffer[A], A]
+         with Subtractable[ListBuffer[A], A]
          with Builder[List, A]
          with SequenceForwarder[A]
 {
diff --git a/src/library/scalax/collection/mutable/Map.scala b/src/library/scalax/collection/mutable/Map.scala
new file mode 100755
index 0000000000..43f42df298
--- /dev/null
+++ b/src/library/scalax/collection/mutable/Map.scala
@@ -0,0 +1,75 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2009, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+// $Id: Map.scala 16884 2009-01-09 16:52:09Z cunei $
+
+
+package scalax.collection.mutable
+
+import generic._
+
+/* Factory object for `Map` class */
+object Map extends MapFactory[Map] {
+  def empty[A, B]: Map[A, B] = new HashMap[A, B]
+}
+
+trait Map[A, B]
+  extends collection.Map[A, B]
+     with MapTemplate[A, B, Map]
+     with Growable[(A, B)]
+     with Shrinkable[A]
+     with Cloneable[Map[A, B]] {
+self =>
+
+  override def thisCC: Map[A, B] = this
+
+  /** This method allows one to add a new mapping from <code>key</code>
+   *  to <code>value</code> to the map. If the map already contains a
+   *  mapping for <code>key</code>, it will be overridden by this
+   *  function.
+   *
+   * @param key    The key to update
+   * @param value  The new value
+   */
+  def update(key: A, value: B): this.type
+
+  /** Add a key/value pair to this map.
+   *  @param    kv the key/value pair.
+   */
+  def += (kv: (A, B)) { update(kv._1, kv._2) }
+
+  /** Remove a key from this map, noop if key is not present.
+   *  @param    key the key to be removed
+   */
+  def -= (key: A)
+
+  def -(key: A): this.type = { -=(key); this }
+
+  /** Removes all elements from the set for
+   *  which the predicate <code>p</code> yields the value <code>false</code>.
+   */
+  def retain(p: A => Boolean): Unit = for ((k, v) <- this) if (!p(k)) -=(k)
+
+  /** Removes all elements from the set. After this operation is completed,
+   *  the set will be empty.
+   */
+  def clear() { for ((k, v) <- elements) -=(k) }
+
+  override def clone(): Map[A, B] = empty[B] ++ this
+
+  /** Return a read-only projection of this set !!! just us an (immutable) setProxy? */
+  def readOnly : collection.Map[A, B] = new collection.Map[A, B] {
+    override def size = self.size
+    override def update(key: A, value: B) = self.update(key, value)
+    override def - (elem: A) = self - elem
+    override def elements = self.elements
+    override def foreach(f: ((A, B)) => Unit) = self.foreach(f)
+    override def empty[C] = self.empty[C]
+    def get(key: A) = self.get(key)
+  }
+}
diff --git a/src/library/scalax/collection/mutable/Set.scala b/src/library/scalax/collection/mutable/Set.scala
index 40dc643012..78f3234336 100644
--- a/src/library/scalax/collection/mutable/Set.scala
+++ b/src/library/scalax/collection/mutable/Set.scala
@@ -12,14 +12,13 @@
 package scalax.collection.mutable
 
 import collection.generic._
-import collection.generic.mutable.{Growable, Shrinkable}
 
 /** The canonical factory methods for <a href="Set.html">mutable sets</a>.
  *  Currently these return <a href="HashSet.html">HashSet's</a>.
  */
 object Set extends generic.SetFactory[Set] {
   /** The empty map of this type; this is implemented as a hashtable */
-  def empty[A]: Set[A] = null // !!! new HashSet[A]
+  def empty[A]: Set[A] = new HashSet[A]
 }
 
 /** This class represents mutable sets. Concrete set implementations
@@ -32,13 +31,13 @@ object Set extends generic.SetFactory[Set] {
  *  @author Martin Odersky
  *  @version 2.8
  */
-@cloneable
-trait Set[A] extends OrderedIterable[A]
-                with collection.Set[A]
+trait Set[A] extends collection.Set[A]
                 with SetTemplate[Set, A]
+                with Addable[Set[A], A]
+                with Subtractable[Set[A], A]
                 with Growable[A]
                 with Shrinkable[A]
-                with Cloneable[A] {
+                with Cloneable[Set[A]] {
 self =>
 
   /** This method allows one to add or remove an element <code>elem</code>
@@ -51,7 +50,7 @@ self =>
     if (included) this += elem else this -= elem
   }
 
-  /** Add a new element to the set.
+  /** Adds a new element to the set.
    *
    *  @param elem the element to be added
    */
@@ -62,18 +61,17 @@ self =>
    */
   def -=(elem: A)
 
-  // Bridge methods to methods in Growable/Shrinkable;
-  // we can't directly inherit these because they override nothing.
-
-  override def - (elem: A): this.type = super.-(elem)
-  override def - (elem1: A, elem2: A, elems: A*): this.type = super.-(elem1, elem2, elems: _*)
-  override def -- (elems: collection.Iterable[A]): this.type = super.--(elems)
-  override def -- (elems: Iterator[A]): this.type = super.--(elems)
+  /** Adds a new element to the set and returns the set itself.
+   *
+   *  @param elem the element to be added
+   */
+  def +(elem: A): this.type = { +=(elem); this }
 
-  override def + (elem: A): this.type = super.+(elem)
-  override def + (elem1: A, elem2: A, elems: A*): this.type = super.+(elem1, elem2, elems: _*)
-  override def ++ (elems: collection.Iterable[A]): this.type = super.++(elems)
-  override def ++ (elems: Iterator[A]): this.type = super.++(elems)
+  /** Removed a new element from the set and returns the set itself.
+   *
+   *  @param elem the element to be added
+   */
+  def -(elem: A): this.type = { -=(elem); this }
 
   /** This method computes an intersection with set <code>that</code>.
    *  It removes all the elements that are not present in <code>that</code>.
@@ -90,14 +88,16 @@ self =>
   /** Removes all elements from the set. After this operation is completed,
    *  the set will be empty.
    */
-  def clear() { elements foreach -= }
+  def clear() { foreach(-=) }
+
+  override def clone(): Set[A] = { val b = newBuilder[A]; b ++= this; b.result }
 
   /** Send a message to this scriptable object.
    *
    *  @param cmd  the message to send.
    *  @throws <code>Predef.UnsupportedOperationException</code>
    *  if the message was not understood.
-  def <<(cmd: Message[A]): Unit = cmd match {
+   def <<(cmd: Message[A]): Unit = cmd match {
     case Include(elem) => this += elem
     case Remove(elem) => this -= elem
     case Reset() => clear
diff --git a/src/library/scalax/collection/mutable/StringBuilder.scala b/src/library/scalax/collection/mutable/StringBuilder.scala
index 3152182dc4..30aeba4aed 100755
--- a/src/library/scalax/collection/mutable/StringBuilder.scala
+++ b/src/library/scalax/collection/mutable/StringBuilder.scala
@@ -12,7 +12,6 @@
 package scalax.collection.mutable
 
 import scalax.collection.generic._
-import scalax.collection.generic.mutable.Growable
 import scalax.runtime._
 
 
diff --git a/src/library/scalax/collection/mutable/Vector.scala b/src/library/scalax/collection/mutable/Vector.scala
index aef1c75d94..1813172fbf 100644
--- a/src/library/scalax/collection/mutable/Vector.scala
+++ b/src/library/scalax/collection/mutable/Vector.scala
@@ -12,7 +12,7 @@ package scalax.collection.mutable
 
 import generic._
 
-trait Vector[A] extends Sequence[A] with collection.Vector[A] with generic.mutable.VectorTemplate[Vector, A]
+trait Vector[A] extends Sequence[A] with collection.Vector[A] with MutableVectorTemplate[Vector, A]
 
 /* Factory object for `Vector` class */
 object Vector extends SequenceFactory[Vector] {