1/* 2 * Copyright (C) 2012 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkNotNull; 20 21import com.google.common.annotations.GwtCompatible; 22 23import java.util.AbstractCollection; 24import java.util.Collection; 25import java.util.Iterator; 26import java.util.Map; 27import java.util.Map.Entry; 28import java.util.Set; 29 30import javax.annotation.Nullable; 31 32/** 33 * A skeleton {@code Multimap} implementation, not necessarily in terms of a {@code Map}. 34 * 35 * @author Louis Wasserman 36 */ 37@GwtCompatible 38abstract class AbstractMultimap<K, V> implements Multimap<K, V> { 39 @Override 40 public boolean isEmpty() { 41 return size() == 0; 42 } 43 44 @Override 45 public boolean containsValue(@Nullable Object value) { 46 for (Collection<V> collection : asMap().values()) { 47 if (collection.contains(value)) { 48 return true; 49 } 50 } 51 52 return false; 53 } 54 55 @Override 56 public boolean containsEntry(@Nullable Object key, @Nullable Object value) { 57 Collection<V> collection = asMap().get(key); 58 return collection != null && collection.contains(value); 59 } 60 61 @Override 62 public boolean remove(@Nullable Object key, @Nullable Object value) { 63 Collection<V> collection = asMap().get(key); 64 return collection != null && collection.remove(value); 65 } 66 67 @Override 68 public boolean put(@Nullable K key, @Nullable V value) { 69 return get(key).add(value); 70 } 71 72 @Override 73 public boolean putAll(@Nullable K key, Iterable<? extends V> values) { 74 checkNotNull(values); 75 // make sure we only call values.iterator() once 76 // and we only call get(key) if values is nonempty 77 if (values instanceof Collection) { 78 Collection<? extends V> valueCollection = (Collection<? extends V>) values; 79 return !valueCollection.isEmpty() && get(key).addAll(valueCollection); 80 } else { 81 Iterator<? extends V> valueItr = values.iterator(); 82 return valueItr.hasNext() && Iterators.addAll(get(key), valueItr); 83 } 84 } 85 86 @Override 87 public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 88 boolean changed = false; 89 for (Map.Entry<? extends K, ? extends V> entry : multimap.entries()) { 90 changed |= put(entry.getKey(), entry.getValue()); 91 } 92 return changed; 93 } 94 95 @Override 96 public Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values) { 97 checkNotNull(values); 98 Collection<V> result = removeAll(key); 99 putAll(key, values); 100 return result; 101 } 102 103 private transient Collection<Entry<K, V>> entries; 104 105 @Override 106 public Collection<Entry<K, V>> entries() { 107 Collection<Entry<K, V>> result = entries; 108 return (result == null) ? entries = createEntries() : result; 109 } 110 111 Collection<Entry<K, V>> createEntries() { 112 if (this instanceof SetMultimap) { 113 return new EntrySet(); 114 } else { 115 return new Entries(); 116 } 117 } 118 119 private class Entries extends Multimaps.Entries<K, V> { 120 @Override 121 Multimap<K, V> multimap() { 122 return AbstractMultimap.this; 123 } 124 125 @Override 126 public Iterator<Entry<K, V>> iterator() { 127 return entryIterator(); 128 } 129 } 130 131 private class EntrySet extends Entries implements Set<Entry<K, V>> { 132 @Override 133 public int hashCode() { 134 return Sets.hashCodeImpl(this); 135 } 136 137 @Override 138 public boolean equals(@Nullable Object obj) { 139 return Sets.equalsImpl(this, obj); 140 } 141 } 142 143 abstract Iterator<Entry<K, V>> entryIterator(); 144 145 private transient Set<K> keySet; 146 147 @Override 148 public Set<K> keySet() { 149 Set<K> result = keySet; 150 return (result == null) ? keySet = createKeySet() : result; 151 } 152 153 Set<K> createKeySet() { 154 return new Maps.KeySet<K, Collection<V>>(asMap()); 155 } 156 157 private transient Multiset<K> keys; 158 159 @Override 160 public Multiset<K> keys() { 161 Multiset<K> result = keys; 162 return (result == null) ? keys = createKeys() : result; 163 } 164 165 Multiset<K> createKeys() { 166 return new Multimaps.Keys<K, V>(this); 167 } 168 169 private transient Collection<V> values; 170 171 @Override 172 public Collection<V> values() { 173 Collection<V> result = values; 174 return (result == null) ? values = createValues() : result; 175 } 176 177 Collection<V> createValues() { 178 return new Values(); 179 } 180 181 class Values extends AbstractCollection<V> { 182 @Override public Iterator<V> iterator() { 183 return valueIterator(); 184 } 185 186 @Override public int size() { 187 return AbstractMultimap.this.size(); 188 } 189 190 @Override public boolean contains(@Nullable Object o) { 191 return AbstractMultimap.this.containsValue(o); 192 } 193 194 @Override public void clear() { 195 AbstractMultimap.this.clear(); 196 } 197 } 198 199 Iterator<V> valueIterator() { 200 return Maps.valueIterator(entries().iterator()); 201 } 202 203 private transient Map<K, Collection<V>> asMap; 204 205 @Override 206 public Map<K, Collection<V>> asMap() { 207 Map<K, Collection<V>> result = asMap; 208 return (result == null) ? asMap = createAsMap() : result; 209 } 210 211 abstract Map<K, Collection<V>> createAsMap(); 212 213 // Comparison and hashing 214 215 @Override public boolean equals(@Nullable Object object) { 216 return Multimaps.equalsImpl(this, object); 217 } 218 219 /** 220 * Returns the hash code for this multimap. 221 * 222 * <p>The hash code of a multimap is defined as the hash code of the map view, 223 * as returned by {@link Multimap#asMap}. 224 * 225 * @see Map#hashCode 226 */ 227 @Override public int hashCode() { 228 return asMap().hashCode(); 229 } 230 231 /** 232 * Returns a string representation of the multimap, generated by calling 233 * {@code toString} on the map returned by {@link Multimap#asMap}. 234 * 235 * @return a string representation of the multimap 236 */ 237 @Override 238 public String toString() { 239 return asMap().toString(); 240 } 241} 242