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