From 607cb4250d1b92d819525df61460bf412bc1c916 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Mon, 25 May 2009 22:18:48 +0000 Subject: added SynchronizedMap; changed Set.put to Set.a... added SynchronizedMap; changed Set.put to Set.add, implemented LinkedHashMap/Set more efficiently. --- src/library/scala/collection/mutable/BitSet.scala | 8 +- .../scala/collection/mutable/FlatHashTable.scala | 3 + src/library/scala/collection/mutable/HashMap.scala | 40 +++++- src/library/scala/collection/mutable/HashSet.scala | 4 +- .../scala/collection/mutable/HashTable.scala | 19 ++- .../scala/collection/mutable/LinkedHashMap.scala | 86 ++++++++--- .../scala/collection/mutable/LinkedHashSet.scala | 55 +++---- .../scala/collection/mutable/SynchronizedMap.scala | 158 ++++----------------- .../scala/collection/mutable/SynchronizedSet.scala | 18 ++- 9 files changed, 191 insertions(+), 200 deletions(-) (limited to 'src') 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) } -- cgit v1.2.3