diff options
Diffstat (limited to 'guava/src/com/google/common/collect/AbstractMapBasedMultimap.java')
| -rw-r--r-- | guava/src/com/google/common/collect/AbstractMapBasedMultimap.java | 1567 |
1 files changed, 0 insertions, 1567 deletions
diff --git a/guava/src/com/google/common/collect/AbstractMapBasedMultimap.java b/guava/src/com/google/common/collect/AbstractMapBasedMultimap.java deleted file mode 100644 index 0a1edf3..0000000 --- a/guava/src/com/google/common/collect/AbstractMapBasedMultimap.java +++ /dev/null @@ -1,1567 +0,0 @@ -/* - * 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. - * 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.checkArgument; -import static com.google.common.base.Preconditions.checkNotNull; - -import com.google.common.annotations.GwtCompatible; -import com.google.common.annotations.GwtIncompatible; - -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.NavigableMap; -import java.util.NavigableSet; -import java.util.RandomAccess; -import java.util.Set; -import java.util.SortedMap; -import java.util.SortedSet; - -import javax.annotation.Nullable; - -/** - * 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 AbstractMapBasedMultimap} 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(emulated = true) -abstract class AbstractMapBasedMultimap<K, V> extends AbstractMultimap<K, V> - implements 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 AbstractMapBasedMultimap(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 an unmodifiable, empty collection of values. - * - * <p>This is used in {@link #removeAll} on an empty key. - */ - Collection<V> createUnmodifiableEmptyCollection() { - return unmodifiableCollectionSubclass(createCollection()); - } - - /** - * 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 containsKey(@Nullable Object key) { - return map.containsKey(key); - } - - // Modification Operations - - @Override - public boolean put(@Nullable K key, @Nullable V value) { - Collection<V> collection = map.get(key); - if (collection == null) { - collection = createCollection(key); - if (collection.add(value)) { - totalSize++; - map.put(key, collection); - return true; - } else { - throw new AssertionError("New Collection violated the Collection spec"); - } - } else 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; - } - - // Bulk Operations - - /** - * {@inheritDoc} - * - * <p>The returned collection is immutable. - */ - @Override - public Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values) { - Iterator<? extends V> iterator = values.iterator(); - if (!iterator.hasNext()) { - return removeAll(key); - } - - // TODO(user): investigate atomic failure? - 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); - } - - /** - * {@inheritDoc} - * - * <p>The returned collection is immutable. - */ - @Override - public Collection<V> removeAll(@Nullable Object key) { - Collection<V> collection = map.remove(key); - - if (collection == null) { - return createUnmodifiableEmptyCollection(); - } - - Collection<V> output = createCollection(); - output.addAll(collection); - totalSize -= collection.size(); - collection.clear(); - - return unmodifiableCollectionSubclass(output); - } - - Collection<V> unmodifiableCollectionSubclass(Collection<V> collection) { - // We don't deal with NavigableSet here yet for GWT reasons -- instead, - // non-GWT TreeMultimap explicitly overrides this and uses NavigableSet. - 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. - */ - Collection<V> wrapCollection(@Nullable K key, Collection<V> collection) { - // We don't deal with NavigableSet here yet for GWT reasons -- instead, - // non-GWT TreeMultimap explicitly overrides this and uses NavigableSet. - 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 - * AbstractMapBasedMultimap#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; - } - } - } - - /** - * If collection is empty, remove it from {@code AbstractMapBasedMultimap.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; - } - } - - @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); - } - - @Override - public boolean removeAll(Collection<?> c) { - if (c.isEmpty()) { - return false; - } - int oldSize = size(); // calls refreshIfEmpty - - // Guava issue 1013: AbstractSet and most JDK set implementations are - // susceptible to quadratic removeAll performance on lists; - // use a slightly smarter implementation here - boolean changed = Sets.removeAllImpl((Set<V>) delegate, c); - if (changed) { - int newSize = delegate.size(); - totalSize += (newSize - oldSize); - removeIfEmpty(); - } - return changed; - } - } - - /** - * 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()); - } - } - - @GwtIncompatible("NavigableSet") - class WrappedNavigableSet extends WrappedSortedSet implements NavigableSet<V> { - WrappedNavigableSet( - @Nullable K key, NavigableSet<V> delegate, @Nullable WrappedCollection ancestor) { - super(key, delegate, ancestor); - } - - @Override - NavigableSet<V> getSortedSetDelegate() { - return (NavigableSet<V>) super.getSortedSetDelegate(); - } - - @Override - public V lower(V v) { - return getSortedSetDelegate().lower(v); - } - - @Override - public V floor(V v) { - return getSortedSetDelegate().floor(v); - } - - @Override - public V ceiling(V v) { - return getSortedSetDelegate().ceiling(v); - } - - @Override - public V higher(V v) { - return getSortedSetDelegate().higher(v); - } - - @Override - public V pollFirst() { - return Iterators.pollNext(iterator()); - } - - @Override - public V pollLast() { - return Iterators.pollNext(descendingIterator()); - } - - private NavigableSet<V> wrap(NavigableSet<V> wrapped) { - return new WrappedNavigableSet(key, wrapped, - (getAncestor() == null) ? this : getAncestor()); - } - - @Override - public NavigableSet<V> descendingSet() { - return wrap(getSortedSetDelegate().descendingSet()); - } - - @Override - public Iterator<V> descendingIterator() { - return new WrappedIterator(getSortedSetDelegate().descendingIterator()); - } - - @Override - public NavigableSet<V> subSet( - V fromElement, boolean fromInclusive, V toElement, boolean toInclusive) { - return wrap( - getSortedSetDelegate().subSet(fromElement, fromInclusive, toElement, toInclusive)); - } - - @Override - public NavigableSet<V> headSet(V toElement, boolean inclusive) { - return wrap(getSortedSetDelegate().headSet(toElement, inclusive)); - } - - @Override - public NavigableSet<V> tailSet(V fromElement, boolean inclusive) { - return wrap(getSortedSetDelegate().tailSet(fromElement, inclusive)); - } - } - - /** 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 - public boolean hasPrevious() { - return getDelegateListIterator().hasPrevious(); - } - - @Override - 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); - } - } - - @Override - Set<K> createKeySet() { - // TreeMultimap uses NavigableKeySet explicitly, but we don't handle that here for GWT - // compatibility reasons - 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() { - final Iterator<Map.Entry<K, Collection<V>>> entryIterator - = subMap.entrySet().iterator(); - return new Iterator<K>() { - 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() { - Iterators.checkRemove(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)); - } - } - - @GwtIncompatible("NavigableSet") - class NavigableKeySet extends SortedKeySet implements NavigableSet<K> { - NavigableKeySet(NavigableMap<K, Collection<V>> subMap) { - super(subMap); - } - - @Override - NavigableMap<K, Collection<V>> sortedMap() { - return (NavigableMap<K, Collection<V>>) super.sortedMap(); - } - - @Override - public K lower(K k) { - return sortedMap().lowerKey(k); - } - - @Override - public K floor(K k) { - return sortedMap().floorKey(k); - } - - @Override - public K ceiling(K k) { - return sortedMap().ceilingKey(k); - } - - @Override - public K higher(K k) { - return sortedMap().higherKey(k); - } - - @Override - public K pollFirst() { - return Iterators.pollNext(iterator()); - } - - @Override - public K pollLast() { - return Iterators.pollNext(descendingIterator()); - } - - @Override - public NavigableSet<K> descendingSet() { - return new NavigableKeySet(sortedMap().descendingMap()); - } - - @Override - public Iterator<K> descendingIterator() { - return descendingSet().iterator(); - } - - @Override - public NavigableSet<K> headSet(K toElement) { - return headSet(toElement, false); - } - - @Override - public NavigableSet<K> headSet(K toElement, boolean inclusive) { - return new NavigableKeySet(sortedMap().headMap(toElement, inclusive)); - } - - @Override - public NavigableSet<K> subSet(K fromElement, K toElement) { - return subSet(fromElement, true, toElement, false); - } - - @Override - public NavigableSet<K> subSet( - K fromElement, boolean fromInclusive, K toElement, boolean toInclusive) { - return new NavigableKeySet( - sortedMap().subMap(fromElement, fromInclusive, toElement, toInclusive)); - } - - @Override - public NavigableSet<K> tailSet(K fromElement) { - return tailSet(fromElement, true); - } - - @Override - public NavigableSet<K> tailSet(K fromElement, boolean inclusive) { - return new NavigableKeySet(sortedMap().tailMap(fromElement, inclusive)); - } - } - - /** - * 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 = Maps.safeRemove(map, key); - - int count = 0; - if (collection != null) { - count = collection.size(); - collection.clear(); - totalSize -= count; - } - return count; - } - - /** - * {@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() { - return super.values(); - } - - /* - * 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<Map.Entry<K, V>> entries() { - return super.entries(); - } - - /** - * 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 AbstractMapBasedMultimap} implementations. - * - * @return an iterator across map entries - */ - @Override - Iterator<Map.Entry<K, V>> entryIterator() { - 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--; - } - } - - @Override - Map<K, Collection<V>> createAsMap() { - // TreeMultimap uses NavigableAsMap explicitly, but we don't handle that here for GWT - // compatibility reasons - 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 AbstractMapBasedMultimap.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) { - AbstractMapBasedMultimap.this.clear(); - } else { - - Iterators.clear(new AsMapIterator()); - } - } - - Entry<K, Collection<V>> wrapEntry(Entry<K, Collection<V>> entry) { - K key = entry.getKey(); - return Maps.immutableEntry(key, wrapCollection(key, entry.getValue())); - } - - 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(); - collection = entry.getValue(); - return wrapEntry(entry); - } - - @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 = createKeySet() : result; - } - - SortedSet<K> createKeySet() { - return new SortedKeySet(sortedMap()); - } - } - - @GwtIncompatible("NavigableAsMap") - class NavigableAsMap extends SortedAsMap implements NavigableMap<K, Collection<V>> { - - NavigableAsMap(NavigableMap<K, Collection<V>> submap) { - super(submap); - } - - @Override - NavigableMap<K, Collection<V>> sortedMap() { - return (NavigableMap<K, Collection<V>>) super.sortedMap(); - } - - @Override - public Entry<K, Collection<V>> lowerEntry(K key) { - Entry<K, Collection<V>> entry = sortedMap().lowerEntry(key); - return (entry == null) ? null : wrapEntry(entry); - } - - @Override - public K lowerKey(K key) { - return sortedMap().lowerKey(key); - } - - @Override - public Entry<K, Collection<V>> floorEntry(K key) { - Entry<K, Collection<V>> entry = sortedMap().floorEntry(key); - return (entry == null) ? null : wrapEntry(entry); - } - - @Override - public K floorKey(K key) { - return sortedMap().floorKey(key); - } - - @Override - public Entry<K, Collection<V>> ceilingEntry(K key) { - Entry<K, Collection<V>> entry = sortedMap().ceilingEntry(key); - return (entry == null) ? null : wrapEntry(entry); - } - - @Override - public K ceilingKey(K key) { - return sortedMap().ceilingKey(key); - } - - @Override - public Entry<K, Collection<V>> higherEntry(K key) { - Entry<K, Collection<V>> entry = sortedMap().higherEntry(key); - return (entry == null) ? null : wrapEntry(entry); - } - - @Override - public K higherKey(K key) { - return sortedMap().higherKey(key); - } - - @Override - public Entry<K, Collection<V>> firstEntry() { - Entry<K, Collection<V>> entry = sortedMap().firstEntry(); - return (entry == null) ? null : wrapEntry(entry); - } - - @Override - public Entry<K, Collection<V>> lastEntry() { - Entry<K, Collection<V>> entry = sortedMap().lastEntry(); - return (entry == null) ? null : wrapEntry(entry); - } - - @Override - public Entry<K, Collection<V>> pollFirstEntry() { - return pollAsMapEntry(entrySet().iterator()); - } - - @Override - public Entry<K, Collection<V>> pollLastEntry() { - return pollAsMapEntry(descendingMap().entrySet().iterator()); - } - - Map.Entry<K, Collection<V>> pollAsMapEntry(Iterator<Entry<K, Collection<V>>> entryIterator) { - if (!entryIterator.hasNext()) { - return null; - } - Entry<K, Collection<V>> entry = entryIterator.next(); - Collection<V> output = createCollection(); - output.addAll(entry.getValue()); - entryIterator.remove(); - return Maps.immutableEntry(entry.getKey(), unmodifiableCollectionSubclass(output)); - } - - @Override - public NavigableMap<K, Collection<V>> descendingMap() { - return new NavigableAsMap(sortedMap().descendingMap()); - } - - @Override - public NavigableSet<K> keySet() { - return (NavigableSet<K>) super.keySet(); - } - - @Override - NavigableSet<K> createKeySet() { - return new NavigableKeySet(sortedMap()); - } - - @Override - public NavigableSet<K> navigableKeySet() { - return keySet(); - } - - @Override - public NavigableSet<K> descendingKeySet() { - return descendingMap().navigableKeySet(); - } - - @Override - public NavigableMap<K, Collection<V>> subMap(K fromKey, K toKey) { - return subMap(fromKey, true, toKey, false); - } - - @Override - public NavigableMap<K, Collection<V>> subMap( - K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { - return new NavigableAsMap(sortedMap().subMap(fromKey, fromInclusive, toKey, toInclusive)); - } - - @Override - public NavigableMap<K, Collection<V>> headMap(K toKey) { - return headMap(toKey, false); - } - - @Override - public NavigableMap<K, Collection<V>> headMap(K toKey, boolean inclusive) { - return new NavigableAsMap(sortedMap().headMap(toKey, false)); - } - - @Override - public NavigableMap<K, Collection<V>> tailMap(K fromKey) { - return tailMap(fromKey, true); - } - - @Override - public NavigableMap<K, Collection<V>> tailMap(K fromKey, boolean inclusive) { - return new NavigableAsMap(sortedMap().tailMap(fromKey, inclusive)); - } - } - - private static final long serialVersionUID = 2447537837011683357L; -} |