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; 20import static com.google.common.base.Preconditions.checkNotNull; 21import static com.google.common.base.Preconditions.checkState; 22import static com.google.common.collect.Multisets.setCountImpl; 23import static java.util.Collections.unmodifiableList; 24 25import com.google.common.annotations.GwtCompatible; 26import com.google.common.base.Objects; 27import com.google.common.base.Preconditions; 28 29import java.io.Serializable; 30import java.util.AbstractCollection; 31import java.util.AbstractMap; 32import java.util.AbstractSequentialList; 33import java.util.AbstractSet; 34import java.util.Collection; 35import java.util.Iterator; 36import java.util.List; 37import java.util.ListIterator; 38import java.util.Map; 39import java.util.Map.Entry; 40import java.util.NoSuchElementException; 41import java.util.Set; 42 43import javax.annotation.Nullable; 44 45/** 46 * An implementation of {@code ListMultimap} that supports deterministic 47 * iteration order for both keys and values. The iteration order is preserved 48 * across non-distinct key values. For example, for the following multimap 49 * definition: <pre> {@code 50 * 51 * Multimap<K, V> multimap = LinkedListMultimap.create(); 52 * multimap.put(key1, foo); 53 * multimap.put(key2, bar); 54 * multimap.put(key1, baz);}</pre> 55 * 56 * ... the iteration order for {@link #keys()} is {@code [key1, key2, key1]}, 57 * and similarly for {@link #entries()}. Unlike {@link LinkedHashMultimap}, the 58 * iteration order is kept consistent between keys, entries and values. For 59 * example, calling: <pre> {@code 60 * 61 * map.remove(key1, foo);}</pre> 62 * 63 * changes the entries iteration order to {@code [key2=bar, key1=baz]} and the 64 * key iteration order to {@code [key2, key1]}. The {@link #entries()} iterator 65 * returns mutable map entries, and {@link #replaceValues} attempts to preserve 66 * iteration order as much as possible. 67 * 68 * <p>The collections returned by {@link #keySet()} and {@link #asMap} iterate 69 * through the keys in the order they were first added to the multimap. 70 * Similarly, {@link #get}, {@link #removeAll}, and {@link #replaceValues} 71 * return collections that iterate through the values in the order they were 72 * added. The collections generated by {@link #entries()}, {@link #keys()}, and 73 * {@link #values} iterate across the key-value mappings in the order they were 74 * added to the multimap. 75 * 76 * <p>The {@link #values()} and {@link #entries()} methods both return a 77 * {@code List}, instead of the {@code Collection} specified by the {@link 78 * ListMultimap} interface. 79 * 80 * <p>The methods {@link #get}, {@link #keySet()}, {@link #keys()}, 81 * {@link #values}, {@link #entries()}, and {@link #asMap} return collections 82 * that are views of the multimap. If the multimap is modified while an 83 * iteration over any of those collections is in progress, except through the 84 * iterator's methods, the results of the iteration are undefined. 85 * 86 * <p>Keys and values may be null. All optional multimap methods are supported, 87 * and all returned views are modifiable. 88 * 89 * <p>This class is not threadsafe when any concurrent operations update the 90 * multimap. Concurrent read operations will work correctly. To allow concurrent 91 * update operations, wrap your multimap with a call to {@link 92 * Multimaps#synchronizedListMultimap}. 93 * 94 * @author Mike Bostock 95 * @since 2.0 (imported from Google Collections Library) 96 */ 97@GwtCompatible(serializable = true, emulated = true) 98public class LinkedListMultimap<K, V> 99 implements ListMultimap<K, V>, Serializable { 100 /* 101 * Order is maintained using a linked list containing all key-value pairs. In 102 * addition, a series of disjoint linked lists of "siblings", each containing 103 * the values for a specific key, is used to implement {@link 104 * ValueForKeyIterator} in constant time. 105 */ 106 107 private static final class Node<K, V> { 108 final K key; 109 V value; 110 Node<K, V> next; // the next node (with any key) 111 Node<K, V> previous; // the previous node (with any key) 112 Node<K, V> nextSibling; // the next node with the same key 113 Node<K, V> previousSibling; // the previous node with the same key 114 115 Node(@Nullable K key, @Nullable V value) { 116 this.key = key; 117 this.value = value; 118 } 119 120 @Override public String toString() { 121 return key + "=" + value; 122 } 123 } 124 125 private transient Node<K, V> head; // the head for all keys 126 private transient Node<K, V> tail; // the tail for all keys 127 private transient Multiset<K> keyCount; // the number of values for each key 128 private transient Map<K, Node<K, V>> keyToKeyHead; // the head for a given key 129 private transient Map<K, Node<K, V>> keyToKeyTail; // the tail for a given key 130 131 /** 132 * Creates a new, empty {@code LinkedListMultimap} with the default initial 133 * capacity. 134 */ 135 public static <K, V> LinkedListMultimap<K, V> create() { 136 return new LinkedListMultimap<K, V>(); 137 } 138 139 /** 140 * Constructs an empty {@code LinkedListMultimap} with enough capacity to hold 141 * the specified number of keys without rehashing. 142 * 143 * @param expectedKeys the expected number of distinct keys 144 * @throws IllegalArgumentException if {@code expectedKeys} is negative 145 */ 146 public static <K, V> LinkedListMultimap<K, V> create(int expectedKeys) { 147 return new LinkedListMultimap<K, V>(expectedKeys); 148 } 149 150 /** 151 * Constructs a {@code LinkedListMultimap} with the same mappings as the 152 * specified {@code Multimap}. The new multimap has the same 153 * {@link Multimap#entries()} iteration order as the input multimap. 154 * 155 * @param multimap the multimap whose contents are copied to this multimap 156 */ 157 public static <K, V> LinkedListMultimap<K, V> create( 158 Multimap<? extends K, ? extends V> multimap) { 159 return new LinkedListMultimap<K, V>(multimap); 160 } 161 162 LinkedListMultimap() { 163 keyCount = LinkedHashMultiset.create(); 164 keyToKeyHead = Maps.newHashMap(); 165 keyToKeyTail = Maps.newHashMap(); 166 } 167 168 private LinkedListMultimap(int expectedKeys) { 169 keyCount = LinkedHashMultiset.create(expectedKeys); 170 keyToKeyHead = Maps.newHashMapWithExpectedSize(expectedKeys); 171 keyToKeyTail = Maps.newHashMapWithExpectedSize(expectedKeys); 172 } 173 174 private LinkedListMultimap(Multimap<? extends K, ? extends V> multimap) { 175 this(multimap.keySet().size()); 176 putAll(multimap); 177 } 178 179 /** 180 * Adds a new node for the specified key-value pair before the specified 181 * {@code nextSibling} element, or at the end of the list if {@code 182 * nextSibling} is null. Note: if {@code nextSibling} is specified, it MUST be 183 * for an node for the same {@code key}! 184 */ 185 private Node<K, V> addNode( 186 @Nullable K key, @Nullable V value, @Nullable Node<K, V> nextSibling) { 187 Node<K, V> node = new Node<K, V>(key, value); 188 if (head == null) { // empty list 189 head = tail = node; 190 keyToKeyHead.put(key, node); 191 keyToKeyTail.put(key, node); 192 } else if (nextSibling == null) { // non-empty list, add to tail 193 tail.next = node; 194 node.previous = tail; 195 Node<K, V> keyTail = keyToKeyTail.get(key); 196 if (keyTail == null) { // first for this key 197 keyToKeyHead.put(key, node); 198 } else { 199 keyTail.nextSibling = node; 200 node.previousSibling = keyTail; 201 } 202 keyToKeyTail.put(key, node); 203 tail = node; 204 } else { // non-empty list, insert before nextSibling 205 node.previous = nextSibling.previous; 206 node.previousSibling = nextSibling.previousSibling; 207 node.next = nextSibling; 208 node.nextSibling = nextSibling; 209 if (nextSibling.previousSibling == null) { // nextSibling was key head 210 keyToKeyHead.put(key, node); 211 } else { 212 nextSibling.previousSibling.nextSibling = node; 213 } 214 if (nextSibling.previous == null) { // nextSibling was head 215 head = node; 216 } else { 217 nextSibling.previous.next = node; 218 } 219 nextSibling.previous = node; 220 nextSibling.previousSibling = node; 221 } 222 keyCount.add(key); 223 return node; 224 } 225 226 /** 227 * Removes the specified node from the linked list. This method is only 228 * intended to be used from the {@code Iterator} classes. See also {@link 229 * LinkedListMultimap#removeAllNodes(Object)}. 230 */ 231 private void removeNode(Node<K, V> node) { 232 if (node.previous != null) { 233 node.previous.next = node.next; 234 } else { // node was head 235 head = node.next; 236 } 237 if (node.next != null) { 238 node.next.previous = node.previous; 239 } else { // node was tail 240 tail = node.previous; 241 } 242 if (node.previousSibling != null) { 243 node.previousSibling.nextSibling = node.nextSibling; 244 } else if (node.nextSibling != null) { // node was key head 245 keyToKeyHead.put(node.key, node.nextSibling); 246 } else { 247 keyToKeyHead.remove(node.key); // don't leak a key-null entry 248 } 249 if (node.nextSibling != null) { 250 node.nextSibling.previousSibling = node.previousSibling; 251 } else if (node.previousSibling != null) { // node was key tail 252 keyToKeyTail.put(node.key, node.previousSibling); 253 } else { 254 keyToKeyTail.remove(node.key); // don't leak a key-null entry 255 } 256 keyCount.remove(node.key); 257 } 258 259 /** Removes all nodes for the specified key. */ 260 private void removeAllNodes(@Nullable Object key) { 261 for (Iterator<V> i = new ValueForKeyIterator(key); i.hasNext();) { 262 i.next(); 263 i.remove(); 264 } 265 } 266 267 /** Helper method for verifying that an iterator element is present. */ 268 private static void checkElement(@Nullable Object node) { 269 if (node == null) { 270 throw new NoSuchElementException(); 271 } 272 } 273 274 /** An {@code Iterator} over all nodes. */ 275 private class NodeIterator implements ListIterator<Node<K, V>> { 276 int nextIndex; 277 Node<K, V> next; 278 Node<K, V> current; 279 Node<K, V> previous; 280 281 NodeIterator() { 282 next = head; 283 } 284 NodeIterator(int index) { 285 int size = size(); 286 Preconditions.checkPositionIndex(index, size); 287 if (index >= (size / 2)) { 288 previous = tail; 289 nextIndex = size; 290 while (index++ < size) { 291 previous(); 292 } 293 } else { 294 next = head; 295 while (index-- > 0) { 296 next(); 297 } 298 } 299 current = null; 300 } 301 @Override 302 public boolean hasNext() { 303 return next != null; 304 } 305 @Override 306 public Node<K, V> next() { 307 checkElement(next); 308 previous = current = next; 309 next = next.next; 310 nextIndex++; 311 return current; 312 } 313 @Override 314 public void remove() { 315 checkState(current != null); 316 if (current != next) { // after call to next() 317 previous = current.previous; 318 nextIndex--; 319 } else { // after call to previous() 320 next = current.next; 321 } 322 removeNode(current); 323 current = null; 324 } 325 @Override 326 public boolean hasPrevious() { 327 return previous != null; 328 } 329 @Override 330 public Node<K, V> previous() { 331 checkElement(previous); 332 next = current = previous; 333 previous = previous.previous; 334 nextIndex--; 335 return current; 336 } 337 @Override 338 public int nextIndex() { 339 return nextIndex; 340 } 341 @Override 342 public int previousIndex() { 343 return nextIndex - 1; 344 } 345 @Override 346 public void set(Node<K, V> e) { 347 throw new UnsupportedOperationException(); 348 } 349 @Override 350 public void add(Node<K, V> e) { 351 throw new UnsupportedOperationException(); 352 } 353 void setValue(V value) { 354 checkState(current != null); 355 current.value = value; 356 } 357 } 358 359 /** An {@code Iterator} over distinct keys in key head order. */ 360 private class DistinctKeyIterator implements Iterator<K> { 361 final Set<K> seenKeys = Sets.<K>newHashSetWithExpectedSize(keySet().size()); 362 Node<K, V> next = head; 363 Node<K, V> current; 364 365 @Override 366 public boolean hasNext() { 367 return next != null; 368 } 369 @Override 370 public K next() { 371 checkElement(next); 372 current = next; 373 seenKeys.add(current.key); 374 do { // skip ahead to next unseen key 375 next = next.next; 376 } while ((next != null) && !seenKeys.add(next.key)); 377 return current.key; 378 } 379 @Override 380 public void remove() { 381 checkState(current != null); 382 removeAllNodes(current.key); 383 current = null; 384 } 385 } 386 387 /** A {@code ListIterator} over values for a specified key. */ 388 private class ValueForKeyIterator implements ListIterator<V> { 389 final Object key; 390 int nextIndex; 391 Node<K, V> next; 392 Node<K, V> current; 393 Node<K, V> previous; 394 395 /** Constructs a new iterator over all values for the specified key. */ 396 ValueForKeyIterator(@Nullable Object key) { 397 this.key = key; 398 next = keyToKeyHead.get(key); 399 } 400 401 /** 402 * Constructs a new iterator over all values for the specified key starting 403 * at the specified index. This constructor is optimized so that it starts 404 * at either the head or the tail, depending on which is closer to the 405 * specified index. This allows adds to the tail to be done in constant 406 * time. 407 * 408 * @throws IndexOutOfBoundsException if index is invalid 409 */ 410 public ValueForKeyIterator(@Nullable Object key, int index) { 411 int size = keyCount.count(key); 412 Preconditions.checkPositionIndex(index, size); 413 if (index >= (size / 2)) { 414 previous = keyToKeyTail.get(key); 415 nextIndex = size; 416 while (index++ < size) { 417 previous(); 418 } 419 } else { 420 next = keyToKeyHead.get(key); 421 while (index-- > 0) { 422 next(); 423 } 424 } 425 this.key = key; 426 current = null; 427 } 428 429 @Override 430 public boolean hasNext() { 431 return next != null; 432 } 433 434 @Override 435 public V next() { 436 checkElement(next); 437 previous = current = next; 438 next = next.nextSibling; 439 nextIndex++; 440 return current.value; 441 } 442 443 @Override 444 public boolean hasPrevious() { 445 return previous != null; 446 } 447 448 @Override 449 public V previous() { 450 checkElement(previous); 451 next = current = previous; 452 previous = previous.previousSibling; 453 nextIndex--; 454 return current.value; 455 } 456 457 @Override 458 public int nextIndex() { 459 return nextIndex; 460 } 461 462 @Override 463 public int previousIndex() { 464 return nextIndex - 1; 465 } 466 467 @Override 468 public void remove() { 469 checkState(current != null); 470 if (current != next) { // after call to next() 471 previous = current.previousSibling; 472 nextIndex--; 473 } else { // after call to previous() 474 next = current.nextSibling; 475 } 476 removeNode(current); 477 current = null; 478 } 479 480 @Override 481 public void set(V value) { 482 checkState(current != null); 483 current.value = value; 484 } 485 486 @Override 487 @SuppressWarnings("unchecked") 488 public void add(V value) { 489 previous = addNode((K) key, value, next); 490 nextIndex++; 491 current = null; 492 } 493 } 494 495 // Query Operations 496 497 @Override 498 public int size() { 499 return keyCount.size(); 500 } 501 502 @Override 503 public boolean isEmpty() { 504 return head == null; 505 } 506 507 @Override 508 public boolean containsKey(@Nullable Object key) { 509 return keyToKeyHead.containsKey(key); 510 } 511 512 @Override 513 public boolean containsValue(@Nullable Object value) { 514 for (Iterator<Node<K, V>> i = new NodeIterator(); i.hasNext();) { 515 if (Objects.equal(i.next().value, value)) { 516 return true; 517 } 518 } 519 return false; 520 } 521 522 @Override 523 public boolean containsEntry(@Nullable Object key, @Nullable Object value) { 524 for (Iterator<V> i = new ValueForKeyIterator(key); i.hasNext();) { 525 if (Objects.equal(i.next(), value)) { 526 return true; 527 } 528 } 529 return false; 530 } 531 532 // Modification Operations 533 534 /** 535 * Stores a key-value pair in the multimap. 536 * 537 * @param key key to store in the multimap 538 * @param value value to store in the multimap 539 * @return {@code true} always 540 */ 541 @Override 542 public boolean put(@Nullable K key, @Nullable V value) { 543 addNode(key, value, null); 544 return true; 545 } 546 547 @Override 548 public boolean remove(@Nullable Object key, @Nullable Object value) { 549 Iterator<V> values = new ValueForKeyIterator(key); 550 while (values.hasNext()) { 551 if (Objects.equal(values.next(), value)) { 552 values.remove(); 553 return true; 554 } 555 } 556 return false; 557 } 558 559 // Bulk Operations 560 561 @Override 562 public boolean putAll(@Nullable K key, Iterable<? extends V> values) { 563 boolean changed = false; 564 for (V value : values) { 565 changed |= put(key, value); 566 } 567 return changed; 568 } 569 570 @Override 571 public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 572 boolean changed = false; 573 for (Entry<? extends K, ? extends V> entry : multimap.entries()) { 574 changed |= put(entry.getKey(), entry.getValue()); 575 } 576 return changed; 577 } 578 579 /** 580 * {@inheritDoc} 581 * 582 * <p>If any entries for the specified {@code key} already exist in the 583 * multimap, their values are changed in-place without affecting the iteration 584 * order. 585 * 586 * <p>The returned list is immutable and implements 587 * {@link java.util.RandomAccess}. 588 */ 589 @Override 590 public List<V> replaceValues(@Nullable K key, Iterable<? extends V> values) { 591 List<V> oldValues = getCopy(key); 592 ListIterator<V> keyValues = new ValueForKeyIterator(key); 593 Iterator<? extends V> newValues = values.iterator(); 594 595 // Replace existing values, if any. 596 while (keyValues.hasNext() && newValues.hasNext()) { 597 keyValues.next(); 598 keyValues.set(newValues.next()); 599 } 600 601 // Remove remaining old values, if any. 602 while (keyValues.hasNext()) { 603 keyValues.next(); 604 keyValues.remove(); 605 } 606 607 // Add remaining new values, if any. 608 while (newValues.hasNext()) { 609 keyValues.add(newValues.next()); 610 } 611 612 return oldValues; 613 } 614 615 private List<V> getCopy(@Nullable Object key) { 616 return unmodifiableList(Lists.newArrayList(new ValueForKeyIterator(key))); 617 } 618 619 /** 620 * {@inheritDoc} 621 * 622 * <p>The returned list is immutable and implements 623 * {@link java.util.RandomAccess}. 624 */ 625 @Override 626 public List<V> removeAll(@Nullable Object key) { 627 List<V> oldValues = getCopy(key); 628 removeAllNodes(key); 629 return oldValues; 630 } 631 632 @Override 633 public void clear() { 634 head = null; 635 tail = null; 636 keyCount.clear(); 637 keyToKeyHead.clear(); 638 keyToKeyTail.clear(); 639 } 640 641 // Views 642 643 /** 644 * {@inheritDoc} 645 * 646 * <p>If the multimap is modified while an iteration over the list is in 647 * progress (except through the iterator's own {@code add}, {@code set} or 648 * {@code remove} operations) the results of the iteration are undefined. 649 * 650 * <p>The returned list is not serializable and does not have random access. 651 */ 652 @Override 653 public List<V> get(final @Nullable K key) { 654 return new AbstractSequentialList<V>() { 655 @Override public int size() { 656 return keyCount.count(key); 657 } 658 @Override public ListIterator<V> listIterator(int index) { 659 return new ValueForKeyIterator(key, index); 660 } 661 @Override public boolean removeAll(Collection<?> c) { 662 return Iterators.removeAll(iterator(), c); 663 } 664 @Override public boolean retainAll(Collection<?> c) { 665 return Iterators.retainAll(iterator(), c); 666 } 667 }; 668 } 669 670 private transient Set<K> keySet; 671 672 @Override 673 public Set<K> keySet() { 674 Set<K> result = keySet; 675 if (result == null) { 676 keySet = result = new AbstractSet<K>() { 677 @Override public int size() { 678 return keyCount.elementSet().size(); 679 } 680 @Override public Iterator<K> iterator() { 681 return new DistinctKeyIterator(); 682 } 683 @Override public boolean contains(Object key) { // for performance 684 return keyCount.contains(key); 685 } 686 @Override public boolean removeAll(Collection<?> c) { 687 checkNotNull(c); // eager for GWT 688 return super.removeAll(c); 689 } 690 }; 691 } 692 return result; 693 } 694 695 private transient Multiset<K> keys; 696 697 @Override 698 public Multiset<K> keys() { 699 Multiset<K> result = keys; 700 if (result == null) { 701 keys = result = new MultisetView(); 702 } 703 return result; 704 } 705 706 private class MultisetView extends AbstractCollection<K> 707 implements Multiset<K> { 708 709 @Override public int size() { 710 return keyCount.size(); 711 } 712 713 @Override public Iterator<K> iterator() { 714 final Iterator<Node<K, V>> nodes = new NodeIterator(); 715 return new Iterator<K>() { 716 @Override 717 public boolean hasNext() { 718 return nodes.hasNext(); 719 } 720 @Override 721 public K next() { 722 return nodes.next().key; 723 } 724 @Override 725 public void remove() { 726 nodes.remove(); 727 } 728 }; 729 } 730 731 @Override 732 public int count(@Nullable Object key) { 733 return keyCount.count(key); 734 } 735 736 @Override 737 public int add(@Nullable K key, int occurrences) { 738 throw new UnsupportedOperationException(); 739 } 740 741 @Override 742 public int remove(@Nullable Object key, int occurrences) { 743 checkArgument(occurrences >= 0); 744 int oldCount = count(key); 745 Iterator<V> values = new ValueForKeyIterator(key); 746 while ((occurrences-- > 0) && values.hasNext()) { 747 values.next(); 748 values.remove(); 749 } 750 return oldCount; 751 } 752 753 @Override 754 public int setCount(K element, int count) { 755 return setCountImpl(this, element, count); 756 } 757 758 @Override 759 public boolean setCount(K element, int oldCount, int newCount) { 760 return setCountImpl(this, element, oldCount, newCount); 761 } 762 763 @Override public boolean removeAll(Collection<?> c) { 764 return Iterators.removeAll(iterator(), c); 765 } 766 767 @Override public boolean retainAll(Collection<?> c) { 768 return Iterators.retainAll(iterator(), c); 769 } 770 771 @Override 772 public Set<K> elementSet() { 773 return keySet(); 774 } 775 776 @Override 777 public Set<Entry<K>> entrySet() { 778 // TODO(jlevy): lazy init? 779 return new AbstractSet<Entry<K>>() { 780 @Override public int size() { 781 return keyCount.elementSet().size(); 782 } 783 784 @Override public Iterator<Entry<K>> iterator() { 785 final Iterator<K> keyIterator = new DistinctKeyIterator(); 786 return new Iterator<Entry<K>>() { 787 @Override 788 public boolean hasNext() { 789 return keyIterator.hasNext(); 790 } 791 @Override 792 public Entry<K> next() { 793 final K key = keyIterator.next(); 794 return new Multisets.AbstractEntry<K>() { 795 @Override 796 public K getElement() { 797 return key; 798 } 799 @Override 800 public int getCount() { 801 return keyCount.count(key); 802 } 803 }; 804 } 805 @Override 806 public void remove() { 807 keyIterator.remove(); 808 } 809 }; 810 } 811 }; 812 } 813 814 @Override public boolean equals(@Nullable Object object) { 815 return keyCount.equals(object); 816 } 817 818 @Override public int hashCode() { 819 return keyCount.hashCode(); 820 } 821 822 @Override public String toString() { 823 return keyCount.toString(); // XXX observe order? 824 } 825 } 826 827 private transient List<V> valuesList; 828 829 /** 830 * {@inheritDoc} 831 * 832 * <p>The iterator generated by the returned collection traverses the values 833 * in the order they were added to the multimap. Because the values may have 834 * duplicates and follow the insertion ordering, this method returns a {@link 835 * List}, instead of the {@link Collection} specified in the {@link 836 * ListMultimap} interface. 837 */ 838 @Override 839 public List<V> values() { 840 List<V> result = valuesList; 841 if (result == null) { 842 valuesList = result = new AbstractSequentialList<V>() { 843 @Override public int size() { 844 return keyCount.size(); 845 } 846 @Override 847 public ListIterator<V> listIterator(int index) { 848 final NodeIterator nodes = new NodeIterator(index); 849 return new ListIterator<V>() { 850 @Override 851 public boolean hasNext() { 852 return nodes.hasNext(); 853 } 854 @Override 855 public V next() { 856 return nodes.next().value; 857 } 858 @Override 859 public boolean hasPrevious() { 860 return nodes.hasPrevious(); 861 } 862 @Override 863 public V previous() { 864 return nodes.previous().value; 865 } 866 @Override 867 public int nextIndex() { 868 return nodes.nextIndex(); 869 } 870 @Override 871 public int previousIndex() { 872 return nodes.previousIndex(); 873 } 874 @Override 875 public void remove() { 876 nodes.remove(); 877 } 878 @Override 879 public void set(V e) { 880 nodes.setValue(e); 881 } 882 @Override 883 public void add(V e) { 884 throw new UnsupportedOperationException(); 885 } 886 }; 887 } 888 }; 889 } 890 return result; 891 } 892 893 private static <K, V> Entry<K, V> createEntry(final Node<K, V> node) { 894 return new AbstractMapEntry<K, V>() { 895 @Override public K getKey() { 896 return node.key; 897 } 898 @Override public V getValue() { 899 return node.value; 900 } 901 @Override public V setValue(V value) { 902 V oldValue = node.value; 903 node.value = value; 904 return oldValue; 905 } 906 }; 907 } 908 909 private transient List<Entry<K, V>> entries; 910 911 /** 912 * {@inheritDoc} 913 * 914 * <p>The iterator generated by the returned collection traverses the entries 915 * in the order they were added to the multimap. Because the entries may have 916 * duplicates and follow the insertion ordering, this method returns a {@link 917 * List}, instead of the {@link Collection} specified in the {@link 918 * ListMultimap} interface. 919 * 920 * <p>An entry's {@link Entry#getKey} method always returns the same key, 921 * regardless of what happens subsequently. As long as the corresponding 922 * key-value mapping is not removed from the multimap, {@link Entry#getValue} 923 * returns the value from the multimap, which may change over time, and {@link 924 * Entry#setValue} modifies that value. Removing the mapping from the 925 * multimap does not alter the value returned by {@code getValue()}, though a 926 * subsequent {@code setValue()} call won't update the multimap but will lead 927 * to a revised value being returned by {@code getValue()}. 928 */ 929 @Override 930 public List<Entry<K, V>> entries() { 931 List<Entry<K, V>> result = entries; 932 if (result == null) { 933 entries = result = new AbstractSequentialList<Entry<K, V>>() { 934 @Override public int size() { 935 return keyCount.size(); 936 } 937 938 @Override public ListIterator<Entry<K, V>> listIterator(int index) { 939 final ListIterator<Node<K, V>> nodes = new NodeIterator(index); 940 return new ListIterator<Entry<K, V>>() { 941 @Override 942 public boolean hasNext() { 943 return nodes.hasNext(); 944 } 945 946 @Override 947 public Entry<K, V> next() { 948 return createEntry(nodes.next()); 949 } 950 951 @Override 952 public void remove() { 953 nodes.remove(); 954 } 955 956 @Override 957 public boolean hasPrevious() { 958 return nodes.hasPrevious(); 959 } 960 961 @Override 962 public Map.Entry<K, V> previous() { 963 return createEntry(nodes.previous()); 964 } 965 966 @Override 967 public int nextIndex() { 968 return nodes.nextIndex(); 969 } 970 971 @Override 972 public int previousIndex() { 973 return nodes.previousIndex(); 974 } 975 976 @Override 977 public void set(Map.Entry<K, V> e) { 978 throw new UnsupportedOperationException(); 979 } 980 981 @Override 982 public void add(Map.Entry<K, V> e) { 983 throw new UnsupportedOperationException(); 984 } 985 }; 986 } 987 }; 988 } 989 return result; 990 } 991 992 private class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> { 993 @Override public int size() { 994 return keyCount.elementSet().size(); 995 } 996 997 @Override public Iterator<Entry<K, Collection<V>>> iterator() { 998 final Iterator<K> keyIterator = new DistinctKeyIterator(); 999 return new Iterator<Entry<K, Collection<V>>>() { 1000 @Override 1001 public boolean hasNext() { 1002 return keyIterator.hasNext(); 1003 } 1004 1005 @Override 1006 public Entry<K, Collection<V>> next() { 1007 final K key = keyIterator.next(); 1008 return new AbstractMapEntry<K, Collection<V>>() { 1009 @Override public K getKey() { 1010 return key; 1011 } 1012 1013 @Override public Collection<V> getValue() { 1014 return LinkedListMultimap.this.get(key); 1015 } 1016 }; 1017 } 1018 1019 @Override 1020 public void remove() { 1021 keyIterator.remove(); 1022 } 1023 }; 1024 } 1025 1026 // TODO(jlevy): Override contains() and remove() for better performance. 1027 } 1028 1029 private transient Map<K, Collection<V>> map; 1030 1031 @Override 1032 public Map<K, Collection<V>> asMap() { 1033 Map<K, Collection<V>> result = map; 1034 if (result == null) { 1035 map = result = new AbstractMap<K, Collection<V>>() { 1036 Set<Entry<K, Collection<V>>> entrySet; 1037 1038 @Override public Set<Entry<K, Collection<V>>> entrySet() { 1039 Set<Entry<K, Collection<V>>> result = entrySet; 1040 if (result == null) { 1041 entrySet = result = new AsMapEntries(); 1042 } 1043 return result; 1044 } 1045 1046 // The following methods are included for performance. 1047 1048 @Override public boolean containsKey(@Nullable Object key) { 1049 return LinkedListMultimap.this.containsKey(key); 1050 } 1051 1052 @SuppressWarnings("unchecked") 1053 @Override public Collection<V> get(@Nullable Object key) { 1054 Collection<V> collection = LinkedListMultimap.this.get((K) key); 1055 return collection.isEmpty() ? null : collection; 1056 } 1057 1058 @Override public Collection<V> remove(@Nullable Object key) { 1059 Collection<V> collection = removeAll(key); 1060 return collection.isEmpty() ? null : collection; 1061 } 1062 }; 1063 } 1064 1065 return result; 1066 } 1067 1068 // Comparison and hashing 1069 1070 /** 1071 * Compares the specified object to this multimap for equality. 1072 * 1073 * <p>Two {@code ListMultimap} instances are equal if, for each key, they 1074 * contain the same values in the same order. If the value orderings disagree, 1075 * the multimaps will not be considered equal. 1076 */ 1077 @Override public boolean equals(@Nullable Object other) { 1078 if (other == this) { 1079 return true; 1080 } 1081 if (other instanceof Multimap) { 1082 Multimap<?, ?> that = (Multimap<?, ?>) other; 1083 return this.asMap().equals(that.asMap()); 1084 } 1085 return false; 1086 } 1087 1088 /** 1089 * Returns the hash code for this multimap. 1090 * 1091 * <p>The hash code of a multimap is defined as the hash code of the map view, 1092 * as returned by {@link Multimap#asMap}. 1093 */ 1094 @Override public int hashCode() { 1095 return asMap().hashCode(); 1096 } 1097 1098 /** 1099 * Returns a string representation of the multimap, generated by calling 1100 * {@code toString} on the map returned by {@link Multimap#asMap}. 1101 * 1102 * @return a string representation of the multimap 1103 */ 1104 @Override public String toString() { 1105 return asMap().toString(); 1106 } 1107} 1108 1109