001 /*
002 * Copyright (C) 2009 Google Inc.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkNotNull;
020
021 import com.google.common.annotations.GwtCompatible;
022 import com.google.common.annotations.GwtIncompatible;
023
024 import java.io.IOException;
025 import java.io.InvalidObjectException;
026 import java.io.ObjectInputStream;
027 import java.io.ObjectOutputStream;
028 import java.util.Arrays;
029 import java.util.Collection;
030 import java.util.LinkedHashMap;
031 import java.util.Map;
032
033 import javax.annotation.Nullable;
034
035 /**
036 * An immutable {@link SetMultimap} with reliable user-specified key and value
037 * iteration order. Does not permit null keys or values.
038 *
039 * <p>Unlike {@link Multimaps#unmodifiableSetMultimap(SetMultimap)}, which is
040 * a <i>view</i> of a separate multimap which can still change, an instance of
041 * {@code ImmutableSetMultimap} contains its own data and will <i>never</i>
042 * change. {@code ImmutableSetMultimap} is convenient for
043 * {@code public static final} multimaps ("constant multimaps") and also lets
044 * you easily make a "defensive copy" of a multimap provided to your class by
045 * a caller.
046 *
047 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed as
048 * it has no public or protected constructors. Thus, instances of this class
049 * are guaranteed to be immutable.
050 *
051 * @author Mike Ward
052 * @since 2 (imported from Google Collections Library)
053 */
054 @GwtCompatible(serializable = true, emulated = true)
055 public class ImmutableSetMultimap<K, V>
056 extends ImmutableMultimap<K, V>
057 implements SetMultimap<K, V> {
058
059 /** Returns the empty multimap. */
060 // Casting is safe because the multimap will never hold any elements.
061 @SuppressWarnings("unchecked")
062 public static <K, V> ImmutableSetMultimap<K, V> of() {
063 return (ImmutableSetMultimap<K, V>) EmptyImmutableSetMultimap.INSTANCE;
064 }
065
066 /**
067 * Returns an immutable multimap containing a single entry.
068 */
069 public static <K, V> ImmutableSetMultimap<K, V> of(K k1, V v1) {
070 ImmutableSetMultimap.Builder<K, V> builder = ImmutableSetMultimap.builder();
071 builder.put(k1, v1);
072 return builder.build();
073 }
074
075 /**
076 * Returns an immutable multimap containing the given entries, in order.
077 * Repeated occurrences of an entry (according to {@link Object#equals}) after
078 * the first are ignored.
079 */
080 public static <K, V> ImmutableSetMultimap<K, V> of(K k1, V v1, K k2, V v2) {
081 ImmutableSetMultimap.Builder<K, V> builder = ImmutableSetMultimap.builder();
082 builder.put(k1, v1);
083 builder.put(k2, v2);
084 return builder.build();
085 }
086
087 /**
088 * Returns an immutable multimap containing the given entries, in order.
089 * Repeated occurrences of an entry (according to {@link Object#equals}) after
090 * the first are ignored.
091 */
092 public static <K, V> ImmutableSetMultimap<K, V> of(
093 K k1, V v1, K k2, V v2, K k3, V v3) {
094 ImmutableSetMultimap.Builder<K, V> builder = ImmutableSetMultimap.builder();
095 builder.put(k1, v1);
096 builder.put(k2, v2);
097 builder.put(k3, v3);
098 return builder.build();
099 }
100
101 /**
102 * Returns an immutable multimap containing the given entries, in order.
103 * Repeated occurrences of an entry (according to {@link Object#equals}) after
104 * the first are ignored.
105 */
106 public static <K, V> ImmutableSetMultimap<K, V> of(
107 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
108 ImmutableSetMultimap.Builder<K, V> builder = ImmutableSetMultimap.builder();
109 builder.put(k1, v1);
110 builder.put(k2, v2);
111 builder.put(k3, v3);
112 builder.put(k4, v4);
113 return builder.build();
114 }
115
116 /**
117 * Returns an immutable multimap containing the given entries, in order.
118 * Repeated occurrences of an entry (according to {@link Object#equals}) after
119 * the first are ignored.
120 */
121 public static <K, V> ImmutableSetMultimap<K, V> of(
122 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
123 ImmutableSetMultimap.Builder<K, V> builder = ImmutableSetMultimap.builder();
124 builder.put(k1, v1);
125 builder.put(k2, v2);
126 builder.put(k3, v3);
127 builder.put(k4, v4);
128 builder.put(k5, v5);
129 return builder.build();
130 }
131
132 // looking for of() with > 5 entries? Use the builder instead.
133
134 /**
135 * Returns a new {@link Builder}.
136 */
137 public static <K, V> Builder<K, V> builder() {
138 return new Builder<K, V>();
139 }
140
141 /**
142 * Multimap for {@link ImmutableSetMultimap.Builder} that maintains key
143 * and value orderings and performs better than {@link LinkedHashMultimap}.
144 */
145 private static class BuilderMultimap<K, V> extends AbstractMultimap<K, V> {
146 BuilderMultimap() {
147 super(new LinkedHashMap<K, Collection<V>>());
148 }
149 @Override Collection<V> createCollection() {
150 return Sets.newLinkedHashSet();
151 }
152 private static final long serialVersionUID = 0;
153 }
154
155 /**
156 * A builder for creating immutable {@code SetMultimap} instances, especially
157 * {@code public static final} multimaps ("constant multimaps"). Example:
158 * <pre> {@code
159 *
160 * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
161 * new ImmutableSetMultimap.Builder<String, Integer>()
162 * .put("one", 1)
163 * .putAll("several", 1, 2, 3)
164 * .putAll("many", 1, 2, 3, 4, 5)
165 * .build();}</pre>
166 *
167 * <p>Builder instances can be reused - it is safe to call {@link #build}
168 * multiple times to build multiple multimaps in series. Each multimap
169 * contains the key-value mappings in the previously created multimaps.
170 */
171 public static final class Builder<K, V>
172 extends ImmutableMultimap.Builder<K, V> {
173 private final Multimap<K, V> builderMultimap = new BuilderMultimap<K, V>();
174
175 /**
176 * Creates a new builder. The returned builder is equivalent to the builder
177 * generated by {@link ImmutableSetMultimap#builder}.
178 */
179 public Builder() {}
180
181 /**
182 * Adds a key-value mapping to the built multimap if it is not already
183 * present.
184 */
185 @Override public Builder<K, V> put(K key, V value) {
186 builderMultimap.put(checkNotNull(key), checkNotNull(value));
187 return this;
188 }
189
190 /**
191 * Stores a collection of values with the same key in the built multimap.
192 *
193 * @throws NullPointerException if {@code key}, {@code values}, or any
194 * element in {@code values} is null. The builder is left in an invalid
195 * state.
196 */
197 @Override public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
198 Collection<V> collection = builderMultimap.get(checkNotNull(key));
199 for (V value : values) {
200 collection.add(checkNotNull(value));
201 }
202 return this;
203 }
204
205 /**
206 * Stores an array of values with the same key in the built multimap.
207 *
208 * @throws NullPointerException if the key or any value is null. The
209 * builder is left in an invalid state.
210 */
211 @Override public Builder<K, V> putAll(K key, V... values) {
212 return putAll(key, Arrays.asList(values));
213 }
214
215 /**
216 * Stores another multimap's entries in the built multimap. The generated
217 * multimap's key and value orderings correspond to the iteration ordering
218 * of the {@code multimap.asMap()} view, with new keys and values following
219 * any existing keys and values.
220 *
221 * @throws NullPointerException if any key or value in {@code multimap} is
222 * null. The builder is left in an invalid state.
223 */
224 @Override public Builder<K, V> putAll(
225 Multimap<? extends K, ? extends V> multimap) {
226 for (Map.Entry<? extends K, ? extends Collection<? extends V>> entry
227 : multimap.asMap().entrySet()) {
228 putAll(entry.getKey(), entry.getValue());
229 }
230 return this;
231 }
232
233 /**
234 * Returns a newly-created immutable set multimap.
235 */
236 @Override public ImmutableSetMultimap<K, V> build() {
237 return copyOf(builderMultimap);
238 }
239 }
240
241 /**
242 * Returns an immutable set multimap containing the same mappings as
243 * {@code multimap}. The generated multimap's key and value orderings
244 * correspond to the iteration ordering of the {@code multimap.asMap()} view.
245 * Repeated occurrences of an entry in the multimap after the first are
246 * ignored.
247 *
248 * <p><b>Note:</b> Despite what the method name suggests, if
249 * {@code multimap} is an {@code ImmutableSetMultimap}, no copy will actually
250 * be performed, and the given multimap itself will be returned.
251 *
252 * @throws NullPointerException if any key or value in {@code multimap} is
253 * null
254 */
255 public static <K, V> ImmutableSetMultimap<K, V> copyOf(
256 Multimap<? extends K, ? extends V> multimap) {
257 if (multimap.isEmpty()) {
258 return of();
259 }
260
261 if (multimap instanceof ImmutableSetMultimap) {
262 @SuppressWarnings("unchecked") // safe since multimap is not writable
263 ImmutableSetMultimap<K, V> kvMultimap
264 = (ImmutableSetMultimap<K, V>) multimap;
265 return kvMultimap;
266 }
267
268 ImmutableMap.Builder<K, ImmutableSet<V>> builder = ImmutableMap.builder();
269 int size = 0;
270
271 for (Map.Entry<? extends K, ? extends Collection<? extends V>> entry
272 : multimap.asMap().entrySet()) {
273 K key = entry.getKey();
274 Collection<? extends V> values = entry.getValue();
275 ImmutableSet<V> set = ImmutableSet.copyOf(values);
276 if (!set.isEmpty()) {
277 builder.put(key, set);
278 size += set.size();
279 }
280 }
281
282 return new ImmutableSetMultimap<K, V>(builder.build(), size);
283 }
284
285 ImmutableSetMultimap(ImmutableMap<K, ImmutableSet<V>> map, int size) {
286 super(map, size);
287 }
288
289 // views
290
291 /**
292 * Returns an immutable set of the values for the given key. If no mappings
293 * in the multimap have the provided key, an empty immutable set is returned.
294 * The values are in the same order as the parameters used to build this
295 * multimap.
296 */
297 @Override public ImmutableSet<V> get(@Nullable K key) {
298 // This cast is safe as its type is known in constructor.
299 ImmutableSet<V> set = (ImmutableSet<V>) map.get(key);
300 return (set == null) ? ImmutableSet.<V>of() : set;
301 }
302
303 /**
304 * Guaranteed to throw an exception and leave the multimap unmodified.
305 *
306 * @throws UnsupportedOperationException always
307 */
308 @Override public ImmutableSet<V> removeAll(Object key) {
309 throw new UnsupportedOperationException();
310 }
311
312 /**
313 * Guaranteed to throw an exception and leave the multimap unmodified.
314 *
315 * @throws UnsupportedOperationException always
316 */
317 @Override public ImmutableSet<V> replaceValues(
318 K key, Iterable<? extends V> values) {
319 throw new UnsupportedOperationException();
320 }
321
322 private transient ImmutableSet<Map.Entry<K, V>> entries;
323
324 /**
325 * Returns an immutable collection of all key-value pairs in the multimap.
326 * Its iterator traverses the values for the first key, the values for the
327 * second key, and so on.
328 */
329 // TODO: Fix this so that two copies of the entries are not created.
330 @Override public ImmutableSet<Map.Entry<K, V>> entries() {
331 ImmutableSet<Map.Entry<K, V>> result = entries;
332 return (result == null)
333 ? (entries = ImmutableSet.copyOf(super.entries()))
334 : result;
335 }
336
337 /**
338 * @serialData number of distinct keys, and then for each distinct key: the
339 * key, the number of values for that key, and the key's values
340 */
341 @GwtIncompatible("java.io.ObjectOutputStream")
342 private void writeObject(ObjectOutputStream stream) throws IOException {
343 stream.defaultWriteObject();
344 Serialization.writeMultimap(this, stream);
345 }
346
347 @GwtIncompatible("java.io.ObjectInputStream")
348 private void readObject(ObjectInputStream stream)
349 throws IOException, ClassNotFoundException {
350 stream.defaultReadObject();
351 int keyCount = stream.readInt();
352 if (keyCount < 0) {
353 throw new InvalidObjectException("Invalid key count " + keyCount);
354 }
355 ImmutableMap.Builder<Object, ImmutableSet<Object>> builder
356 = ImmutableMap.builder();
357 int tmpSize = 0;
358
359 for (int i = 0; i < keyCount; i++) {
360 Object key = stream.readObject();
361 int valueCount = stream.readInt();
362 if (valueCount <= 0) {
363 throw new InvalidObjectException("Invalid value count " + valueCount);
364 }
365
366 Object[] array = new Object[valueCount];
367 for (int j = 0; j < valueCount; j++) {
368 array[j] = stream.readObject();
369 }
370 ImmutableSet<Object> valueSet = ImmutableSet.copyOf(array);
371 if (valueSet.size() != array.length) {
372 throw new InvalidObjectException(
373 "Duplicate key-value pairs exist for key " + key);
374 }
375 builder.put(key, valueSet);
376 tmpSize += valueCount;
377 }
378
379 ImmutableMap<Object, ImmutableSet<Object>> tmpMap;
380 try {
381 tmpMap = builder.build();
382 } catch (IllegalArgumentException e) {
383 throw (InvalidObjectException)
384 new InvalidObjectException(e.getMessage()).initCause(e);
385 }
386
387 FieldSettersHolder.MAP_FIELD_SETTER.set(this, tmpMap);
388 FieldSettersHolder.SIZE_FIELD_SETTER.set(this, tmpSize);
389 }
390
391 @GwtIncompatible("not needed in emulated source.")
392 private static final long serialVersionUID = 0;
393 }