diff options
Diffstat (limited to 'guava/src/com/google/common/collect/AbstractMultimap.java')
| -rw-r--r-- | guava/src/com/google/common/collect/AbstractMultimap.java | 1318 |
1 files changed, 1244 insertions, 74 deletions
diff --git a/guava/src/com/google/common/collect/AbstractMultimap.java b/guava/src/com/google/common/collect/AbstractMultimap.java index 13fdd00..38f69ec 100644 --- a/guava/src/com/google/common/collect/AbstractMultimap.java +++ b/guava/src/com/google/common/collect/AbstractMultimap.java @@ -1,5 +1,5 @@ /* - * Copyright (C) 2012 The Guava Authors + * Copyright (C) 2007 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. @@ -16,33 +16,170 @@ package com.google.common.collect; +import static com.google.common.base.Preconditions.checkArgument; import static com.google.common.base.Preconditions.checkNotNull; +import static com.google.common.base.Preconditions.checkState; import com.google.common.annotations.GwtCompatible; +import java.io.Serializable; +import java.util.AbstractCollection; +import java.util.AbstractMap; import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.ConcurrentModificationException; import java.util.Iterator; +import java.util.List; +import java.util.ListIterator; import java.util.Map; import java.util.Map.Entry; +import java.util.RandomAccess; import java.util.Set; +import java.util.SortedMap; +import java.util.SortedSet; import javax.annotation.Nullable; /** - * A skeleton {@code Multimap} implementation, not necessarily in terms of a {@code Map}. - * + * Basic implementation of the {@link Multimap} interface. This class represents + * a multimap as a map that associates each key with a collection of values. All + * methods of {@link Multimap} are supported, including those specified as + * optional in the interface. + * + * <p>To implement a multimap, a subclass must define the method {@link + * #createCollection()}, which creates an empty collection of values for a key. + * + * <p>The multimap constructor takes a map that has a single entry for each + * distinct key. When you insert a key-value pair with a key that isn't already + * in the multimap, {@code AbstractMultimap} calls {@link #createCollection()} + * to create the collection of values for that key. The subclass should not call + * {@link #createCollection()} directly, and a new instance should be created + * every time the method is called. + * + * <p>For example, the subclass could pass a {@link java.util.TreeMap} during + * construction, and {@link #createCollection()} could return a {@link + * java.util.TreeSet}, in which case the multimap's iterators would propagate + * through the keys and values in sorted order. + * + * <p>Keys and values may be null, as long as the underlying collection classes + * support null elements. + * + * <p>The collections created by {@link #createCollection()} may or may not + * allow duplicates. If the collection, such as a {@link Set}, does not support + * duplicates, an added key-value pair will replace an existing pair with the + * same key and value, if such a pair is present. With collections like {@link + * List} that allow duplicates, the collection will keep the existing key-value + * pairs while adding a new pair. + * + * <p>This class is not threadsafe when any concurrent operations update the + * multimap, even if the underlying map and {@link #createCollection()} method + * return threadsafe classes. Concurrent read operations will work correctly. To + * allow concurrent update operations, wrap your multimap with a call to {@link + * Multimaps#synchronizedMultimap}. + * + * <p>For serialization to work, the subclass must specify explicit + * {@code readObject} and {@code writeObject} methods. + * + * @author Jared Levy * @author Louis Wasserman */ @GwtCompatible -abstract class AbstractMultimap<K, V> implements Multimap<K, V> { +abstract class AbstractMultimap<K, V> implements Multimap<K, V>, Serializable { + /* + * Here's an outline of the overall design. + * + * The map variable contains the collection of values associated with each + * key. When a key-value pair is added to a multimap that didn't previously + * contain any values for that key, a new collection generated by + * createCollection is added to the map. That same collection instance + * remains in the map as long as the multimap has any values for the key. If + * all values for the key are removed, the key and collection are removed + * from the map. + * + * The get method returns a WrappedCollection, which decorates the collection + * in the map (if the key is present) or an empty collection (if the key is + * not present). When the collection delegate in the WrappedCollection is + * empty, the multimap may contain subsequently added values for that key. To + * handle that situation, the WrappedCollection checks whether map contains + * an entry for the provided key, and if so replaces the delegate. + */ + + private transient Map<K, Collection<V>> map; + private transient int totalSize; + + /** + * Creates a new multimap that uses the provided map. + * + * @param map place to store the mapping from each key to its corresponding + * values + * @throws IllegalArgumentException if {@code map} is not empty + */ + protected AbstractMultimap(Map<K, Collection<V>> map) { + checkArgument(map.isEmpty()); + this.map = map; + } + + /** Used during deserialization only. */ + final void setMap(Map<K, Collection<V>> map) { + this.map = map; + totalSize = 0; + for (Collection<V> values : map.values()) { + checkArgument(!values.isEmpty()); + totalSize += values.size(); + } + } + + /** + * Creates the collection of values for a single key. + * + * <p>Collections with weak, soft, or phantom references are not supported. + * Each call to {@code createCollection} should create a new instance. + * + * <p>The returned collection class determines whether duplicate key-value + * pairs are allowed. + * + * @return an empty collection of values + */ + abstract Collection<V> createCollection(); + + /** + * Creates the collection of values for an explicitly provided key. By + * default, it simply calls {@link #createCollection()}, which is the correct + * behavior for most implementations. The {@link LinkedHashMultimap} class + * overrides it. + * + * @param key key to associate with values in the collection + * @return an empty collection of values + */ + Collection<V> createCollection(@Nullable K key) { + return createCollection(); + } + + Map<K, Collection<V>> backingMap() { + return map; + } + + // Query Operations + + @Override + public int size() { + return totalSize; + } + @Override public boolean isEmpty() { - return size() == 0; + return totalSize == 0; + } + + @Override + public boolean containsKey(@Nullable Object key) { + return map.containsKey(key); } @Override public boolean containsValue(@Nullable Object value) { - for (Collection<V> collection : asMap().values()) { + for (Collection<V> collection : map.values()) { if (collection.contains(value)) { return true; } @@ -53,25 +190,72 @@ abstract class AbstractMultimap<K, V> implements Multimap<K, V> { @Override public boolean containsEntry(@Nullable Object key, @Nullable Object value) { - Collection<V> collection = asMap().get(key); + Collection<V> collection = map.get(key); return collection != null && collection.contains(value); } - + + // Modification Operations + @Override - public boolean remove(@Nullable Object key, @Nullable Object value) { - Collection<V> collection = asMap().get(key); - return collection != null && collection.remove(value); + public boolean put(@Nullable K key, @Nullable V value) { + Collection<V> collection = getOrCreateCollection(key); + + if (collection.add(value)) { + totalSize++; + return true; + } else { + return false; + } + } + + private Collection<V> getOrCreateCollection(@Nullable K key) { + Collection<V> collection = map.get(key); + if (collection == null) { + collection = createCollection(key); + map.put(key, collection); + } + return collection; } @Override - public boolean put(@Nullable K key, @Nullable V value) { - return get(key).add(value); + public boolean remove(@Nullable Object key, @Nullable Object value) { + Collection<V> collection = map.get(key); + if (collection == null) { + return false; + } + + boolean changed = collection.remove(value); + if (changed) { + totalSize--; + if (collection.isEmpty()) { + map.remove(key); + } + } + return changed; } + // Bulk Operations + @Override public boolean putAll(@Nullable K key, Iterable<? extends V> values) { - checkNotNull(values); - return values.iterator().hasNext() && Iterables.addAll(get(key), values); + if (!values.iterator().hasNext()) { + return false; + } + Collection<V> collection = getOrCreateCollection(key); + int oldSize = collection.size(); + + boolean changed = false; + if (values instanceof Collection) { + Collection<? extends V> c = Collections2.cast(values); + changed = collection.addAll(c); + } else { + for (V value : values) { + changed |= collection.add(value); + } + } + + totalSize += (collection.size() - oldSize); + return changed; } @Override @@ -83,50 +267,597 @@ abstract class AbstractMultimap<K, V> implements Multimap<K, V> { return changed; } + /** + * {@inheritDoc} + * + * <p>The returned collection is immutable. + */ @Override - public Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values) { - checkNotNull(values); - Collection<V> result = removeAll(key); - putAll(key, values); - return result; + public Collection<V> replaceValues( + @Nullable K key, Iterable<? extends V> values) { + Iterator<? extends V> iterator = values.iterator(); + if (!iterator.hasNext()) { + return removeAll(key); + } + + Collection<V> collection = getOrCreateCollection(key); + Collection<V> oldValues = createCollection(); + oldValues.addAll(collection); + + totalSize -= collection.size(); + collection.clear(); + + while (iterator.hasNext()) { + if (collection.add(iterator.next())) { + totalSize++; + } + } + + return unmodifiableCollectionSubclass(oldValues); } - - private transient Collection<Entry<K, V>> entries; + /** + * {@inheritDoc} + * + * <p>The returned collection is immutable. + */ @Override - public Collection<Entry<K, V>> entries() { - Collection<Entry<K, V>> result = entries; - return (result == null) ? entries = createEntries() : result; + public Collection<V> removeAll(@Nullable Object key) { + Collection<V> collection = map.remove(key); + Collection<V> output = createCollection(); + + if (collection != null) { + output.addAll(collection); + totalSize -= collection.size(); + collection.clear(); + } + + return unmodifiableCollectionSubclass(output); } - - Collection<Entry<K, V>> createEntries() { - if (this instanceof SetMultimap) { - return new Multimaps.EntrySet<K, V>() { - @Override - Multimap<K, V> multimap() { - return AbstractMultimap.this; + + private Collection<V> unmodifiableCollectionSubclass( + Collection<V> collection) { + if (collection instanceof SortedSet) { + return Collections.unmodifiableSortedSet((SortedSet<V>) collection); + } else if (collection instanceof Set) { + return Collections.unmodifiableSet((Set<V>) collection); + } else if (collection instanceof List) { + return Collections.unmodifiableList((List<V>) collection); + } else { + return Collections.unmodifiableCollection(collection); + } + } + + @Override + public void clear() { + // Clear each collection, to make previously returned collections empty. + for (Collection<V> collection : map.values()) { + collection.clear(); + } + map.clear(); + totalSize = 0; + } + + // Views + + /** + * {@inheritDoc} + * + * <p>The returned collection is not serializable. + */ + @Override + public Collection<V> get(@Nullable K key) { + Collection<V> collection = map.get(key); + if (collection == null) { + collection = createCollection(key); + } + return wrapCollection(key, collection); + } + + /** + * Generates a decorated collection that remains consistent with the values in + * the multimap for the provided key. Changes to the multimap may alter the + * returned collection, and vice versa. + */ + private Collection<V> wrapCollection( + @Nullable K key, Collection<V> collection) { + if (collection instanceof SortedSet) { + return new WrappedSortedSet(key, (SortedSet<V>) collection, null); + } else if (collection instanceof Set) { + return new WrappedSet(key, (Set<V>) collection); + } else if (collection instanceof List) { + return wrapList(key, (List<V>) collection, null); + } else { + return new WrappedCollection(key, collection, null); + } + } + + private List<V> wrapList( + @Nullable K key, List<V> list, @Nullable WrappedCollection ancestor) { + return (list instanceof RandomAccess) + ? new RandomAccessWrappedList(key, list, ancestor) + : new WrappedList(key, list, ancestor); + } + + /** + * Collection decorator that stays in sync with the multimap values for a key. + * There are two kinds of wrapped collections: full and subcollections. Both + * have a delegate pointing to the underlying collection class. + * + * <p>Full collections, identified by a null ancestor field, contain all + * multimap values for a given key. Its delegate is a value in {@link + * AbstractMultimap#map} whenever the delegate is non-empty. The {@code + * refreshIfEmpty}, {@code removeIfEmpty}, and {@code addToMap} methods ensure + * that the {@code WrappedCollection} and map remain consistent. + * + * <p>A subcollection, such as a sublist, contains some of the values for a + * given key. Its ancestor field points to the full wrapped collection with + * all values for the key. The subcollection {@code refreshIfEmpty}, {@code + * removeIfEmpty}, and {@code addToMap} methods call the corresponding methods + * of the full wrapped collection. + */ + private class WrappedCollection extends AbstractCollection<V> { + final K key; + Collection<V> delegate; + final WrappedCollection ancestor; + final Collection<V> ancestorDelegate; + + WrappedCollection(@Nullable K key, Collection<V> delegate, + @Nullable WrappedCollection ancestor) { + this.key = key; + this.delegate = delegate; + this.ancestor = ancestor; + this.ancestorDelegate + = (ancestor == null) ? null : ancestor.getDelegate(); + } + + /** + * If the delegate collection is empty, but the multimap has values for the + * key, replace the delegate with the new collection for the key. + * + * <p>For a subcollection, refresh its ancestor and validate that the + * ancestor delegate hasn't changed. + */ + void refreshIfEmpty() { + if (ancestor != null) { + ancestor.refreshIfEmpty(); + if (ancestor.getDelegate() != ancestorDelegate) { + throw new ConcurrentModificationException(); } + } else if (delegate.isEmpty()) { + Collection<V> newDelegate = map.get(key); + if (newDelegate != null) { + delegate = newDelegate; + } + } + } - @Override - public Iterator<Entry<K, V>> iterator() { - return entryIterator(); + /** + * If collection is empty, remove it from {@code AbstractMultimap.this.map}. + * For subcollections, check whether the ancestor collection is empty. + */ + void removeIfEmpty() { + if (ancestor != null) { + ancestor.removeIfEmpty(); + } else if (delegate.isEmpty()) { + map.remove(key); + } + } + + K getKey() { + return key; + } + + /** + * Add the delegate to the map. Other {@code WrappedCollection} methods + * should call this method after adding elements to a previously empty + * collection. + * + * <p>Subcollection add the ancestor's delegate instead. + */ + void addToMap() { + if (ancestor != null) { + ancestor.addToMap(); + } else { + map.put(key, delegate); + } + } + + @Override public int size() { + refreshIfEmpty(); + return delegate.size(); + } + + @Override public boolean equals(@Nullable Object object) { + if (object == this) { + return true; + } + refreshIfEmpty(); + return delegate.equals(object); + } + + @Override public int hashCode() { + refreshIfEmpty(); + return delegate.hashCode(); + } + + @Override public String toString() { + refreshIfEmpty(); + return delegate.toString(); + } + + Collection<V> getDelegate() { + return delegate; + } + + @Override public Iterator<V> iterator() { + refreshIfEmpty(); + return new WrappedIterator(); + } + + /** Collection iterator for {@code WrappedCollection}. */ + class WrappedIterator implements Iterator<V> { + final Iterator<V> delegateIterator; + final Collection<V> originalDelegate = delegate; + + WrappedIterator() { + delegateIterator = iteratorOrListIterator(delegate); + } + + WrappedIterator(Iterator<V> delegateIterator) { + this.delegateIterator = delegateIterator; + } + + /** + * If the delegate changed since the iterator was created, the iterator is + * no longer valid. + */ + void validateIterator() { + refreshIfEmpty(); + if (delegate != originalDelegate) { + throw new ConcurrentModificationException(); } - }; + } + + @Override + public boolean hasNext() { + validateIterator(); + return delegateIterator.hasNext(); + } + + @Override + public V next() { + validateIterator(); + return delegateIterator.next(); + } + + @Override + public void remove() { + delegateIterator.remove(); + totalSize--; + removeIfEmpty(); + } + + Iterator<V> getDelegateIterator() { + validateIterator(); + return delegateIterator; + } } - return new Multimaps.Entries<K, V>() { + + @Override public boolean add(V value) { + refreshIfEmpty(); + boolean wasEmpty = delegate.isEmpty(); + boolean changed = delegate.add(value); + if (changed) { + totalSize++; + if (wasEmpty) { + addToMap(); + } + } + return changed; + } + + WrappedCollection getAncestor() { + return ancestor; + } + + // The following methods are provided for better performance. + + @Override public boolean addAll(Collection<? extends V> collection) { + if (collection.isEmpty()) { + return false; + } + int oldSize = size(); // calls refreshIfEmpty + boolean changed = delegate.addAll(collection); + if (changed) { + int newSize = delegate.size(); + totalSize += (newSize - oldSize); + if (oldSize == 0) { + addToMap(); + } + } + return changed; + } + + @Override public boolean contains(Object o) { + refreshIfEmpty(); + return delegate.contains(o); + } + + @Override public boolean containsAll(Collection<?> c) { + refreshIfEmpty(); + return delegate.containsAll(c); + } + + @Override public void clear() { + int oldSize = size(); // calls refreshIfEmpty + if (oldSize == 0) { + return; + } + delegate.clear(); + totalSize -= oldSize; + removeIfEmpty(); // maybe shouldn't be removed if this is a sublist + } + + @Override public boolean remove(Object o) { + refreshIfEmpty(); + boolean changed = delegate.remove(o); + if (changed) { + totalSize--; + removeIfEmpty(); + } + return changed; + } + + @Override public boolean removeAll(Collection<?> c) { + if (c.isEmpty()) { + return false; + } + int oldSize = size(); // calls refreshIfEmpty + boolean changed = delegate.removeAll(c); + if (changed) { + int newSize = delegate.size(); + totalSize += (newSize - oldSize); + removeIfEmpty(); + } + return changed; + } + + @Override public boolean retainAll(Collection<?> c) { + checkNotNull(c); + int oldSize = size(); // calls refreshIfEmpty + boolean changed = delegate.retainAll(c); + if (changed) { + int newSize = delegate.size(); + totalSize += (newSize - oldSize); + removeIfEmpty(); + } + return changed; + } + } + + private Iterator<V> iteratorOrListIterator(Collection<V> collection) { + return (collection instanceof List) + ? ((List<V>) collection).listIterator() + : collection.iterator(); + } + + /** Set decorator that stays in sync with the multimap values for a key. */ + private class WrappedSet extends WrappedCollection implements Set<V> { + WrappedSet(@Nullable K key, Set<V> delegate) { + super(key, delegate, null); + } + } + + /** + * SortedSet decorator that stays in sync with the multimap values for a key. + */ + private class WrappedSortedSet extends WrappedCollection + implements SortedSet<V> { + WrappedSortedSet(@Nullable K key, SortedSet<V> delegate, + @Nullable WrappedCollection ancestor) { + super(key, delegate, ancestor); + } + + SortedSet<V> getSortedSetDelegate() { + return (SortedSet<V>) getDelegate(); + } + + @Override + public Comparator<? super V> comparator() { + return getSortedSetDelegate().comparator(); + } + + @Override + public V first() { + refreshIfEmpty(); + return getSortedSetDelegate().first(); + } + + @Override + public V last() { + refreshIfEmpty(); + return getSortedSetDelegate().last(); + } + + @Override + public SortedSet<V> headSet(V toElement) { + refreshIfEmpty(); + return new WrappedSortedSet( + getKey(), getSortedSetDelegate().headSet(toElement), + (getAncestor() == null) ? this : getAncestor()); + } + + @Override + public SortedSet<V> subSet(V fromElement, V toElement) { + refreshIfEmpty(); + return new WrappedSortedSet( + getKey(), getSortedSetDelegate().subSet(fromElement, toElement), + (getAncestor() == null) ? this : getAncestor()); + } + + @Override + public SortedSet<V> tailSet(V fromElement) { + refreshIfEmpty(); + return new WrappedSortedSet( + getKey(), getSortedSetDelegate().tailSet(fromElement), + (getAncestor() == null) ? this : getAncestor()); + } + } + + /** List decorator that stays in sync with the multimap values for a key. */ + private class WrappedList extends WrappedCollection implements List<V> { + WrappedList(@Nullable K key, List<V> delegate, + @Nullable WrappedCollection ancestor) { + super(key, delegate, ancestor); + } + + List<V> getListDelegate() { + return (List<V>) getDelegate(); + } + + @Override + public boolean addAll(int index, Collection<? extends V> c) { + if (c.isEmpty()) { + return false; + } + int oldSize = size(); // calls refreshIfEmpty + boolean changed = getListDelegate().addAll(index, c); + if (changed) { + int newSize = getDelegate().size(); + totalSize += (newSize - oldSize); + if (oldSize == 0) { + addToMap(); + } + } + return changed; + } + + @Override + public V get(int index) { + refreshIfEmpty(); + return getListDelegate().get(index); + } + + @Override + public V set(int index, V element) { + refreshIfEmpty(); + return getListDelegate().set(index, element); + } + + @Override + public void add(int index, V element) { + refreshIfEmpty(); + boolean wasEmpty = getDelegate().isEmpty(); + getListDelegate().add(index, element); + totalSize++; + if (wasEmpty) { + addToMap(); + } + } + + @Override + public V remove(int index) { + refreshIfEmpty(); + V value = getListDelegate().remove(index); + totalSize--; + removeIfEmpty(); + return value; + } + + @Override + public int indexOf(Object o) { + refreshIfEmpty(); + return getListDelegate().indexOf(o); + } + + @Override + public int lastIndexOf(Object o) { + refreshIfEmpty(); + return getListDelegate().lastIndexOf(o); + } + + @Override + public ListIterator<V> listIterator() { + refreshIfEmpty(); + return new WrappedListIterator(); + } + + @Override + public ListIterator<V> listIterator(int index) { + refreshIfEmpty(); + return new WrappedListIterator(index); + } + + @Override + public List<V> subList(int fromIndex, int toIndex) { + refreshIfEmpty(); + return wrapList(getKey(), + getListDelegate().subList(fromIndex, toIndex), + (getAncestor() == null) ? this : getAncestor()); + } + + /** ListIterator decorator. */ + private class WrappedListIterator extends WrappedIterator + implements ListIterator<V> { + WrappedListIterator() {} + + public WrappedListIterator(int index) { + super(getListDelegate().listIterator(index)); + } + + private ListIterator<V> getDelegateListIterator() { + return (ListIterator<V>) getDelegateIterator(); + } + @Override - Multimap<K, V> multimap() { - return AbstractMultimap.this; + public boolean hasPrevious() { + return getDelegateListIterator().hasPrevious(); } @Override - public Iterator<Entry<K, V>> iterator() { - return entryIterator(); + public V previous() { + return getDelegateListIterator().previous(); } - }; + + @Override + public int nextIndex() { + return getDelegateListIterator().nextIndex(); + } + + @Override + public int previousIndex() { + return getDelegateListIterator().previousIndex(); + } + + @Override + public void set(V value) { + getDelegateListIterator().set(value); + } + + @Override + public void add(V value) { + boolean wasEmpty = isEmpty(); + getDelegateListIterator().add(value); + totalSize++; + if (wasEmpty) { + addToMap(); + } + } + } + } + + /** + * List decorator that stays in sync with the multimap values for a key and + * supports rapid random access. + */ + private class RandomAccessWrappedList extends WrappedList + implements RandomAccess { + RandomAccessWrappedList(@Nullable K key, List<V> delegate, + @Nullable WrappedCollection ancestor) { + super(key, delegate, ancestor); + } } - - abstract Iterator<Entry<K, V>> entryIterator(); private transient Set<K> keySet; @@ -136,48 +867,484 @@ abstract class AbstractMultimap<K, V> implements Multimap<K, V> { return (result == null) ? keySet = createKeySet() : result; } - Set<K> createKeySet() { - return new Maps.KeySet<K, Collection<V>>() { - @Override - Map<K, Collection<V>> map() { - return asMap(); + private Set<K> createKeySet() { + return (map instanceof SortedMap) + ? new SortedKeySet((SortedMap<K, Collection<V>>) map) : new KeySet(map); + } + + private class KeySet extends Maps.KeySet<K, Collection<V>> { + + /** + * This is usually the same as map, except when someone requests a + * subcollection of a {@link SortedKeySet}. + */ + final Map<K, Collection<V>> subMap; + + KeySet(final Map<K, Collection<V>> subMap) { + this.subMap = subMap; + } + + @Override + Map<K, Collection<V>> map() { + return subMap; + } + + @Override public Iterator<K> iterator() { + return new Iterator<K>() { + final Iterator<Map.Entry<K, Collection<V>>> entryIterator + = subMap.entrySet().iterator(); + Map.Entry<K, Collection<V>> entry; + + @Override + public boolean hasNext() { + return entryIterator.hasNext(); + } + @Override + public K next() { + entry = entryIterator.next(); + return entry.getKey(); + } + @Override + public void remove() { + checkState(entry != null); + Collection<V> collection = entry.getValue(); + entryIterator.remove(); + totalSize -= collection.size(); + collection.clear(); + } + }; + } + + // The following methods are included for better performance. + + @Override public boolean remove(Object key) { + int count = 0; + Collection<V> collection = subMap.remove(key); + if (collection != null) { + count = collection.size(); + collection.clear(); + totalSize -= count; } - }; + return count > 0; + } + + @Override + public void clear() { + Iterators.clear(iterator()); + } + + @Override public boolean containsAll(Collection<?> c) { + return subMap.keySet().containsAll(c); + } + + @Override public boolean equals(@Nullable Object object) { + return this == object || this.subMap.keySet().equals(object); + } + + @Override public int hashCode() { + return subMap.keySet().hashCode(); + } + } + + private class SortedKeySet extends KeySet implements SortedSet<K> { + + SortedKeySet(SortedMap<K, Collection<V>> subMap) { + super(subMap); + } + + SortedMap<K, Collection<V>> sortedMap() { + return (SortedMap<K, Collection<V>>) subMap; + } + + @Override + public Comparator<? super K> comparator() { + return sortedMap().comparator(); + } + + @Override + public K first() { + return sortedMap().firstKey(); + } + + @Override + public SortedSet<K> headSet(K toElement) { + return new SortedKeySet(sortedMap().headMap(toElement)); + } + + @Override + public K last() { + return sortedMap().lastKey(); + } + + @Override + public SortedSet<K> subSet(K fromElement, K toElement) { + return new SortedKeySet(sortedMap().subMap(fromElement, toElement)); + } + + @Override + public SortedSet<K> tailSet(K fromElement) { + return new SortedKeySet(sortedMap().tailMap(fromElement)); + } } - - private transient Multiset<K> keys; - + + private transient Multiset<K> multiset; + @Override public Multiset<K> keys() { - Multiset<K> result = keys; - return (result == null) ? keys = createKeys() : result; + Multiset<K> result = multiset; + if (result == null) { + return multiset = new Multimaps.Keys<K, V>() { + @Override Multimap<K, V> multimap() { + return AbstractMultimap.this; + } + }; + } + return result; } - - Multiset<K> createKeys() { - return new Multimaps.Keys<K, V>(this); + + /** + * Removes all values for the provided key. Unlike {@link #removeAll}, it + * returns the number of removed mappings. + */ + private int removeValuesForKey(Object key) { + Collection<V> collection; + try { + collection = map.remove(key); + } catch (NullPointerException e) { + return 0; + } catch (ClassCastException e) { + return 0; + } + + int count = 0; + if (collection != null) { + count = collection.size(); + collection.clear(); + totalSize -= count; + } + return count; } - - private transient Collection<V> values; - + + private transient Collection<V> valuesCollection; + + /** + * {@inheritDoc} + * + * <p>The iterator generated by the returned collection traverses the values + * for one key, followed by the values of a second key, and so on. + */ + @Override public Collection<V> values() { + Collection<V> result = valuesCollection; + if (result == null) { + return valuesCollection = new Multimaps.Values<K, V>() { + @Override Multimap<K, V> multimap() { + return AbstractMultimap.this; + } + }; + } + return result; + } + + private transient Collection<Map.Entry<K, V>> entries; + + /* + * TODO(kevinb): should we copy this javadoc to each concrete class, so that + * classes like LinkedHashMultimap that need to say something different are + * still able to {@inheritDoc} all the way from Multimap? + */ + + /** + * {@inheritDoc} + * + * <p>The iterator generated by the returned collection traverses the values + * for one key, followed by the values of a second key, and so on. + * + * <p>Each entry is an immutable snapshot of a key-value mapping in the + * multimap, taken at the time the entry is returned by a method call to the + * collection or its iterator. + */ @Override - public Collection<V> values() { - Collection<V> result = values; - return (result == null) ? values = createValues() : result; + public Collection<Map.Entry<K, V>> entries() { + Collection<Map.Entry<K, V>> result = entries; + return (result == null) ? entries = createEntries() : result; } - - Collection<V> createValues() { - return new Multimaps.Values<K, V>(this); + + Collection<Map.Entry<K, V>> createEntries() { + if (this instanceof SetMultimap) { + return new Multimaps.EntrySet<K, V>() { + @Override Multimap<K, V> multimap() { + return AbstractMultimap.this; + } + + @Override public Iterator<Entry<K, V>> iterator() { + return createEntryIterator(); + } + }; + } + return new Multimaps.Entries<K, V>() { + @Override Multimap<K, V> multimap() { + return AbstractMultimap.this; + } + + @Override public Iterator<Entry<K, V>> iterator() { + return createEntryIterator(); + } + }; } - + + /** + * Returns an iterator across all key-value map entries, used by {@code + * entries().iterator()} and {@code values().iterator()}. The default + * behavior, which traverses the values for one key, the values for a second + * key, and so on, suffices for most {@code AbstractMultimap} implementations. + * + * @return an iterator across map entries + */ + Iterator<Map.Entry<K, V>> createEntryIterator() { + return new EntryIterator(); + } + + /** Iterator across all key-value pairs. */ + private class EntryIterator implements Iterator<Map.Entry<K, V>> { + final Iterator<Map.Entry<K, Collection<V>>> keyIterator; + K key; + Collection<V> collection; + Iterator<V> valueIterator; + + EntryIterator() { + keyIterator = map.entrySet().iterator(); + if (keyIterator.hasNext()) { + findValueIteratorAndKey(); + } else { + valueIterator = Iterators.emptyModifiableIterator(); + } + } + + void findValueIteratorAndKey() { + Map.Entry<K, Collection<V>> entry = keyIterator.next(); + key = entry.getKey(); + collection = entry.getValue(); + valueIterator = collection.iterator(); + } + + @Override + public boolean hasNext() { + return keyIterator.hasNext() || valueIterator.hasNext(); + } + + @Override + public Map.Entry<K, V> next() { + if (!valueIterator.hasNext()) { + findValueIteratorAndKey(); + } + return Maps.immutableEntry(key, valueIterator.next()); + } + + @Override + public void remove() { + valueIterator.remove(); + if (collection.isEmpty()) { + keyIterator.remove(); + } + totalSize--; + } + } + private transient Map<K, Collection<V>> asMap; - + @Override public Map<K, Collection<V>> asMap() { Map<K, Collection<V>> result = asMap; return (result == null) ? asMap = createAsMap() : result; } - - abstract Map<K, Collection<V>> createAsMap(); + + private Map<K, Collection<V>> createAsMap() { + return (map instanceof SortedMap) + ? new SortedAsMap((SortedMap<K, Collection<V>>) map) : new AsMap(map); + } + + private class AsMap extends AbstractMap<K, Collection<V>> { + /** + * Usually the same as map, but smaller for the headMap(), tailMap(), or + * subMap() of a SortedAsMap. + */ + final transient Map<K, Collection<V>> submap; + + AsMap(Map<K, Collection<V>> submap) { + this.submap = submap; + } + + transient Set<Map.Entry<K, Collection<V>>> entrySet; + + @Override public Set<Map.Entry<K, Collection<V>>> entrySet() { + Set<Map.Entry<K, Collection<V>>> result = entrySet; + return (result == null) ? entrySet = new AsMapEntries() : result; + } + + // The following methods are included for performance. + + @Override public boolean containsKey(Object key) { + return Maps.safeContainsKey(submap, key); + } + + @Override public Collection<V> get(Object key) { + Collection<V> collection = Maps.safeGet(submap, key); + if (collection == null) { + return null; + } + @SuppressWarnings("unchecked") + K k = (K) key; + return wrapCollection(k, collection); + } + + @Override public Set<K> keySet() { + return AbstractMultimap.this.keySet(); + } + + @Override + public int size() { + return submap.size(); + } + + @Override public Collection<V> remove(Object key) { + Collection<V> collection = submap.remove(key); + if (collection == null) { + return null; + } + + Collection<V> output = createCollection(); + output.addAll(collection); + totalSize -= collection.size(); + collection.clear(); + return output; + } + + @Override public boolean equals(@Nullable Object object) { + return this == object || submap.equals(object); + } + + @Override public int hashCode() { + return submap.hashCode(); + } + + @Override public String toString() { + return submap.toString(); + } + + @Override + public void clear() { + if (submap == map) { + AbstractMultimap.this.clear(); + } else { + + Iterators.clear(new AsMapIterator()); + } + } + + class AsMapEntries extends Maps.EntrySet<K, Collection<V>> { + @Override + Map<K, Collection<V>> map() { + return AsMap.this; + } + + @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() { + return new AsMapIterator(); + } + + // The following methods are included for performance. + + @Override public boolean contains(Object o) { + return Collections2.safeContains(submap.entrySet(), o); + } + + @Override public boolean remove(Object o) { + if (!contains(o)) { + return false; + } + Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; + removeValuesForKey(entry.getKey()); + return true; + } + } + + /** Iterator across all keys and value collections. */ + class AsMapIterator implements Iterator<Map.Entry<K, Collection<V>>> { + final Iterator<Map.Entry<K, Collection<V>>> delegateIterator + = submap.entrySet().iterator(); + Collection<V> collection; + + @Override + public boolean hasNext() { + return delegateIterator.hasNext(); + } + + @Override + public Map.Entry<K, Collection<V>> next() { + Map.Entry<K, Collection<V>> entry = delegateIterator.next(); + K key = entry.getKey(); + collection = entry.getValue(); + return Maps.immutableEntry(key, wrapCollection(key, collection)); + } + + @Override + public void remove() { + delegateIterator.remove(); + totalSize -= collection.size(); + collection.clear(); + } + } + } + + private class SortedAsMap extends AsMap + implements SortedMap<K, Collection<V>> { + SortedAsMap(SortedMap<K, Collection<V>> submap) { + super(submap); + } + + SortedMap<K, Collection<V>> sortedMap() { + return (SortedMap<K, Collection<V>>) submap; + } + + @Override + public Comparator<? super K> comparator() { + return sortedMap().comparator(); + } + + @Override + public K firstKey() { + return sortedMap().firstKey(); + } + + @Override + public K lastKey() { + return sortedMap().lastKey(); + } + + @Override + public SortedMap<K, Collection<V>> headMap(K toKey) { + return new SortedAsMap(sortedMap().headMap(toKey)); + } + + @Override + public SortedMap<K, Collection<V>> subMap(K fromKey, K toKey) { + return new SortedAsMap(sortedMap().subMap(fromKey, toKey)); + } + + @Override + public SortedMap<K, Collection<V>> tailMap(K fromKey) { + return new SortedAsMap(sortedMap().tailMap(fromKey)); + } + + SortedSet<K> sortedKeySet; + + // returns a SortedSet, even though returning a Set would be sufficient to + // satisfy the SortedMap.keySet() interface + @Override public SortedSet<K> keySet() { + SortedSet<K> result = sortedKeySet; + return (result == null) + ? sortedKeySet = new SortedKeySet(sortedMap()) : result; + } + } // Comparison and hashing @@ -187,7 +1354,7 @@ abstract class AbstractMultimap<K, V> implements Multimap<K, V> { } if (object instanceof Multimap) { Multimap<?, ?> that = (Multimap<?, ?>) object; - return this.asMap().equals(that.asMap()); + return this.map.equals(that.asMap()); } return false; } @@ -201,7 +1368,7 @@ abstract class AbstractMultimap<K, V> implements Multimap<K, V> { * @see Map#hashCode */ @Override public int hashCode() { - return asMap().hashCode(); + return map.hashCode(); } /** @@ -212,6 +1379,9 @@ abstract class AbstractMultimap<K, V> implements Multimap<K, V> { */ @Override public String toString() { - return asMap().toString(); + return map.toString(); } + + private static final long serialVersionUID = 2447537837011683357L; } + |