| /* |
| * Copyright (C) 2008 The Guava Authors |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.google.common.collect; |
| |
| import static com.google.common.base.Preconditions.checkNotNull; |
| import static com.google.common.collect.CollectPreconditions.checkEntryNotNull; |
| |
| import com.google.common.annotations.GwtCompatible; |
| |
| import java.io.Serializable; |
| import java.util.Arrays; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.Iterator; |
| import java.util.LinkedHashMap; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.Map.Entry; |
| import java.util.Set; |
| |
| import javax.annotation.Nullable; |
| |
| /** |
| * An immutable {@link Multimap}. Does not permit null keys or values. |
| * |
| * <p>Unlike {@link Multimaps#unmodifiableMultimap(Multimap)}, which is |
| * a <i>view</i> of a separate multimap which can still change, an instance of |
| * {@code ImmutableMultimap} contains its own data and will <i>never</i> |
| * change. {@code ImmutableMultimap} is convenient for |
| * {@code public static final} multimaps ("constant multimaps") and also lets |
| * you easily make a "defensive copy" of a multimap provided to your class by |
| * a caller. |
| * |
| * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as |
| * it has no public or protected constructors. Thus, instances of this class |
| * are guaranteed to be immutable. |
| * |
| * <p>In addition to methods defined by {@link Multimap}, an {@link #inverse} |
| * method is also supported. |
| * |
| * <p>See the Guava User Guide article on <a href= |
| * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained"> |
| * immutable collections</a>. |
| * |
| * @author Jared Levy |
| * @since 2.0 (imported from Google Collections Library) |
| */ |
| @GwtCompatible(emulated = true) |
| public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> |
| implements Serializable { |
| |
| /** Returns an empty multimap. */ |
| public static <K, V> ImmutableMultimap<K, V> of() { |
| return ImmutableListMultimap.of(); |
| } |
| |
| /** |
| * Returns an immutable multimap containing a single entry. |
| */ |
| public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1) { |
| return ImmutableListMultimap.of(k1, v1); |
| } |
| |
| /** |
| * Returns an immutable multimap containing the given entries, in order. |
| */ |
| public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2) { |
| return ImmutableListMultimap.of(k1, v1, k2, v2); |
| } |
| |
| /** |
| * Returns an immutable multimap containing the given entries, in order. |
| */ |
| public static <K, V> ImmutableMultimap<K, V> of( |
| K k1, V v1, K k2, V v2, K k3, V v3) { |
| return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3); |
| } |
| |
| /** |
| * Returns an immutable multimap containing the given entries, in order. |
| */ |
| public static <K, V> ImmutableMultimap<K, V> of( |
| K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { |
| return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4); |
| } |
| |
| /** |
| * Returns an immutable multimap containing the given entries, in order. |
| */ |
| public static <K, V> ImmutableMultimap<K, V> of( |
| K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { |
| return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5); |
| } |
| |
| // looking for of() with > 5 entries? Use the builder instead. |
| |
| /** |
| * Returns a new builder. The generated builder is equivalent to the builder |
| * created by the {@link Builder} constructor. |
| */ |
| public static <K, V> Builder<K, V> builder() { |
| return new Builder<K, V>(); |
| } |
| |
| /** |
| * Multimap for {@link ImmutableMultimap.Builder} that maintains key and |
| * value orderings, allows duplicate values, and performs better than |
| * {@link LinkedListMultimap}. |
| */ |
| private static class BuilderMultimap<K, V> extends AbstractMapBasedMultimap<K, V> { |
| BuilderMultimap() { |
| super(new LinkedHashMap<K, Collection<V>>()); |
| } |
| @Override Collection<V> createCollection() { |
| return Lists.newArrayList(); |
| } |
| private static final long serialVersionUID = 0; |
| } |
| |
| /** |
| * A builder for creating immutable multimap instances, especially |
| * {@code public static final} multimaps ("constant multimaps"). Example: |
| * <pre> {@code |
| * |
| * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP = |
| * new ImmutableMultimap.Builder<String, Integer>() |
| * .put("one", 1) |
| * .putAll("several", 1, 2, 3) |
| * .putAll("many", 1, 2, 3, 4, 5) |
| * .build();}</pre> |
| * |
| * <p>Builder instances can be reused; it is safe to call {@link #build} multiple |
| * times to build multiple multimaps in series. Each multimap contains the |
| * key-value mappings in the previously created multimaps. |
| * |
| * @since 2.0 (imported from Google Collections Library) |
| */ |
| public static class Builder<K, V> { |
| Multimap<K, V> builderMultimap = new BuilderMultimap<K, V>(); |
| Comparator<? super K> keyComparator; |
| Comparator<? super V> valueComparator; |
| |
| /** |
| * Creates a new builder. The returned builder is equivalent to the builder |
| * generated by {@link ImmutableMultimap#builder}. |
| */ |
| public Builder() {} |
| |
| /** |
| * Adds a key-value mapping to the built multimap. |
| */ |
| public Builder<K, V> put(K key, V value) { |
| checkEntryNotNull(key, value); |
| builderMultimap.put(key, value); |
| return this; |
| } |
| |
| /** |
| * Adds an entry to the built multimap. |
| * |
| * @since 11.0 |
| */ |
| public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { |
| return put(entry.getKey(), entry.getValue()); |
| } |
| |
| /** |
| * Stores a collection of values with the same key in the built multimap. |
| * |
| * @throws NullPointerException if {@code key}, {@code values}, or any |
| * element in {@code values} is null. The builder is left in an invalid |
| * state. |
| */ |
| public Builder<K, V> putAll(K key, Iterable<? extends V> values) { |
| if (key == null) { |
| throw new NullPointerException( |
| "null key in entry: null=" + Iterables.toString(values)); |
| } |
| Collection<V> valueList = builderMultimap.get(key); |
| for (V value : values) { |
| checkEntryNotNull(key, value); |
| valueList.add(value); |
| } |
| return this; |
| } |
| |
| /** |
| * Stores an array of values with the same key in the built multimap. |
| * |
| * @throws NullPointerException if the key or any value is null. The builder |
| * is left in an invalid state. |
| */ |
| public Builder<K, V> putAll(K key, V... values) { |
| return putAll(key, Arrays.asList(values)); |
| } |
| |
| /** |
| * Stores another multimap's entries in the built multimap. The generated |
| * multimap's key and value orderings correspond to the iteration ordering |
| * of the {@code multimap.asMap()} view, with new keys and values following |
| * any existing keys and values. |
| * |
| * @throws NullPointerException if any key or value in {@code multimap} is |
| * null. The builder is left in an invalid state. |
| */ |
| public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) { |
| for (Entry<? extends K, ? extends Collection<? extends V>> entry |
| : multimap.asMap().entrySet()) { |
| putAll(entry.getKey(), entry.getValue()); |
| } |
| return this; |
| } |
| |
| /** |
| * Specifies the ordering of the generated multimap's keys. |
| * |
| * @since 8.0 |
| */ |
| public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) { |
| this.keyComparator = checkNotNull(keyComparator); |
| return this; |
| } |
| |
| /** |
| * Specifies the ordering of the generated multimap's values for each key. |
| * |
| * @since 8.0 |
| */ |
| public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) { |
| this.valueComparator = checkNotNull(valueComparator); |
| return this; |
| } |
| |
| /** |
| * Returns a newly-created immutable multimap. |
| */ |
| public ImmutableMultimap<K, V> build() { |
| if (valueComparator != null) { |
| for (Collection<V> values : builderMultimap.asMap().values()) { |
| List<V> list = (List <V>) values; |
| Collections.sort(list, valueComparator); |
| } |
| } |
| if (keyComparator != null) { |
| Multimap<K, V> sortedCopy = new BuilderMultimap<K, V>(); |
| List<Map.Entry<K, Collection<V>>> entries = Lists.newArrayList( |
| builderMultimap.asMap().entrySet()); |
| Collections.sort( |
| entries, |
| Ordering.from(keyComparator).<K>onKeys()); |
| for (Map.Entry<K, Collection<V>> entry : entries) { |
| sortedCopy.putAll(entry.getKey(), entry.getValue()); |
| } |
| builderMultimap = sortedCopy; |
| } |
| return copyOf(builderMultimap); |
| } |
| } |
| |
| /** |
| * Returns an immutable multimap containing the same mappings as {@code |
| * multimap}. The generated multimap's key and value orderings correspond to |
| * the iteration ordering of the {@code multimap.asMap()} view. |
| * |
| * <p>Despite the method name, this method attempts to avoid actually copying |
| * the data when it is safe to do so. The exact circumstances under which a |
| * copy will or will not be performed are undocumented and subject to change. |
| * |
| * @throws NullPointerException if any key or value in {@code multimap} is |
| * null |
| */ |
| public static <K, V> ImmutableMultimap<K, V> copyOf( |
| Multimap<? extends K, ? extends V> multimap) { |
| if (multimap instanceof ImmutableMultimap) { |
| @SuppressWarnings("unchecked") // safe since multimap is not writable |
| ImmutableMultimap<K, V> kvMultimap |
| = (ImmutableMultimap<K, V>) multimap; |
| if (!kvMultimap.isPartialView()) { |
| return kvMultimap; |
| } |
| } |
| return ImmutableListMultimap.copyOf(multimap); |
| } |
| |
| final transient ImmutableMap<K, ? extends ImmutableCollection<V>> map; |
| final transient int size; |
| |
| // These constants allow the deserialization code to set final fields. This |
| // holder class makes sure they are not initialized unless an instance is |
| // deserialized. |
| |
| ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map, |
| int size) { |
| this.map = map; |
| this.size = size; |
| } |
| |
| // mutators (not supported) |
| |
| /** |
| * Guaranteed to throw an exception and leave the multimap unmodified. |
| * |
| * @throws UnsupportedOperationException always |
| * @deprecated Unsupported operation. |
| */ |
| @Deprecated |
| @Override |
| public ImmutableCollection<V> removeAll(Object key) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Guaranteed to throw an exception and leave the multimap unmodified. |
| * |
| * @throws UnsupportedOperationException always |
| * @deprecated Unsupported operation. |
| */ |
| @Deprecated |
| @Override |
| public ImmutableCollection<V> replaceValues(K key, |
| Iterable<? extends V> values) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Guaranteed to throw an exception and leave the multimap unmodified. |
| * |
| * @throws UnsupportedOperationException always |
| * @deprecated Unsupported operation. |
| */ |
| @Deprecated |
| @Override |
| public void clear() { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Returns an immutable collection of the values for the given key. If no |
| * mappings in the multimap have the provided key, an empty immutable |
| * collection is returned. The values are in the same order as the parameters |
| * used to build this multimap. |
| */ |
| @Override |
| public abstract ImmutableCollection<V> get(K key); |
| |
| /** |
| * Returns an immutable multimap which is the inverse of this one. For every |
| * key-value mapping in the original, the result will have a mapping with |
| * key and value reversed. |
| * |
| * @since 11.0 |
| */ |
| public abstract ImmutableMultimap<V, K> inverse(); |
| |
| /** |
| * Guaranteed to throw an exception and leave the multimap unmodified. |
| * |
| * @throws UnsupportedOperationException always |
| * @deprecated Unsupported operation. |
| */ |
| @Deprecated |
| @Override |
| public boolean put(K key, V value) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Guaranteed to throw an exception and leave the multimap unmodified. |
| * |
| * @throws UnsupportedOperationException always |
| * @deprecated Unsupported operation. |
| */ |
| @Deprecated |
| @Override |
| public boolean putAll(K key, Iterable<? extends V> values) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Guaranteed to throw an exception and leave the multimap unmodified. |
| * |
| * @throws UnsupportedOperationException always |
| * @deprecated Unsupported operation. |
| */ |
| @Deprecated |
| @Override |
| public boolean putAll(Multimap<? extends K, ? extends V> multimap) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Guaranteed to throw an exception and leave the multimap unmodified. |
| * |
| * @throws UnsupportedOperationException always |
| * @deprecated Unsupported operation. |
| */ |
| @Deprecated |
| @Override |
| public boolean remove(Object key, Object value) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** |
| * Returns {@code true} if this immutable multimap's implementation contains references to |
| * user-created objects that aren't accessible via this multimap's methods. This is generally |
| * used to determine whether {@code copyOf} implementations should make an explicit copy to avoid |
| * memory leaks. |
| */ |
| boolean isPartialView() { |
| return map.isPartialView(); |
| } |
| |
| // accessors |
| |
| @Override |
| public boolean containsKey(@Nullable Object key) { |
| return map.containsKey(key); |
| } |
| |
| @Override |
| public boolean containsValue(@Nullable Object value) { |
| return value != null && super.containsValue(value); |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| // views |
| |
| /** |
| * Returns an immutable set of the distinct keys in this multimap. These keys |
| * are ordered according to when they first appeared during the construction |
| * of this multimap. |
| */ |
| @Override |
| public ImmutableSet<K> keySet() { |
| return map.keySet(); |
| } |
| |
| /** |
| * Returns an immutable map that associates each key with its corresponding |
| * values in the multimap. |
| */ |
| @Override |
| @SuppressWarnings("unchecked") // a widening cast |
| public ImmutableMap<K, Collection<V>> asMap() { |
| return (ImmutableMap) map; |
| } |
| |
| @Override |
| Map<K, Collection<V>> createAsMap() { |
| throw new AssertionError("should never be called"); |
| } |
| |
| /** |
| * Returns an immutable collection of all key-value pairs in the multimap. Its |
| * iterator traverses the values for the first key, the values for the second |
| * key, and so on. |
| */ |
| @Override |
| public ImmutableCollection<Entry<K, V>> entries() { |
| return (ImmutableCollection<Entry<K, V>>) super.entries(); |
| } |
| |
| @Override |
| ImmutableCollection<Entry<K, V>> createEntries() { |
| return new EntryCollection<K, V>(this); |
| } |
| |
| private static class EntryCollection<K, V> |
| extends ImmutableCollection<Entry<K, V>> { |
| final ImmutableMultimap<K, V> multimap; |
| |
| EntryCollection(ImmutableMultimap<K, V> multimap) { |
| this.multimap = multimap; |
| } |
| |
| @Override public UnmodifiableIterator<Entry<K, V>> iterator() { |
| return multimap.entryIterator(); |
| } |
| |
| @Override boolean isPartialView() { |
| return multimap.isPartialView(); |
| } |
| |
| @Override |
| public int size() { |
| return multimap.size(); |
| } |
| |
| @Override public boolean contains(Object object) { |
| if (object instanceof Entry) { |
| Entry<?, ?> entry = (Entry<?, ?>) object; |
| return multimap.containsEntry(entry.getKey(), entry.getValue()); |
| } |
| return false; |
| } |
| |
| private static final long serialVersionUID = 0; |
| } |
| |
| private abstract class Itr<T> extends UnmodifiableIterator<T> { |
| final Iterator<Entry<K, Collection<V>>> mapIterator = asMap().entrySet().iterator(); |
| K key = null; |
| Iterator<V> valueIterator = Iterators.emptyIterator(); |
| |
| abstract T output(K key, V value); |
| |
| @Override |
| public boolean hasNext() { |
| return mapIterator.hasNext() || valueIterator.hasNext(); |
| } |
| |
| @Override |
| public T next() { |
| if (!valueIterator.hasNext()) { |
| Entry<K, Collection<V>> mapEntry = mapIterator.next(); |
| key = mapEntry.getKey(); |
| valueIterator = mapEntry.getValue().iterator(); |
| } |
| return output(key, valueIterator.next()); |
| } |
| } |
| |
| @Override |
| UnmodifiableIterator<Entry<K, V>> entryIterator() { |
| return new Itr<Entry<K, V>>() { |
| @Override |
| Entry<K, V> output(K key, V value) { |
| return Maps.immutableEntry(key, value); |
| } |
| }; |
| } |
| |
| /** |
| * Returns a collection, which may contain duplicates, of all keys. The number |
| * of times a key appears in the returned multiset equals the number of |
| * mappings the key has in the multimap. Duplicate keys appear consecutively |
| * in the multiset's iteration order. |
| */ |
| @Override |
| public ImmutableMultiset<K> keys() { |
| return (ImmutableMultiset<K>) super.keys(); |
| } |
| |
| @Override |
| ImmutableMultiset<K> createKeys() { |
| return new Keys(); |
| } |
| |
| @SuppressWarnings("serial") // Uses writeReplace, not default serialization |
| class Keys extends ImmutableMultiset<K> { |
| @Override |
| public boolean contains(@Nullable Object object) { |
| return containsKey(object); |
| } |
| |
| @Override |
| public int count(@Nullable Object element) { |
| Collection<V> values = map.get(element); |
| return (values == null) ? 0 : values.size(); |
| } |
| |
| @Override |
| public Set<K> elementSet() { |
| return keySet(); |
| } |
| |
| @Override |
| public int size() { |
| return ImmutableMultimap.this.size(); |
| } |
| |
| @Override |
| Multiset.Entry<K> getEntry(int index) { |
| Map.Entry<K, ? extends Collection<V>> entry = map.entrySet().asList().get(index); |
| return Multisets.immutableEntry(entry.getKey(), entry.getValue().size()); |
| } |
| |
| @Override |
| boolean isPartialView() { |
| return true; |
| } |
| } |
| |
| /** |
| * Returns an immutable collection of the values in this multimap. Its |
| * iterator traverses the values for the first key, the values for the second |
| * key, and so on. |
| */ |
| @Override |
| public ImmutableCollection<V> values() { |
| return (ImmutableCollection<V>) super.values(); |
| } |
| |
| @Override |
| ImmutableCollection<V> createValues() { |
| return new Values<K, V>(this); |
| } |
| |
| @Override |
| UnmodifiableIterator<V> valueIterator() { |
| return new Itr<V>() { |
| @Override |
| V output(K key, V value) { |
| return value; |
| } |
| }; |
| } |
| |
| private static final class Values<K, V> extends ImmutableCollection<V> { |
| private transient final ImmutableMultimap<K, V> multimap; |
| |
| Values(ImmutableMultimap<K, V> multimap) { |
| this.multimap = multimap; |
| } |
| |
| @Override |
| public boolean contains(@Nullable Object object) { |
| return multimap.containsValue(object); |
| } |
| |
| @Override public UnmodifiableIterator<V> iterator() { |
| return multimap.valueIterator(); |
| } |
| |
| @Override |
| public int size() { |
| return multimap.size(); |
| } |
| |
| @Override boolean isPartialView() { |
| return true; |
| } |
| |
| private static final long serialVersionUID = 0; |
| } |
| |
| private static final long serialVersionUID = 0; |
| } |
| |