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.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.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.build(multimap); 474 } 475 } 476}