1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 27dd252788645e940eada959bdde927426e2531c9Paul Duffin * Copyright (C) 2012 The Guava Authors 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkNotNull; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 230888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.AbstractCollection; 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Map.Entry; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 337dd252788645e940eada959bdde927426e2531c9Paul Duffin * A skeleton {@code Multimap} implementation, not necessarily in terms of a {@code Map}. 347dd252788645e940eada959bdde927426e2531c9Paul Duffin * 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@GwtCompatible 387dd252788645e940eada959bdde927426e2531c9Paul Duffinabstract class AbstractMultimap<K, V> implements Multimap<K, V> { 390888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean isEmpty() { 417dd252788645e940eada959bdde927426e2531c9Paul Duffin return size() == 0; 42dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 43dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 440888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsValue(@Nullable Object value) { 467dd252788645e940eada959bdde927426e2531c9Paul Duffin for (Collection<V> collection : asMap().values()) { 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection.contains(value)) { 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 550888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsEntry(@Nullable Object key, @Nullable Object value) { 577dd252788645e940eada959bdde927426e2531c9Paul Duffin Collection<V> collection = asMap().get(key); 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return collection != null && collection.contains(value); 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 600888a09821a98ac0680fad765217302858e70fa4Paul Duffin 610888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 62dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin public boolean remove(@Nullable Object key, @Nullable Object value) { 637dd252788645e940eada959bdde927426e2531c9Paul Duffin Collection<V> collection = asMap().get(key); 647dd252788645e940eada959bdde927426e2531c9Paul Duffin return collection != null && collection.remove(value); 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 670888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 687dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean put(@Nullable K key, @Nullable V value) { 697dd252788645e940eada959bdde927426e2531c9Paul Duffin return get(key).add(value); 707dd252788645e940eada959bdde927426e2531c9Paul Duffin } 71dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 720888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean putAll(@Nullable K key, Iterable<? extends V> values) { 747dd252788645e940eada959bdde927426e2531c9Paul Duffin checkNotNull(values); 750888a09821a98ac0680fad765217302858e70fa4Paul Duffin // make sure we only call values.iterator() once 760888a09821a98ac0680fad765217302858e70fa4Paul Duffin // and we only call get(key) if values is nonempty 770888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (values instanceof Collection) { 780888a09821a98ac0680fad765217302858e70fa4Paul Duffin Collection<? extends V> valueCollection = (Collection<? extends V>) values; 790888a09821a98ac0680fad765217302858e70fa4Paul Duffin return !valueCollection.isEmpty() && get(key).addAll(valueCollection); 800888a09821a98ac0680fad765217302858e70fa4Paul Duffin } else { 810888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<? extends V> valueItr = values.iterator(); 820888a09821a98ac0680fad765217302858e70fa4Paul Duffin return valueItr.hasNext() && Iterators.addAll(get(key), valueItr); 830888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 860888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = false; 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Map.Entry<? extends K, ? extends V> entry : multimap.entries()) { 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson changed |= put(entry.getKey(), entry.getValue()); 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 950888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 967dd252788645e940eada959bdde927426e2531c9Paul Duffin public Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values) { 977dd252788645e940eada959bdde927426e2531c9Paul Duffin checkNotNull(values); 987dd252788645e940eada959bdde927426e2531c9Paul Duffin Collection<V> result = removeAll(key); 997dd252788645e940eada959bdde927426e2531c9Paul Duffin putAll(key, values); 1007dd252788645e940eada959bdde927426e2531c9Paul Duffin return result; 101dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 1020888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1037dd252788645e940eada959bdde927426e2531c9Paul Duffin private transient Collection<Entry<K, V>> entries; 104dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 1050888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1067dd252788645e940eada959bdde927426e2531c9Paul Duffin public Collection<Entry<K, V>> entries() { 1077dd252788645e940eada959bdde927426e2531c9Paul Duffin Collection<Entry<K, V>> result = entries; 1087dd252788645e940eada959bdde927426e2531c9Paul Duffin return (result == null) ? entries = createEntries() : result; 109dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 1100888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1117dd252788645e940eada959bdde927426e2531c9Paul Duffin Collection<Entry<K, V>> createEntries() { 1127dd252788645e940eada959bdde927426e2531c9Paul Duffin if (this instanceof SetMultimap) { 1130888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new EntrySet(); 1140888a09821a98ac0680fad765217302858e70fa4Paul Duffin } else { 1150888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new Entries(); 1160888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1170888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1180888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1190888a09821a98ac0680fad765217302858e70fa4Paul Duffin private class Entries extends Multimaps.Entries<K, V> { 1200888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1210888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multimap<K, V> multimap() { 1220888a09821a98ac0680fad765217302858e70fa4Paul Duffin return AbstractMultimap.this; 123dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 124dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 1250888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1260888a09821a98ac0680fad765217302858e70fa4Paul Duffin public Iterator<Entry<K, V>> iterator() { 1270888a09821a98ac0680fad765217302858e70fa4Paul Duffin return entryIterator(); 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 129dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 1300888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1310888a09821a98ac0680fad765217302858e70fa4Paul Duffin private class EntrySet extends Entries implements Set<Entry<K, V>> { 1320888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1330888a09821a98ac0680fad765217302858e70fa4Paul Duffin public int hashCode() { 1340888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Sets.hashCodeImpl(this); 1350888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 136dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 1370888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1380888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean equals(@Nullable Object obj) { 1390888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Sets.equalsImpl(this, obj); 1400888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1410888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1420888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1437dd252788645e940eada959bdde927426e2531c9Paul Duffin abstract Iterator<Entry<K, V>> entryIterator(); 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Set<K> keySet; 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1470888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Set<K> keySet() { 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<K> result = keySet; 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (result == null) ? keySet = createKeySet() : result; 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1537dd252788645e940eada959bdde927426e2531c9Paul Duffin Set<K> createKeySet() { 1540888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new Maps.KeySet<K, Collection<V>>(asMap()); 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1560888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1577dd252788645e940eada959bdde927426e2531c9Paul Duffin private transient Multiset<K> keys; 1580888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1590888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Multiset<K> keys() { 1617dd252788645e940eada959bdde927426e2531c9Paul Duffin Multiset<K> result = keys; 1627dd252788645e940eada959bdde927426e2531c9Paul Duffin return (result == null) ? keys = createKeys() : result; 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1640888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1657dd252788645e940eada959bdde927426e2531c9Paul Duffin Multiset<K> createKeys() { 1667dd252788645e940eada959bdde927426e2531c9Paul Duffin return new Multimaps.Keys<K, V>(this); 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1680888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1697dd252788645e940eada959bdde927426e2531c9Paul Duffin private transient Collection<V> values; 1700888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1710888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1727dd252788645e940eada959bdde927426e2531c9Paul Duffin public Collection<V> values() { 1737dd252788645e940eada959bdde927426e2531c9Paul Duffin Collection<V> result = values; 1747dd252788645e940eada959bdde927426e2531c9Paul Duffin return (result == null) ? values = createValues() : result; 175dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 1760888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1777dd252788645e940eada959bdde927426e2531c9Paul Duffin Collection<V> createValues() { 1780888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new Values(); 179dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 180dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 1810888a09821a98ac0680fad765217302858e70fa4Paul Duffin class Values extends AbstractCollection<V> { 1820888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Iterator<V> iterator() { 1830888a09821a98ac0680fad765217302858e70fa4Paul Duffin return valueIterator(); 1840888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1850888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1860888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 1870888a09821a98ac0680fad765217302858e70fa4Paul Duffin return AbstractMultimap.this.size(); 1880888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1890888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1900888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean contains(@Nullable Object o) { 1910888a09821a98ac0680fad765217302858e70fa4Paul Duffin return AbstractMultimap.this.containsValue(o); 1920888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 193dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 1940888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void clear() { 1950888a09821a98ac0680fad765217302858e70fa4Paul Duffin AbstractMultimap.this.clear(); 1960888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1970888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1980888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1990888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterator<V> valueIterator() { 2000888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Maps.valueIterator(entries().iterator()); 2010888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2020888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2030888a09821a98ac0680fad765217302858e70fa4Paul Duffin private transient Map<K, Collection<V>> asMap; 2040888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2050888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Map<K, Collection<V>> asMap() { 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map<K, Collection<V>> result = asMap; 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (result == null) ? asMap = createAsMap() : result; 209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 2100888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2117dd252788645e940eada959bdde927426e2531c9Paul Duffin abstract Map<K, Collection<V>> createAsMap(); 212090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Comparison and hashing 214090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2150888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean equals(@Nullable Object object) { 2160888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Multimaps.equalsImpl(this, object); 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the hash code for this multimap. 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The hash code of a multimap is defined as the hash code of the map view, 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * as returned by {@link Multimap#asMap}. 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @see Map#hashCode 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 2270888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int hashCode() { 2287dd252788645e940eada959bdde927426e2531c9Paul Duffin return asMap().hashCode(); 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a string representation of the multimap, generated by calling 233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code toString} on the map returned by {@link Multimap#asMap}. 234090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a string representation of the multimap 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public String toString() { 2397dd252788645e940eada959bdde927426e2531c9Paul Duffin return asMap().toString(); 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 242