1 /*
2 * Copyright (C) 2013 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 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
21
22 import com.google.common.annotations.GwtCompatible;
23 import com.google.common.base.Supplier;
24 import java.io.Serializable;
25 import java.util.ArrayList;
26 import java.util.Collection;
27 import java.util.Comparator;
28 import java.util.EnumMap;
29 import java.util.EnumSet;
30 import java.util.LinkedList;
31 import java.util.List;
32 import java.util.Map;
33 import java.util.Set;
34 import java.util.SortedSet;
35 import java.util.TreeMap;
36 import java.util.TreeSet;
37
38 /**
39 * A builder for a multimap implementation that allows customization of the backing map and value
40 * collection implementations used in a particular multimap.
41 *
42 * <p>This can be used to easily configure multimap data structure implementations not provided
43 * explicitly in {@code com.google.common.collect}, for example:
44 *
45 * <pre>{@code
46 * ListMultimap<String, Integer> treeListMultimap =
47 * MultimapBuilder.treeKeys().arrayListValues().build();
48 * SetMultimap<Integer, MyEnum> hashEnumMultimap =
49 * MultimapBuilder.hashKeys().enumSetValues(MyEnum.class).build();
50 * }</pre>
51 *
52 * <p>{@code MultimapBuilder} instances are immutable. Invoking a configuration method has no effect
53 * on the receiving instance; you must store and use the new builder instance it returns instead.
54 *
55 * <p>The generated multimaps are serializable if the key and value types are serializable, unless
56 * stated otherwise in one of the configuration methods.
57 *
58 * @author Louis Wasserman
59 * @param <K0> An upper bound on the key type of the generated multimap.
60 * @param <V0> An upper bound on the value type of the generated multimap.
61 * @since 16.0
62 */
63 @GwtCompatible
64 public abstract class MultimapBuilder<K0, V0> {
65 /*
66 * Leaving K and V as upper bounds rather than the actual key and value types allows type
67 * parameters to be left implicit more often. CacheBuilder uses the same technique.
68 */
69
70 private MultimapBuilder() {}
71
72 private static final int DEFAULT_EXPECTED_KEYS = 8;
73
74 /** Uses a hash table to map keys to value collections. */
75 public static MultimapBuilderWithKeys<Object> hashKeys() {
76 return hashKeys(DEFAULT_EXPECTED_KEYS);
77 }
78
79 /**
80 * Uses a hash table to map keys to value collections, initialized to expect the specified number
81 * of keys.
82 *
83 * @throws IllegalArgumentException if {@code expectedKeys < 0}
84 */
85 public static MultimapBuilderWithKeys<Object> hashKeys(final int expectedKeys) {
86 checkNonnegative(expectedKeys, "expectedKeys");
87 return new MultimapBuilderWithKeys<Object>() {
88 @Override
89 <K, V> Map<K, Collection<V>> createMap() {
90 return Platform.newHashMapWithExpectedSize(expectedKeys);
91 }
92 };
93 }
94
95 /**
96 * Uses a hash table to map keys to value collections.
97 *
98 * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and {@link
99 * Multimap#asMap()} will iterate through the keys in the order that they were first added to the
100 * multimap, save that if all values associated with a key are removed and then the key is added
101 * back into the multimap, that key will come last in the key iteration order.
102 */
103 public static MultimapBuilderWithKeys<Object> linkedHashKeys() {
104 return linkedHashKeys(DEFAULT_EXPECTED_KEYS);
105 }
106
107 /**
108 * Uses an hash table to map keys to value collections, initialized to expect the specified number
109 * of keys.
110 *
111 * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and {@link
112 * Multimap#asMap()} will iterate through the keys in the order that they were first added to the
113 * multimap, save that if all values associated with a key are removed and then the key is added
114 * back into the multimap, that key will come last in the key iteration order.
115 */
116 public static MultimapBuilderWithKeys<Object> linkedHashKeys(final int expectedKeys) {
117 checkNonnegative(expectedKeys, "expectedKeys");
118 return new MultimapBuilderWithKeys<Object>() {
119 @Override
120 <K, V> Map<K, Collection<V>> createMap() {
121 return Platform.newLinkedHashMapWithExpectedSize(expectedKeys);
122 }
123 };
124 }
125
126 /**
127 * Uses a naturally-ordered {@link TreeMap} to map keys to value collections.
128 *
129 * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and {@link
130 * Multimap#asMap()} will iterate through the keys in sorted order.
131 *
132 * <p>For all multimaps generated by the resulting builder, the {@link Multimap#keySet()} can be
133 * safely cast to a {@link java.util.SortedSet}, and the {@link Multimap#asMap()} can safely be
134 * cast to a {@link java.util.SortedMap}.
135 */
136 @SuppressWarnings("rawtypes")
137 public static MultimapBuilderWithKeys<Comparable> treeKeys() {
138 return treeKeys(Ordering.natural());
139 }
140
141 /**
142 * Uses a {@link TreeMap} sorted by the specified comparator to map keys to value collections.
143 *
144 * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and {@link
145 * Multimap#asMap()} will iterate through the keys in sorted order.
146 *
147 * <p>For all multimaps generated by the resulting builder, the {@link Multimap#keySet()} can be
148 * safely cast to a {@link java.util.SortedSet}, and the {@link Multimap#asMap()} can safely be
149 * cast to a {@link java.util.SortedMap}.
150 *
151 * <p>Multimaps generated by the resulting builder will not be serializable if {@code comparator}
152 * is not serializable.
153 */
154 public static <K0> MultimapBuilderWithKeys<K0> treeKeys(final Comparator<K0> comparator) {
155 checkNotNull(comparator);
156 return new MultimapBuilderWithKeys<K0>() {
157 @Override
158 <K extends K0, V> Map<K, Collection<V>> createMap() {
159 return new TreeMap<>(comparator);
160 }
161 };
162 }
163
164 /**
165 * Uses an {@link EnumMap} to map keys to value collections.
166 *
167 * @since 16.0
168 */
169 public static <K0 extends Enum<K0>> MultimapBuilderWithKeys<K0> enumKeys(
170 final Class<K0> keyClass) {
171 checkNotNull(keyClass);
172 return new MultimapBuilderWithKeys<K0>() {
173 @SuppressWarnings("unchecked")
174 @Override
175 <K extends K0, V> Map<K, Collection<V>> createMap() {
176 // K must actually be K0, since enums are effectively final
177 // (their subclasses are inaccessible)
178 return (Map<K, Collection<V>>) new EnumMap<K0, Collection<V>>(keyClass);
179 }
180 };
181 }
182
183 private static final class ArrayListSupplier<V> implements Supplier<List<V>>, Serializable {
184 private final int expectedValuesPerKey;
185
186 ArrayListSupplier(int expectedValuesPerKey) {
187 this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
188 }
189
190 @Override
191 public List<V> get() {
192 return new ArrayList<V>(expectedValuesPerKey);
193 }
194 }
195
196 private enum LinkedListSupplier implements Supplier<List<Object>> {
197 INSTANCE;
198
199 public static <V> Supplier<List<V>> instance() {
200 // Each call generates a fresh LinkedList, which can serve as a List<V> for any V.
201 @SuppressWarnings({"rawtypes", "unchecked"})
202 Supplier<List<V>> result = (Supplier) INSTANCE;
203 return result;
204 }
205
206 @Override
207 public List<Object> get() {
208 return new LinkedList<>();
209 }
210 }
211
212 private static final class HashSetSupplier<V> implements Supplier<Set<V>>, Serializable {
213 private final int expectedValuesPerKey;
214
215 HashSetSupplier(int expectedValuesPerKey) {
216 this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
217 }
218
219 @Override
220 public Set<V> get() {
221 return Platform.newHashSetWithExpectedSize(expectedValuesPerKey);
222 }
223 }
224
225 private static final class LinkedHashSetSupplier<V> implements Supplier<Set<V>>, Serializable {
226 private final int expectedValuesPerKey;
227
228 LinkedHashSetSupplier(int expectedValuesPerKey) {
229 this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
230 }
231
232 @Override
233 public Set<V> get() {
234 return Platform.newLinkedHashSetWithExpectedSize(expectedValuesPerKey);
235 }
236 }
237
238 private static final class TreeSetSupplier<V> implements Supplier<SortedSet<V>>, Serializable {
239 private final Comparator<? super V> comparator;
240
241 TreeSetSupplier(Comparator<? super V> comparator) {
242 this.comparator = checkNotNull(comparator);
243 }
244
245 @Override
246 public SortedSet<V> get() {
247 return new TreeSet<V>(comparator);
248 }
249 }
250
251 private static final class EnumSetSupplier<V extends Enum<V>>
252 implements Supplier<Set<V>>, Serializable {
253 private final Class<V> clazz;
254
255 EnumSetSupplier(Class<V> clazz) {
256 this.clazz = checkNotNull(clazz);
257 }
258
259 @Override
260 public Set<V> get() {
261 return EnumSet.noneOf(clazz);
262 }
263 }
264
265 /**
266 * An intermediate stage in a {@link MultimapBuilder} in which the key-value collection map
267 * implementation has been specified, but the value collection implementation has not.
268 *
269 * @param <K0> The upper bound on the key type of the generated multimap.
270 * @since 16.0
271 */
272 public abstract static class MultimapBuilderWithKeys<K0> {
273
274 private static final int DEFAULT_EXPECTED_VALUES_PER_KEY = 2;
275
276 MultimapBuilderWithKeys() {}
277
278 abstract <K extends K0, V> Map<K, Collection<V>> createMap();
279
280 /** Uses an {@link ArrayList} to store value collections. */
281 public ListMultimapBuilder<K0, Object> arrayListValues() {
282 return arrayListValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
283 }
284
285 /**
286 * Uses an {@link ArrayList} to store value collections, initialized to expect the specified
287 * number of values per key.
288 *
289 * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
290 */
291 public ListMultimapBuilder<K0, Object> arrayListValues(final int expectedValuesPerKey) {
292 checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
293 return new ListMultimapBuilder<K0, Object>() {
294 @Override
295 public <K extends K0, V> ListMultimap<K, V> build() {
296 return Multimaps.newListMultimap(
297 MultimapBuilderWithKeys.this.<K, V>createMap(),
298 new ArrayListSupplier<V>(expectedValuesPerKey));
299 }
300 };
301 }
302
303 /** Uses a {@link LinkedList} to store value collections. */
304 public ListMultimapBuilder<K0, Object> linkedListValues() {
305 return new ListMultimapBuilder<K0, Object>() {
306 @Override
307 public <K extends K0, V> ListMultimap<K, V> build() {
308 return Multimaps.newListMultimap(
309 MultimapBuilderWithKeys.this.<K, V>createMap(), LinkedListSupplier.<V>instance());
310 }
311 };
312 }
313
314 /** Uses a hash-based {@code Set} to store value collections. */
315 public SetMultimapBuilder<K0, Object> hashSetValues() {
316 return hashSetValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
317 }
318
319 /**
320 * Uses a hash-based {@code Set} to store value collections, initialized to expect the specified
321 * number of values per key.
322 *
323 * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
324 */
325 public SetMultimapBuilder<K0, Object> hashSetValues(final int expectedValuesPerKey) {
326 checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
327 return new SetMultimapBuilder<K0, Object>() {
328 @Override
329 public <K extends K0, V> SetMultimap<K, V> build() {
330 return Multimaps.newSetMultimap(
331 MultimapBuilderWithKeys.this.<K, V>createMap(),
332 new HashSetSupplier<V>(expectedValuesPerKey));
333 }
334 };
335 }
336
337 /** Uses an insertion-ordered hash-based {@code Set} to store value collections. */
338 public SetMultimapBuilder<K0, Object> linkedHashSetValues() {
339 return linkedHashSetValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
340 }
341
342 /**
343 * Uses an insertion-ordered hash-based {@code Set} to store value collections, initialized to
344 * expect the specified number of values per key.
345 *
346 * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
347 */
348 public SetMultimapBuilder<K0, Object> linkedHashSetValues(final int expectedValuesPerKey) {
349 checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
350 return new SetMultimapBuilder<K0, Object>() {
351 @Override
352 public <K extends K0, V> SetMultimap<K, V> build() {
353 return Multimaps.newSetMultimap(
354 MultimapBuilderWithKeys.this.<K, V>createMap(),
355 new LinkedHashSetSupplier<V>(expectedValuesPerKey));
356 }
357 };
358 }
359
360 /** Uses a naturally-ordered {@link TreeSet} to store value collections. */
361 @SuppressWarnings("rawtypes")
362 public SortedSetMultimapBuilder<K0, Comparable> treeSetValues() {
363 return treeSetValues(Ordering.natural());
364 }
365
366 /**
367 * Uses a {@link TreeSet} ordered by the specified comparator to store value collections.
368 *
369 * <p>Multimaps generated by the resulting builder will not be serializable if {@code
370 * comparator} is not serializable.
371 */
372 public <V0> SortedSetMultimapBuilder<K0, V0> treeSetValues(final Comparator<V0> comparator) {
373 checkNotNull(comparator, "comparator");
374 return new SortedSetMultimapBuilder<K0, V0>() {
375 @Override
376 public <K extends K0, V extends V0> SortedSetMultimap<K, V> build() {
377 return Multimaps.newSortedSetMultimap(
378 MultimapBuilderWithKeys.this.<K, V>createMap(), new TreeSetSupplier<V>(comparator));
379 }
380 };
381 }
382
383 /** Uses an {@link EnumSet} to store value collections. */
384 public <V0 extends Enum<V0>> SetMultimapBuilder<K0, V0> enumSetValues(
385 final Class<V0> valueClass) {
386 checkNotNull(valueClass, "valueClass");
387 return new SetMultimapBuilder<K0, V0>() {
388 @Override
389 public <K extends K0, V extends V0> SetMultimap<K, V> build() {
390 // V must actually be V0, since enums are effectively final
391 // (their subclasses are inaccessible)
392 @SuppressWarnings({"unchecked", "rawtypes"})
393 Supplier<Set<V>> factory = (Supplier) new EnumSetSupplier<V0>(valueClass);
394 return Multimaps.newSetMultimap(MultimapBuilderWithKeys.this.<K, V>createMap(), factory);
395 }
396 };
397 }
398 }
399
400 /** Returns a new, empty {@code Multimap} with the specified implementation. */
401 public abstract <K extends K0, V extends V0> Multimap<K, V> build();
402
403 /**
404 * Returns a {@code Multimap} with the specified implementation, initialized with the entries of
405 * {@code multimap}.
406 */
407 public <K extends K0, V extends V0> Multimap<K, V> build(
408 Multimap<? extends K, ? extends V> multimap) {
409 Multimap<K, V> result = build();
410 result.putAll(multimap);
411 return result;
412 }
413
414 /**
415 * A specialization of {@link MultimapBuilder} that generates {@link ListMultimap} instances.
416 *
417 * @since 16.0
418 */
419 public abstract static class ListMultimapBuilder<K0, V0> extends MultimapBuilder<K0, V0> {
420 ListMultimapBuilder() {}
421
422 @Override
423 public abstract <K extends K0, V extends V0> ListMultimap<K, V> build();
424
425 @Override
426 public <K extends K0, V extends V0> ListMultimap<K, V> build(
427 Multimap<? extends K, ? extends V> multimap) {
428 return (ListMultimap<K, V>) super.build(multimap);
429 }
430 }
431
432 /**
433 * A specialization of {@link MultimapBuilder} that generates {@link SetMultimap} instances.
434 *
435 * @since 16.0
436 */
437 public abstract static class SetMultimapBuilder<K0, V0> extends MultimapBuilder<K0, V0> {
438 SetMultimapBuilder() {}
439
440 @Override
441 public abstract <K extends K0, V extends V0> SetMultimap<K, V> build();
442
443 @Override
444 public <K extends K0, V extends V0> SetMultimap<K, V> build(
445 Multimap<? extends K, ? extends V> multimap) {
446 return (SetMultimap<K, V>) super.build(multimap);
447 }
448 }
449
450 /**
451 * A specialization of {@link MultimapBuilder} that generates {@link SortedSetMultimap} instances.
452 *
453 * @since 16.0
454 */
455 public abstract static class SortedSetMultimapBuilder<K0, V0> extends SetMultimapBuilder<K0, V0> {
456 SortedSetMultimapBuilder() {}
457
458 @Override
459 public abstract <K extends K0, V extends V0> SortedSetMultimap<K, V> build();
460
461 @Override
462 public <K extends K0, V extends V0> SortedSetMultimap<K, V> build(
463 Multimap<? extends K, ? extends V> multimap) {
464 return (SortedSetMultimap<K, V>) super.build(multimap);
465 }
466 }
467 }