001 /*
002 * Copyright (C) 2008 The Guava Authors
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 com.google.common.annotations.Beta;
020 import com.google.common.annotations.GwtCompatible;
021 import com.google.common.annotations.GwtIncompatible;
022
023 import java.io.IOException;
024 import java.io.InvalidObjectException;
025 import java.io.ObjectInputStream;
026 import java.io.ObjectOutputStream;
027 import java.util.Collection;
028 import java.util.Comparator;
029 import java.util.Map.Entry;
030
031 import javax.annotation.Nullable;
032
033 /**
034 * An immutable {@link ListMultimap} with reliable user-specified key and value
035 * iteration order. Does not permit null keys or values.
036 *
037 * <p>Unlike {@link Multimaps#unmodifiableListMultimap(ListMultimap)}, which is
038 * a <i>view</i> of a separate multimap which can still change, an instance of
039 * {@code ImmutableListMultimap} contains its own data and will <i>never</i>
040 * change. {@code ImmutableListMultimap} is convenient for
041 * {@code public static final} multimaps ("constant multimaps") and also lets
042 * you easily make a "defensive copy" of a multimap provided to your class by
043 * a caller.
044 *
045 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
046 * it has no public or protected constructors. Thus, instances of this class
047 * are guaranteed to be immutable.
048 *
049 * @author Jared Levy
050 * @since 2.0 (imported from Google Collections Library)
051 */
052 @GwtCompatible(serializable = true, emulated = true)
053 public class ImmutableListMultimap<K, V>
054 extends ImmutableMultimap<K, V>
055 implements ListMultimap<K, V> {
056
057 /** Returns the empty multimap. */
058 // Casting is safe because the multimap will never hold any elements.
059 @SuppressWarnings("unchecked")
060 public static <K, V> ImmutableListMultimap<K, V> of() {
061 return (ImmutableListMultimap<K, V>) EmptyImmutableListMultimap.INSTANCE;
062 }
063
064 /**
065 * Returns an immutable multimap containing a single entry.
066 */
067 public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1) {
068 ImmutableListMultimap.Builder<K, V> builder
069 = ImmutableListMultimap.builder();
070 builder.put(k1, v1);
071 return builder.build();
072 }
073
074 /**
075 * Returns an immutable multimap containing the given entries, in order.
076 */
077 public static <K, V> ImmutableListMultimap<K, V> of(K k1, V v1, K k2, V v2) {
078 ImmutableListMultimap.Builder<K, V> builder
079 = ImmutableListMultimap.builder();
080 builder.put(k1, v1);
081 builder.put(k2, v2);
082 return builder.build();
083 }
084
085 /**
086 * Returns an immutable multimap containing the given entries, in order.
087 */
088 public static <K, V> ImmutableListMultimap<K, V> of(
089 K k1, V v1, K k2, V v2, K k3, V v3) {
090 ImmutableListMultimap.Builder<K, V> builder
091 = ImmutableListMultimap.builder();
092 builder.put(k1, v1);
093 builder.put(k2, v2);
094 builder.put(k3, v3);
095 return builder.build();
096 }
097
098 /**
099 * Returns an immutable multimap containing the given entries, in order.
100 */
101 public static <K, V> ImmutableListMultimap<K, V> of(
102 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
103 ImmutableListMultimap.Builder<K, V> builder
104 = ImmutableListMultimap.builder();
105 builder.put(k1, v1);
106 builder.put(k2, v2);
107 builder.put(k3, v3);
108 builder.put(k4, v4);
109 return builder.build();
110 }
111
112 /**
113 * Returns an immutable multimap containing the given entries, in order.
114 */
115 public static <K, V> ImmutableListMultimap<K, V> of(
116 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
117 ImmutableListMultimap.Builder<K, V> builder
118 = ImmutableListMultimap.builder();
119 builder.put(k1, v1);
120 builder.put(k2, v2);
121 builder.put(k3, v3);
122 builder.put(k4, v4);
123 builder.put(k5, v5);
124 return builder.build();
125 }
126
127 // looking for of() with > 5 entries? Use the builder instead.
128
129 /**
130 * Returns a new builder. The generated builder is equivalent to the builder
131 * created by the {@link Builder} constructor.
132 */
133 public static <K, V> Builder<K, V> builder() {
134 return new Builder<K, V>();
135 }
136
137 /**
138 * A builder for creating immutable {@code ListMultimap} instances, especially
139 * {@code public static final} multimaps ("constant multimaps"). Example:
140 * <pre> {@code
141 *
142 * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
143 * new ImmutableListMultimap.Builder<String, Integer>()
144 * .put("one", 1)
145 * .putAll("several", 1, 2, 3)
146 * .putAll("many", 1, 2, 3, 4, 5)
147 * .build();}</pre>
148 *
149 * Builder instances can be reused; it is safe to call {@link #build} multiple
150 * times to build multiple multimaps in series. Each multimap contains the
151 * key-value mappings in the previously created multimaps.
152 *
153 * @since 2.0 (imported from Google Collections Library)
154 */
155 public static final class Builder<K, V>
156 extends ImmutableMultimap.Builder<K, V> {
157 /**
158 * Creates a new builder. The returned builder is equivalent to the builder
159 * generated by {@link ImmutableListMultimap#builder}.
160 */
161 public Builder() {}
162
163 @Override public Builder<K, V> put(K key, V value) {
164 super.put(key, value);
165 return this;
166 }
167
168 /**
169 * {@inheritDoc}
170 *
171 * @since 11.0
172 */
173 @Override public Builder<K, V> put(
174 Entry<? extends K, ? extends V> entry) {
175 super.put(entry);
176 return this;
177 }
178
179 @Override public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
180 super.putAll(key, values);
181 return this;
182 }
183
184 @Override public Builder<K, V> putAll(K key, V... values) {
185 super.putAll(key, values);
186 return this;
187 }
188
189 @Override public Builder<K, V> putAll(
190 Multimap<? extends K, ? extends V> multimap) {
191 super.putAll(multimap);
192 return this;
193 }
194
195 /**
196 * {@inheritDoc}
197 *
198 * @since 8.0
199 */
200 @Beta @Override
201 public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
202 super.orderKeysBy(keyComparator);
203 return this;
204 }
205
206 /**
207 * {@inheritDoc}
208 *
209 * @since 8.0
210 */
211 @Beta @Override
212 public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
213 super.orderValuesBy(valueComparator);
214 return this;
215 }
216
217 /**
218 * Returns a newly-created immutable list multimap.
219 */
220 @Override public ImmutableListMultimap<K, V> build() {
221 return (ImmutableListMultimap<K, V>) super.build();
222 }
223 }
224
225 /**
226 * Returns an immutable multimap containing the same mappings as {@code
227 * multimap}. The generated multimap's key and value orderings correspond to
228 * the iteration ordering of the {@code multimap.asMap()} view.
229 *
230 * <p>Despite the method name, this method attempts to avoid actually copying
231 * the data when it is safe to do so. The exact circumstances under which a
232 * copy will or will not be performed are undocumented and subject to change.
233 *
234 * @throws NullPointerException if any key or value in {@code multimap} is
235 * null
236 */
237 public static <K, V> ImmutableListMultimap<K, V> copyOf(
238 Multimap<? extends K, ? extends V> multimap) {
239 if (multimap.isEmpty()) {
240 return of();
241 }
242
243 // TODO(user): copy ImmutableSetMultimap by using asList() on the sets
244 if (multimap instanceof ImmutableListMultimap) {
245 @SuppressWarnings("unchecked") // safe since multimap is not writable
246 ImmutableListMultimap<K, V> kvMultimap
247 = (ImmutableListMultimap<K, V>) multimap;
248 if (!kvMultimap.isPartialView()) {
249 return kvMultimap;
250 }
251 }
252
253 ImmutableMap.Builder<K, ImmutableList<V>> builder = ImmutableMap.builder();
254 int size = 0;
255
256 for (Entry<? extends K, ? extends Collection<? extends V>> entry
257 : multimap.asMap().entrySet()) {
258 ImmutableList<V> list = ImmutableList.copyOf(entry.getValue());
259 if (!list.isEmpty()) {
260 builder.put(entry.getKey(), list);
261 size += list.size();
262 }
263 }
264
265 return new ImmutableListMultimap<K, V>(builder.build(), size);
266 }
267
268 ImmutableListMultimap(ImmutableMap<K, ImmutableList<V>> map, int size) {
269 super(map, size);
270 }
271
272 // views
273
274 /**
275 * Returns an immutable list of the values for the given key. If no mappings
276 * in the multimap have the provided key, an empty immutable list is
277 * returned. The values are in the same order as the parameters used to build
278 * this multimap.
279 */
280 @Override public ImmutableList<V> get(@Nullable K key) {
281 // This cast is safe as its type is known in constructor.
282 ImmutableList<V> list = (ImmutableList<V>) map.get(key);
283 return (list == null) ? ImmutableList.<V>of() : list;
284 }
285
286 private transient ImmutableListMultimap<V, K> inverse;
287
288 /**
289 * {@inheritDoc}
290 *
291 * <p>Because an inverse of a list multimap can contain multiple pairs with the same key and
292 * value, this method returns an {@code ImmutableListMultimap} rather than the
293 * {@code ImmutableMultimap} specified in the {@code ImmutableMultimap} class.
294 *
295 * @since 11
296 */
297 @Beta
298 public ImmutableListMultimap<V, K> inverse() {
299 ImmutableListMultimap<V, K> result = inverse;
300 return (result == null) ? (inverse = invert()) : result;
301 }
302
303 private ImmutableListMultimap<V, K> invert() {
304 Builder<V, K> builder = builder();
305 for (Entry<K, V> entry : entries()) {
306 builder.put(entry.getValue(), entry.getKey());
307 }
308 ImmutableListMultimap<V, K> invertedMultimap = builder.build();
309 invertedMultimap.inverse = this;
310 return invertedMultimap;
311 }
312
313 /**
314 * Guaranteed to throw an exception and leave the multimap unmodified.
315 *
316 * @throws UnsupportedOperationException always
317 */
318 @Override public ImmutableList<V> removeAll(Object key) {
319 throw new UnsupportedOperationException();
320 }
321
322 /**
323 * Guaranteed to throw an exception and leave the multimap unmodified.
324 *
325 * @throws UnsupportedOperationException always
326 */
327 @Override public ImmutableList<V> replaceValues(
328 K key, Iterable<? extends V> values) {
329 throw new UnsupportedOperationException();
330 }
331
332 /**
333 * @serialData number of distinct keys, and then for each distinct key: the
334 * key, the number of values for that key, and the key's values
335 */
336 @GwtIncompatible("java.io.ObjectOutputStream")
337 private void writeObject(ObjectOutputStream stream) throws IOException {
338 stream.defaultWriteObject();
339 Serialization.writeMultimap(this, stream);
340 }
341
342 @GwtIncompatible("java.io.ObjectInputStream")
343 private void readObject(ObjectInputStream stream)
344 throws IOException, ClassNotFoundException {
345 stream.defaultReadObject();
346 int keyCount = stream.readInt();
347 if (keyCount < 0) {
348 throw new InvalidObjectException("Invalid key count " + keyCount);
349 }
350 ImmutableMap.Builder<Object, ImmutableList<Object>> builder
351 = ImmutableMap.builder();
352 int tmpSize = 0;
353
354 for (int i = 0; i < keyCount; i++) {
355 Object key = stream.readObject();
356 int valueCount = stream.readInt();
357 if (valueCount <= 0) {
358 throw new InvalidObjectException("Invalid value count " + valueCount);
359 }
360
361 Object[] array = new Object[valueCount];
362 for (int j = 0; j < valueCount; j++) {
363 array[j] = stream.readObject();
364 }
365 builder.put(key, ImmutableList.copyOf(array));
366 tmpSize += valueCount;
367 }
368
369 ImmutableMap<Object, ImmutableList<Object>> tmpMap;
370 try {
371 tmpMap = builder.build();
372 } catch (IllegalArgumentException e) {
373 throw (InvalidObjectException)
374 new InvalidObjectException(e.getMessage()).initCause(e);
375 }
376
377 FieldSettersHolder.MAP_FIELD_SETTER.set(this, tmpMap);
378 FieldSettersHolder.SIZE_FIELD_SETTER.set(this, tmpSize);
379 }
380
381 @GwtIncompatible("Not needed in emulated source")
382 private static final long serialVersionUID = 0;
383 }