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;
021import static com.google.common.collect.Maps.newLinkedHashMapWithExpectedSize;
022
023import com.google.common.annotations.Beta;
024import com.google.common.annotations.GwtCompatible;
025import com.google.common.base.Supplier;
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 Maps.newHashMapWithExpectedSize(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 newLinkedHashMapWithExpectedSize(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<>(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<>();
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 Sets.newHashSetWithExpectedSize(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 Sets.newLinkedHashSetWithExpectedSize(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(), LinkedListSupplier.<V>instance());
320        }
321      };
322    }
323
324    /**
325     * Uses a {@link HashSet} to store value collections.
326     */
327    public SetMultimapBuilder<K0, Object> hashSetValues() {
328      return hashSetValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
329    }
330
331    /**
332     * Uses a {@link HashSet} to store value collections, initialized to expect the specified number
333     * of values per key.
334     *
335     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
336     */
337    public SetMultimapBuilder<K0, Object> hashSetValues(final int expectedValuesPerKey) {
338      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
339      return new SetMultimapBuilder<K0, Object>() {
340        @Override
341        public <K extends K0, V> SetMultimap<K, V> build() {
342          return Multimaps.newSetMultimap(
343              MultimapBuilderWithKeys.this.<K, V>createMap(),
344              new HashSetSupplier<V>(expectedValuesPerKey));
345        }
346      };
347    }
348
349    /**
350     * Uses a {@link LinkedHashSet} to store value collections.
351     */
352    public SetMultimapBuilder<K0, Object> linkedHashSetValues() {
353      return linkedHashSetValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
354    }
355
356    /**
357     * Uses a {@link LinkedHashSet} to store value collections, initialized to expect the specified
358     * number of values per key.
359     *
360     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
361     */
362    public SetMultimapBuilder<K0, Object> linkedHashSetValues(final int expectedValuesPerKey) {
363      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
364      return new SetMultimapBuilder<K0, Object>() {
365        @Override
366        public <K extends K0, V> SetMultimap<K, V> build() {
367          return Multimaps.newSetMultimap(
368              MultimapBuilderWithKeys.this.<K, V>createMap(),
369              new LinkedHashSetSupplier<V>(expectedValuesPerKey));
370        }
371      };
372    }
373
374    /**
375     * Uses a naturally-ordered {@link TreeSet} to store value collections.
376     */
377    @SuppressWarnings("rawtypes")
378    public SortedSetMultimapBuilder<K0, Comparable> treeSetValues() {
379      return treeSetValues(Ordering.natural());
380    }
381
382    /**
383     * Uses a {@link TreeSet} ordered by the specified comparator to store value collections.
384     *
385     * <p>Multimaps generated by the resulting builder will not be serializable if
386     * {@code comparator} is not serializable.
387     */
388    public <V0> SortedSetMultimapBuilder<K0, V0> treeSetValues(final Comparator<V0> comparator) {
389      checkNotNull(comparator, "comparator");
390      return new SortedSetMultimapBuilder<K0, V0>() {
391        @Override
392        public <K extends K0, V extends V0> SortedSetMultimap<K, V> build() {
393          return Multimaps.newSortedSetMultimap(
394              MultimapBuilderWithKeys.this.<K, V>createMap(), new TreeSetSupplier<V>(comparator));
395        }
396      };
397    }
398
399    /**
400     * Uses an {@link EnumSet} to store value collections.
401     */
402    public <V0 extends Enum<V0>> SetMultimapBuilder<K0, V0> enumSetValues(
403        final Class<V0> valueClass) {
404      checkNotNull(valueClass, "valueClass");
405      return new SetMultimapBuilder<K0, V0>() {
406        @Override
407        public <K extends K0, V extends V0> SetMultimap<K, V> build() {
408          // V must actually be V0, since enums are effectively final
409          // (their subclasses are inaccessible)
410          @SuppressWarnings({"unchecked", "rawtypes"})
411          Supplier<Set<V>> factory = (Supplier) new EnumSetSupplier<V0>(valueClass);
412          return Multimaps.newSetMultimap(MultimapBuilderWithKeys.this.<K, V>createMap(), factory);
413        }
414      };
415    }
416  }
417
418  /**
419   * Returns a new, empty {@code Multimap} with the specified implementation.
420   */
421  public abstract <K extends K0, V extends V0> Multimap<K, V> build();
422
423  /**
424   * Returns a {@code Multimap} with the specified implementation, initialized with the entries of
425   * {@code multimap}.
426   */
427  public <K extends K0, V extends V0> Multimap<K, V> build(
428      Multimap<? extends K, ? extends V> multimap) {
429    Multimap<K, V> result = build();
430    result.putAll(multimap);
431    return result;
432  }
433
434  /**
435   * A specialization of {@link MultimapBuilder} that generates {@link ListMultimap} instances.
436   */
437  public abstract static class ListMultimapBuilder<K0, V0> extends MultimapBuilder<K0, V0> {
438    ListMultimapBuilder() {}
439
440    @Override
441    public abstract <K extends K0, V extends V0> ListMultimap<K, V> build();
442
443    @Override
444    public <K extends K0, V extends V0> ListMultimap<K, V> build(
445        Multimap<? extends K, ? extends V> multimap) {
446      return (ListMultimap<K, V>) super.build(multimap);
447    }
448  }
449
450  /**
451   * A specialization of {@link MultimapBuilder} that generates {@link SetMultimap} instances.
452   */
453  public abstract static class SetMultimapBuilder<K0, V0> extends MultimapBuilder<K0, V0> {
454    SetMultimapBuilder() {}
455
456    @Override
457    public abstract <K extends K0, V extends V0> SetMultimap<K, V> build();
458
459    @Override
460    public <K extends K0, V extends V0> SetMultimap<K, V> build(
461        Multimap<? extends K, ? extends V> multimap) {
462      return (SetMultimap<K, V>) super.build(multimap);
463    }
464  }
465
466  /**
467   * A specialization of {@link MultimapBuilder} that generates {@link SortedSetMultimap} instances.
468   */
469  public abstract static class SortedSetMultimapBuilder<K0, V0> extends SetMultimapBuilder<K0, V0> {
470    SortedSetMultimapBuilder() {}
471
472    @Override
473    public abstract <K extends K0, V extends V0> SortedSetMultimap<K, V> build();
474
475    @Override
476    public <K extends K0, V extends V0> SortedSetMultimap<K, V> build(
477        Multimap<? extends K, ? extends V> multimap) {
478      return (SortedSetMultimap<K, V>) super.build(multimap);
479    }
480  }
481}