001/* 002 * Copyright (C) 2007 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.collect.CollectPreconditions.checkNonnegative; 020 021import com.google.common.annotations.GwtCompatible; 022import com.google.common.annotations.GwtIncompatible; 023import com.google.common.annotations.VisibleForTesting; 024import java.io.IOException; 025import java.io.ObjectInputStream; 026import java.io.ObjectOutputStream; 027import java.util.ArrayList; 028import java.util.Collection; 029import java.util.HashMap; 030import java.util.List; 031import java.util.Map; 032import org.checkerframework.checker.nullness.qual.Nullable; 033 034/** 035 * Implementation of {@code Multimap} that uses an {@code ArrayList} to store the values for a given 036 * key. A {@link HashMap} associates each key with an {@link ArrayList} of values. 037 * 038 * <p>When iterating through the collections supplied by this class, the ordering of values for a 039 * given key agrees with the order in which the values were added. 040 * 041 * <p>This multimap allows duplicate key-value pairs. After adding a new key-value pair equal to an 042 * existing key-value pair, the {@code ArrayListMultimap} will contain entries for both the new 043 * value and the old value. 044 * 045 * <p>Keys and values may be null. All optional multimap methods are supported, and all returned 046 * views are modifiable. 047 * 048 * <p>The lists returned by {@link #get}, {@link #removeAll}, and {@link #replaceValues} all 049 * implement {@link java.util.RandomAccess}. 050 * 051 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent 052 * read operations will work correctly. To allow concurrent update operations, wrap your multimap 053 * with a call to {@link Multimaps#synchronizedListMultimap}. 054 * 055 * <p>See the Guava User Guide article on <a href= 056 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">{@code Multimap}</a>. 057 * 058 * @author Jared Levy 059 * @since 2.0 060 */ 061@GwtCompatible(serializable = true, emulated = true) 062@ElementTypesAreNonnullByDefault 063public final class ArrayListMultimap<K extends @Nullable Object, V extends @Nullable Object> 064 extends ArrayListMultimapGwtSerializationDependencies<K, V> { 065 // Default from ArrayList 066 private static final int DEFAULT_VALUES_PER_KEY = 3; 067 068 @VisibleForTesting transient int expectedValuesPerKey; 069 070 /** 071 * Creates a new, empty {@code ArrayListMultimap} with the default initial capacities. 072 * 073 * <p>This method will soon be deprecated in favor of {@code 074 * MultimapBuilder.hashKeys().arrayListValues().build()}. 075 */ 076 public static <K extends @Nullable Object, V extends @Nullable Object> 077 ArrayListMultimap<K, V> create() { 078 return new ArrayListMultimap<>(); 079 } 080 081 /** 082 * Constructs an empty {@code ArrayListMultimap} with enough capacity to hold the specified 083 * numbers of keys and values without resizing. 084 * 085 * <p>This method will soon be deprecated in favor of {@code 086 * MultimapBuilder.hashKeys(expectedKeys).arrayListValues(expectedValuesPerKey).build()}. 087 * 088 * @param expectedKeys the expected number of distinct keys 089 * @param expectedValuesPerKey the expected average number of values per key 090 * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is 091 * negative 092 */ 093 public static <K extends @Nullable Object, V extends @Nullable Object> 094 ArrayListMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) { 095 return new ArrayListMultimap<>(expectedKeys, expectedValuesPerKey); 096 } 097 098 /** 099 * Constructs an {@code ArrayListMultimap} with the same mappings as the specified multimap. 100 * 101 * <p>This method will soon be deprecated in favor of {@code 102 * MultimapBuilder.hashKeys().arrayListValues().build(multimap)}. 103 * 104 * @param multimap the multimap whose contents are copied to this multimap 105 */ 106 public static <K extends @Nullable Object, V extends @Nullable Object> 107 ArrayListMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) { 108 return new ArrayListMultimap<>(multimap); 109 } 110 111 private ArrayListMultimap() { 112 this(12, DEFAULT_VALUES_PER_KEY); 113 } 114 115 private ArrayListMultimap(int expectedKeys, int expectedValuesPerKey) { 116 super(Platform.<K, Collection<V>>newHashMapWithExpectedSize(expectedKeys)); 117 checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey"); 118 this.expectedValuesPerKey = expectedValuesPerKey; 119 } 120 121 private ArrayListMultimap(Multimap<? extends K, ? extends V> multimap) { 122 this( 123 multimap.keySet().size(), 124 (multimap instanceof ArrayListMultimap) 125 ? ((ArrayListMultimap<?, ?>) multimap).expectedValuesPerKey 126 : DEFAULT_VALUES_PER_KEY); 127 putAll(multimap); 128 } 129 130 /** 131 * Creates a new, empty {@code ArrayList} to hold the collection of values for an arbitrary key. 132 */ 133 @Override 134 List<V> createCollection() { 135 return new ArrayList<V>(expectedValuesPerKey); 136 } 137 138 /** 139 * Reduces the memory used by this {@code ArrayListMultimap}, if feasible. 140 * 141 * @deprecated For a {@link ListMultimap} that automatically trims to size, use {@link 142 * ImmutableListMultimap}. If you need a mutable collection, remove the {@code trimToSize} 143 * call, or switch to a {@code HashMap<K, ArrayList<V>>}. 144 */ 145 @Deprecated 146 public void trimToSize() { 147 for (Collection<V> collection : backingMap().values()) { 148 ArrayList<V> arrayList = (ArrayList<V>) collection; 149 arrayList.trimToSize(); 150 } 151 } 152 153 /** 154 * @serialData expectedValuesPerKey, number of distinct keys, and then for each distinct key: the 155 * key, number of values for that key, and the key's values 156 */ 157 @GwtIncompatible // java.io.ObjectOutputStream 158 private void writeObject(ObjectOutputStream stream) throws IOException { 159 stream.defaultWriteObject(); 160 Serialization.writeMultimap(this, stream); 161 } 162 163 @GwtIncompatible // java.io.ObjectOutputStream 164 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 165 stream.defaultReadObject(); 166 expectedValuesPerKey = DEFAULT_VALUES_PER_KEY; 167 int distinctKeys = Serialization.readCount(stream); 168 Map<K, Collection<V>> map = Maps.newHashMap(); 169 setMap(map); 170 Serialization.populateMultimap(this, stream, distinctKeys); 171 } 172 173 @GwtIncompatible // Not needed in emulated source. 174 private static final long serialVersionUID = 0; 175}