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