View Javadoc
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  
17  package com.google.common.collect;
18  
19  import static com.google.common.collect.CollectPreconditions.checkNonnegative;
20  
21  import com.google.common.annotations.GwtCompatible;
22  import com.google.common.annotations.GwtIncompatible;
23  import com.google.common.annotations.VisibleForTesting;
24  import java.io.IOException;
25  import java.io.ObjectInputStream;
26  import java.io.ObjectOutputStream;
27  import java.util.ArrayList;
28  import java.util.Collection;
29  import java.util.HashMap;
30  import java.util.List;
31  import java.util.Map;
32  
33  /**
34   * Implementation of {@code Multimap} that uses an {@code ArrayList} to store
35   * the values for a given key. A {@link HashMap} associates each key with an
36   * {@link ArrayList} of values.
37   *
38   * <p>When iterating through the collections supplied by this class, the
39   * ordering of values for a given key agrees with the order in which the values
40   * were added.
41   *
42   * <p>This multimap allows duplicate key-value pairs. After adding a new
43   * key-value pair equal to an existing key-value pair, the {@code
44   * ArrayListMultimap} will contain entries for both the new value and the old
45   * value.
46   *
47   * <p>Keys and values may be null. All optional multimap methods are supported,
48   * and all returned views are modifiable.
49   *
50   * <p>The lists returned by {@link #get}, {@link #removeAll}, and {@link
51   * #replaceValues} all implement {@link java.util.RandomAccess}.
52   *
53   * <p>This class is not threadsafe when any concurrent operations update the
54   * multimap. Concurrent read operations will work correctly. To allow concurrent
55   * update operations, wrap your multimap with a call to {@link
56   * Multimaps#synchronizedListMultimap}.
57   *
58   * <p>See the Guava User Guide article on <a href=
59   * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">
60   * {@code Multimap}</a>.
61   *
62   * @author Jared Levy
63   * @since 2.0
64   */
65  @GwtCompatible(serializable = true, emulated = true)
66  public final class ArrayListMultimap<K, V>
67      extends ArrayListMultimapGwtSerializationDependencies<K, V> {
68    // Default from ArrayList
69    private static final int DEFAULT_VALUES_PER_KEY = 3;
70  
71    @VisibleForTesting transient int expectedValuesPerKey;
72  
73    /**
74     * Creates a new, empty {@code ArrayListMultimap} with the default initial capacities.
75     *
76     * <p>This method will soon be deprecated in favor of {@code
77     * MultimapBuilder.hashKeys().arrayListValues().build()}.
78     */
79    public static <K, V> ArrayListMultimap<K, V> create() {
80      return new ArrayListMultimap<>();
81    }
82  
83    /**
84     * Constructs an empty {@code ArrayListMultimap} with enough capacity to hold the specified
85     * numbers of keys and values without resizing.
86     *
87     * <p>This method will soon be deprecated in favor of {@code
88     * MultimapBuilder.hashKeys(expectedKeys).arrayListValues(expectedValuesPerKey).build()}.
89     *
90     * @param expectedKeys the expected number of distinct keys
91     * @param expectedValuesPerKey the expected average number of values per key
92     * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is
93     *     negative
94     */
95    public static <K, V> ArrayListMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) {
96      return new ArrayListMultimap<>(expectedKeys, expectedValuesPerKey);
97    }
98  
99    /**
100    * Constructs an {@code ArrayListMultimap} with the same mappings as the specified multimap.
101    *
102    * <p>This method will soon be deprecated in favor of {@code
103    * MultimapBuilder.hashKeys().arrayListValues().build(multimap)}.
104    *
105    * @param multimap the multimap whose contents are copied to this multimap
106    */
107   public static <K, V> ArrayListMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) {
108     return new ArrayListMultimap<>(multimap);
109   }
110 
111   private ArrayListMultimap() {
112     super(new HashMap<K, Collection<V>>());
113     expectedValuesPerKey = DEFAULT_VALUES_PER_KEY;
114   }
115 
116   private ArrayListMultimap(int expectedKeys, int expectedValuesPerKey) {
117     super(Maps.<K, Collection<V>>newHashMapWithExpectedSize(expectedKeys));
118     checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
119     this.expectedValuesPerKey = expectedValuesPerKey;
120   }
121 
122   private ArrayListMultimap(Multimap<? extends K, ? extends V> multimap) {
123     this(
124         multimap.keySet().size(),
125         (multimap instanceof ArrayListMultimap)
126             ? ((ArrayListMultimap<?, ?>) multimap).expectedValuesPerKey
127             : DEFAULT_VALUES_PER_KEY);
128     putAll(multimap);
129   }
130 
131   /**
132    * Creates a new, empty {@code ArrayList} to hold the collection of values for
133    * an arbitrary key.
134    */
135   @Override
136   List<V> createCollection() {
137     return new ArrayList<V>(expectedValuesPerKey);
138   }
139 
140   /**
141    * Reduces the memory used by this {@code ArrayListMultimap}, if feasible.
142    *
143    * @deprecated For a {@link ListMultimap} that automatically trims to size, use {@link
144    *     ImmutableListMultimap}. If you need a mutable collection, remove the {@code trimToSize}
145    *     call, or switch to a {@code HashMap<K, ArrayList<V>>}.
146    */
147   @Deprecated
148   public void trimToSize() {
149     for (Collection<V> collection : backingMap().values()) {
150       ArrayList<V> arrayList = (ArrayList<V>) collection;
151       arrayList.trimToSize();
152     }
153   }
154 
155   /**
156    * @serialData expectedValuesPerKey, number of distinct keys, and then for
157    *     each distinct key: the key, number of values for that key, and the
158    *     key's values
159    */
160   @GwtIncompatible // java.io.ObjectOutputStream
161   private void writeObject(ObjectOutputStream stream) throws IOException {
162     stream.defaultWriteObject();
163     Serialization.writeMultimap(this, stream);
164   }
165 
166   @GwtIncompatible // java.io.ObjectOutputStream
167   private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
168     stream.defaultReadObject();
169     expectedValuesPerKey = DEFAULT_VALUES_PER_KEY;
170     int distinctKeys = Serialization.readCount(stream);
171     Map<K, Collection<V>> map = Maps.newHashMap();
172     setMap(map);
173     Serialization.populateMultimap(this, stream, distinctKeys);
174   }
175 
176   @GwtIncompatible // Not needed in emulated source.
177   private static final long serialVersionUID = 0;
178 }