diff options
author | Martin Odersky <odersky@gmail.com> | 2009-02-13 11:59:49 +0000 |
---|---|---|
committer | Martin Odersky <odersky@gmail.com> | 2009-02-13 11:59:49 +0000 |
commit | 04840e2ed4530df9a5ca59b984bf2b37a976dc70 (patch) | |
tree | 61394762e202f8ab60e0d3a8e8ac688404241bc3 /src/library/scalax/collection/mutable | |
parent | 708baf94764e2a839e24ca6204060a8d0664d88c (diff) | |
download | scala-04840e2ed4530df9a5ca59b984bf2b37a976dc70.tar.gz scala-04840e2ed4530df9a5ca59b984bf2b37a976dc70.tar.bz2 scala-04840e2ed4530df9a5ca59b984bf2b37a976dc70.zip |
new version of collection libraries
Diffstat (limited to 'src/library/scalax/collection/mutable')
-rwxr-xr-x | src/library/scalax/collection/mutable/Array.scala | 2 | ||||
-rw-r--r-- | src/library/scalax/collection/mutable/ArrayBuffer.scala | 4 | ||||
-rw-r--r-- | src/library/scalax/collection/mutable/Buffer.scala | 28 | ||||
-rw-r--r-- | src/library/scalax/collection/mutable/DefaultEntry.scala (renamed from src/library/scalax/collection/mutable/CloneableCollection.scala) | 11 | ||||
-rw-r--r-- | src/library/scalax/collection/mutable/DefaultMapModel.scala | 44 | ||||
-rw-r--r-- | src/library/scalax/collection/mutable/FlatHashTable.scala | 164 | ||||
-rw-r--r-- | src/library/scalax/collection/mutable/HashMap.scala | 43 | ||||
-rw-r--r-- | src/library/scalax/collection/mutable/HashSet.scala | 48 | ||||
-rw-r--r-- | src/library/scalax/collection/mutable/HashTable.scala | 172 | ||||
-rw-r--r-- | src/library/scalax/collection/mutable/ListBuffer.scala | 4 | ||||
-rwxr-xr-x | src/library/scalax/collection/mutable/Map.scala | 75 | ||||
-rw-r--r-- | src/library/scalax/collection/mutable/Set.scala | 40 | ||||
-rwxr-xr-x | src/library/scalax/collection/mutable/StringBuilder.scala | 1 | ||||
-rw-r--r-- | src/library/scalax/collection/mutable/Vector.scala | 2 |
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] { |