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
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20
21 import com.google.common.annotations.GwtCompatible;
22 import com.google.errorprone.annotations.CanIgnoreReturnValue;
23 import com.google.errorprone.annotations.concurrent.LazyInit;
24 import com.google.j2objc.annotations.WeakOuter;
25 import java.util.AbstractCollection;
26 import java.util.Collection;
27 import java.util.Iterator;
28 import java.util.Map;
29 import java.util.Map.Entry;
30 import java.util.Set;
31 import java.util.Spliterator;
32 import java.util.Spliterators;
33 import org.checkerframework.checker.nullness.qual.Nullable;
34
35 /**
36 * A skeleton {@code Multimap} implementation, not necessarily in terms of a {@code Map}.
37 *
38 * @author Louis Wasserman
39 */
40 @GwtCompatible
41 abstract class AbstractMultimap<K, V> implements Multimap<K, V> {
42 @Override
43 public boolean isEmpty() {
44 return size() == 0;
45 }
46
47 @Override
48 public boolean containsValue(@Nullable Object value) {
49 for (Collection<V> collection : asMap().values()) {
50 if (collection.contains(value)) {
51 return true;
52 }
53 }
54
55 return false;
56 }
57
58 @Override
59 public boolean containsEntry(@Nullable Object key, @Nullable Object value) {
60 Collection<V> collection = asMap().get(key);
61 return collection != null && collection.contains(value);
62 }
63
64 @CanIgnoreReturnValue
65 @Override
66 public boolean remove(@Nullable Object key, @Nullable Object value) {
67 Collection<V> collection = asMap().get(key);
68 return collection != null && collection.remove(value);
69 }
70
71 @CanIgnoreReturnValue
72 @Override
73 public boolean put(@Nullable K key, @Nullable V value) {
74 return get(key).add(value);
75 }
76
77 @CanIgnoreReturnValue
78 @Override
79 public boolean putAll(@Nullable K key, Iterable<? extends V> values) {
80 checkNotNull(values);
81 // make sure we only call values.iterator() once
82 // and we only call get(key) if values is nonempty
83 if (values instanceof Collection) {
84 Collection<? extends V> valueCollection = (Collection<? extends V>) values;
85 return !valueCollection.isEmpty() && get(key).addAll(valueCollection);
86 } else {
87 Iterator<? extends V> valueItr = values.iterator();
88 return valueItr.hasNext() && Iterators.addAll(get(key), valueItr);
89 }
90 }
91
92 @CanIgnoreReturnValue
93 @Override
94 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
95 boolean changed = false;
96 for (Entry<? extends K, ? extends V> entry : multimap.entries()) {
97 changed |= put(entry.getKey(), entry.getValue());
98 }
99 return changed;
100 }
101
102 @CanIgnoreReturnValue
103 @Override
104 public Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
105 checkNotNull(values);
106 Collection<V> result = removeAll(key);
107 putAll(key, values);
108 return result;
109 }
110
111 @LazyInit private transient @Nullable Collection<Entry<K, V>> entries;
112
113 @Override
114 public Collection<Entry<K, V>> entries() {
115 Collection<Entry<K, V>> result = entries;
116 return (result == null) ? entries = createEntries() : result;
117 }
118
119 abstract Collection<Entry<K, V>> createEntries();
120
121 @WeakOuter
122 class Entries extends Multimaps.Entries<K, V> {
123 @Override
124 Multimap<K, V> multimap() {
125 return AbstractMultimap.this;
126 }
127
128 @Override
129 public Iterator<Entry<K, V>> iterator() {
130 return entryIterator();
131 }
132
133 @Override
134 public Spliterator<Entry<K, V>> spliterator() {
135 return entrySpliterator();
136 }
137 }
138
139 @WeakOuter
140 class EntrySet extends Entries implements Set<Entry<K, V>> {
141 @Override
142 public int hashCode() {
143 return Sets.hashCodeImpl(this);
144 }
145
146 @Override
147 public boolean equals(@Nullable Object obj) {
148 return Sets.equalsImpl(this, obj);
149 }
150 }
151
152 abstract Iterator<Entry<K, V>> entryIterator();
153
154 Spliterator<Entry<K, V>> entrySpliterator() {
155 return Spliterators.spliterator(
156 entryIterator(), size(), (this instanceof SetMultimap) ? Spliterator.DISTINCT : 0);
157 }
158
159 @LazyInit private transient @Nullable Set<K> keySet;
160
161 @Override
162 public Set<K> keySet() {
163 Set<K> result = keySet;
164 return (result == null) ? keySet = createKeySet() : result;
165 }
166
167 abstract Set<K> createKeySet();
168
169 @LazyInit private transient @Nullable Multiset<K> keys;
170
171 @Override
172 public Multiset<K> keys() {
173 Multiset<K> result = keys;
174 return (result == null) ? keys = createKeys() : result;
175 }
176
177 abstract Multiset<K> createKeys();
178
179 @LazyInit private transient @Nullable Collection<V> values;
180
181 @Override
182 public Collection<V> values() {
183 Collection<V> result = values;
184 return (result == null) ? values = createValues() : result;
185 }
186
187 abstract Collection<V> createValues();
188
189 @WeakOuter
190 class Values extends AbstractCollection<V> {
191 @Override
192 public Iterator<V> iterator() {
193 return valueIterator();
194 }
195
196 @Override
197 public Spliterator<V> spliterator() {
198 return valueSpliterator();
199 }
200
201 @Override
202 public int size() {
203 return AbstractMultimap.this.size();
204 }
205
206 @Override
207 public boolean contains(@Nullable Object o) {
208 return AbstractMultimap.this.containsValue(o);
209 }
210
211 @Override
212 public void clear() {
213 AbstractMultimap.this.clear();
214 }
215 }
216
217 Iterator<V> valueIterator() {
218 return Maps.valueIterator(entries().iterator());
219 }
220
221 Spliterator<V> valueSpliterator() {
222 return Spliterators.spliterator(valueIterator(), size(), 0);
223 }
224
225 @LazyInit private transient @Nullable Map<K, Collection<V>> asMap;
226
227 @Override
228 public Map<K, Collection<V>> asMap() {
229 Map<K, Collection<V>> result = asMap;
230 return (result == null) ? asMap = createAsMap() : result;
231 }
232
233 abstract Map<K, Collection<V>> createAsMap();
234
235 // Comparison and hashing
236
237 @Override
238 public boolean equals(@Nullable Object object) {
239 return Multimaps.equalsImpl(this, object);
240 }
241
242 /**
243 * Returns the hash code for this multimap.
244 *
245 * <p>The hash code of a multimap is defined as the hash code of the map view, as returned by
246 * {@link Multimap#asMap}.
247 *
248 * @see Map#hashCode
249 */
250 @Override
251 public int hashCode() {
252 return asMap().hashCode();
253 }
254
255 /**
256 * Returns a string representation of the multimap, generated by calling {@code toString} on the
257 * map returned by {@link Multimap#asMap}.
258 *
259 * @return a string representation of the multimap
260 */
261 @Override
262 public String toString() {
263 return asMap().toString();
264 }
265 }