diff options
Diffstat (limited to 'guava/src/com/google/common/collect/ImmutableMultimap.java')
| -rw-r--r-- | guava/src/com/google/common/collect/ImmutableMultimap.java | 279 |
1 files changed, 121 insertions, 158 deletions
diff --git a/guava/src/com/google/common/collect/ImmutableMultimap.java b/guava/src/com/google/common/collect/ImmutableMultimap.java index e29dbc1..13e213e 100644 --- a/guava/src/com/google/common/collect/ImmutableMultimap.java +++ b/guava/src/com/google/common/collect/ImmutableMultimap.java @@ -18,9 +18,9 @@ package com.google.common.collect; import static com.google.common.base.Preconditions.checkNotNull; +import com.google.common.annotations.Beta; import com.google.common.annotations.GwtCompatible; import com.google.common.annotations.GwtIncompatible; -import com.google.common.base.Function; import java.io.Serializable; import java.util.Arrays; @@ -30,9 +30,8 @@ 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 java.util.TreeMap; import javax.annotation.Nullable; @@ -54,16 +53,13 @@ import javax.annotation.Nullable; * <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 { +// TODO(user): If BiMultimap graduates from labs, this class should implement it. +public abstract class ImmutableMultimap<K, V> + implements Multimap<K, V>, Serializable { /** Returns an empty multimap. */ public static <K, V> ImmutableMultimap<K, V> of() { @@ -123,7 +119,7 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> * value orderings, allows duplicate values, and performs better than * {@link LinkedListMultimap}. */ - private static class BuilderMultimap<K, V> extends AbstractMapBasedMultimap<K, V> { + private static class BuilderMultimap<K, V> extends AbstractMultimap<K, V> { BuilderMultimap() { super(new LinkedHashMap<K, Collection<V>>()); } @@ -134,6 +130,23 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> } /** + * Multimap for {@link ImmutableMultimap.Builder} that sorts key and allows + * duplicate values, + */ + private static class SortedKeyBuilderMultimap<K, V> + extends AbstractMultimap<K, V> { + SortedKeyBuilderMultimap( + Comparator<? super K> keyComparator, Multimap<K, V> multimap) { + super(new TreeMap<K, Collection<V>>(keyComparator)); + putAll(multimap); + } + @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 @@ -153,7 +166,6 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> */ public static class Builder<K, V> { Multimap<K, V> builderMultimap = new BuilderMultimap<K, V>(); - Comparator<? super K> keyComparator; Comparator<? super V> valueComparator; /** @@ -228,8 +240,10 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> * * @since 8.0 */ + @Beta public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) { - this.keyComparator = checkNotNull(keyComparator); + builderMultimap = new SortedKeyBuilderMultimap<K, V>( + checkNotNull(keyComparator), builderMultimap); return this; } @@ -238,6 +252,7 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> * * @since 8.0 */ + @Beta public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) { this.valueComparator = checkNotNull(valueComparator); return this; @@ -253,23 +268,6 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> 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).onResultOf(new Function<Entry<K, Collection<V>>, K>() { - @Override - public K apply(Entry<K, Collection<V>> entry) { - return entry.getKey(); - } - })); - for (Map.Entry<K, Collection<V>> entry : entries) { - sortedCopy.putAll(entry.getKey(), entry.getValue()); - } - builderMultimap = sortedCopy; - } return copyOf(builderMultimap); } } @@ -327,9 +325,7 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> * 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(); @@ -339,9 +335,7 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> * 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) { @@ -352,9 +346,7 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> * Guaranteed to throw an exception and leave the multimap unmodified. * * @throws UnsupportedOperationException always - * @deprecated Unsupported operation. */ - @Deprecated @Override public void clear() { throw new UnsupportedOperationException(); @@ -374,17 +366,16 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> * key-value mapping in the original, the result will have a mapping with * key and value reversed. * - * @since 11.0 + * @since 11 */ + @Beta 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(); @@ -394,9 +385,7 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> * 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(); @@ -406,9 +395,7 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> * 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(); @@ -418,30 +405,65 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> * 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(); } - boolean isPartialView() { + boolean isPartialView(){ return map.isPartialView(); } // accessors @Override + public boolean containsEntry(@Nullable Object key, @Nullable Object value) { + Collection<V> values = map.get(key); + return values != null && values.contains(value); + } + + @Override public boolean containsKey(@Nullable Object key) { return map.containsKey(key); } @Override + public boolean containsValue(@Nullable Object value) { + for (Collection<V> valueCollection : map.values()) { + if (valueCollection.contains(value)) { + return true; + } + } + return false; + } + + @Override + public boolean isEmpty() { + return size == 0; + } + + @Override public int size() { return size; } + @Override public boolean equals(@Nullable Object object) { + if (object instanceof Multimap) { + Multimap<?, ?> that = (Multimap<?, ?>) object; + return this.map.equals(that.asMap()); + } + return false; + } + + @Override public int hashCode() { + return map.hashCode(); + } + + @Override public String toString() { + return map.toString(); + } + // views /** @@ -463,11 +485,8 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> public ImmutableMap<K, Collection<V>> asMap() { return (ImmutableMap) map; } - - @Override - Map<K, Collection<V>> createAsMap() { - throw new AssertionError("should never be called"); - } + + private transient ImmutableCollection<Entry<K, V>> entries; /** * Returns an immutable collection of all key-value pairs in the multimap. Its @@ -476,12 +495,9 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> */ @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); + ImmutableCollection<Entry<K, V>> result = entries; + return (result == null) + ? (entries = new EntryCollection<K, V>(this)) : result; } private static class EntryCollection<K, V> @@ -493,7 +509,30 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> } @Override public UnmodifiableIterator<Entry<K, V>> iterator() { - return multimap.entryIterator(); + final Iterator<? extends Entry<K, ? extends ImmutableCollection<V>>> + mapIterator = this.multimap.map.entrySet().iterator(); + + return new UnmodifiableIterator<Entry<K, V>>() { + K key; + Iterator<V> valueIterator; + + @Override + public boolean hasNext() { + return (key != null && valueIterator.hasNext()) + || mapIterator.hasNext(); + } + + @Override + public Entry<K, V> next() { + if (key == null || !valueIterator.hasNext()) { + Entry<K, ? extends ImmutableCollection<V>> entry + = mapIterator.next(); + key = entry.getKey(); + valueIterator = entry.getValue().iterator(); + } + return Maps.immutableEntry(key, valueIterator.next()); + } + }; } @Override boolean isPartialView() { @@ -515,34 +554,8 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> private static final long serialVersionUID = 0; } - - @Override - UnmodifiableIterator<Entry<K, V>> entryIterator() { - final Iterator<? extends Entry<K, ? extends ImmutableCollection<V>>> - mapIterator = map.entrySet().iterator(); - - return new UnmodifiableIterator<Entry<K, V>>() { - K key; - Iterator<V> valueIterator; - - @Override - public boolean hasNext() { - return (key != null && valueIterator.hasNext()) - || mapIterator.hasNext(); - } - @Override - public Entry<K, V> next() { - if (key == null || !valueIterator.hasNext()) { - Entry<K, ? extends ImmutableCollection<V>> entry - = mapIterator.next(); - key = entry.getKey(); - valueIterator = entry.getValue().iterator(); - } - return Maps.immutableEntry(key, valueIterator.next()); - } - }; - } + private transient ImmutableMultiset<K> keys; /** * Returns a collection, which may contain duplicates, of all keys. The number @@ -552,78 +565,21 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> */ @Override public ImmutableMultiset<K> keys() { - return (ImmutableMultiset<K>) super.keys(); + ImmutableMultiset<K> result = keys; + return (result == null) ? (keys = createKeys()) : result; } - @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 - ImmutableSet<Entry<K>> createEntrySet() { - return new KeysEntrySet(); - } - - private class KeysEntrySet extends ImmutableMultiset<K>.EntrySet { - @Override - public int size() { - return keySet().size(); - } - - @Override - public UnmodifiableIterator<Entry<K>> iterator() { - return asList().iterator(); - } - - @Override - ImmutableList<Entry<K>> createAsList() { - final ImmutableList<? extends Map.Entry<K, ? extends Collection<V>>> mapEntries = - map.entrySet().asList(); - return new ImmutableAsList<Entry<K>>() { - @Override - public Entry<K> get(int index) { - Map.Entry<K, ? extends Collection<V>> entry = mapEntries.get(index); - return Multisets.immutableEntry(entry.getKey(), entry.getValue().size()); - } - - @Override - ImmutableCollection<Entry<K>> delegateCollection() { - return KeysEntrySet.this; - } - }; - } - } - - @Override - boolean isPartialView() { - return true; + private ImmutableMultiset<K> createKeys() { + ImmutableMultiset.Builder<K> builder = ImmutableMultiset.builder(); + for (Entry<K, ? extends ImmutableCollection<V>> entry + : map.entrySet()) { + builder.addCopies(entry.getKey(), entry.getValue().size()); } + return builder.build(); } + private transient ImmutableCollection<V> values; + /** * Returns an immutable collection of the values in this multimap. Its * iterator traverses the values for the first key, the values for the second @@ -631,12 +587,8 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> */ @Override public ImmutableCollection<V> values() { - return (ImmutableCollection<V>) super.values(); - } - - @Override - ImmutableCollection<V> createValues() { - return new Values<V>(this); + ImmutableCollection<V> result = values; + return (result == null) ? (values = new Values<V>(this)) : result; } private static class Values<V> extends ImmutableCollection<V> { @@ -647,7 +599,18 @@ public abstract class ImmutableMultimap<K, V> extends AbstractMultimap<K, V> } @Override public UnmodifiableIterator<V> iterator() { - return Maps.valueIterator(multimap.entries().iterator()); + final Iterator<? extends Entry<?, V>> entryIterator + = multimap.entries().iterator(); + return new UnmodifiableIterator<V>() { + @Override + public boolean hasNext() { + return entryIterator.hasNext(); + } + @Override + public V next() { + return entryIterator.next().getValue(); + } + }; } @Override |