001/*
002 * Copyright (C) 2013 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
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.CollectPreconditions.checkNonnegative;
021
022import com.google.common.annotations.Beta;
023import com.google.common.annotations.GwtCompatible;
024import com.google.common.base.Supplier;
025
026import java.io.Serializable;
027import java.util.ArrayList;
028import java.util.Collection;
029import java.util.Comparator;
030import java.util.EnumMap;
031import java.util.EnumSet;
032import java.util.HashMap;
033import java.util.HashSet;
034import java.util.LinkedHashMap;
035import java.util.LinkedHashSet;
036import java.util.LinkedList;
037import java.util.List;
038import java.util.Map;
039import java.util.Set;
040import java.util.SortedSet;
041import java.util.TreeMap;
042import java.util.TreeSet;
043
044/**
045 * A builder for a multimap implementation that allows customization of the backing map and value
046 * collection implementations used in a particular multimap.
047 *
048 * <p>This can be used to easily configure multimap data structure implementations not provided
049 * explicitly in {@code com.google.common.collect}, for example:
050 *
051 * <pre>   {@code
052 *   ListMultimap<String, Integer> treeListMultimap =
053 *       MultimapBuilder.treeKeys().arrayListValues().build();
054 *   SetMultimap<Integer, MyEnum> hashEnumMultimap =
055 *       MultimapBuilder.hashKeys().enumSetValues(MyEnum.class).build();}</pre>
056 *
057 * <p>{@code MultimapBuilder} instances are immutable.  Invoking a configuration method has no
058 * effect on the receiving instance; you must store and use the new builder instance it returns
059 * instead.
060 *
061 * <p>The generated multimaps are serializable if the key and value types are serializable,
062 * unless stated otherwise in one of the configuration methods.
063 *
064 * @author Louis Wasserman
065 * @param <K0> An upper bound on the key type of the generated multimap.
066 * @param <V0> An upper bound on the value type of the generated multimap.
067 * @since 16.0
068 */
069@Beta
070@GwtCompatible
071public abstract class MultimapBuilder<K0, V0> {
072  /*
073   * Leaving K and V as upper bounds rather than the actual key and value types allows type
074   * parameters to be left implicit more often. CacheBuilder uses the same technique.
075   */
076
077  private MultimapBuilder() {}
078
079  private static final int DEFAULT_EXPECTED_KEYS = 8;
080
081  /**
082   * Uses a {@link HashMap} to map keys to value collections.
083   */
084  public static MultimapBuilderWithKeys<Object> hashKeys() {
085    return hashKeys(DEFAULT_EXPECTED_KEYS);
086  }
087
088  /**
089   * Uses a {@link HashMap} to map keys to value collections, initialized to expect the specified
090   * number of keys.
091   *
092   * @throws IllegalArgumentException if {@code expectedKeys < 0}
093   */
094  public static MultimapBuilderWithKeys<Object> hashKeys(final int expectedKeys) {
095    checkNonnegative(expectedKeys, "expectedKeys");
096    return new MultimapBuilderWithKeys<Object>() {
097      @Override
098      <K, V> Map<K, Collection<V>> createMap() {
099        return new HashMap<K, Collection<V>>(expectedKeys);
100      }
101    };
102  }
103
104  /**
105   * Uses a {@link LinkedHashMap} to map keys to value collections.
106   *
107   * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and
108   * {@link Multimap#asMap()} will iterate through the keys in the order that they were first added
109   * to the multimap, save that if all values associated with a key are removed and then the key is
110   * added back into the multimap, that key will come last in the key iteration order.
111   */
112  public static MultimapBuilderWithKeys<Object> linkedHashKeys() {
113    return linkedHashKeys(DEFAULT_EXPECTED_KEYS);
114  }
115
116  /**
117   * Uses a {@link LinkedHashMap} to map keys to value collections, initialized to expect the
118   * specified number of keys.
119   *
120   * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and
121   * {@link Multimap#asMap()} will iterate through the keys in the order that they were first added
122   * to the multimap, save that if all values associated with a key are removed and then the key is
123   * added back into the multimap, that key will come last in the key iteration order.
124   */
125  public static MultimapBuilderWithKeys<Object> linkedHashKeys(final int expectedKeys) {
126    checkNonnegative(expectedKeys, "expectedKeys");
127    return new MultimapBuilderWithKeys<Object>() {
128      @Override
129      <K, V> Map<K, Collection<V>> createMap() {
130        return new LinkedHashMap<K, Collection<V>>(expectedKeys);
131      }
132    };
133  }
134
135  /**
136   * Uses a naturally-ordered {@link TreeMap} to map keys to value collections.
137   *
138   * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and
139   * {@link Multimap#asMap()} will iterate through the keys in sorted order.
140   *
141   * <p>For all multimaps generated by the resulting builder, the {@link Multimap#keySet()} can be
142   * safely cast to a {@link java.util.SortedSet}, and the {@link Multimap#asMap()} can safely be
143   * cast to a {@link java.util.SortedMap}.
144   */
145  @SuppressWarnings("rawtypes")
146  public static MultimapBuilderWithKeys<Comparable> treeKeys() {
147    return treeKeys(Ordering.natural());
148  }
149
150  /**
151   * Uses a {@link TreeMap} sorted by the specified comparator to map keys to value collections.
152   *
153   * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and
154   * {@link Multimap#asMap()} will iterate through the keys in sorted order.
155   *
156   * <p>For all multimaps generated by the resulting builder, the {@link Multimap#keySet()} can be
157   * safely cast to a {@link java.util.SortedSet}, and the {@link Multimap#asMap()} can safely be
158   * cast to a {@link java.util.SortedMap}.
159   *
160   * <p>Multimaps generated by the resulting builder will not be serializable if {@code comparator}
161   * is not serializable.
162   */
163  public static <K0> MultimapBuilderWithKeys<K0> treeKeys(final Comparator<K0> comparator) {
164    checkNotNull(comparator);
165    return new MultimapBuilderWithKeys<K0>() {
166      @Override
167      <K extends K0, V> Map<K, Collection<V>> createMap() {
168        return new TreeMap<K, Collection<V>>(comparator);
169      }
170    };
171  }
172
173  /**
174   * Uses an {@link EnumMap} to map keys to value collections.
175   */
176  public static <K0 extends Enum<K0>> MultimapBuilderWithKeys<K0> enumKeys(
177      final Class<K0> keyClass) {
178    checkNotNull(keyClass);
179    return new MultimapBuilderWithKeys<K0>() {
180      @SuppressWarnings("unchecked")
181      @Override
182      <K extends K0, V> Map<K, Collection<V>> createMap() {
183        // K must actually be K0, since enums are effectively final
184        // (their subclasses are inaccessible)
185        return (Map<K, Collection<V>>) new EnumMap<K0, Collection<V>>(keyClass);
186      }
187    };
188  }
189
190  private static final class ArrayListSupplier<V> implements Supplier<List<V>>, Serializable {
191    private final int expectedValuesPerKey;
192
193    ArrayListSupplier(int expectedValuesPerKey) {
194      this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
195    }
196
197    @Override
198    public List<V> get() {
199      return new ArrayList<V>(expectedValuesPerKey);
200    }
201  }
202
203  private enum LinkedListSupplier implements Supplier<List<Object>> {
204    INSTANCE;
205
206    public static <V> Supplier<List<V>> instance() {
207      // Each call generates a fresh LinkedList, which can serve as a List<V> for any V.
208      @SuppressWarnings({"rawtypes", "unchecked"})
209      Supplier<List<V>> result = (Supplier) INSTANCE;
210      return result;
211    }
212
213    @Override
214    public List<Object> get() {
215      return new LinkedList<Object>();
216    }
217  }
218
219  private static final class HashSetSupplier<V> implements Supplier<Set<V>>, Serializable {
220    private final int expectedValuesPerKey;
221
222    HashSetSupplier(int expectedValuesPerKey) {
223      this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
224    }
225
226    @Override
227    public Set<V> get() {
228      return new HashSet<V>(expectedValuesPerKey);
229    }
230  }
231
232  private static final class LinkedHashSetSupplier<V> implements Supplier<Set<V>>, Serializable {
233    private final int expectedValuesPerKey;
234
235    LinkedHashSetSupplier(int expectedValuesPerKey) {
236      this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
237    }
238
239    @Override
240    public Set<V> get() {
241      return new LinkedHashSet<V>(expectedValuesPerKey);
242    }
243  }
244
245  private static final class TreeSetSupplier<V> implements Supplier<SortedSet<V>>, Serializable {
246    private final Comparator<? super V> comparator;
247
248    TreeSetSupplier(Comparator<? super V> comparator) {
249      this.comparator = checkNotNull(comparator);
250    }
251
252    @Override
253    public SortedSet<V> get() {
254      return new TreeSet<V>(comparator);
255    }
256  }
257
258  private static final class EnumSetSupplier<V extends Enum<V>>
259      implements Supplier<Set<V>>, Serializable {
260    private final Class<V> clazz;
261
262    EnumSetSupplier(Class<V> clazz) {
263      this.clazz = checkNotNull(clazz);
264    }
265
266    @Override
267    public Set<V> get() {
268      return EnumSet.noneOf(clazz);
269    }
270  }
271
272  /**
273   * An intermediate stage in a {@link MultimapBuilder} in which the key-value collection map
274   * implementation has been specified, but the value collection implementation has not.
275   *
276   * @param <K0> The upper bound on the key type of the generated multimap.
277   */
278  public abstract static class MultimapBuilderWithKeys<K0> {
279
280    private static final int DEFAULT_EXPECTED_VALUES_PER_KEY = 2;
281
282    MultimapBuilderWithKeys() {}
283
284    abstract <K extends K0, V> Map<K, Collection<V>> createMap();
285
286    /**
287     * Uses an {@link ArrayList} to store value collections.
288     */
289    public ListMultimapBuilder<K0, Object> arrayListValues() {
290      return arrayListValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
291    }
292
293    /**
294     * Uses an {@link ArrayList} to store value collections, initialized to expect the specified
295     * number of values per key.
296     *
297     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
298     */
299    public ListMultimapBuilder<K0, Object> arrayListValues(final int expectedValuesPerKey) {
300      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
301      return new ListMultimapBuilder<K0, Object>() {
302        @Override
303        public <K extends K0, V> ListMultimap<K, V> build() {
304          return Multimaps.newListMultimap(
305              MultimapBuilderWithKeys.this.<K, V>createMap(),
306              new ArrayListSupplier<V>(expectedValuesPerKey));
307        }
308      };
309    }
310
311    /**
312     * Uses a {@link LinkedList} to store value collections.
313     */
314    public ListMultimapBuilder<K0, Object> linkedListValues() {
315      return new ListMultimapBuilder<K0, Object>() {
316        @Override
317        public <K extends K0, V> ListMultimap<K, V> build() {
318          return Multimaps.newListMultimap(
319              MultimapBuilderWithKeys.this.<K, V>createMap(),
320              LinkedListSupplier.<V>instance());
321        }
322      };
323    }
324
325    /**
326     * Uses a {@link HashSet} to store value collections.
327     */
328    public SetMultimapBuilder<K0, Object> hashSetValues() {
329      return hashSetValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
330    }
331
332    /**
333     * Uses a {@link HashSet} to store value collections, initialized to expect the specified number
334     * of values per key.
335     *
336     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
337     */
338    public SetMultimapBuilder<K0, Object> hashSetValues(final int expectedValuesPerKey) {
339      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
340      return new SetMultimapBuilder<K0, Object>() {
341        @Override
342        public <K extends K0, V> SetMultimap<K, V> build() {
343          return Multimaps.newSetMultimap(
344              MultimapBuilderWithKeys.this.<K, V>createMap(),
345              new HashSetSupplier<V>(expectedValuesPerKey));
346        }
347      };
348    }
349
350    /**
351     * Uses a {@link LinkedHashSet} to store value collections.
352     */
353    public SetMultimapBuilder<K0, Object> linkedHashSetValues() {
354      return linkedHashSetValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
355    }
356
357    /**
358     * Uses a {@link LinkedHashSet} to store value collections, initialized to expect the specified
359     * number of values per key.
360     *
361     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
362     */
363    public SetMultimapBuilder<K0, Object> linkedHashSetValues(final int expectedValuesPerKey) {
364      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
365      return new SetMultimapBuilder<K0, Object>() {
366        @Override
367        public <K extends K0, V> SetMultimap<K, V> build() {
368          return Multimaps.newSetMultimap(
369              MultimapBuilderWithKeys.this.<K, V>createMap(),
370              new LinkedHashSetSupplier<V>(expectedValuesPerKey));
371        }
372      };
373    }
374
375    /**
376     * Uses a naturally-ordered {@link TreeSet} to store value collections.
377     */
378    @SuppressWarnings("rawtypes")
379    public SortedSetMultimapBuilder<K0, Comparable> treeSetValues() {
380      return treeSetValues(Ordering.natural());
381    }
382
383    /**
384     * Uses a {@link TreeSet} ordered by the specified comparator to store value collections.
385     *
386     * <p>Multimaps generated by the resulting builder will not be serializable if
387     * {@code comparator} is not serializable.
388     */
389    public <V0> SortedSetMultimapBuilder<K0, V0> treeSetValues(final Comparator<V0> comparator) {
390      checkNotNull(comparator, "comparator");
391      return new SortedSetMultimapBuilder<K0, V0>() {
392        @Override
393        public <K extends K0, V extends V0> SortedSetMultimap<K, V> build() {
394          return Multimaps.newSortedSetMultimap(
395              MultimapBuilderWithKeys.this.<K, V>createMap(),
396              new TreeSetSupplier<V>(comparator));
397        }
398      };
399    }
400
401    /**
402     * Uses an {@link EnumSet} to store value collections.
403     */
404    public <V0 extends Enum<V0>> SetMultimapBuilder<K0, V0> enumSetValues(
405        final Class<V0> valueClass) {
406      checkNotNull(valueClass, "valueClass");
407      return new SetMultimapBuilder<K0, V0>() {
408        @Override
409        public <K extends K0, V extends V0> SetMultimap<K, V> build() {
410          // V must actually be V0, since enums are effectively final
411          // (their subclasses are inaccessible)
412          @SuppressWarnings({"unchecked", "rawtypes"})
413          Supplier<Set<V>> factory = (Supplier) new EnumSetSupplier<V0>(valueClass);
414          return Multimaps.newSetMultimap(
415              MultimapBuilderWithKeys.this.<K, V>createMap(),
416              factory);
417        }
418      };
419    }
420  }
421
422  /**
423   * Returns a new, empty {@code Multimap} with the specified implementation.
424   */
425  public abstract <K extends K0, V extends V0> Multimap<K, V> build();
426
427  /**
428   * Returns a {@code Multimap} with the specified implementation, initialized with the entries of
429   * {@code multimap}.
430   */
431  public <K extends K0, V extends V0> Multimap<K, V> build(
432      Multimap<? extends K, ? extends V> multimap) {
433    Multimap<K, V> result = build();
434    result.putAll(multimap);
435    return result;
436  }
437
438  /**
439   * A specialization of {@link MultimapBuilder} that generates {@link ListMultimap} instances.
440   */
441  public abstract static class ListMultimapBuilder<K0, V0> extends MultimapBuilder<K0, V0> {
442    ListMultimapBuilder() {}
443
444    @Override
445    public abstract <K extends K0, V extends V0> ListMultimap<K, V> build();
446
447    @Override
448    public <K extends K0, V extends V0> ListMultimap<K, V> build(
449        Multimap<? extends K, ? extends V> multimap) {
450      return (ListMultimap<K, V>) super.build(multimap);
451    }
452  }
453
454  /**
455   * A specialization of {@link MultimapBuilder} that generates {@link SetMultimap} instances.
456   */
457  public abstract static class SetMultimapBuilder<K0, V0> extends MultimapBuilder<K0, V0> {
458    SetMultimapBuilder() {}
459
460    @Override
461    public abstract <K extends K0, V extends V0> SetMultimap<K, V> build();
462
463    @Override
464    public <K extends K0, V extends V0> SetMultimap<K, V> build(
465        Multimap<? extends K, ? extends V> multimap) {
466      return (SetMultimap<K, V>) super.build(multimap);
467    }
468  }
469
470  /**
471   * A specialization of {@link MultimapBuilder} that generates {@link SortedSetMultimap} instances.
472   */
473  public abstract static class SortedSetMultimapBuilder<K0, V0> extends SetMultimapBuilder<K0, V0> {
474    SortedSetMultimapBuilder() {}
475
476    @Override
477    public abstract <K extends K0, V extends V0> SortedSetMultimap<K, V> build();
478
479    @Override
480    public <K extends K0, V extends V0> SortedSetMultimap<K, V> build(
481        Multimap<? extends K, ? extends V> multimap) {
482      return (SortedSetMultimap<K, V>) super.build(multimap);
483    }
484  }
485}