diff options
Diffstat (limited to 'src/library/scala/collection/MapLike.scala')
| -rw-r--r-- | src/library/scala/collection/MapLike.scala | 157 |
1 files changed, 87 insertions, 70 deletions
diff --git a/src/library/scala/collection/MapLike.scala b/src/library/scala/collection/MapLike.scala index 99ed67325c..a087cb0f45 100644 --- a/src/library/scala/collection/MapLike.scala +++ b/src/library/scala/collection/MapLike.scala @@ -11,7 +11,7 @@ package collection import generic._ import mutable.{ Builder, MapBuilder } -import scala.annotation.{migration, bridge} +import scala.annotation.migration import parallel.ParMap /** A template trait for maps, which associate keys with values. @@ -28,10 +28,10 @@ import parallel.ParMap * To implement a concrete map, you need to provide implementations of the * following methods: * {{{ - * def get(key: A): Option[B] - * def iterator: Iterator[(A, B)] - * def + [B1 >: B](kv: (A, B1)): This - * def -(key: A): This + * def get(key: K): Option[V] + * def iterator: Iterator[(K, V)] + * def + [V1 >: V](kv: (K, V1)): This + * def -(key: K): This * }}} * If you wish that methods like `take`, `drop`, `filter` also return the same kind of map * you should also override: @@ -42,8 +42,8 @@ import parallel.ParMap * `size` for efficiency. * * @define mapTags - * @tparam A the type of the keys. - * @tparam B the type of associated values. + * @tparam K the type of the keys. + * @tparam V the type of associated values. * @tparam This the type of the map itself. * * @author Martin Odersky @@ -54,12 +54,12 @@ import parallel.ParMap * @define willNotTerminateInf * @define mayNotTerminateInf */ -trait MapLike[A, +B, +This <: MapLike[A, B, This] with Map[A, B]] - extends PartialFunction[A, B] - with IterableLike[(A, B), This] - with GenMapLike[A, B, This] - with Subtractable[A, This] - with Parallelizable[(A, B), ParMap[A, B]] +trait MapLike[K, +V, +This <: MapLike[K, V, This] with Map[K, V]] + extends PartialFunction[K, V] + with IterableLike[(K, V), This] + with GenMapLike[K, V, This] + with Subtractable[K, This] + with Parallelizable[(K, V), ParMap[K, V]] { self => @@ -71,7 +71,7 @@ self => /** A common implementation of `newBuilder` for all maps in terms of `empty`. * Overridden for mutable maps in `mutable.MapLike`. */ - override protected[this] def newBuilder: Builder[(A, B), This] = new MapBuilder[A, B, This](empty) + override protected[this] def newBuilder: Builder[(K, V), This] = new MapBuilder[K, V, This](empty) /** Optionally returns the value associated with a key. * @@ -79,32 +79,32 @@ self => * @return an option value containing the value associated with `key` in this map, * or `None` if none exists. */ - def get(key: A): Option[B] + def get(key: K): Option[V] /** Creates a new iterator over all key/value pairs of this map * * @return the new iterator */ - def iterator: Iterator[(A, B)] + def iterator: Iterator[(K, V)] /** Adds a key/value pair to this map, returning a new map. * @param kv the key/value pair - * @tparam B1 the type of the value in the key/value pair. + * @tparam V1 the type of the value in the key/value pair. * @return a new map with the new binding added to this map * - * @usecase def + (kv: (A, B)): Map[A, B] + * @usecase def + (kv: (K, V)): Map[K, V] * @inheritdoc */ - def + [B1 >: B] (kv: (A, B1)): Map[A, B1] + def + [V1 >: V] (kv: (K, V1)): Map[K, V1] /** Removes a key from this map, returning a new map. * @param key the key to be removed * @return a new map without a binding for `key` * - * @usecase def - (key: A): Map[A, B] + * @usecase def - (key: K): Map[K, V] * @inheritdoc */ - def - (key: A): This + def - (key: K): This /** Tests whether the map is empty. * @@ -116,14 +116,14 @@ self => * @param key the key. * @param default a computation that yields a default value in case no binding for `key` is * found in the map. - * @tparam B1 the result type of the default computation. + * @tparam V1 the result type of the default computation. * @return the value associated with `key` if it exists, * otherwise the result of the `default` computation. * - * @usecase def getOrElse(key: A, default: => B): B + * @usecase def getOrElse(key: K, default: => V): V * @inheritdoc */ - def getOrElse[B1 >: B](key: A, default: => B1): B1 = get(key) match { + def getOrElse[V1 >: V](key: K, default: => V1): V1 = get(key) match { case Some(v) => v case None => default } @@ -137,7 +137,7 @@ self => * @return the value associated with the given key, or the result of the * map's `default` method, if none exists. */ - def apply(key: A): B = get(key) match { + def apply(key: K): V = get(key) match { case None => default(key) case Some(value) => value } @@ -147,7 +147,7 @@ self => * @param key the key * @return `true` if there is a binding for `key` in this map, `false` otherwise. */ - def contains(key: A): Boolean = get(key).isDefined + def contains(key: K): Boolean = get(key).isDefined /** Tests whether this map contains a binding for a key. This method, * which implements an abstract method of trait `PartialFunction`, @@ -156,29 +156,33 @@ self => * @param key the key * @return `true` if there is a binding for `key` in this map, `false` otherwise. */ - def isDefinedAt(key: A) = contains(key) + def isDefinedAt(key: K) = contains(key) + + override /*PartialFunction*/ + def applyOrElse[K1 <: K, V1 >: V](x: K1, default: K1 => V1): V1 = + getOrElse(x, default(x)) /** Collects all keys of this map in a set. * @return a set containing all keys of this map. */ - def keySet: Set[A] = new DefaultKeySet + def keySet: Set[K] = new DefaultKeySet /** The implementation class of the set returned by `keySet`. */ - protected class DefaultKeySet extends AbstractSet[A] with Set[A] with Serializable { - def contains(key : A) = self.contains(key) + protected class DefaultKeySet extends AbstractSet[K] with Set[K] with Serializable { + def contains(key : K) = self.contains(key) def iterator = keysIterator - def + (elem: A): Set[A] = (Set[A]() ++ this + elem).asInstanceOf[Set[A]] // !!! concrete overrides abstract problem - def - (elem: A): Set[A] = (Set[A]() ++ this - elem).asInstanceOf[Set[A]] // !!! concrete overrides abstract problem + def + (elem: K): Set[K] = (Set[K]() ++ this + elem).asInstanceOf[Set[K]] // !!! concrete overrides abstract problem + def - (elem: K): Set[K] = (Set[K]() ++ this - elem).asInstanceOf[Set[K]] // !!! concrete overrides abstract problem override def size = self.size - override def foreach[U](f: A => U) = self.keysIterator foreach f + override def foreach[U](f: K => U) = self.keysIterator foreach f } /** Creates an iterator for all keys. * * @return an iterator over all keys. */ - def keysIterator: Iterator[A] = new AbstractIterator[A] { + def keysIterator: Iterator[K] = new AbstractIterator[K] { val iter = self.iterator def hasNext = iter.hasNext def next() = iter.next()._1 @@ -188,29 +192,29 @@ self => * * @return the keys of this map as an iterable. */ - @migration("`keys` returns `Iterable[A]` rather than `Iterator[A]`.", "2.8.0") - def keys: Iterable[A] = keySet + @migration("`keys` returns `Iterable[K]` rather than `Iterator[K]`.", "2.8.0") + def keys: Iterable[K] = keySet /** Collects all values of this map in an iterable collection. * * @return the values of this map as an iterable. */ - @migration("`values` returns `Iterable[B]` rather than `Iterator[B]`.", "2.8.0") - def values: Iterable[B] = new DefaultValuesIterable + @migration("`values` returns `Iterable[V]` rather than `Iterator[V]`.", "2.8.0") + def values: Iterable[V] = new DefaultValuesIterable /** The implementation class of the iterable returned by `values`. */ - protected class DefaultValuesIterable extends AbstractIterable[B] with Iterable[B] with Serializable { + protected class DefaultValuesIterable extends AbstractIterable[V] with Iterable[V] with Serializable { def iterator = valuesIterator override def size = self.size - override def foreach[U](f: B => U) = self.valuesIterator foreach f + override def foreach[U](f: V => U) = self.valuesIterator foreach f } /** Creates an iterator for all values in this map. * * @return an iterator over all values that are associated with some key in this map. */ - def valuesIterator: Iterator[B] = new AbstractIterator[B] { + def valuesIterator: Iterator[V] = new AbstractIterator[V] { val iter = self.iterator def hasNext = iter.hasNext def next() = iter.next()._2 @@ -224,29 +228,33 @@ self => * @param key the given key value for which a binding is missing. * @throws NoSuchElementException */ - def default(key: A): B = + def default(key: K): V = throw new NoSuchElementException("key not found: " + key) - protected class FilteredKeys(p: A => Boolean) extends AbstractMap[A, B] with DefaultMap[A, B] { - override def foreach[U](f: ((A, B)) => U): Unit = for (kv <- self) if (p(kv._1)) f(kv) + protected class FilteredKeys(p: K => Boolean) extends AbstractMap[K, V] with DefaultMap[K, V] { + override def foreach[U](f: ((K, V)) => U): Unit = for (kv <- self) if (p(kv._1)) f(kv) def iterator = self.iterator.filter(kv => p(kv._1)) - override def contains(key: A) = self.contains(key) && p(key) - def get(key: A) = if (!p(key)) None else self.get(key) + override def contains(key: K) = p(key) && self.contains(key) + def get(key: K) = if (!p(key)) None else self.get(key) } /** Filters this map by retaining only keys satisfying a predicate. + * + * '''Note''': the predicate must accept any key of type `K`, not just those already + * present in the map, as the predicate is tested before the underlying map is queried. + * * @param p the predicate used to test keys * @return an immutable map consisting only of those key value pairs of this map where the key satisfies * the predicate `p`. The resulting map wraps the original map without copying any elements. */ - def filterKeys(p: A => Boolean): Map[A, B] = new FilteredKeys(p) + def filterKeys(p: K => Boolean): Map[K, V] = new FilteredKeys(p) - protected class MappedValues[C](f: B => C) extends AbstractMap[A, C] with DefaultMap[A, C] { - override def foreach[U](g: ((A, C)) => U): Unit = for ((k, v) <- self) g((k, f(v))) + protected class MappedValues[W](f: V => W) extends AbstractMap[K, W] with DefaultMap[K, W] { + override def foreach[U](g: ((K, W)) => U): Unit = for ((k, v) <- self) g((k, f(v))) def iterator = for ((k, v) <- self.iterator) yield (k, f(v)) override def size = self.size - override def contains(key: A) = self.contains(key) - def get(key: A) = self.get(key).map(f) + override def contains(key: K) = self.contains(key) + def get(key: K) = self.get(key).map(f) } /** Transforms this map by applying a function to every retrieved value. @@ -254,22 +262,22 @@ self => * @return a map view which maps every key of this map * to `f(this(key))`. The resulting map wraps the original map without copying any elements. */ - def mapValues[C](f: B => C): Map[A, C] = new MappedValues(f) + def mapValues[W](f: V => W): Map[K, W] = new MappedValues(f) // The following 5 operations (updated, two times +, two times ++) should really be - // generic, returning This[B]. We need better covariance support to express that though. + // generic, returning This[V]. We need better covariance support to express that though. // So right now we do the brute force approach of code duplication. /** Creates a new map obtained by updating this map with a given key/value pair. * @param key the key * @param value the value - * @tparam B1 the type of the added value + * @tparam V1 the type of the added value * @return A new map with the new key/value mapping added to this map. * - * @usecase def updated(key: A, value: B): Map[A, B] + * @usecase def updated(key: K, value: V): Map[K, V] * @inheritdoc */ - def updated [B1 >: B](key: A, value: B1): Map[A, B1] = this + ((key, value)) + def updated [V1 >: V](key: K, value: V1): Map[K, V1] = this + ((key, value)) /** Adds key/value pairs to this map, returning a new map. * @@ -279,27 +287,27 @@ self => * @param kv1 the first key/value pair * @param kv2 the second key/value pair * @param kvs the remaining key/value pairs - * @tparam B1 the type of the added values + * @tparam V1 the type of the added values * @return a new map with the given bindings added to this map * - * @usecase def + (kvs: (A, B)*): Map[A, B] + * @usecase def + (kvs: (K, V)*): Map[K, V] * @inheritdoc * @param kvs the key/value pairs */ - def + [B1 >: B] (kv1: (A, B1), kv2: (A, B1), kvs: (A, B1) *): Map[A, B1] = + def + [V1 >: V] (kv1: (K, V1), kv2: (K, V1), kvs: (K, V1) *): Map[K, V1] = this + kv1 + kv2 ++ kvs /** Adds all key/value pairs in a traversable collection to this map, returning a new map. * * @param xs the collection containing the added key/value pairs - * @tparam B1 the type of the added values + * @tparam V1 the type of the added values * @return a new map with the given bindings added to this map * - * @usecase def ++ (xs: Traversable[(A, B)]): Map[A, B] + * @usecase def ++ (xs: Traversable[(K, V)]): Map[K, V] * @inheritdoc */ - def ++[B1 >: B](xs: GenTraversableOnce[(A, B1)]): Map[A, B1] = - ((repr: Map[A, B1]) /: xs.seq) (_ + _) + def ++[V1 >: V](xs: GenTraversableOnce[(K, V1)]): Map[K, V1] = + ((repr: Map[K, V1]) /: xs.seq) (_ + _) /** Returns a new map obtained by removing all key/value pairs for which the predicate * `p` returns `true`. @@ -312,22 +320,31 @@ self => * @param p A predicate over key-value pairs * @return A new map containing elements not satisfying the predicate. */ - override def filterNot(p: ((A, B)) => Boolean): This = { + override def filterNot(p: ((K, V)) => Boolean): This = { var res: This = repr for (kv <- this) if (p(kv)) res = (res - kv._1).asInstanceOf[This] // !!! concrete overrides abstract problem res } - /* Overridden for efficiency. */ - override def toSeq: Seq[(A, B)] = toBuffer[(A, B)] - override def toBuffer[C >: (A, B)]: mutable.Buffer[C] = { - val result = new mutable.ArrayBuffer[C](size) - copyToBuffer(result) + override def toSeq: Seq[(K, V)] = { + if (isEmpty) Vector.empty[(K, V)] + else { + // Default appropriate for immutable collections; mutable collections override this + val vb = Vector.newBuilder[(K, V)] + foreach(vb += _) + vb.result + } + } + + override def toBuffer[E >: (K, V)]: mutable.Buffer[E] = { + val result = new mutable.ArrayBuffer[E](size) + // Faster to let the map iterate itself than to defer through copyToBuffer + foreach(result += _) result } - protected[this] override def parCombiner = ParMap.newCombiner[A, B] + protected[this] override def parCombiner = ParMap.newCombiner[K, V] /** Appends all bindings of this map to a string builder using start, end, and separator strings. * The written text begins with the string `start` and ends with the string |