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;
037
038/**
039 * A builder for a multimap implementation that allows customization of the backing map and value
040 * collection implementations used in a particular multimap.
041 *
042 * <p>This can be used to easily configure multimap data structure implementations not provided
043 * explicitly in {@code com.google.common.collect}, for example:
044 *
045 * <pre>{@code
046 * ListMultimap<String, Integer> treeListMultimap =
047 *     MultimapBuilder.treeKeys().arrayListValues().build();
048 * SetMultimap<Integer, MyEnum> hashEnumMultimap =
049 *     MultimapBuilder.hashKeys().enumSetValues(MyEnum.class).build();
050 * }</pre>
051 *
052 * <p>{@code MultimapBuilder} instances are immutable. Invoking a configuration method has no effect
053 * on the receiving instance; you must store and use the new builder instance it returns instead.
054 *
055 * <p>The generated multimaps are serializable if the key and value types are serializable, unless
056 * stated otherwise in one of the configuration methods.
057 *
058 * @author Louis Wasserman
059 * @param <K0> An upper bound on the key type of the generated multimap.
060 * @param <V0> An upper bound on the value type of the generated multimap.
061 * @since 16.0
062 */
063@GwtCompatible
064public abstract class MultimapBuilder<K0, V0> {
065  /*
066   * Leaving K and V as upper bounds rather than the actual key and value types allows type
067   * parameters to be left implicit more often. CacheBuilder uses the same technique.
068   */
069
070  private MultimapBuilder() {}
071
072  private static final int DEFAULT_EXPECTED_KEYS = 8;
073
074  /** Uses a hash table to map keys to value collections. */
075  public static MultimapBuilderWithKeys<Object> hashKeys() {
076    return hashKeys(DEFAULT_EXPECTED_KEYS);
077  }
078
079  /**
080   * Uses a hash table to map keys to value collections, initialized to expect the specified number
081   * of keys.
082   *
083   * @throws IllegalArgumentException if {@code expectedKeys < 0}
084   */
085  public static MultimapBuilderWithKeys<Object> hashKeys(final int expectedKeys) {
086    checkNonnegative(expectedKeys, "expectedKeys");
087    return new MultimapBuilderWithKeys<Object>() {
088      @Override
089      <K, V> Map<K, Collection<V>> createMap() {
090        return Platform.newHashMapWithExpectedSize(expectedKeys);
091      }
092    };
093  }
094
095  /**
096   * Uses a hash table to map keys to value collections.
097   *
098   * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and {@link
099   * 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}