1/* 2 * Copyright (C) 2007 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkArgument; 20 21import com.google.common.annotations.GwtCompatible; 22import com.google.common.annotations.VisibleForTesting; 23 24import java.util.ArrayList; 25import java.util.Collection; 26import java.util.HashMap; 27import java.util.List; 28 29/** 30 * Implementation of {@code Multimap} that uses an {@code ArrayList} to store 31 * the values for a given key. A {@link HashMap} associates each key with an 32 * {@link ArrayList} of values. 33 * 34 * <p>When iterating through the collections supplied by this class, the 35 * ordering of values for a given key agrees with the order in which the values 36 * were added. 37 * 38 * <p>This multimap allows duplicate key-value pairs. After adding a new 39 * key-value pair equal to an existing key-value pair, the {@code 40 * ArrayListMultimap} will contain entries for both the new value and the old 41 * value. 42 * 43 * <p>Keys and values may be null. All optional multimap methods are supported, 44 * and all returned views are modifiable. 45 * 46 * <p>The lists returned by {@link #get}, {@link #removeAll}, and {@link 47 * #replaceValues} all implement {@link java.util.RandomAccess}. 48 * 49 * <p>This class is not threadsafe when any concurrent operations update the 50 * multimap. Concurrent read operations will work correctly. To allow concurrent 51 * update operations, wrap your multimap with a call to {@link 52 * Multimaps#synchronizedListMultimap}. 53 * 54 * @author Jared Levy 55 * @since 2.0 (imported from Google Collections Library) 56 */ 57@GwtCompatible(serializable = true, emulated = true) 58public final class ArrayListMultimap<K, V> extends AbstractListMultimap<K, V> { 59 // Default from ArrayList 60 private static final int DEFAULT_VALUES_PER_KEY = 10; 61 62 @VisibleForTesting transient int expectedValuesPerKey; 63 64 /** 65 * Creates a new, empty {@code ArrayListMultimap} with the default initial 66 * capacities. 67 */ 68 public static <K, V> ArrayListMultimap<K, V> create() { 69 return new ArrayListMultimap<K, V>(); 70 } 71 72 /** 73 * Constructs an empty {@code ArrayListMultimap} with enough capacity to hold 74 * the specified numbers of keys and values without resizing. 75 * 76 * @param expectedKeys the expected number of distinct keys 77 * @param expectedValuesPerKey the expected average number of values per key 78 * @throws IllegalArgumentException if {@code expectedKeys} or {@code 79 * expectedValuesPerKey} is negative 80 */ 81 public static <K, V> ArrayListMultimap<K, V> create( 82 int expectedKeys, int expectedValuesPerKey) { 83 return new ArrayListMultimap<K, V>(expectedKeys, expectedValuesPerKey); 84 } 85 86 /** 87 * Constructs an {@code ArrayListMultimap} with the same mappings as the 88 * specified multimap. 89 * 90 * @param multimap the multimap whose contents are copied to this multimap 91 */ 92 public static <K, V> ArrayListMultimap<K, V> create( 93 Multimap<? extends K, ? extends V> multimap) { 94 return new ArrayListMultimap<K, V>(multimap); 95 } 96 97 private ArrayListMultimap() { 98 super(new HashMap<K, Collection<V>>()); 99 expectedValuesPerKey = DEFAULT_VALUES_PER_KEY; 100 } 101 102 private ArrayListMultimap(int expectedKeys, int expectedValuesPerKey) { 103 super(Maps.<K, Collection<V>>newHashMapWithExpectedSize(expectedKeys)); 104 checkArgument(expectedValuesPerKey >= 0); 105 this.expectedValuesPerKey = expectedValuesPerKey; 106 } 107 108 private ArrayListMultimap(Multimap<? extends K, ? extends V> multimap) { 109 this(multimap.keySet().size(), 110 (multimap instanceof ArrayListMultimap) ? 111 ((ArrayListMultimap<?, ?>) multimap).expectedValuesPerKey : 112 DEFAULT_VALUES_PER_KEY); 113 putAll(multimap); 114 } 115 116 /** 117 * Creates a new, empty {@code ArrayList} to hold the collection of values for 118 * an arbitrary key. 119 */ 120 @Override List<V> createCollection() { 121 return new ArrayList<V>(expectedValuesPerKey); 122 } 123 124 /** 125 * Reduces the memory used by this {@code ArrayListMultimap}, if feasible. 126 */ 127 public void trimToSize() { 128 for (Collection<V> collection : backingMap().values()) { 129 ArrayList<V> arrayList = (ArrayList<V>) collection; 130 arrayList.trimToSize(); 131 } 132 } 133} 134 135