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(final 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(final 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      final 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(
173      final Class<K0> keyClass) {
174    checkNotNull(keyClass);
175    return new MultimapBuilderWithKeys<K0>() {
176      @SuppressWarnings("unchecked")
177      @Override
178      <K extends K0, V extends @Nullable Object> Map<K, Collection<V>> createMap() {
179        // K must actually be K0, since enums are effectively final
180        // (their subclasses are inaccessible)
181        return (Map<K, Collection<V>>) new EnumMap<K0, Collection<V>>(keyClass);
182      }
183    };
184  }
185
186  private static final class ArrayListSupplier<V extends @Nullable Object>
187      implements Supplier<List<V>>, Serializable {
188    private final int expectedValuesPerKey;
189
190    ArrayListSupplier(int expectedValuesPerKey) {
191      this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
192    }
193
194    @Override
195    public List<V> get() {
196      return new ArrayList<V>(expectedValuesPerKey);
197    }
198  }
199
200  private enum LinkedListSupplier implements Supplier<List<?>> {
201    INSTANCE;
202
203    public static <V extends @Nullable Object> Supplier<List<V>> instance() {
204      // Each call generates a fresh LinkedList, which can serve as a List<V> for any V.
205      @SuppressWarnings({"rawtypes", "unchecked"})
206      Supplier<List<V>> result = (Supplier) INSTANCE;
207      return result;
208    }
209
210    @Override
211    public List<?> get() {
212      return new LinkedList<>();
213    }
214  }
215
216  private static final class HashSetSupplier<V extends @Nullable Object>
217      implements Supplier<Set<V>>, Serializable {
218    private final int expectedValuesPerKey;
219
220    HashSetSupplier(int expectedValuesPerKey) {
221      this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
222    }
223
224    @Override
225    public Set<V> get() {
226      return Platform.newHashSetWithExpectedSize(expectedValuesPerKey);
227    }
228  }
229
230  private static final class LinkedHashSetSupplier<V extends @Nullable Object>
231      implements Supplier<Set<V>>, Serializable {
232    private final int expectedValuesPerKey;
233
234    LinkedHashSetSupplier(int expectedValuesPerKey) {
235      this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
236    }
237
238    @Override
239    public Set<V> get() {
240      return Platform.newLinkedHashSetWithExpectedSize(expectedValuesPerKey);
241    }
242  }
243
244  private static final class TreeSetSupplier<V extends @Nullable Object>
245      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   * @since 16.0
278   */
279  public abstract static class MultimapBuilderWithKeys<K0 extends @Nullable Object> {
280
281    private static final int DEFAULT_EXPECTED_VALUES_PER_KEY = 2;
282
283    MultimapBuilderWithKeys() {}
284
285    abstract <K extends K0, V extends @Nullable Object> Map<K, Collection<V>> createMap();
286
287    /** Uses an {@link ArrayList} to store value collections. */
288    public ListMultimapBuilder<K0, @Nullable Object> arrayListValues() {
289      return arrayListValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
290    }
291
292    /**
293     * Uses an {@link ArrayList} to store value collections, initialized to expect the specified
294     * number of values per key.
295     *
296     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
297     */
298    public ListMultimapBuilder<K0, @Nullable Object> arrayListValues(
299        final int expectedValuesPerKey) {
300      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
301      return new ListMultimapBuilder<K0, @Nullable Object>() {
302        @Override
303        public <K extends K0, V extends @Nullable Object> ListMultimap<K, V> build() {
304          return Multimaps.newListMultimap(
305              MultimapBuilderWithKeys.this.<K, V>createMap(),
306              new ArrayListSupplier<V>(expectedValuesPerKey));
307        }
308      };
309    }
310
311    /** Uses a {@link LinkedList} to store value collections. */
312    public ListMultimapBuilder<K0, @Nullable Object> linkedListValues() {
313      return new ListMultimapBuilder<K0, @Nullable Object>() {
314        @Override
315        public <K extends K0, V extends @Nullable Object> ListMultimap<K, V> build() {
316          return Multimaps.newListMultimap(
317              MultimapBuilderWithKeys.this.<K, V>createMap(), LinkedListSupplier.<V>instance());
318        }
319      };
320    }
321
322    /** Uses a hash-based {@code Set} to store value collections. */
323    public SetMultimapBuilder<K0, @Nullable Object> hashSetValues() {
324      return hashSetValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
325    }
326
327    /**
328     * Uses a hash-based {@code Set} to store value collections, initialized to expect the specified
329     * number of values per key.
330     *
331     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
332     */
333    public SetMultimapBuilder<K0, @Nullable Object> hashSetValues(final int expectedValuesPerKey) {
334      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
335      return new SetMultimapBuilder<K0, @Nullable Object>() {
336        @Override
337        public <K extends K0, V extends @Nullable Object> SetMultimap<K, V> build() {
338          return Multimaps.newSetMultimap(
339              MultimapBuilderWithKeys.this.<K, V>createMap(),
340              new HashSetSupplier<V>(expectedValuesPerKey));
341        }
342      };
343    }
344
345    /** Uses an insertion-ordered hash-based {@code Set} to store value collections. */
346    public SetMultimapBuilder<K0, @Nullable Object> linkedHashSetValues() {
347      return linkedHashSetValues(DEFAULT_EXPECTED_VALUES_PER_KEY);
348    }
349
350    /**
351     * Uses an insertion-ordered hash-based {@code Set} to store value collections, initialized to
352     * expect the specified number of values per key.
353     *
354     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
355     */
356    public SetMultimapBuilder<K0, @Nullable Object> linkedHashSetValues(
357        final int expectedValuesPerKey) {
358      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
359      return new SetMultimapBuilder<K0, @Nullable Object>() {
360        @Override
361        public <K extends K0, V extends @Nullable Object> SetMultimap<K, V> build() {
362          return Multimaps.newSetMultimap(
363              MultimapBuilderWithKeys.this.<K, V>createMap(),
364              new LinkedHashSetSupplier<V>(expectedValuesPerKey));
365        }
366      };
367    }
368
369    /** Uses a naturally-ordered {@link TreeSet} to store value collections. */
370    @SuppressWarnings("rawtypes")
371    public SortedSetMultimapBuilder<K0, Comparable> treeSetValues() {
372      return treeSetValues(Ordering.natural());
373    }
374
375    /**
376     * Uses a {@link TreeSet} ordered by the specified comparator to store value collections.
377     *
378     * <p>Multimaps generated by the resulting builder will not be serializable if {@code
379     * comparator} is not serializable.
380     */
381    public <V0 extends @Nullable Object> SortedSetMultimapBuilder<K0, V0> treeSetValues(
382        final Comparator<V0> comparator) {
383      checkNotNull(comparator, "comparator");
384      return new SortedSetMultimapBuilder<K0, V0>() {
385        @Override
386        public <K extends K0, V extends V0> SortedSetMultimap<K, V> build() {
387          return Multimaps.newSortedSetMultimap(
388              MultimapBuilderWithKeys.this.<K, V>createMap(), new TreeSetSupplier<V>(comparator));
389        }
390      };
391    }
392
393    /** Uses an {@link EnumSet} to store value collections. */
394    public <V0 extends Enum<V0>> SetMultimapBuilder<K0, V0> enumSetValues(
395        final Class<V0> valueClass) {
396      checkNotNull(valueClass, "valueClass");
397      return new SetMultimapBuilder<K0, V0>() {
398        @Override
399        public <K extends K0, V extends V0> SetMultimap<K, V> build() {
400          // V must actually be V0, since enums are effectively final
401          // (their subclasses are inaccessible)
402          @SuppressWarnings({"unchecked", "rawtypes"})
403          Supplier<Set<V>> factory = (Supplier) new EnumSetSupplier<V0>(valueClass);
404          return Multimaps.newSetMultimap(MultimapBuilderWithKeys.this.<K, V>createMap(), factory);
405        }
406      };
407    }
408  }
409
410  /** Returns a new, empty {@code Multimap} with the specified implementation. */
411  public abstract <K extends K0, V extends V0> Multimap<K, V> build();
412
413  /**
414   * Returns a {@code Multimap} with the specified implementation, initialized with the entries of
415   * {@code multimap}.
416   */
417  public <K extends K0, V extends V0> Multimap<K, V> build(
418      Multimap<? extends K, ? extends V> multimap) {
419    Multimap<K, V> result = build();
420    result.putAll(multimap);
421    return result;
422  }
423
424  /**
425   * A specialization of {@link MultimapBuilder} that generates {@link ListMultimap} instances.
426   *
427   * @since 16.0
428   */
429  public abstract static class ListMultimapBuilder<
430          K0 extends @Nullable Object, V0 extends @Nullable Object>
431      extends MultimapBuilder<K0, V0> {
432    ListMultimapBuilder() {}
433
434    @Override
435    public abstract <K extends K0, V extends V0> ListMultimap<K, V> build();
436
437    @Override
438    public <K extends K0, V extends V0> ListMultimap<K, V> build(
439        Multimap<? extends K, ? extends V> multimap) {
440      return (ListMultimap<K, V>) super.build(multimap);
441    }
442  }
443
444  /**
445   * A specialization of {@link MultimapBuilder} that generates {@link SetMultimap} instances.
446   *
447   * @since 16.0
448   */
449  public abstract static class SetMultimapBuilder<
450          K0 extends @Nullable Object, V0 extends @Nullable Object>
451      extends MultimapBuilder<K0, V0> {
452    SetMultimapBuilder() {}
453
454    @Override
455    public abstract <K extends K0, V extends V0> SetMultimap<K, V> build();
456
457    @Override
458    public <K extends K0, V extends V0> SetMultimap<K, V> build(
459        Multimap<? extends K, ? extends V> multimap) {
460      return (SetMultimap<K, V>) super.build(multimap);
461    }
462  }
463
464  /**
465   * A specialization of {@link MultimapBuilder} that generates {@link SortedSetMultimap} instances.
466   *
467   * @since 16.0
468   */
469  public abstract static class SortedSetMultimapBuilder<
470          K0 extends @Nullable Object, V0 extends @Nullable Object>
471      extends SetMultimapBuilder<K0, V0> {
472    SortedSetMultimapBuilder() {}
473
474    @Override
475    public abstract <K extends K0, V extends V0> SortedSetMultimap<K, V> build();
476
477    @Override
478    public <K extends K0, V extends V0> SortedSetMultimap<K, V> build(
479        Multimap<? extends K, ? extends V> multimap) {
480      return (SortedSetMultimap<K, V>) super.build(multimap);
481    }
482  }
483}