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;
025import java.io.Serializable;
026import java.util.ArrayList;
027import java.util.Collection;
028import java.util.Comparator;
029import java.util.EnumMap;
030import java.util.EnumSet;
031import java.util.LinkedList;
032import java.util.List;
033import java.util.Map;
034import java.util.Set;
035import java.util.SortedSet;
036import java.util.TreeMap;
037import java.util.TreeSet;
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@Beta
065@GwtCompatible
066public abstract class MultimapBuilder<K0, V0> {
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<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
083   * number of keys.
084   *
085   * @throws IllegalArgumentException if {@code expectedKeys < 0}
086   */
087  public static MultimapBuilderWithKeys<Object> hashKeys(final int expectedKeys) {
088    checkNonnegative(expectedKeys, "expectedKeys");
089    return new MultimapBuilderWithKeys<Object>() {
090      @Override
091      <K, V> 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<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
111   * specified number 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<Object> linkedHashKeys(final int expectedKeys) {
119    checkNonnegative(expectedKeys, "expectedKeys");
120    return new MultimapBuilderWithKeys<Object>() {
121      @Override
122      <K, V> 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> MultimapBuilderWithKeys<K0> treeKeys(final Comparator<K0> comparator) {
157    checkNotNull(comparator);
158    return new MultimapBuilderWithKeys<K0>() {
159      @Override
160      <K extends K0, V> Map<K, Collection<V>> createMap() {
161        return new TreeMap<>(comparator);
162      }
163    };
164  }
165
166  /**
167   * Uses an {@link EnumMap} to map keys to value collections.
168   *
169   * @since 16.0
170   */
171  public static <K0 extends Enum<K0>> MultimapBuilderWithKeys<K0> enumKeys(
172      final Class<K0> keyClass) {
173    checkNotNull(keyClass);
174    return new MultimapBuilderWithKeys<K0>() {
175      @SuppressWarnings("unchecked")
176      @Override
177      <K extends K0, V> 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> implements Supplier<List<V>>, Serializable {
186    private final int expectedValuesPerKey;
187
188    ArrayListSupplier(int expectedValuesPerKey) {
189      this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
190    }
191
192    @Override
193    public List<V> get() {
194      return new ArrayList<V>(expectedValuesPerKey);
195    }
196  }
197
198  private enum LinkedListSupplier implements Supplier<List<Object>> {
199    INSTANCE;
200
201    public static <V> Supplier<List<V>> instance() {
202      // Each call generates a fresh LinkedList, which can serve as a List<V> for any V.
203      @SuppressWarnings({"rawtypes", "unchecked"})
204      Supplier<List<V>> result = (Supplier) INSTANCE;
205      return result;
206    }
207
208    @Override
209    public List<Object> get() {
210      return new LinkedList<>();
211    }
212  }
213
214  private static final class HashSetSupplier<V> implements Supplier<Set<V>>, Serializable {
215    private final int expectedValuesPerKey;
216
217    HashSetSupplier(int expectedValuesPerKey) {
218      this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
219    }
220
221    @Override
222    public Set<V> get() {
223      return Platform.newHashSetWithExpectedSize(expectedValuesPerKey);
224    }
225  }
226  
227  private static final class LinkedHashSetSupplier<V> implements Supplier<Set<V>>, Serializable {
228    private final int expectedValuesPerKey;
229
230    LinkedHashSetSupplier(int expectedValuesPerKey) {
231      this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
232    }
233
234    @Override
235    public Set<V> get() {
236      return Platform.newLinkedHashSetWithExpectedSize(expectedValuesPerKey);
237    }
238  }
239
240  private static final class TreeSetSupplier<V> implements Supplier<SortedSet<V>>, Serializable {
241    private final Comparator<? super V> comparator;
242
243    TreeSetSupplier(Comparator<? super V> comparator) {
244      this.comparator = checkNotNull(comparator);
245    }
246
247    @Override
248    public SortedSet<V> get() {
249      return new TreeSet<V>(comparator);
250    }
251  }
252
253  private static final class EnumSetSupplier<V extends Enum<V>>
254      implements Supplier<Set<V>>, Serializable {
255    private final Class<V> clazz;
256
257    EnumSetSupplier(Class<V> clazz) {
258      this.clazz = checkNotNull(clazz);
259    }
260
261    @Override
262    public Set<V> get() {
263      return EnumSet.noneOf(clazz);
264    }
265  }
266
267  /**
268   * An intermediate stage in a {@link MultimapBuilder} in which the key-value collection map
269   * implementation has been specified, but the value collection implementation has not.
270   *
271   * @param <K0> The upper bound on the key type of the generated multimap.
272   * @since 16.0
273   */
274  public abstract static class MultimapBuilderWithKeys<K0> {
275
276    private static final int DEFAULT_EXPECTED_VALUES_PER_KEY = 2;
277
278    MultimapBuilderWithKeys() {}
279
280    abstract <K extends K0, V> Map<K, Collection<V>> createMap();
281
282    /** Uses an {@link ArrayList} to store value collections. */
283    public ListMultimapBuilder<K0, Object> arrayListValues() {
284      return arrayListValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
285    }
286
287    /**
288     * Uses an {@link ArrayList} to store value collections, initialized to expect the specified
289     * number of values per key.
290     *
291     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
292     */
293    public ListMultimapBuilder<K0, Object> arrayListValues(final int expectedValuesPerKey) {
294      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
295      return new ListMultimapBuilder<K0, Object>() {
296        @Override
297        public <K extends K0, V> ListMultimap<K, V> build() {
298          return Multimaps.newListMultimap(
299              MultimapBuilderWithKeys.this.<K, V>createMap(),
300              new ArrayListSupplier<V>(expectedValuesPerKey));
301        }
302      };
303    }
304
305    /** Uses a {@link LinkedList} to store value collections. */
306    public ListMultimapBuilder<K0, Object> linkedListValues() {
307      return new ListMultimapBuilder<K0, Object>() {
308        @Override
309        public <K extends K0, V> ListMultimap<K, V> build() {
310          return Multimaps.newListMultimap(
311              MultimapBuilderWithKeys.this.<K, V>createMap(), LinkedListSupplier.<V>instance());
312        }
313      };
314    }
315
316    /** Uses a hash-based {@code Set} to store value collections. */
317    public SetMultimapBuilder<K0, Object> hashSetValues() {
318      return hashSetValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
319    }
320
321    /**
322     * Uses a hash-based {@code Set} to store value collections, initialized to expect the specified number
323     * of values per key.
324     *
325     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
326     */
327    public SetMultimapBuilder<K0, Object> hashSetValues(final int expectedValuesPerKey) {
328      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
329      return new SetMultimapBuilder<K0, Object>() {
330        @Override
331        public <K extends K0, V> SetMultimap<K, V> build() {
332          return Multimaps.newSetMultimap(
333              MultimapBuilderWithKeys.this.<K, V>createMap(),
334              new HashSetSupplier<V>(expectedValuesPerKey));
335        }
336      };
337    }
338
339    /** Uses an insertion-ordered hash-based {@code Set} to store value collections. */
340    public SetMultimapBuilder<K0, Object> linkedHashSetValues() {
341      return linkedHashSetValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
342    }
343
344    /**
345     * Uses an insertion-ordered hash-based {@code Set} to store value collections, initialized to expect the specified
346     * number of values per key.
347     *
348     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
349     */
350    public SetMultimapBuilder<K0, Object> linkedHashSetValues(final int expectedValuesPerKey) {
351      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
352      return new SetMultimapBuilder<K0, Object>() {
353        @Override
354        public <K extends K0, V> SetMultimap<K, V> build() {
355          return Multimaps.newSetMultimap(
356              MultimapBuilderWithKeys.this.<K, V>createMap(),
357              new LinkedHashSetSupplier<V>(expectedValuesPerKey));
358        }
359      };
360    }
361
362    /** Uses a naturally-ordered {@link TreeSet} to store value collections. */
363    @SuppressWarnings("rawtypes")
364    public SortedSetMultimapBuilder<K0, Comparable> treeSetValues() {
365      return treeSetValues(Ordering.natural());
366    }
367
368    /**
369     * Uses a {@link TreeSet} ordered by the specified comparator to store value collections.
370     *
371     * <p>Multimaps generated by the resulting builder will not be serializable if {@code
372     * comparator} is not serializable.
373     */
374    public <V0> SortedSetMultimapBuilder<K0, V0> treeSetValues(final Comparator<V0> comparator) {
375      checkNotNull(comparator, "comparator");
376      return new SortedSetMultimapBuilder<K0, V0>() {
377        @Override
378        public <K extends K0, V extends V0> SortedSetMultimap<K, V> build() {
379          return Multimaps.newSortedSetMultimap(
380              MultimapBuilderWithKeys.this.<K, V>createMap(), new TreeSetSupplier<V>(comparator));
381        }
382      };
383    }
384
385    /** Uses an {@link EnumSet} to store value collections. */
386    public <V0 extends Enum<V0>> SetMultimapBuilder<K0, V0> enumSetValues(
387        final Class<V0> valueClass) {
388      checkNotNull(valueClass, "valueClass");
389      return new SetMultimapBuilder<K0, V0>() {
390        @Override
391        public <K extends K0, V extends V0> SetMultimap<K, V> build() {
392          // V must actually be V0, since enums are effectively final
393          // (their subclasses are inaccessible)
394          @SuppressWarnings({"unchecked", "rawtypes"})
395          Supplier<Set<V>> factory = (Supplier) new EnumSetSupplier<V0>(valueClass);
396          return Multimaps.newSetMultimap(MultimapBuilderWithKeys.this.<K, V>createMap(), factory);
397        }
398      };
399    }
400  }
401
402  /** Returns a new, empty {@code Multimap} with the specified implementation. */
403  public abstract <K extends K0, V extends V0> Multimap<K, V> build();
404
405  /**
406   * Returns a {@code Multimap} with the specified implementation, initialized with the entries of
407   * {@code multimap}.
408   */
409  public <K extends K0, V extends V0> Multimap<K, V> build(
410      Multimap<? extends K, ? extends V> multimap) {
411    Multimap<K, V> result = build();
412    result.putAll(multimap);
413    return result;
414  }
415
416  /**
417   * A specialization of {@link MultimapBuilder} that generates {@link ListMultimap} instances.
418   *
419   * @since 16.0
420   */
421  public abstract static class ListMultimapBuilder<K0, V0> extends MultimapBuilder<K0, V0> {
422    ListMultimapBuilder() {}
423
424    @Override
425    public abstract <K extends K0, V extends V0> ListMultimap<K, V> build();
426
427    @Override
428    public <K extends K0, V extends V0> ListMultimap<K, V> build(
429        Multimap<? extends K, ? extends V> multimap) {
430      return (ListMultimap<K, V>) super.build(multimap);
431    }
432  }
433
434  /**
435   * A specialization of {@link MultimapBuilder} that generates {@link SetMultimap} instances.
436   *
437   * @since 16.0
438   */
439  public abstract static class SetMultimapBuilder<K0, V0> extends MultimapBuilder<K0, V0> {
440    SetMultimapBuilder() {}
441
442    @Override
443    public abstract <K extends K0, V extends V0> SetMultimap<K, V> build();
444
445    @Override
446    public <K extends K0, V extends V0> SetMultimap<K, V> build(
447        Multimap<? extends K, ? extends V> multimap) {
448      return (SetMultimap<K, V>) super.build(multimap);
449    }
450  }
451
452  /**
453   * A specialization of {@link MultimapBuilder} that generates {@link SortedSetMultimap} instances.
454   *
455   * @since 16.0
456   */
457  public abstract static class SortedSetMultimapBuilder<K0, V0> extends SetMultimapBuilder<K0, V0> {
458    SortedSetMultimapBuilder() {}
459
460    @Override
461    public abstract <K extends K0, V extends V0> SortedSetMultimap<K, V> build();
462
463    @Override
464    public <K extends K0, V extends V0> SortedSetMultimap<K, V> build(
465        Multimap<? extends K, ? extends V> multimap) {
466      return (SortedSetMultimap<K, V>) super.build(multimap);
467    }
468  }
469}