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.base.Preconditions.checkNotNull; 020import static com.google.common.collect.CollectPreconditions.checkNonnegative; 021import static com.google.common.collect.CollectPreconditions.checkRemove; 022 023import com.google.common.annotations.GwtCompatible; 024import com.google.common.annotations.GwtIncompatible; 025import com.google.common.annotations.VisibleForTesting; 026import com.google.common.base.Objects; 027import com.google.errorprone.annotations.CanIgnoreReturnValue; 028import com.google.j2objc.annotations.WeakOuter; 029import java.io.IOException; 030import java.io.ObjectInputStream; 031import java.io.ObjectOutputStream; 032import java.util.Arrays; 033import java.util.Collection; 034import java.util.ConcurrentModificationException; 035import java.util.Iterator; 036import java.util.LinkedHashMap; 037import java.util.LinkedHashSet; 038import java.util.Map; 039import java.util.Map.Entry; 040import java.util.NoSuchElementException; 041import java.util.Set; 042import java.util.Spliterator; 043import java.util.Spliterators; 044import java.util.function.Consumer; 045import javax.annotation.Nullable; 046 047/** 048 * Implementation of {@code Multimap} that does not allow duplicate key-value 049 * entries and that returns collections whose iterators follow the ordering in 050 * which the data was added to the multimap. 051 * 052 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code 053 * asMap} iterate through the keys in the order they were first added to the 054 * multimap. Similarly, {@code get}, {@code removeAll}, and {@code 055 * replaceValues} return collections that iterate through the values in the 056 * order they were added. The collections generated by {@code entries} and 057 * {@code values} iterate across the key-value mappings in the order they were 058 * added to the multimap. 059 * 060 * <p>The iteration ordering of the collections generated by {@code keySet}, 061 * {@code keys}, and {@code asMap} has a few subtleties. As long as the set of 062 * keys remains unchanged, adding or removing mappings does not affect the key 063 * iteration order. However, if you remove all values associated with a key and 064 * then add the key back to the multimap, that key will come last in the key 065 * iteration order. 066 * 067 * <p>The multimap does not store duplicate key-value pairs. Adding a new 068 * key-value pair equal to an existing key-value pair has no effect. 069 * 070 * <p>Keys and values may be null. All optional multimap methods are supported, 071 * and all returned views are modifiable. 072 * 073 * <p>This class is not threadsafe when any concurrent operations update the 074 * multimap. Concurrent read operations will work correctly. To allow concurrent 075 * update operations, wrap your multimap with a call to {@link 076 * Multimaps#synchronizedSetMultimap}. 077 * 078 * <p>See the Guava User Guide article on <a href= 079 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap"> 080 * {@code Multimap}</a>. 081 * 082 * @author Jared Levy 083 * @author Louis Wasserman 084 * @since 2.0 085 */ 086@GwtCompatible(serializable = true, emulated = true) 087public final class LinkedHashMultimap<K, V> 088 extends LinkedHashMultimapGwtSerializationDependencies<K, V> { 089 090 /** 091 * Creates a new, empty {@code LinkedHashMultimap} with the default initial 092 * capacities. 093 */ 094 public static <K, V> LinkedHashMultimap<K, V> create() { 095 return new LinkedHashMultimap<K, V>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY); 096 } 097 098 /** 099 * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold 100 * the specified numbers of keys and values without rehashing. 101 * 102 * @param expectedKeys the expected number of distinct keys 103 * @param expectedValuesPerKey the expected average number of values per key 104 * @throws IllegalArgumentException if {@code expectedKeys} or {@code 105 * expectedValuesPerKey} is negative 106 */ 107 public static <K, V> LinkedHashMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) { 108 return new LinkedHashMultimap<K, V>( 109 Maps.capacity(expectedKeys), Maps.capacity(expectedValuesPerKey)); 110 } 111 112 /** 113 * Constructs a {@code LinkedHashMultimap} with the same mappings as the 114 * specified multimap. If a key-value mapping appears multiple times in the 115 * input multimap, it only appears once in the constructed multimap. The new 116 * multimap has the same {@link Multimap#entries()} iteration order as the 117 * input multimap, except for excluding duplicate mappings. 118 * 119 * @param multimap the multimap whose contents are copied to this multimap 120 */ 121 public static <K, V> LinkedHashMultimap<K, V> create( 122 Multimap<? extends K, ? extends V> multimap) { 123 LinkedHashMultimap<K, V> result = create(multimap.keySet().size(), DEFAULT_VALUE_SET_CAPACITY); 124 result.putAll(multimap); 125 return result; 126 } 127 128 private interface ValueSetLink<K, V> { 129 ValueSetLink<K, V> getPredecessorInValueSet(); 130 131 ValueSetLink<K, V> getSuccessorInValueSet(); 132 133 void setPredecessorInValueSet(ValueSetLink<K, V> entry); 134 135 void setSuccessorInValueSet(ValueSetLink<K, V> entry); 136 } 137 138 private static <K, V> void succeedsInValueSet(ValueSetLink<K, V> pred, ValueSetLink<K, V> succ) { 139 pred.setSuccessorInValueSet(succ); 140 succ.setPredecessorInValueSet(pred); 141 } 142 143 private static <K, V> void succeedsInMultimap(ValueEntry<K, V> pred, ValueEntry<K, V> succ) { 144 pred.setSuccessorInMultimap(succ); 145 succ.setPredecessorInMultimap(pred); 146 } 147 148 private static <K, V> void deleteFromValueSet(ValueSetLink<K, V> entry) { 149 succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet()); 150 } 151 152 private static <K, V> void deleteFromMultimap(ValueEntry<K, V> entry) { 153 succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap()); 154 } 155 156 /** 157 * LinkedHashMultimap entries are in no less than three coexisting linked lists: a bucket in the 158 * hash table for a {@code Set<V>} associated with a key, the linked list of insertion-ordered 159 * entries in that {@code Set<V>}, and the linked list of entries in the LinkedHashMultimap as a 160 * whole. 161 */ 162 @VisibleForTesting 163 static final class ValueEntry<K, V> extends ImmutableEntry<K, V> implements ValueSetLink<K, V> { 164 final int smearedValueHash; 165 166 @Nullable ValueEntry<K, V> nextInValueBucket; 167 168 ValueSetLink<K, V> predecessorInValueSet; 169 ValueSetLink<K, V> successorInValueSet; 170 171 ValueEntry<K, V> predecessorInMultimap; 172 ValueEntry<K, V> successorInMultimap; 173 174 ValueEntry( 175 @Nullable K key, 176 @Nullable V value, 177 int smearedValueHash, 178 @Nullable ValueEntry<K, V> nextInValueBucket) { 179 super(key, value); 180 this.smearedValueHash = smearedValueHash; 181 this.nextInValueBucket = nextInValueBucket; 182 } 183 184 boolean matchesValue(@Nullable Object v, int smearedVHash) { 185 return smearedValueHash == smearedVHash && Objects.equal(getValue(), v); 186 } 187 188 @Override 189 public ValueSetLink<K, V> getPredecessorInValueSet() { 190 return predecessorInValueSet; 191 } 192 193 @Override 194 public ValueSetLink<K, V> getSuccessorInValueSet() { 195 return successorInValueSet; 196 } 197 198 @Override 199 public void setPredecessorInValueSet(ValueSetLink<K, V> entry) { 200 predecessorInValueSet = entry; 201 } 202 203 @Override 204 public void setSuccessorInValueSet(ValueSetLink<K, V> entry) { 205 successorInValueSet = entry; 206 } 207 208 public ValueEntry<K, V> getPredecessorInMultimap() { 209 return predecessorInMultimap; 210 } 211 212 public ValueEntry<K, V> getSuccessorInMultimap() { 213 return successorInMultimap; 214 } 215 216 public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) { 217 this.successorInMultimap = multimapSuccessor; 218 } 219 220 public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) { 221 this.predecessorInMultimap = multimapPredecessor; 222 } 223 } 224 225 private static final int DEFAULT_KEY_CAPACITY = 16; 226 private static final int DEFAULT_VALUE_SET_CAPACITY = 2; 227 @VisibleForTesting static final double VALUE_SET_LOAD_FACTOR = 1.0; 228 229 @VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY; 230 private transient ValueEntry<K, V> multimapHeaderEntry; 231 232 private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) { 233 super(new LinkedHashMap<K, Collection<V>>(keyCapacity)); 234 checkNonnegative(valueSetCapacity, "expectedValuesPerKey"); 235 236 this.valueSetCapacity = valueSetCapacity; 237 this.multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null); 238 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry); 239 } 240 241 /** 242 * {@inheritDoc} 243 * 244 * <p>Creates an empty {@code LinkedHashSet} for a collection of values for 245 * one key. 246 * 247 * @return a new {@code LinkedHashSet} containing a collection of values for 248 * one key 249 */ 250 @Override 251 Set<V> createCollection() { 252 return new LinkedHashSet<V>(valueSetCapacity); 253 } 254 255 /** 256 * {@inheritDoc} 257 * 258 * <p>Creates a decorated insertion-ordered set that also keeps track of the 259 * order in which key-value pairs are added to the multimap. 260 * 261 * @param key key to associate with values in the collection 262 * @return a new decorated set containing a collection of values for one key 263 */ 264 @Override 265 Collection<V> createCollection(K key) { 266 return new ValueSet(key, valueSetCapacity); 267 } 268 269 /** 270 * {@inheritDoc} 271 * 272 * <p>If {@code values} is not empty and the multimap already contains a 273 * mapping for {@code key}, the {@code keySet()} ordering is unchanged. 274 * However, the provided values always come last in the {@link #entries()} and 275 * {@link #values()} iteration orderings. 276 */ 277 @CanIgnoreReturnValue 278 @Override 279 public Set<V> replaceValues(@Nullable K key, Iterable<? extends V> values) { 280 return super.replaceValues(key, values); 281 } 282 283 /** 284 * Returns a set of all key-value pairs. Changes to the returned set will 285 * update the underlying multimap, and vice versa. The entries set does not 286 * support the {@code add} or {@code addAll} operations. 287 * 288 * <p>The iterator generated by the returned set traverses the entries in the 289 * order they were added to the multimap. 290 * 291 * <p>Each entry is an immutable snapshot of a key-value mapping in the 292 * multimap, taken at the time the entry is returned by a method call to the 293 * collection or its iterator. 294 */ 295 @Override 296 public Set<Map.Entry<K, V>> entries() { 297 return super.entries(); 298 } 299 300 /** 301 * Returns a view collection of all <i>distinct</i> keys contained in this 302 * multimap. Note that the key set contains a key if and only if this multimap 303 * maps that key to at least one value. 304 * 305 * <p>The iterator generated by the returned set traverses the keys in the 306 * order they were first added to the multimap. 307 * 308 * <p>Changes to the returned set will update the underlying multimap, and 309 * vice versa. However, <i>adding</i> to the returned set is not possible. 310 */ 311 @Override 312 public Set<K> keySet() { 313 return super.keySet(); 314 } 315 316 /** 317 * Returns a collection of all values in the multimap. Changes to the returned 318 * collection will update the underlying multimap, and vice versa. 319 * 320 * <p>The iterator generated by the returned collection traverses the values 321 * in the order they were added to the multimap. 322 */ 323 @Override 324 public Collection<V> values() { 325 return super.values(); 326 } 327 328 @VisibleForTesting 329 @WeakOuter 330 final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> { 331 /* 332 * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory 333 * consumption. 334 */ 335 336 private final K key; 337 @VisibleForTesting ValueEntry<K, V>[] hashTable; 338 private int size = 0; 339 private int modCount = 0; 340 341 // We use the set object itself as the end of the linked list, avoiding an unnecessary 342 // entry object per key. 343 private ValueSetLink<K, V> firstEntry; 344 private ValueSetLink<K, V> lastEntry; 345 346 ValueSet(K key, int expectedValues) { 347 this.key = key; 348 this.firstEntry = this; 349 this.lastEntry = this; 350 // Round expected values up to a power of 2 to get the table size. 351 int tableSize = Hashing.closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR); 352 353 @SuppressWarnings("unchecked") 354 ValueEntry<K, V>[] hashTable = new ValueEntry[tableSize]; 355 this.hashTable = hashTable; 356 } 357 358 private int mask() { 359 return hashTable.length - 1; 360 } 361 362 @Override 363 public ValueSetLink<K, V> getPredecessorInValueSet() { 364 return lastEntry; 365 } 366 367 @Override 368 public ValueSetLink<K, V> getSuccessorInValueSet() { 369 return firstEntry; 370 } 371 372 @Override 373 public void setPredecessorInValueSet(ValueSetLink<K, V> entry) { 374 lastEntry = entry; 375 } 376 377 @Override 378 public void setSuccessorInValueSet(ValueSetLink<K, V> entry) { 379 firstEntry = entry; 380 } 381 382 @Override 383 public Iterator<V> iterator() { 384 return new Iterator<V>() { 385 ValueSetLink<K, V> nextEntry = firstEntry; 386 ValueEntry<K, V> toRemove; 387 int expectedModCount = modCount; 388 389 private void checkForComodification() { 390 if (modCount != expectedModCount) { 391 throw new ConcurrentModificationException(); 392 } 393 } 394 395 @Override 396 public boolean hasNext() { 397 checkForComodification(); 398 return nextEntry != ValueSet.this; 399 } 400 401 @Override 402 public V next() { 403 if (!hasNext()) { 404 throw new NoSuchElementException(); 405 } 406 ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry; 407 V result = entry.getValue(); 408 toRemove = entry; 409 nextEntry = entry.getSuccessorInValueSet(); 410 return result; 411 } 412 413 @Override 414 public void remove() { 415 checkForComodification(); 416 checkRemove(toRemove != null); 417 ValueSet.this.remove(toRemove.getValue()); 418 expectedModCount = modCount; 419 toRemove = null; 420 } 421 }; 422 } 423 424 @Override 425 public void forEach(Consumer<? super V> action) { 426 checkNotNull(action); 427 for (ValueSetLink<K, V> entry = firstEntry; 428 entry != ValueSet.this; 429 entry = entry.getSuccessorInValueSet()) { 430 action.accept(((ValueEntry<K, V>) entry).getValue()); 431 } 432 } 433 434 @Override 435 public int size() { 436 return size; 437 } 438 439 @Override 440 public boolean contains(@Nullable Object o) { 441 int smearedHash = Hashing.smearedHash(o); 442 for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()]; 443 entry != null; 444 entry = entry.nextInValueBucket) { 445 if (entry.matchesValue(o, smearedHash)) { 446 return true; 447 } 448 } 449 return false; 450 } 451 452 @Override 453 public boolean add(@Nullable V value) { 454 int smearedHash = Hashing.smearedHash(value); 455 int bucket = smearedHash & mask(); 456 ValueEntry<K, V> rowHead = hashTable[bucket]; 457 for (ValueEntry<K, V> entry = rowHead; entry != null; entry = entry.nextInValueBucket) { 458 if (entry.matchesValue(value, smearedHash)) { 459 return false; 460 } 461 } 462 463 ValueEntry<K, V> newEntry = new ValueEntry<K, V>(key, value, smearedHash, rowHead); 464 succeedsInValueSet(lastEntry, newEntry); 465 succeedsInValueSet(newEntry, this); 466 succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry); 467 succeedsInMultimap(newEntry, multimapHeaderEntry); 468 hashTable[bucket] = newEntry; 469 size++; 470 modCount++; 471 rehashIfNecessary(); 472 return true; 473 } 474 475 private void rehashIfNecessary() { 476 if (Hashing.needsResizing(size, hashTable.length, VALUE_SET_LOAD_FACTOR)) { 477 @SuppressWarnings("unchecked") 478 ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2]; 479 this.hashTable = hashTable; 480 int mask = hashTable.length - 1; 481 for (ValueSetLink<K, V> entry = firstEntry; 482 entry != this; 483 entry = entry.getSuccessorInValueSet()) { 484 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry; 485 int bucket = valueEntry.smearedValueHash & mask; 486 valueEntry.nextInValueBucket = hashTable[bucket]; 487 hashTable[bucket] = valueEntry; 488 } 489 } 490 } 491 492 @CanIgnoreReturnValue 493 @Override 494 public boolean remove(@Nullable Object o) { 495 int smearedHash = Hashing.smearedHash(o); 496 int bucket = smearedHash & mask(); 497 ValueEntry<K, V> prev = null; 498 for (ValueEntry<K, V> entry = hashTable[bucket]; 499 entry != null; 500 prev = entry, entry = entry.nextInValueBucket) { 501 if (entry.matchesValue(o, smearedHash)) { 502 if (prev == null) { 503 // first entry in the bucket 504 hashTable[bucket] = entry.nextInValueBucket; 505 } else { 506 prev.nextInValueBucket = entry.nextInValueBucket; 507 } 508 deleteFromValueSet(entry); 509 deleteFromMultimap(entry); 510 size--; 511 modCount++; 512 return true; 513 } 514 } 515 return false; 516 } 517 518 @Override 519 public void clear() { 520 Arrays.fill(hashTable, null); 521 size = 0; 522 for (ValueSetLink<K, V> entry = firstEntry; 523 entry != this; 524 entry = entry.getSuccessorInValueSet()) { 525 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry; 526 deleteFromMultimap(valueEntry); 527 } 528 succeedsInValueSet(this, this); 529 modCount++; 530 } 531 } 532 533 @Override 534 Iterator<Map.Entry<K, V>> entryIterator() { 535 return new Iterator<Map.Entry<K, V>>() { 536 ValueEntry<K, V> nextEntry = multimapHeaderEntry.successorInMultimap; 537 ValueEntry<K, V> toRemove; 538 539 @Override 540 public boolean hasNext() { 541 return nextEntry != multimapHeaderEntry; 542 } 543 544 @Override 545 public Map.Entry<K, V> next() { 546 if (!hasNext()) { 547 throw new NoSuchElementException(); 548 } 549 ValueEntry<K, V> result = nextEntry; 550 toRemove = result; 551 nextEntry = nextEntry.successorInMultimap; 552 return result; 553 } 554 555 @Override 556 public void remove() { 557 checkRemove(toRemove != null); 558 LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue()); 559 toRemove = null; 560 } 561 }; 562 } 563 564 @Override 565 Spliterator<Entry<K, V>> entrySpliterator() { 566 return Spliterators.spliterator(entries(), Spliterator.DISTINCT | Spliterator.ORDERED); 567 } 568 569 @Override 570 Iterator<V> valueIterator() { 571 return Maps.valueIterator(entryIterator()); 572 } 573 574 @Override 575 Spliterator<V> valueSpliterator() { 576 return CollectSpliterators.map(entrySpliterator(), Entry::getValue); 577 } 578 579 @Override 580 public void clear() { 581 super.clear(); 582 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry); 583 } 584 585 /** 586 * @serialData the expected values per key, the number of distinct keys, 587 * the number of entries, and the entries in order 588 */ 589 @GwtIncompatible // java.io.ObjectOutputStream 590 private void writeObject(ObjectOutputStream stream) throws IOException { 591 stream.defaultWriteObject(); 592 stream.writeInt(keySet().size()); 593 for (K key : keySet()) { 594 stream.writeObject(key); 595 } 596 stream.writeInt(size()); 597 for (Map.Entry<K, V> entry : entries()) { 598 stream.writeObject(entry.getKey()); 599 stream.writeObject(entry.getValue()); 600 } 601 } 602 603 @GwtIncompatible // java.io.ObjectInputStream 604 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 605 stream.defaultReadObject(); 606 multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null); 607 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry); 608 valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY; 609 int distinctKeys = stream.readInt(); 610 Map<K, Collection<V>> map = new LinkedHashMap<K, Collection<V>>(); 611 for (int i = 0; i < distinctKeys; i++) { 612 @SuppressWarnings("unchecked") 613 K key = (K) stream.readObject(); 614 map.put(key, createCollection(key)); 615 } 616 int entries = stream.readInt(); 617 for (int i = 0; i < entries; i++) { 618 @SuppressWarnings("unchecked") 619 K key = (K) stream.readObject(); 620 @SuppressWarnings("unchecked") 621 V value = (V) stream.readObject(); 622 map.get(key).add(value); 623 } 624 setMap(map); 625 } 626 627 @GwtIncompatible // java serialization not supported 628 private static final long serialVersionUID = 1; 629}