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;
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 @Override public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
169 super.putAll(key, values);
170 return this;
171 }
172
173 @Override public Builder<K, V> putAll(K key, V... values) {
174 super.putAll(key, values);
175 return this;
176 }
177
178 @Override public Builder<K, V> putAll(
179 Multimap<? extends K, ? extends V> multimap) {
180 super.putAll(multimap);
181 return this;
182 }
183
184 /**
185 * {@inheritDoc}
186 *
187 * @since 8.0
188 */
189 @Beta @Override
190 public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
191 super.orderKeysBy(keyComparator);
192 return this;
193 }
194
195 /**
196 * {@inheritDoc}
197 *
198 * @since 8.0
199 */
200 @Beta @Override
201 public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
202 super.orderValuesBy(valueComparator);
203 return this;
204 }
205
206 /**
207 * Returns a newly-created immutable list multimap.
208 */
209 @Override public ImmutableListMultimap<K, V> build() {
210 return (ImmutableListMultimap<K, V>) super.build();
211 }
212 }
213
214 /**
215 * Returns an immutable multimap containing the same mappings as {@code
216 * multimap}. The generated multimap's key and value orderings correspond to
217 * the iteration ordering of the {@code multimap.asMap()} view.
218 *
219 * <p>Despite the method name, this method attempts to avoid actually copying
220 * the data when it is safe to do so. The exact circumstances under which a
221 * copy will or will not be performed are undocumented and subject to change.
222 *
223 * @throws NullPointerException if any key or value in {@code multimap} is
224 * null
225 */
226 public static <K, V> ImmutableListMultimap<K, V> copyOf(
227 Multimap<? extends K, ? extends V> multimap) {
228 if (multimap.isEmpty()) {
229 return of();
230 }
231
232 // TODO(user): copy ImmutableSetMultimap by using asList() on the sets
233 if (multimap instanceof ImmutableListMultimap) {
234 @SuppressWarnings("unchecked") // safe since multimap is not writable
235 ImmutableListMultimap<K, V> kvMultimap
236 = (ImmutableListMultimap<K, V>) multimap;
237 if (!kvMultimap.isPartialView()) {
238 return kvMultimap;
239 }
240 }
241
242 ImmutableMap.Builder<K, ImmutableList<V>> builder = ImmutableMap.builder();
243 int size = 0;
244
245 for (Map.Entry<? extends K, ? extends Collection<? extends V>> entry
246 : multimap.asMap().entrySet()) {
247 ImmutableList<V> list = ImmutableList.copyOf(entry.getValue());
248 if (!list.isEmpty()) {
249 builder.put(entry.getKey(), list);
250 size += list.size();
251 }
252 }
253
254 return new ImmutableListMultimap<K, V>(builder.build(), size);
255 }
256
257 ImmutableListMultimap(ImmutableMap<K, ImmutableList<V>> map, int size) {
258 super(map, size);
259 }
260
261 // views
262
263 /**
264 * Returns an immutable list of the values for the given key. If no mappings
265 * in the multimap have the provided key, an empty immutable list is
266 * returned. The values are in the same order as the parameters used to build
267 * this multimap.
268 */
269 @Override public ImmutableList<V> get(@Nullable K key) {
270 // This cast is safe as its type is known in constructor.
271 ImmutableList<V> list = (ImmutableList<V>) map.get(key);
272 return (list == null) ? ImmutableList.<V>of() : list;
273 }
274
275 /**
276 * Guaranteed to throw an exception and leave the multimap unmodified.
277 *
278 * @throws UnsupportedOperationException always
279 */
280 @Override public ImmutableList<V> removeAll(Object key) {
281 throw new UnsupportedOperationException();
282 }
283
284 /**
285 * Guaranteed to throw an exception and leave the multimap unmodified.
286 *
287 * @throws UnsupportedOperationException always
288 */
289 @Override public ImmutableList<V> replaceValues(
290 K key, Iterable<? extends V> values) {
291 throw new UnsupportedOperationException();
292 }
293
294 /**
295 * @serialData number of distinct keys, and then for each distinct key: the
296 * key, the number of values for that key, and the key's values
297 */
298 @GwtIncompatible("java.io.ObjectOutputStream")
299 private void writeObject(ObjectOutputStream stream) throws IOException {
300 stream.defaultWriteObject();
301 Serialization.writeMultimap(this, stream);
302 }
303
304 @GwtIncompatible("java.io.ObjectInputStream")
305 private void readObject(ObjectInputStream stream)
306 throws IOException, ClassNotFoundException {
307 stream.defaultReadObject();
308 int keyCount = stream.readInt();
309 if (keyCount < 0) {
310 throw new InvalidObjectException("Invalid key count " + keyCount);
311 }
312 ImmutableMap.Builder<Object, ImmutableList<Object>> builder
313 = ImmutableMap.builder();
314 int tmpSize = 0;
315
316 for (int i = 0; i < keyCount; i++) {
317 Object key = stream.readObject();
318 int valueCount = stream.readInt();
319 if (valueCount <= 0) {
320 throw new InvalidObjectException("Invalid value count " + valueCount);
321 }
322
323 Object[] array = new Object[valueCount];
324 for (int j = 0; j < valueCount; j++) {
325 array[j] = stream.readObject();
326 }
327 builder.put(key, ImmutableList.copyOf(array));
328 tmpSize += valueCount;
329 }
330
331 ImmutableMap<Object, ImmutableList<Object>> tmpMap;
332 try {
333 tmpMap = builder.build();
334 } catch (IllegalArgumentException e) {
335 throw (InvalidObjectException)
336 new InvalidObjectException(e.getMessage()).initCause(e);
337 }
338
339 FieldSettersHolder.MAP_FIELD_SETTER.set(this, tmpMap);
340 FieldSettersHolder.SIZE_FIELD_SETTER.set(this, tmpSize);
341 }
342
343 @GwtIncompatible("Not needed in emulated source")
344 private static final long serialVersionUID = 0;
345 }