001 /* 002 * Copyright (C) 2007 Google Inc. 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 017 package com.google.common.collect; 018 019 import com.google.common.annotations.GwtCompatible; 020 import com.google.common.annotations.GwtIncompatible; 021 import com.google.common.annotations.VisibleForTesting; 022 import com.google.common.base.Preconditions; 023 024 import java.io.IOException; 025 import java.io.ObjectInputStream; 026 import java.io.ObjectOutputStream; 027 import java.util.Collection; 028 import java.util.Iterator; 029 import java.util.LinkedHashMap; 030 import java.util.LinkedHashSet; 031 import java.util.Map; 032 import java.util.Set; 033 034 import javax.annotation.Nullable; 035 036 /** 037 * Implementation of {@code Multimap} that does not allow duplicate key-value 038 * entries and that returns collections whose iterators follow the ordering in 039 * which the data was added to the multimap. 040 * 041 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code 042 * asMap} iterate through the keys in the order they were first added to the 043 * multimap. Similarly, {@code get}, {@code removeAll}, and {@code 044 * replaceValues} return collections that iterate through the values in the 045 * order they were added. The collections generated by {@code entries} and 046 * {@code values} iterate across the key-value mappings in the order they were 047 * added to the multimap. 048 * 049 * <p>The iteration ordering of the collections generated by {@code keySet}, 050 * {@code keys}, and {@code asMap} has a few subtleties. As long as the set of 051 * keys remains unchanged, adding or removing mappings does not affect the key 052 * iteration order. However, if you remove all values associated with a key and 053 * then add the key back to the multimap, that key will come last in the key 054 * iteration order. 055 * 056 * <p>The multimap does not store duplicate key-value pairs. Adding a new 057 * key-value pair equal to an existing key-value pair has no effect. 058 * 059 * <p>Keys and values may be null. All optional multimap methods are supported, 060 * and all returned views are modifiable. 061 * 062 * <p>This class is not threadsafe when any concurrent operations update the 063 * multimap. Concurrent read operations will work correctly. To allow concurrent 064 * update operations, wrap your multimap with a call to {@link 065 * Multimaps#synchronizedSetMultimap}. 066 * 067 * @author Jared Levy 068 * @since 2 (imported from Google Collections Library) 069 */ 070 @GwtCompatible(serializable = true, emulated = true) 071 public final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> { 072 private static final int DEFAULT_VALUES_PER_KEY = 8; 073 074 @VisibleForTesting 075 transient int expectedValuesPerKey = DEFAULT_VALUES_PER_KEY; 076 077 /** 078 * Map entries with an iteration order corresponding to the order in which the 079 * key-value pairs were added to the multimap. 080 */ 081 // package-private for GWT deserialization 082 transient Collection<Map.Entry<K, V>> linkedEntries; 083 084 /** 085 * Creates a new, empty {@code LinkedHashMultimap} with the default initial 086 * capacities. 087 */ 088 public static <K, V> LinkedHashMultimap<K, V> create() { 089 return new LinkedHashMultimap<K, V>(); 090 } 091 092 /** 093 * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold 094 * the specified numbers of keys and values without rehashing. 095 * 096 * @param expectedKeys the expected number of distinct keys 097 * @param expectedValuesPerKey the expected average number of values per key 098 * @throws IllegalArgumentException if {@code expectedKeys} or {@code 099 * expectedValuesPerKey} is negative 100 */ 101 public static <K, V> LinkedHashMultimap<K, V> create( 102 int expectedKeys, int expectedValuesPerKey) { 103 return new LinkedHashMultimap<K, V>(expectedKeys, expectedValuesPerKey); 104 } 105 106 /** 107 * Constructs a {@code LinkedHashMultimap} with the same mappings as the 108 * specified multimap. If a key-value mapping appears multiple times in the 109 * input multimap, it only appears once in the constructed multimap. The new 110 * multimap has the same {@link Multimap#entries()} iteration order as the 111 * input multimap, except for excluding duplicate mappings. 112 * 113 * @param multimap the multimap whose contents are copied to this multimap 114 */ 115 public static <K, V> LinkedHashMultimap<K, V> create( 116 Multimap<? extends K, ? extends V> multimap) { 117 return new LinkedHashMultimap<K, V>(multimap); 118 } 119 120 private LinkedHashMultimap() { 121 super(new LinkedHashMap<K, Collection<V>>()); 122 linkedEntries = Sets.newLinkedHashSet(); 123 } 124 125 private LinkedHashMultimap(int expectedKeys, int expectedValuesPerKey) { 126 super(new LinkedHashMap<K, Collection<V>>(expectedKeys)); 127 Preconditions.checkArgument(expectedValuesPerKey >= 0); 128 this.expectedValuesPerKey = expectedValuesPerKey; 129 linkedEntries = new LinkedHashSet<Map.Entry<K, V>>( 130 expectedKeys * expectedValuesPerKey); 131 } 132 133 private LinkedHashMultimap(Multimap<? extends K, ? extends V> multimap) { 134 super(new LinkedHashMap<K, Collection<V>>( 135 Maps.capacity(multimap.keySet().size()))); 136 linkedEntries 137 = new LinkedHashSet<Map.Entry<K, V>>(Maps.capacity(multimap.size())); 138 putAll(multimap); 139 } 140 141 /** 142 * {@inheritDoc} 143 * 144 * <p>Creates an empty {@code LinkedHashSet} for a collection of values for 145 * one key. 146 * 147 * @return a new {@code LinkedHashSet} containing a collection of values for 148 * one key 149 */ 150 @Override Set<V> createCollection() { 151 return new LinkedHashSet<V>(Maps.capacity(expectedValuesPerKey)); 152 } 153 154 /** 155 * {@inheritDoc} 156 * 157 * <p>Creates a decorated {@code LinkedHashSet} that also keeps track of the 158 * order in which key-value pairs are added to the multimap. 159 * 160 * @param key key to associate with values in the collection 161 * @return a new decorated {@code LinkedHashSet} containing a collection of 162 * values for one key 163 */ 164 @Override Collection<V> createCollection(@Nullable K key) { 165 return new SetDecorator(key, createCollection()); 166 } 167 168 private class SetDecorator extends ForwardingSet<V> { 169 final Set<V> delegate; 170 final K key; 171 172 SetDecorator(@Nullable K key, Set<V> delegate) { 173 this.delegate = delegate; 174 this.key = key; 175 } 176 177 @Override protected Set<V> delegate() { 178 return delegate; 179 } 180 181 <E> Map.Entry<K, E> createEntry(@Nullable E value) { 182 return Maps.immutableEntry(key, value); 183 } 184 185 <E> Collection<Map.Entry<K, E>> createEntries(Collection<E> values) { 186 // converts a collection of values into a list of key/value map entries 187 Collection<Map.Entry<K, E>> entries 188 = Lists.newArrayListWithExpectedSize(values.size()); 189 for (E value : values) { 190 entries.add(createEntry(value)); 191 } 192 return entries; 193 } 194 195 @Override public boolean add(@Nullable V value) { 196 boolean changed = delegate.add(value); 197 if (changed) { 198 linkedEntries.add(createEntry(value)); 199 } 200 return changed; 201 } 202 203 @Override public boolean addAll(Collection<? extends V> values) { 204 boolean changed = delegate.addAll(values); 205 if (changed) { 206 linkedEntries.addAll(createEntries(delegate())); 207 } 208 return changed; 209 } 210 211 @Override public void clear() { 212 linkedEntries.removeAll(createEntries(delegate())); 213 delegate.clear(); 214 } 215 216 @Override public Iterator<V> iterator() { 217 final Iterator<V> delegateIterator = delegate.iterator(); 218 return new Iterator<V>() { 219 V value; 220 221 public boolean hasNext() { 222 return delegateIterator.hasNext(); 223 } 224 public V next() { 225 value = delegateIterator.next(); 226 return value; 227 } 228 public void remove() { 229 delegateIterator.remove(); 230 linkedEntries.remove(createEntry(value)); 231 } 232 }; 233 } 234 235 @Override public boolean remove(@Nullable Object value) { 236 boolean changed = delegate.remove(value); 237 if (changed) { 238 /* 239 * linkedEntries.remove() will return false when this method is called 240 * by entries().iterator().remove() 241 */ 242 linkedEntries.remove(createEntry(value)); 243 } 244 return changed; 245 } 246 247 @Override public boolean removeAll(Collection<?> values) { 248 boolean changed = delegate.removeAll(values); 249 if (changed) { 250 linkedEntries.removeAll(createEntries(values)); 251 } 252 return changed; 253 } 254 255 @Override public boolean retainAll(Collection<?> values) { 256 /* 257 * Calling linkedEntries.retainAll() would incorrectly remove values 258 * with other keys. 259 */ 260 boolean changed = false; 261 Iterator<V> iterator = delegate.iterator(); 262 while (iterator.hasNext()) { 263 V value = iterator.next(); 264 if (!values.contains(value)) { 265 iterator.remove(); 266 linkedEntries.remove(Maps.immutableEntry(key, value)); 267 changed = true; 268 } 269 } 270 return changed; 271 } 272 } 273 274 /** 275 * {@inheritDoc} 276 * 277 * <p>Generates an iterator across map entries that follows the ordering in 278 * which the key-value pairs were added to the multimap. 279 * 280 * @return a key-value iterator with the correct ordering 281 */ 282 @Override Iterator<Map.Entry<K, V>> createEntryIterator() { 283 final Iterator<Map.Entry<K, V>> delegateIterator = linkedEntries.iterator(); 284 285 return new Iterator<Map.Entry<K, V>>() { 286 Map.Entry<K, V> entry; 287 288 public boolean hasNext() { 289 return delegateIterator.hasNext(); 290 } 291 292 public Map.Entry<K, V> next() { 293 entry = delegateIterator.next(); 294 return entry; 295 } 296 297 public void remove() { 298 // Remove from iterator first to keep iterator valid. 299 delegateIterator.remove(); 300 LinkedHashMultimap.this.remove(entry.getKey(), entry.getValue()); 301 } 302 }; 303 } 304 305 /** 306 * {@inheritDoc} 307 * 308 * <p>If {@code values} is not empty and the multimap already contains a 309 * mapping for {@code key}, the {@code keySet()} ordering is unchanged. 310 * However, the provided values always come last in the {@link #entries()} and 311 * {@link #values()} iteration orderings. 312 */ 313 @Override public Set<V> replaceValues( 314 @Nullable K key, Iterable<? extends V> values) { 315 return super.replaceValues(key, values); 316 } 317 318 /** 319 * Returns a set of all key-value pairs. Changes to the returned set will 320 * update the underlying multimap, and vice versa. The entries set does not 321 * support the {@code add} or {@code addAll} operations. 322 * 323 * <p>The iterator generated by the returned set traverses the entries in the 324 * order they were added to the multimap. 325 * 326 * <p>Each entry is an immutable snapshot of a key-value mapping in the 327 * multimap, taken at the time the entry is returned by a method call to the 328 * collection or its iterator. 329 */ 330 @Override public Set<Map.Entry<K, V>> entries() { 331 return super.entries(); 332 } 333 334 /** 335 * Returns a collection of all values in the multimap. Changes to the returned 336 * collection will update the underlying multimap, and vice versa. 337 * 338 * <p>The iterator generated by the returned collection traverses the values 339 * in the order they were added to the multimap. 340 */ 341 @Override public Collection<V> values() { 342 return super.values(); 343 } 344 345 // Unfortunately, the entries() ordering does not determine the key ordering; 346 // see the example in the LinkedListMultimap class Javadoc. 347 348 /** 349 * @serialData the number of distinct keys, and then for each distinct key: 350 * the first key, the number of values for that key, and the key's values, 351 * followed by successive keys and values from the entries() ordering 352 */ 353 @GwtIncompatible("java.io.ObjectOutputStream") 354 private void writeObject(ObjectOutputStream stream) throws IOException { 355 stream.defaultWriteObject(); 356 stream.writeInt(expectedValuesPerKey); 357 Serialization.writeMultimap(this, stream); 358 for (Map.Entry<K, V> entry : linkedEntries) { 359 stream.writeObject(entry.getKey()); 360 stream.writeObject(entry.getValue()); 361 } 362 } 363 364 @GwtIncompatible("java.io.ObjectInputStream") 365 private void readObject(ObjectInputStream stream) 366 throws IOException, ClassNotFoundException { 367 stream.defaultReadObject(); 368 expectedValuesPerKey = stream.readInt(); 369 int distinctKeys = Serialization.readCount(stream); 370 setMap(new LinkedHashMap<K, Collection<V>>(Maps.capacity(distinctKeys))); 371 linkedEntries = new LinkedHashSet<Map.Entry<K, V>>( 372 distinctKeys * expectedValuesPerKey); 373 Serialization.populateMultimap(this, stream, distinctKeys); 374 linkedEntries.clear(); // will clear and repopulate entries 375 for (int i = 0; i < size(); i++) { 376 @SuppressWarnings("unchecked") // reading data stored by writeObject 377 K key = (K) stream.readObject(); 378 @SuppressWarnings("unchecked") // reading data stored by writeObject 379 V value = (V) stream.readObject(); 380 linkedEntries.add(Maps.immutableEntry(key, value)); 381 } 382 } 383 384 @GwtIncompatible("java serialization not supported") 385 private static final long serialVersionUID = 0; 386 }