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