| /* |
| * 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 static com.google.common.collect.CollectPreconditions.checkRemove; |
| |
| import com.google.common.annotations.GwtCompatible; |
| import com.google.common.collect.Maps.ViewCachingAbstractMap; |
| import com.google.j2objc.annotations.WeakOuter; |
| import java.io.Serializable; |
| import java.util.AbstractCollection; |
| 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.NavigableMap; |
| import java.util.NavigableSet; |
| import java.util.RandomAccess; |
| import java.util.Set; |
| import java.util.SortedMap; |
| import java.util.SortedSet; |
| import org.checkerframework.checker.nullness.compatqual.MonotonicNonNullDecl; |
| import org.checkerframework.checker.nullness.compatqual.NullableDecl; |
| |
| /** |
| * 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 |
| 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(@NullableDecl K key) { |
| return createCollection(); |
| } |
| |
| Map<K, Collection<V>> backingMap() { |
| return map; |
| } |
| |
| // Query Operations |
| |
| @Override |
| public int size() { |
| return totalSize; |
| } |
| |
| @Override |
| public boolean containsKey(@NullableDecl Object key) { |
| return map.containsKey(key); |
| } |
| |
| // Modification Operations |
| |
| @Override |
| public boolean put(@NullableDecl K key, @NullableDecl 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(@NullableDecl 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(@NullableDecl K key, Iterable<? extends V> values) { |
| Iterator<? extends V> iterator = values.iterator(); |
| if (!iterator.hasNext()) { |
| return removeAll(key); |
| } |
| |
| // TODO(lowasser): 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(@NullableDecl 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); |
| } |
| |
| <E> Collection<E> unmodifiableCollectionSubclass(Collection<E> collection) { |
| 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(@NullableDecl 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(@NullableDecl K key, Collection<V> collection) { |
| return new WrappedCollection(key, collection, null); |
| } |
| |
| final List<V> wrapList( |
| @NullableDecl K key, List<V> list, @NullableDecl 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. |
| */ |
| @WeakOuter |
| class WrappedCollection extends AbstractCollection<V> { |
| @NullableDecl final K key; |
| Collection<V> delegate; |
| @NullableDecl final WrappedCollection ancestor; |
| @NullableDecl final Collection<V> ancestorDelegate; |
| |
| WrappedCollection( |
| @NullableDecl K key, Collection<V> delegate, @NullableDecl 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(@NullableDecl 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 static <E> Iterator<E> iteratorOrListIterator(Collection<E> collection) { |
| return (collection instanceof List) |
| ? ((List<E>) collection).listIterator() |
| : collection.iterator(); |
| } |
| |
| /** Set decorator that stays in sync with the multimap values for a key. */ |
| @WeakOuter |
| class WrappedSet extends WrappedCollection implements Set<V> { |
| WrappedSet(@NullableDecl 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. */ |
| @WeakOuter |
| class WrappedSortedSet extends WrappedCollection implements SortedSet<V> { |
| WrappedSortedSet( |
| @NullableDecl K key, SortedSet<V> delegate, @NullableDecl 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()); |
| } |
| } |
| |
| @WeakOuter |
| class WrappedNavigableSet extends WrappedSortedSet implements NavigableSet<V> { |
| WrappedNavigableSet( |
| @NullableDecl K key, NavigableSet<V> delegate, @NullableDecl 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. */ |
| @WeakOuter |
| class WrappedList extends WrappedCollection implements List<V> { |
| WrappedList(@NullableDecl K key, List<V> delegate, @NullableDecl 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( |
| @NullableDecl K key, List<V> delegate, @NullableDecl WrappedCollection ancestor) { |
| super(key, delegate, ancestor); |
| } |
| } |
| |
| @Override |
| Set<K> createKeySet() { |
| return new KeySet(map); |
| } |
| |
| final Set<K> createMaybeNavigableKeySet() { |
| if (map instanceof NavigableMap) { |
| return new NavigableKeySet((NavigableMap<K, Collection<V>>) map); |
| } else if (map instanceof SortedMap) { |
| return new SortedKeySet((SortedMap<K, Collection<V>>) map); |
| } else { |
| return new KeySet(map); |
| } |
| } |
| |
| @WeakOuter |
| private class KeySet extends Maps.KeySet<K, Collection<V>> { |
| KeySet(final Map<K, Collection<V>> subMap) { |
| super(subMap); |
| } |
| |
| @Override |
| public Iterator<K> iterator() { |
| final Iterator<Entry<K, Collection<V>>> entryIterator = map().entrySet().iterator(); |
| return new Iterator<K>() { |
| @NullableDecl 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() { |
| checkRemove(entry != null); |
| Collection<V> collection = entry.getValue(); |
| entryIterator.remove(); |
| totalSize -= collection.size(); |
| collection.clear(); |
| entry = null; |
| } |
| }; |
| } |
| |
| // The following methods are included for better performance. |
| |
| @Override |
| public boolean remove(Object key) { |
| int count = 0; |
| Collection<V> collection = map().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 map().keySet().containsAll(c); |
| } |
| |
| @Override |
| public boolean equals(@NullableDecl Object object) { |
| return this == object || this.map().keySet().equals(object); |
| } |
| |
| @Override |
| public int hashCode() { |
| return map().keySet().hashCode(); |
| } |
| } |
| |
| @WeakOuter |
| 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>>) super.map(); |
| } |
| |
| @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)); |
| } |
| } |
| |
| @WeakOuter |
| 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. */ |
| private void removeValuesForKey(Object key) { |
| Collection<V> collection = Maps.safeRemove(map, key); |
| |
| if (collection != null) { |
| int count = collection.size(); |
| collection.clear(); |
| totalSize -= count; |
| } |
| } |
| |
| private abstract class Itr<T> implements Iterator<T> { |
| final Iterator<Entry<K, Collection<V>>> keyIterator; |
| @NullableDecl K key; |
| @MonotonicNonNullDecl Collection<V> collection; |
| Iterator<V> valueIterator; |
| |
| Itr() { |
| keyIterator = map.entrySet().iterator(); |
| key = null; |
| collection = null; |
| valueIterator = Iterators.emptyModifiableIterator(); |
| } |
| |
| abstract T output(K key, V value); |
| |
| @Override |
| public boolean hasNext() { |
| return keyIterator.hasNext() || valueIterator.hasNext(); |
| } |
| |
| @Override |
| public T next() { |
| if (!valueIterator.hasNext()) { |
| Entry<K, Collection<V>> mapEntry = keyIterator.next(); |
| key = mapEntry.getKey(); |
| collection = mapEntry.getValue(); |
| valueIterator = collection.iterator(); |
| } |
| return output(key, valueIterator.next()); |
| } |
| |
| @Override |
| public void remove() { |
| valueIterator.remove(); |
| if (collection.isEmpty()) { |
| keyIterator.remove(); |
| } |
| totalSize--; |
| } |
| } |
| |
| /** |
| * {@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(); |
| } |
| |
| @Override |
| Collection<V> createValues() { |
| return new Values(); |
| } |
| |
| @Override |
| Iterator<V> valueIterator() { |
| return new Itr<V>() { |
| @Override |
| V output(K key, V value) { |
| return value; |
| } |
| }; |
| } |
| |
| /* |
| * 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? |
| */ |
| |
| @Override |
| Multiset<K> createKeys() { |
| return new Multimaps.Keys<K, V>(this); |
| } |
| |
| /** |
| * {@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<Entry<K, V>> entries() { |
| return super.entries(); |
| } |
| |
| @Override |
| Collection<Entry<K, V>> createEntries() { |
| if (this instanceof SetMultimap) { |
| return new EntrySet(); |
| } else { |
| return new 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<Entry<K, V>> entryIterator() { |
| return new Itr<Entry<K, V>>() { |
| @Override |
| Entry<K, V> output(K key, V value) { |
| return Maps.immutableEntry(key, value); |
| } |
| }; |
| } |
| |
| @Override |
| Map<K, Collection<V>> createAsMap() { |
| return new AsMap(map); |
| } |
| |
| final Map<K, Collection<V>> createMaybeNavigableAsMap() { |
| if (map instanceof NavigableMap) { |
| return new NavigableAsMap((NavigableMap<K, Collection<V>>) map); |
| } else if (map instanceof SortedMap) { |
| return new SortedAsMap((SortedMap<K, Collection<V>>) map); |
| } else { |
| return new AsMap(map); |
| } |
| } |
| |
| @WeakOuter |
| private class AsMap extends ViewCachingAbstractMap<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; |
| } |
| |
| @Override |
| protected Set<Entry<K, Collection<V>>> createEntrySet() { |
| return new AsMapEntries(); |
| } |
| |
| // 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(@NullableDecl 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())); |
| } |
| |
| @WeakOuter |
| class AsMapEntries extends Maps.EntrySet<K, Collection<V>> { |
| @Override |
| Map<K, Collection<V>> map() { |
| return AsMap.this; |
| } |
| |
| @Override |
| public Iterator<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; |
| } |
| Entry<?, ?> entry = (Entry<?, ?>) o; |
| removeValuesForKey(entry.getKey()); |
| return true; |
| } |
| } |
| |
| /** Iterator across all keys and value collections. */ |
| class AsMapIterator implements Iterator<Entry<K, Collection<V>>> { |
| final Iterator<Entry<K, Collection<V>>> delegateIterator = submap.entrySet().iterator(); |
| @NullableDecl Collection<V> collection; |
| |
| @Override |
| public boolean hasNext() { |
| return delegateIterator.hasNext(); |
| } |
| |
| @Override |
| public Entry<K, Collection<V>> next() { |
| Entry<K, Collection<V>> entry = delegateIterator.next(); |
| collection = entry.getValue(); |
| return wrapEntry(entry); |
| } |
| |
| @Override |
| public void remove() { |
| checkRemove(collection != null); |
| delegateIterator.remove(); |
| totalSize -= collection.size(); |
| collection.clear(); |
| collection = null; |
| } |
| } |
| } |
| |
| @WeakOuter |
| 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)); |
| } |
| |
| @MonotonicNonNullDecl 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; |
| } |
| |
| @Override |
| SortedSet<K> createKeySet() { |
| return new SortedKeySet(sortedMap()); |
| } |
| } |
| |
| 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()); |
| } |
| |
| 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, inclusive)); |
| } |
| |
| @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; |
| } |