|
Java example source code file (AbstractMapBasedMultimap.java)
This example Java source code file (AbstractMapBasedMultimap.java) is included in the alvinalexander.com
"Java Source Code
Warehouse" project. The intent of this project is to help you "Learn
Java by Example" TM.
Learn more about this Java project at its project page.
The AbstractMapBasedMultimap.java Java example source code
/*
* 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.annotations.GwtIncompatible;
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 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
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 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 map) {
checkArgument(map.isEmpty());
this.map = map;
}
/** Used during deserialization only. */
final void setMap(Map<K, Collection 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 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 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(@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 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 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 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.
*/
@WeakOuter
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 collection) {
return (collection instanceof List)
? ((List<V>) collection).listIterator()
: collection.iterator();
}
/** Set decorator that stays in sync with the multimap values for a key. */
@WeakOuter
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.
*/
@WeakOuter
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
@WeakOuter
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 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
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) map)
: new KeySet(map);
}
@WeakOuter
private class KeySet extends Maps.KeySet<K, Collection {
KeySet(final Map<K, Collection subMap) {
super(subMap);
}
@Override
public Iterator<K> iterator() {
final Iterator<Map.Entry> entryIterator = map().entrySet().iterator();
return new Iterator<K>() {
Map.Entry<K, Collection 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();
}
};
}
// 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(@Nullable 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 subMap) {
super(subMap);
}
SortedMap<K, Collection sortedMap() {
return (SortedMap<K, Collection) 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));
}
}
@GwtIncompatible // NavigableSet
@WeakOuter
class NavigableKeySet extends SortedKeySet implements NavigableSet<K> {
NavigableKeySet(NavigableMap<K, Collection subMap) {
super(subMap);
}
@Override
NavigableMap<K, Collection sortedMap() {
return (NavigableMap<K, Collection) 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 {
final Iterator<Map.Entry> keyIterator;
K key;
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()) {
Map.Entry<K, Collection 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
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?
*/
/**
* {@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 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 entryIterator() {
return new Itr<Map.Entry() {
@Override
Entry<K, V> output(K key, V value) {
return Maps.immutableEntry(key, value);
}
};
}
@Override
Map<K, Collection 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) map)
: new AsMap(map);
}
@WeakOuter
private class AsMap extends ViewCachingAbstractMap<K, Collection {
/**
* Usually the same as map, but smaller for the headMap(), tailMap(), or
* subMap() of a SortedAsMap.
*/
final transient Map<K, Collection submap;
AsMap(Map<K, Collection submap) {
this.submap = submap;
}
@Override
protected Set<Entry> 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(@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 wrapEntry(Entry> entry) {
K key = entry.getKey();
return Maps.immutableEntry(key, wrapCollection(key, entry.getValue()));
}
@WeakOuter
class AsMapEntries extends Maps.EntrySet<K, Collection {
@Override
Map<K, Collection map() {
return AsMap.this;
}
@Override
public Iterator<Map.Entry> 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> {
final Iterator<Map.Entry> delegateIterator = submap.entrySet().iterator();
Collection<V> collection;
@Override
public boolean hasNext() {
return delegateIterator.hasNext();
}
@Override
public Map.Entry<K, Collection next() {
Map.Entry<K, Collection entry = delegateIterator.next();
collection = entry.getValue();
return wrapEntry(entry);
}
@Override
public void remove() {
delegateIterator.remove();
totalSize -= collection.size();
collection.clear();
}
}
}
@WeakOuter
private class SortedAsMap extends AsMap implements SortedMap<K, Collection {
SortedAsMap(SortedMap<K, Collection submap) {
super(submap);
}
SortedMap<K, Collection sortedMap() {
return (SortedMap<K, Collection) 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 headMap(K toKey) {
return new SortedAsMap(sortedMap().headMap(toKey));
}
@Override
public SortedMap<K, Collection subMap(K fromKey, K toKey) {
return new SortedAsMap(sortedMap().subMap(fromKey, toKey));
}
@Override
public SortedMap<K, Collection 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;
}
@Override
SortedSet<K> createKeySet() {
return new SortedKeySet(sortedMap());
}
}
@GwtIncompatible // NavigableAsMap
class NavigableAsMap extends SortedAsMap implements NavigableMap<K, Collection {
NavigableAsMap(NavigableMap<K, Collection submap) {
super(submap);
}
@Override
NavigableMap<K, Collection sortedMap() {
return (NavigableMap<K, Collection) super.sortedMap();
}
@Override
public Entry<K, Collection lowerEntry(K key) {
Entry<K, Collection 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 floorEntry(K key) {
Entry<K, Collection 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 ceilingEntry(K key) {
Entry<K, Collection 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 higherEntry(K key) {
Entry<K, Collection 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 firstEntry() {
Entry<K, Collection entry = sortedMap().firstEntry();
return (entry == null) ? null : wrapEntry(entry);
}
@Override
public Entry<K, Collection lastEntry() {
Entry<K, Collection entry = sortedMap().lastEntry();
return (entry == null) ? null : wrapEntry(entry);
}
@Override
public Entry<K, Collection pollFirstEntry() {
return pollAsMapEntry(entrySet().iterator());
}
@Override
public Entry<K, Collection pollLastEntry() {
return pollAsMapEntry(descendingMap().entrySet().iterator());
}
Map.Entry<K, Collection pollAsMapEntry(Iterator>> entryIterator) {
if (!entryIterator.hasNext()) {
return null;
}
Entry<K, Collection 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 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 subMap(K fromKey, K toKey) {
return subMap(fromKey, true, toKey, false);
}
@Override
public NavigableMap<K, Collection subMap(
K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
return new NavigableAsMap(sortedMap().subMap(fromKey, fromInclusive, toKey, toInclusive));
}
@Override
public NavigableMap<K, Collection headMap(K toKey) {
return headMap(toKey, false);
}
@Override
public NavigableMap<K, Collection headMap(K toKey, boolean inclusive) {
return new NavigableAsMap(sortedMap().headMap(toKey, inclusive));
}
@Override
public NavigableMap<K, Collection tailMap(K fromKey) {
return tailMap(fromKey, true);
}
@Override
public NavigableMap<K, Collection tailMap(K fromKey, boolean inclusive) {
return new NavigableAsMap(sortedMap().tailMap(fromKey, inclusive));
}
}
private static final long serialVersionUID = 2447537837011683357L;
}
Other Java examples (source code examples)
Here is a short list of links related to this Java AbstractMapBasedMultimap.java source code file:
|