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