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