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.jspecify.annotations.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
062public abstract class MultimapBuilder<K0 extends @Nullable Object, V0 extends @Nullable Object> {
063  /*
064   * Leaving K and V as upper bounds rather than the actual key and value types allows type
065   * parameters to be left implicit more often. CacheBuilder uses the same technique.
066   */
067
068  private MultimapBuilder() {}
069
070  private static final int DEFAULT_EXPECTED_KEYS = 8;
071
072  /** Uses a hash table to map keys to value collections. */
073  public static MultimapBuilderWithKeys<@Nullable Object> hashKeys() {
074    return hashKeys(DEFAULT_EXPECTED_KEYS);
075  }
076
077  /**
078   * Uses a hash table to map keys to value collections, initialized to expect the specified number
079   * of keys.
080   *
081   * @throws IllegalArgumentException if {@code expectedKeys < 0}
082   */
083  public static MultimapBuilderWithKeys<@Nullable Object> hashKeys(int expectedKeys) {
084    checkNonnegative(expectedKeys, "expectedKeys");
085    return new MultimapBuilderWithKeys<@Nullable Object>() {
086      @Override
087      <K extends @Nullable Object, V extends @Nullable Object> Map<K, Collection<V>> createMap() {
088        return Platform.newHashMapWithExpectedSize(expectedKeys);
089      }
090    };
091  }
092
093  /**
094   * Uses a hash table to map keys to value collections.
095   *
096   * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and {@link
097   * Multimap#asMap()} will iterate through the keys in the order that they were first added to the
098   * multimap, save that if all values associated with a key are removed and then the key is added
099   * back into the multimap, that key will come last in the key iteration order.
100   */
101  public static MultimapBuilderWithKeys<@Nullable Object> linkedHashKeys() {
102    return linkedHashKeys(DEFAULT_EXPECTED_KEYS);
103  }
104
105  /**
106   * Uses an hash table to map keys to value collections, initialized to expect the specified number
107   * of keys.
108   *
109   * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and {@link
110   * Multimap#asMap()} will iterate through the keys in the order that they were first added to the
111   * multimap, save that if all values associated with a key are removed and then the key is added
112   * back into the multimap, that key will come last in the key iteration order.
113   */
114  public static MultimapBuilderWithKeys<@Nullable Object> linkedHashKeys(int expectedKeys) {
115    checkNonnegative(expectedKeys, "expectedKeys");
116    return new MultimapBuilderWithKeys<@Nullable Object>() {
117      @Override
118      <K extends @Nullable Object, V extends @Nullable Object> Map<K, Collection<V>> createMap() {
119        return Platform.newLinkedHashMapWithExpectedSize(expectedKeys);
120      }
121    };
122  }
123
124  /**
125   * Uses a naturally-ordered {@link TreeMap} to map keys to value collections.
126   *
127   * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and {@link
128   * Multimap#asMap()} will iterate through the keys in sorted order.
129   *
130   * <p>For all multimaps generated by the resulting builder, the {@link Multimap#keySet()} can be
131   * safely cast to a {@link java.util.SortedSet}, and the {@link Multimap#asMap()} can safely be
132   * cast to a {@link java.util.SortedMap}.
133   */
134  @SuppressWarnings("rawtypes")
135  public static MultimapBuilderWithKeys<Comparable> treeKeys() {
136    return treeKeys(Ordering.natural());
137  }
138
139  /**
140   * Uses a {@link TreeMap} sorted by the specified comparator to map keys to value collections.
141   *
142   * <p>The collections returned by {@link Multimap#keySet()}, {@link Multimap#keys()}, and {@link
143   * 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   * <p>Multimaps generated by the resulting builder will not be serializable if {@code comparator}
150   * is not serializable.
151   */
152  public static <K0 extends @Nullable Object> MultimapBuilderWithKeys<K0> treeKeys(
153      Comparator<K0> comparator) {
154    checkNotNull(comparator);
155    return new MultimapBuilderWithKeys<K0>() {
156      @Override
157      <K extends K0, V extends @Nullable Object> Map<K, Collection<V>> createMap() {
158        return new TreeMap<>(comparator);
159      }
160    };
161  }
162
163  /**
164   * Uses an {@link EnumMap} to map keys to value collections.
165   *
166   * @since 16.0
167   */
168  public static <K0 extends Enum<K0>> MultimapBuilderWithKeys<K0> enumKeys(Class<K0> keyClass) {
169    checkNotNull(keyClass);
170    return new MultimapBuilderWithKeys<K0>() {
171      @SuppressWarnings("unchecked")
172      @Override
173      <K extends K0, V extends @Nullable Object> Map<K, Collection<V>> createMap() {
174        // K must actually be K0, since enums are effectively final
175        // (their subclasses are inaccessible)
176        return (Map<K, Collection<V>>) new EnumMap<K0, Collection<V>>(keyClass);
177      }
178    };
179  }
180
181  private static final class ArrayListSupplier<V extends @Nullable Object>
182      implements Supplier<List<V>>, Serializable {
183    private final int expectedValuesPerKey;
184
185    ArrayListSupplier(int expectedValuesPerKey) {
186      this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
187    }
188
189    @Override
190    public List<V> get() {
191      return new ArrayList<>(expectedValuesPerKey);
192    }
193  }
194
195  private enum LinkedListSupplier implements Supplier<List<?>> {
196    INSTANCE;
197
198    public static <V extends @Nullable Object> Supplier<List<V>> instance() {
199      // Each call generates a fresh LinkedList, which can serve as a List<V> for any V.
200      @SuppressWarnings({"rawtypes", "unchecked"})
201      Supplier<List<V>> result = (Supplier) INSTANCE;
202      return result;
203    }
204
205    @Override
206    public List<?> get() {
207      return new LinkedList<>();
208    }
209  }
210
211  private static final class HashSetSupplier<V extends @Nullable Object>
212      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 extends @Nullable Object>
226      implements Supplier<Set<V>>, Serializable {
227    private final int expectedValuesPerKey;
228
229    LinkedHashSetSupplier(int expectedValuesPerKey) {
230      this.expectedValuesPerKey = checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
231    }
232
233    @Override
234    public Set<V> get() {
235      return Platform.newLinkedHashSetWithExpectedSize(expectedValuesPerKey);
236    }
237  }
238
239  private static final class TreeSetSupplier<V extends @Nullable Object>
240      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<>(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 extends @Nullable Object> {
275
276    private static final int DEFAULT_EXPECTED_VALUES_PER_KEY = 2;
277
278    MultimapBuilderWithKeys() {}
279
280    abstract <K extends K0, V extends @Nullable Object> Map<K, Collection<V>> createMap();
281
282    /** Uses an {@link ArrayList} to store value collections. */
283    public ListMultimapBuilder<K0, @Nullable 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, @Nullable Object> arrayListValues(int expectedValuesPerKey) {
294      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
295      return new ListMultimapBuilder<K0, @Nullable Object>() {
296        @Override
297        public <K extends K0, V extends @Nullable Object> 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, @Nullable Object> linkedListValues() {
307      return new ListMultimapBuilder<K0, @Nullable Object>() {
308        @Override
309        public <K extends K0, V extends @Nullable Object> 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, @Nullable 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
323     * number of values per key.
324     *
325     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
326     */
327    public SetMultimapBuilder<K0, @Nullable Object> hashSetValues(int expectedValuesPerKey) {
328      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
329      return new SetMultimapBuilder<K0, @Nullable Object>() {
330        @Override
331        public <K extends K0, V extends @Nullable Object> 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, @Nullable 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
346     * expect the specified number of values per key.
347     *
348     * @throws IllegalArgumentException if {@code expectedValuesPerKey < 0}
349     */
350    public SetMultimapBuilder<K0, @Nullable Object> linkedHashSetValues(int expectedValuesPerKey) {
351      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
352      return new SetMultimapBuilder<K0, @Nullable Object>() {
353        @Override
354        public <K extends K0, V extends @Nullable Object> 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 extends @Nullable Object> SortedSetMultimapBuilder<K0, V0> treeSetValues(
375        Comparator<V0> comparator) {
376      checkNotNull(comparator, "comparator");
377      return new SortedSetMultimapBuilder<K0, V0>() {
378        @Override
379        public <K extends K0, V extends V0> SortedSetMultimap<K, V> build() {
380          return Multimaps.newSortedSetMultimap(
381              MultimapBuilderWithKeys.this.<K, V>createMap(), new TreeSetSupplier<V>(comparator));
382        }
383      };
384    }
385
386    /** Uses an {@link EnumSet} to store value collections. */
387    public <V0 extends Enum<V0>> SetMultimapBuilder<K0, V0> enumSetValues(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<
422          K0 extends @Nullable Object, V0 extends @Nullable Object>
423      extends MultimapBuilder<K0, V0> {
424    ListMultimapBuilder() {}
425
426    @Override
427    public abstract <K extends K0, V extends V0> ListMultimap<K, V> build();
428
429    @Override
430    public <K extends K0, V extends V0> ListMultimap<K, V> build(
431        Multimap<? extends K, ? extends V> multimap) {
432      return (ListMultimap<K, V>) super.<K, V>build(multimap);
433    }
434  }
435
436  /**
437   * A specialization of {@link MultimapBuilder} that generates {@link SetMultimap} instances.
438   *
439   * @since 16.0
440   */
441  public abstract static class SetMultimapBuilder<
442          K0 extends @Nullable Object, V0 extends @Nullable Object>
443      extends MultimapBuilder<K0, V0> {
444    SetMultimapBuilder() {}
445
446    @Override
447    public abstract <K extends K0, V extends V0> SetMultimap<K, V> build();
448
449    @Override
450    public <K extends K0, V extends V0> SetMultimap<K, V> build(
451        Multimap<? extends K, ? extends V> multimap) {
452      return (SetMultimap<K, V>) super.<K, V>build(multimap);
453    }
454  }
455
456  /**
457   * A specialization of {@link MultimapBuilder} that generates {@link SortedSetMultimap} instances.
458   *
459   * @since 16.0
460   */
461  public abstract static class SortedSetMultimapBuilder<
462          K0 extends @Nullable Object, V0 extends @Nullable Object>
463      extends SetMultimapBuilder<K0, V0> {
464    SortedSetMultimapBuilder() {}
465
466    @Override
467    public abstract <K extends K0, V extends V0> SortedSetMultimap<K, V> build();
468
469    @Override
470    public <K extends K0, V extends V0> SortedSetMultimap<K, V> build(
471        Multimap<? extends K, ? extends V> multimap) {
472      return (SortedSetMultimap<K, V>) super.<K, V>build(multimap);
473    }
474  }
475}