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.base.Preconditions.checkArgument;
20  import static com.google.common.base.Preconditions.checkNotNull;
21  import static com.google.common.collect.CollectPreconditions.checkRemove;
22  
23  import com.google.common.annotations.GwtCompatible;
24  import com.google.common.collect.Maps.ViewCachingAbstractMap;
25  import com.google.j2objc.annotations.WeakOuter;
26  import java.io.Serializable;
27  import java.util.AbstractCollection;
28  import java.util.Collection;
29  import java.util.Collections;
30  import java.util.Comparator;
31  import java.util.ConcurrentModificationException;
32  import java.util.Iterator;
33  import java.util.List;
34  import java.util.ListIterator;
35  import java.util.Map;
36  import java.util.Map.Entry;
37  import java.util.NavigableMap;
38  import java.util.NavigableSet;
39  import java.util.RandomAccess;
40  import java.util.Set;
41  import java.util.SortedMap;
42  import java.util.SortedSet;
43  import java.util.Spliterator;
44  import java.util.function.BiConsumer;
45  import javax.annotation.Nullable;
46  
47  /**
48   * Basic implementation of the {@link Multimap} interface. This class represents
49   * a multimap as a map that associates each key with a collection of values. All
50   * methods of {@link Multimap} are supported, including those specified as
51   * optional in the interface.
52   *
53   * <p>To implement a multimap, a subclass must define the method {@link
54   * #createCollection()}, which creates an empty collection of values for a key.
55   *
56   * <p>The multimap constructor takes a map that has a single entry for each
57   * distinct key. When you insert a key-value pair with a key that isn't already
58   * in the multimap, {@code AbstractMapBasedMultimap} calls {@link #createCollection()}
59   * to create the collection of values for that key. The subclass should not call
60   * {@link #createCollection()} directly, and a new instance should be created
61   * every time the method is called.
62   *
63   * <p>For example, the subclass could pass a {@link java.util.TreeMap} during
64   * construction, and {@link #createCollection()} could return a {@link
65   * java.util.TreeSet}, in which case the multimap's iterators would propagate
66   * through the keys and values in sorted order.
67   *
68   * <p>Keys and values may be null, as long as the underlying collection classes
69   * support null elements.
70   *
71   * <p>The collections created by {@link #createCollection()} may or may not
72   * allow duplicates. If the collection, such as a {@link Set}, does not support
73   * duplicates, an added key-value pair will replace an existing pair with the
74   * same key and value, if such a pair is present. With collections like {@link
75   * List} that allow duplicates, the collection will keep the existing key-value
76   * pairs while adding a new pair.
77   *
78   * <p>This class is not threadsafe when any concurrent operations update the
79   * multimap, even if the underlying map and {@link #createCollection()} method
80   * return threadsafe classes. Concurrent read operations will work correctly. To
81   * allow concurrent update operations, wrap your multimap with a call to {@link
82   * Multimaps#synchronizedMultimap}.
83   *
84   * <p>For serialization to work, the subclass must specify explicit
85   * {@code readObject} and {@code writeObject} methods.
86   *
87   * @author Jared Levy
88   * @author Louis Wasserman
89   */
90  @GwtCompatible
91  abstract class AbstractMapBasedMultimap<K, V> extends AbstractMultimap<K, V>
92      implements Serializable {
93    /*
94     * Here's an outline of the overall design.
95     *
96     * The map variable contains the collection of values associated with each
97     * key. When a key-value pair is added to a multimap that didn't previously
98     * contain any values for that key, a new collection generated by
99     * createCollection is added to the map. That same collection instance
100    * remains in the map as long as the multimap has any values for the key. If
101    * all values for the key are removed, the key and collection are removed
102    * from the map.
103    *
104    * The get method returns a WrappedCollection, which decorates the collection
105    * in the map (if the key is present) or an empty collection (if the key is
106    * not present). When the collection delegate in the WrappedCollection is
107    * empty, the multimap may contain subsequently added values for that key. To
108    * handle that situation, the WrappedCollection checks whether map contains
109    * an entry for the provided key, and if so replaces the delegate.
110    */
111 
112   private transient Map<K, Collection<V>> map;
113   private transient int totalSize;
114 
115   /**
116    * Creates a new multimap that uses the provided map.
117    *
118    * @param map place to store the mapping from each key to its corresponding
119    *     values
120    * @throws IllegalArgumentException if {@code map} is not empty
121    */
122   protected AbstractMapBasedMultimap(Map<K, Collection<V>> map) {
123     checkArgument(map.isEmpty());
124     this.map = map;
125   }
126 
127   /** Used during deserialization only. */
128   final void setMap(Map<K, Collection<V>> map) {
129     this.map = map;
130     totalSize = 0;
131     for (Collection<V> values : map.values()) {
132       checkArgument(!values.isEmpty());
133       totalSize += values.size();
134     }
135   }
136 
137   /**
138    * Creates an unmodifiable, empty collection of values.
139    *
140    * <p>This is used in {@link #removeAll} on an empty key.
141    */
142   Collection<V> createUnmodifiableEmptyCollection() {
143     return unmodifiableCollectionSubclass(createCollection());
144   }
145 
146   /**
147    * Creates the collection of values for a single key.
148    *
149    * <p>Collections with weak, soft, or phantom references are not supported.
150    * Each call to {@code createCollection} should create a new instance.
151    *
152    * <p>The returned collection class determines whether duplicate key-value
153    * pairs are allowed.
154    *
155    * @return an empty collection of values
156    */
157   abstract Collection<V> createCollection();
158 
159   /**
160    * Creates the collection of values for an explicitly provided key. By
161    * default, it simply calls {@link #createCollection()}, which is the correct
162    * behavior for most implementations. The {@link LinkedHashMultimap} class
163    * overrides it.
164    *
165    * @param key key to associate with values in the collection
166    * @return an empty collection of values
167    */
168   Collection<V> createCollection(@Nullable K key) {
169     return createCollection();
170   }
171 
172   Map<K, Collection<V>> backingMap() {
173     return map;
174   }
175 
176   // Query Operations
177 
178   @Override
179   public int size() {
180     return totalSize;
181   }
182 
183   @Override
184   public boolean containsKey(@Nullable Object key) {
185     return map.containsKey(key);
186   }
187 
188   // Modification Operations
189 
190   @Override
191   public boolean put(@Nullable K key, @Nullable V value) {
192     Collection<V> collection = map.get(key);
193     if (collection == null) {
194       collection = createCollection(key);
195       if (collection.add(value)) {
196         totalSize++;
197         map.put(key, collection);
198         return true;
199       } else {
200         throw new AssertionError("New Collection violated the Collection spec");
201       }
202     } else if (collection.add(value)) {
203       totalSize++;
204       return true;
205     } else {
206       return false;
207     }
208   }
209 
210   private Collection<V> getOrCreateCollection(@Nullable K key) {
211     Collection<V> collection = map.get(key);
212     if (collection == null) {
213       collection = createCollection(key);
214       map.put(key, collection);
215     }
216     return collection;
217   }
218 
219   // Bulk Operations
220 
221   /**
222    * {@inheritDoc}
223    *
224    * <p>The returned collection is immutable.
225    */
226   @Override
227   public Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
228     Iterator<? extends V> iterator = values.iterator();
229     if (!iterator.hasNext()) {
230       return removeAll(key);
231     }
232 
233     // TODO(lowasser): investigate atomic failure?
234     Collection<V> collection = getOrCreateCollection(key);
235     Collection<V> oldValues = createCollection();
236     oldValues.addAll(collection);
237 
238     totalSize -= collection.size();
239     collection.clear();
240 
241     while (iterator.hasNext()) {
242       if (collection.add(iterator.next())) {
243         totalSize++;
244       }
245     }
246 
247     return unmodifiableCollectionSubclass(oldValues);
248   }
249 
250   /**
251    * {@inheritDoc}
252    *
253    * <p>The returned collection is immutable.
254    */
255   @Override
256   public Collection<V> removeAll(@Nullable Object key) {
257     Collection<V> collection = map.remove(key);
258 
259     if (collection == null) {
260       return createUnmodifiableEmptyCollection();
261     }
262 
263     Collection<V> output = createCollection();
264     output.addAll(collection);
265     totalSize -= collection.size();
266     collection.clear();
267 
268     return unmodifiableCollectionSubclass(output);
269   }
270 
271   static <E> Collection<E> unmodifiableCollectionSubclass(Collection<E> collection) {
272     if (collection instanceof NavigableSet) {
273       return Sets.unmodifiableNavigableSet((NavigableSet<E>) collection);
274     } else if (collection instanceof SortedSet) {
275       return Collections.unmodifiableSortedSet((SortedSet<E>) collection);
276     } else if (collection instanceof Set) {
277       return Collections.unmodifiableSet((Set<E>) collection);
278     } else if (collection instanceof List) {
279       return Collections.unmodifiableList((List<E>) collection);
280     } else {
281       return Collections.unmodifiableCollection(collection);
282     }
283   }
284 
285   @Override
286   public void clear() {
287     // Clear each collection, to make previously returned collections empty.
288     for (Collection<V> collection : map.values()) {
289       collection.clear();
290     }
291     map.clear();
292     totalSize = 0;
293   }
294 
295   // Views
296 
297   /**
298    * {@inheritDoc}
299    *
300    * <p>The returned collection is not serializable.
301    */
302   @Override
303   public Collection<V> get(@Nullable K key) {
304     Collection<V> collection = map.get(key);
305     if (collection == null) {
306       collection = createCollection(key);
307     }
308     return wrapCollection(key, collection);
309   }
310 
311   /**
312    * Generates a decorated collection that remains consistent with the values in
313    * the multimap for the provided key. Changes to the multimap may alter the
314    * returned collection, and vice versa.
315    */
316   Collection<V> wrapCollection(@Nullable K key, Collection<V> collection) {
317     if (collection instanceof NavigableSet) {
318       return new WrappedNavigableSet(key, (NavigableSet<V>) collection, null);
319     } else if (collection instanceof SortedSet) {
320       return new WrappedSortedSet(key, (SortedSet<V>) collection, null);
321     } else if (collection instanceof Set) {
322       return new WrappedSet(key, (Set<V>) collection);
323     } else if (collection instanceof List) {
324       return wrapList(key, (List<V>) collection, null);
325     } else {
326       return new WrappedCollection(key, collection, null);
327     }
328   }
329 
330   private List<V> wrapList(@Nullable K key, List<V> list, @Nullable WrappedCollection ancestor) {
331     return (list instanceof RandomAccess)
332         ? new RandomAccessWrappedList(key, list, ancestor)
333         : new WrappedList(key, list, ancestor);
334   }
335 
336   /**
337    * Collection decorator that stays in sync with the multimap values for a key.
338    * There are two kinds of wrapped collections: full and subcollections. Both
339    * have a delegate pointing to the underlying collection class.
340    *
341    * <p>Full collections, identified by a null ancestor field, contain all
342    * multimap values for a given key. Its delegate is a value in {@link
343    * AbstractMapBasedMultimap#map} whenever the delegate is non-empty. The {@code
344    * refreshIfEmpty}, {@code removeIfEmpty}, and {@code addToMap} methods ensure
345    * that the {@code WrappedCollection} and map remain consistent.
346    *
347    * <p>A subcollection, such as a sublist, contains some of the values for a
348    * given key. Its ancestor field points to the full wrapped collection with
349    * all values for the key. The subcollection {@code refreshIfEmpty}, {@code
350    * removeIfEmpty}, and {@code addToMap} methods call the corresponding methods
351    * of the full wrapped collection.
352    */
353   @WeakOuter
354   private class WrappedCollection extends AbstractCollection<V> {
355     final K key;
356     Collection<V> delegate;
357     final WrappedCollection ancestor;
358     final Collection<V> ancestorDelegate;
359 
360     WrappedCollection(
361         @Nullable K key, Collection<V> delegate, @Nullable WrappedCollection ancestor) {
362       this.key = key;
363       this.delegate = delegate;
364       this.ancestor = ancestor;
365       this.ancestorDelegate = (ancestor == null) ? null : ancestor.getDelegate();
366     }
367 
368     /**
369      * If the delegate collection is empty, but the multimap has values for the
370      * key, replace the delegate with the new collection for the key.
371      *
372      * <p>For a subcollection, refresh its ancestor and validate that the
373      * ancestor delegate hasn't changed.
374      */
375     void refreshIfEmpty() {
376       if (ancestor != null) {
377         ancestor.refreshIfEmpty();
378         if (ancestor.getDelegate() != ancestorDelegate) {
379           throw new ConcurrentModificationException();
380         }
381       } else if (delegate.isEmpty()) {
382         Collection<V> newDelegate = map.get(key);
383         if (newDelegate != null) {
384           delegate = newDelegate;
385         }
386       }
387     }
388 
389     /**
390      * If collection is empty, remove it from {@code AbstractMapBasedMultimap.this.map}.
391      * For subcollections, check whether the ancestor collection is empty.
392      */
393     void removeIfEmpty() {
394       if (ancestor != null) {
395         ancestor.removeIfEmpty();
396       } else if (delegate.isEmpty()) {
397         map.remove(key);
398       }
399     }
400 
401     K getKey() {
402       return key;
403     }
404 
405     /**
406      * Add the delegate to the map. Other {@code WrappedCollection} methods
407      * should call this method after adding elements to a previously empty
408      * collection.
409      *
410      * <p>Subcollection add the ancestor's delegate instead.
411      */
412     void addToMap() {
413       if (ancestor != null) {
414         ancestor.addToMap();
415       } else {
416         map.put(key, delegate);
417       }
418     }
419 
420     @Override
421     public int size() {
422       refreshIfEmpty();
423       return delegate.size();
424     }
425 
426     @Override
427     public boolean equals(@Nullable Object object) {
428       if (object == this) {
429         return true;
430       }
431       refreshIfEmpty();
432       return delegate.equals(object);
433     }
434 
435     @Override
436     public int hashCode() {
437       refreshIfEmpty();
438       return delegate.hashCode();
439     }
440 
441     @Override
442     public String toString() {
443       refreshIfEmpty();
444       return delegate.toString();
445     }
446 
447     Collection<V> getDelegate() {
448       return delegate;
449     }
450 
451     @Override
452     public Iterator<V> iterator() {
453       refreshIfEmpty();
454       return new WrappedIterator();
455     }
456     
457     @Override
458     public Spliterator<V> spliterator() {
459       refreshIfEmpty();
460       return delegate.spliterator();
461     }
462 
463     /** Collection iterator for {@code WrappedCollection}. */
464     class WrappedIterator implements Iterator<V> {
465       final Iterator<V> delegateIterator;
466       final Collection<V> originalDelegate = delegate;
467 
468       WrappedIterator() {
469         delegateIterator = iteratorOrListIterator(delegate);
470       }
471 
472       WrappedIterator(Iterator<V> delegateIterator) {
473         this.delegateIterator = delegateIterator;
474       }
475 
476       /**
477        * If the delegate changed since the iterator was created, the iterator is
478        * no longer valid.
479        */
480       void validateIterator() {
481         refreshIfEmpty();
482         if (delegate != originalDelegate) {
483           throw new ConcurrentModificationException();
484         }
485       }
486 
487       @Override
488       public boolean hasNext() {
489         validateIterator();
490         return delegateIterator.hasNext();
491       }
492 
493       @Override
494       public V next() {
495         validateIterator();
496         return delegateIterator.next();
497       }
498 
499       @Override
500       public void remove() {
501         delegateIterator.remove();
502         totalSize--;
503         removeIfEmpty();
504       }
505 
506       Iterator<V> getDelegateIterator() {
507         validateIterator();
508         return delegateIterator;
509       }
510     }
511 
512     @Override
513     public boolean add(V value) {
514       refreshIfEmpty();
515       boolean wasEmpty = delegate.isEmpty();
516       boolean changed = delegate.add(value);
517       if (changed) {
518         totalSize++;
519         if (wasEmpty) {
520           addToMap();
521         }
522       }
523       return changed;
524     }
525 
526     WrappedCollection getAncestor() {
527       return ancestor;
528     }
529 
530     // The following methods are provided for better performance.
531 
532     @Override
533     public boolean addAll(Collection<? extends V> collection) {
534       if (collection.isEmpty()) {
535         return false;
536       }
537       int oldSize = size(); // calls refreshIfEmpty
538       boolean changed = delegate.addAll(collection);
539       if (changed) {
540         int newSize = delegate.size();
541         totalSize += (newSize - oldSize);
542         if (oldSize == 0) {
543           addToMap();
544         }
545       }
546       return changed;
547     }
548 
549     @Override
550     public boolean contains(Object o) {
551       refreshIfEmpty();
552       return delegate.contains(o);
553     }
554 
555     @Override
556     public boolean containsAll(Collection<?> c) {
557       refreshIfEmpty();
558       return delegate.containsAll(c);
559     }
560 
561     @Override
562     public void clear() {
563       int oldSize = size(); // calls refreshIfEmpty
564       if (oldSize == 0) {
565         return;
566       }
567       delegate.clear();
568       totalSize -= oldSize;
569       removeIfEmpty(); // maybe shouldn't be removed if this is a sublist
570     }
571 
572     @Override
573     public boolean remove(Object o) {
574       refreshIfEmpty();
575       boolean changed = delegate.remove(o);
576       if (changed) {
577         totalSize--;
578         removeIfEmpty();
579       }
580       return changed;
581     }
582 
583     @Override
584     public boolean removeAll(Collection<?> c) {
585       if (c.isEmpty()) {
586         return false;
587       }
588       int oldSize = size(); // calls refreshIfEmpty
589       boolean changed = delegate.removeAll(c);
590       if (changed) {
591         int newSize = delegate.size();
592         totalSize += (newSize - oldSize);
593         removeIfEmpty();
594       }
595       return changed;
596     }
597 
598     @Override
599     public boolean retainAll(Collection<?> c) {
600       checkNotNull(c);
601       int oldSize = size(); // calls refreshIfEmpty
602       boolean changed = delegate.retainAll(c);
603       if (changed) {
604         int newSize = delegate.size();
605         totalSize += (newSize - oldSize);
606         removeIfEmpty();
607       }
608       return changed;
609     }
610   }
611 
612   private static <E> Iterator<E> iteratorOrListIterator(Collection<E> collection) {
613     return (collection instanceof List)
614         ? ((List<E>) collection).listIterator()
615         : collection.iterator();
616   }
617 
618   /** Set decorator that stays in sync with the multimap values for a key. */
619   @WeakOuter
620   private class WrappedSet extends WrappedCollection implements Set<V> {
621     WrappedSet(@Nullable K key, Set<V> delegate) {
622       super(key, delegate, null);
623     }
624 
625     @Override
626     public boolean removeAll(Collection<?> c) {
627       if (c.isEmpty()) {
628         return false;
629       }
630       int oldSize = size(); // calls refreshIfEmpty
631 
632       // Guava issue 1013: AbstractSet and most JDK set implementations are
633       // susceptible to quadratic removeAll performance on lists;
634       // use a slightly smarter implementation here
635       boolean changed = Sets.removeAllImpl((Set<V>) delegate, c);
636       if (changed) {
637         int newSize = delegate.size();
638         totalSize += (newSize - oldSize);
639         removeIfEmpty();
640       }
641       return changed;
642     }
643   }
644 
645   /**
646    * SortedSet decorator that stays in sync with the multimap values for a key.
647    */
648   @WeakOuter
649   private class WrappedSortedSet extends WrappedCollection implements SortedSet<V> {
650     WrappedSortedSet(@Nullable K key, SortedSet<V> delegate, @Nullable WrappedCollection ancestor) {
651       super(key, delegate, ancestor);
652     }
653 
654     SortedSet<V> getSortedSetDelegate() {
655       return (SortedSet<V>) getDelegate();
656     }
657 
658     @Override
659     public Comparator<? super V> comparator() {
660       return getSortedSetDelegate().comparator();
661     }
662 
663     @Override
664     public V first() {
665       refreshIfEmpty();
666       return getSortedSetDelegate().first();
667     }
668 
669     @Override
670     public V last() {
671       refreshIfEmpty();
672       return getSortedSetDelegate().last();
673     }
674 
675     @Override
676     public SortedSet<V> headSet(V toElement) {
677       refreshIfEmpty();
678       return new WrappedSortedSet(
679           getKey(),
680           getSortedSetDelegate().headSet(toElement),
681           (getAncestor() == null) ? this : getAncestor());
682     }
683 
684     @Override
685     public SortedSet<V> subSet(V fromElement, V toElement) {
686       refreshIfEmpty();
687       return new WrappedSortedSet(
688           getKey(),
689           getSortedSetDelegate().subSet(fromElement, toElement),
690           (getAncestor() == null) ? this : getAncestor());
691     }
692 
693     @Override
694     public SortedSet<V> tailSet(V fromElement) {
695       refreshIfEmpty();
696       return new WrappedSortedSet(
697           getKey(),
698           getSortedSetDelegate().tailSet(fromElement),
699           (getAncestor() == null) ? this : getAncestor());
700     }
701   }
702 
703   @WeakOuter
704   class WrappedNavigableSet extends WrappedSortedSet implements NavigableSet<V> {
705     WrappedNavigableSet(
706         @Nullable K key, NavigableSet<V> delegate, @Nullable WrappedCollection ancestor) {
707       super(key, delegate, ancestor);
708     }
709 
710     @Override
711     NavigableSet<V> getSortedSetDelegate() {
712       return (NavigableSet<V>) super.getSortedSetDelegate();
713     }
714 
715     @Override
716     public V lower(V v) {
717       return getSortedSetDelegate().lower(v);
718     }
719 
720     @Override
721     public V floor(V v) {
722       return getSortedSetDelegate().floor(v);
723     }
724 
725     @Override
726     public V ceiling(V v) {
727       return getSortedSetDelegate().ceiling(v);
728     }
729 
730     @Override
731     public V higher(V v) {
732       return getSortedSetDelegate().higher(v);
733     }
734 
735     @Override
736     public V pollFirst() {
737       return Iterators.pollNext(iterator());
738     }
739 
740     @Override
741     public V pollLast() {
742       return Iterators.pollNext(descendingIterator());
743     }
744 
745     private NavigableSet<V> wrap(NavigableSet<V> wrapped) {
746       return new WrappedNavigableSet(key, wrapped, (getAncestor() == null) ? this : getAncestor());
747     }
748 
749     @Override
750     public NavigableSet<V> descendingSet() {
751       return wrap(getSortedSetDelegate().descendingSet());
752     }
753 
754     @Override
755     public Iterator<V> descendingIterator() {
756       return new WrappedIterator(getSortedSetDelegate().descendingIterator());
757     }
758 
759     @Override
760     public NavigableSet<V> subSet(
761         V fromElement, boolean fromInclusive, V toElement, boolean toInclusive) {
762       return wrap(
763           getSortedSetDelegate().subSet(fromElement, fromInclusive, toElement, toInclusive));
764     }
765 
766     @Override
767     public NavigableSet<V> headSet(V toElement, boolean inclusive) {
768       return wrap(getSortedSetDelegate().headSet(toElement, inclusive));
769     }
770 
771     @Override
772     public NavigableSet<V> tailSet(V fromElement, boolean inclusive) {
773       return wrap(getSortedSetDelegate().tailSet(fromElement, inclusive));
774     }
775   }
776 
777   /** List decorator that stays in sync with the multimap values for a key. */
778   @WeakOuter
779   private class WrappedList extends WrappedCollection implements List<V> {
780     WrappedList(@Nullable K key, List<V> delegate, @Nullable WrappedCollection ancestor) {
781       super(key, delegate, ancestor);
782     }
783 
784     List<V> getListDelegate() {
785       return (List<V>) getDelegate();
786     }
787 
788     @Override
789     public boolean addAll(int index, Collection<? extends V> c) {
790       if (c.isEmpty()) {
791         return false;
792       }
793       int oldSize = size(); // calls refreshIfEmpty
794       boolean changed = getListDelegate().addAll(index, c);
795       if (changed) {
796         int newSize = getDelegate().size();
797         totalSize += (newSize - oldSize);
798         if (oldSize == 0) {
799           addToMap();
800         }
801       }
802       return changed;
803     }
804 
805     @Override
806     public V get(int index) {
807       refreshIfEmpty();
808       return getListDelegate().get(index);
809     }
810 
811     @Override
812     public V set(int index, V element) {
813       refreshIfEmpty();
814       return getListDelegate().set(index, element);
815     }
816 
817     @Override
818     public void add(int index, V element) {
819       refreshIfEmpty();
820       boolean wasEmpty = getDelegate().isEmpty();
821       getListDelegate().add(index, element);
822       totalSize++;
823       if (wasEmpty) {
824         addToMap();
825       }
826     }
827 
828     @Override
829     public V remove(int index) {
830       refreshIfEmpty();
831       V value = getListDelegate().remove(index);
832       totalSize--;
833       removeIfEmpty();
834       return value;
835     }
836 
837     @Override
838     public int indexOf(Object o) {
839       refreshIfEmpty();
840       return getListDelegate().indexOf(o);
841     }
842 
843     @Override
844     public int lastIndexOf(Object o) {
845       refreshIfEmpty();
846       return getListDelegate().lastIndexOf(o);
847     }
848 
849     @Override
850     public ListIterator<V> listIterator() {
851       refreshIfEmpty();
852       return new WrappedListIterator();
853     }
854 
855     @Override
856     public ListIterator<V> listIterator(int index) {
857       refreshIfEmpty();
858       return new WrappedListIterator(index);
859     }
860 
861     @Override
862     public List<V> subList(int fromIndex, int toIndex) {
863       refreshIfEmpty();
864       return wrapList(
865           getKey(),
866           getListDelegate().subList(fromIndex, toIndex),
867           (getAncestor() == null) ? this : getAncestor());
868     }
869 
870     /** ListIterator decorator. */
871     private class WrappedListIterator extends WrappedIterator implements ListIterator<V> {
872       WrappedListIterator() {}
873 
874       public WrappedListIterator(int index) {
875         super(getListDelegate().listIterator(index));
876       }
877 
878       private ListIterator<V> getDelegateListIterator() {
879         return (ListIterator<V>) getDelegateIterator();
880       }
881 
882       @Override
883       public boolean hasPrevious() {
884         return getDelegateListIterator().hasPrevious();
885       }
886 
887       @Override
888       public V previous() {
889         return getDelegateListIterator().previous();
890       }
891 
892       @Override
893       public int nextIndex() {
894         return getDelegateListIterator().nextIndex();
895       }
896 
897       @Override
898       public int previousIndex() {
899         return getDelegateListIterator().previousIndex();
900       }
901 
902       @Override
903       public void set(V value) {
904         getDelegateListIterator().set(value);
905       }
906 
907       @Override
908       public void add(V value) {
909         boolean wasEmpty = isEmpty();
910         getDelegateListIterator().add(value);
911         totalSize++;
912         if (wasEmpty) {
913           addToMap();
914         }
915       }
916     }
917   }
918 
919   /**
920    * List decorator that stays in sync with the multimap values for a key and
921    * supports rapid random access.
922    */
923   private class RandomAccessWrappedList extends WrappedList implements RandomAccess {
924     RandomAccessWrappedList(
925         @Nullable K key, List<V> delegate, @Nullable WrappedCollection ancestor) {
926       super(key, delegate, ancestor);
927     }
928   }
929 
930   @Override
931   Set<K> createKeySet() {
932     if (map instanceof NavigableMap) {
933       return new NavigableKeySet((NavigableMap<K, Collection<V>>) map);
934     } else if (map instanceof SortedMap) {
935       return new SortedKeySet((SortedMap<K, Collection<V>>) map);
936     } else {
937       return new KeySet(map);
938     }
939   }
940 
941   @WeakOuter
942   private class KeySet extends Maps.KeySet<K, Collection<V>> {
943     KeySet(final Map<K, Collection<V>> subMap) {
944       super(subMap);
945     }
946 
947     @Override
948     public Iterator<K> iterator() {
949       final Iterator<Map.Entry<K, Collection<V>>> entryIterator = map().entrySet().iterator();
950       return new Iterator<K>() {
951         Map.Entry<K, Collection<V>> entry;
952 
953         @Override
954         public boolean hasNext() {
955           return entryIterator.hasNext();
956         }
957 
958         @Override
959         public K next() {
960           entry = entryIterator.next();
961           return entry.getKey();
962         }
963 
964         @Override
965         public void remove() {
966           checkRemove(entry != null);
967           Collection<V> collection = entry.getValue();
968           entryIterator.remove();
969           totalSize -= collection.size();
970           collection.clear();
971         }
972       };
973     }
974 
975     // The following methods are included for better performance.
976 
977     @Override
978     public Spliterator<K> spliterator() {
979       return map().keySet().spliterator();
980     }
981 
982     @Override
983     public boolean remove(Object key) {
984       int count = 0;
985       Collection<V> collection = map().remove(key);
986       if (collection != null) {
987         count = collection.size();
988         collection.clear();
989         totalSize -= count;
990       }
991       return count > 0;
992     }
993 
994     @Override
995     public void clear() {
996       Iterators.clear(iterator());
997     }
998 
999     @Override
1000     public boolean containsAll(Collection<?> c) {
1001       return map().keySet().containsAll(c);
1002     }
1003 
1004     @Override
1005     public boolean equals(@Nullable Object object) {
1006       return this == object || this.map().keySet().equals(object);
1007     }
1008 
1009     @Override
1010     public int hashCode() {
1011       return map().keySet().hashCode();
1012     }
1013   }
1014 
1015   @WeakOuter
1016   private class SortedKeySet extends KeySet implements SortedSet<K> {
1017 
1018     SortedKeySet(SortedMap<K, Collection<V>> subMap) {
1019       super(subMap);
1020     }
1021 
1022     SortedMap<K, Collection<V>> sortedMap() {
1023       return (SortedMap<K, Collection<V>>) super.map();
1024     }
1025 
1026     @Override
1027     public Comparator<? super K> comparator() {
1028       return sortedMap().comparator();
1029     }
1030 
1031     @Override
1032     public K first() {
1033       return sortedMap().firstKey();
1034     }
1035 
1036     @Override
1037     public SortedSet<K> headSet(K toElement) {
1038       return new SortedKeySet(sortedMap().headMap(toElement));
1039     }
1040 
1041     @Override
1042     public K last() {
1043       return sortedMap().lastKey();
1044     }
1045 
1046     @Override
1047     public SortedSet<K> subSet(K fromElement, K toElement) {
1048       return new SortedKeySet(sortedMap().subMap(fromElement, toElement));
1049     }
1050 
1051     @Override
1052     public SortedSet<K> tailSet(K fromElement) {
1053       return new SortedKeySet(sortedMap().tailMap(fromElement));
1054     }
1055   }
1056 
1057   @WeakOuter
1058   class NavigableKeySet extends SortedKeySet implements NavigableSet<K> {
1059     NavigableKeySet(NavigableMap<K, Collection<V>> subMap) {
1060       super(subMap);
1061     }
1062 
1063     @Override
1064     NavigableMap<K, Collection<V>> sortedMap() {
1065       return (NavigableMap<K, Collection<V>>) super.sortedMap();
1066     }
1067 
1068     @Override
1069     public K lower(K k) {
1070       return sortedMap().lowerKey(k);
1071     }
1072 
1073     @Override
1074     public K floor(K k) {
1075       return sortedMap().floorKey(k);
1076     }
1077 
1078     @Override
1079     public K ceiling(K k) {
1080       return sortedMap().ceilingKey(k);
1081     }
1082 
1083     @Override
1084     public K higher(K k) {
1085       return sortedMap().higherKey(k);
1086     }
1087 
1088     @Override
1089     public K pollFirst() {
1090       return Iterators.pollNext(iterator());
1091     }
1092 
1093     @Override
1094     public K pollLast() {
1095       return Iterators.pollNext(descendingIterator());
1096     }
1097 
1098     @Override
1099     public NavigableSet<K> descendingSet() {
1100       return new NavigableKeySet(sortedMap().descendingMap());
1101     }
1102 
1103     @Override
1104     public Iterator<K> descendingIterator() {
1105       return descendingSet().iterator();
1106     }
1107 
1108     @Override
1109     public NavigableSet<K> headSet(K toElement) {
1110       return headSet(toElement, false);
1111     }
1112 
1113     @Override
1114     public NavigableSet<K> headSet(K toElement, boolean inclusive) {
1115       return new NavigableKeySet(sortedMap().headMap(toElement, inclusive));
1116     }
1117 
1118     @Override
1119     public NavigableSet<K> subSet(K fromElement, K toElement) {
1120       return subSet(fromElement, true, toElement, false);
1121     }
1122 
1123     @Override
1124     public NavigableSet<K> subSet(
1125         K fromElement, boolean fromInclusive, K toElement, boolean toInclusive) {
1126       return new NavigableKeySet(
1127           sortedMap().subMap(fromElement, fromInclusive, toElement, toInclusive));
1128     }
1129 
1130     @Override
1131     public NavigableSet<K> tailSet(K fromElement) {
1132       return tailSet(fromElement, true);
1133     }
1134 
1135     @Override
1136     public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
1137       return new NavigableKeySet(sortedMap().tailMap(fromElement, inclusive));
1138     }
1139   }
1140 
1141   /**
1142    * Removes all values for the provided key.
1143    */
1144   private void removeValuesForKey(Object key) {
1145     Collection<V> collection = Maps.safeRemove(map, key);
1146 
1147     if (collection != null) {
1148       int count = collection.size();
1149       collection.clear();
1150       totalSize -= count;
1151     }
1152   }
1153 
1154   private abstract class Itr<T> implements Iterator<T> {
1155     final Iterator<Map.Entry<K, Collection<V>>> keyIterator;
1156     K key;
1157     Collection<V> collection;
1158     Iterator<V> valueIterator;
1159 
1160     Itr() {
1161       keyIterator = map.entrySet().iterator();
1162       key = null;
1163       collection = null;
1164       valueIterator = Iterators.emptyModifiableIterator();
1165     }
1166 
1167     abstract T output(K key, V value);
1168 
1169     @Override
1170     public boolean hasNext() {
1171       return keyIterator.hasNext() || valueIterator.hasNext();
1172     }
1173 
1174     @Override
1175     public T next() {
1176       if (!valueIterator.hasNext()) {
1177         Map.Entry<K, Collection<V>> mapEntry = keyIterator.next();
1178         key = mapEntry.getKey();
1179         collection = mapEntry.getValue();
1180         valueIterator = collection.iterator();
1181       }
1182       return output(key, valueIterator.next());
1183     }
1184 
1185     @Override
1186     public void remove() {
1187       valueIterator.remove();
1188       if (collection.isEmpty()) {
1189         keyIterator.remove();
1190       }
1191       totalSize--;
1192     }
1193   }
1194 
1195   /**
1196    * {@inheritDoc}
1197    *
1198    * <p>The iterator generated by the returned collection traverses the values
1199    * for one key, followed by the values of a second key, and so on.
1200    */
1201   @Override
1202   public Collection<V> values() {
1203     return super.values();
1204   }
1205 
1206   @Override
1207   Iterator<V> valueIterator() {
1208     return new Itr<V>() {
1209       @Override
1210       V output(K key, V value) {
1211         return value;
1212       }
1213     };
1214   }
1215 
1216   @Override
1217   Spliterator<V> valueSpliterator() {
1218     return CollectSpliterators.flatMap(
1219         map.values().spliterator(), Collection::spliterator, Spliterator.SIZED, size());
1220   }
1221 
1222   /*
1223    * TODO(kevinb): should we copy this javadoc to each concrete class, so that
1224    * classes like LinkedHashMultimap that need to say something different are
1225    * still able to {@inheritDoc} all the way from Multimap?
1226    */
1227 
1228   /**
1229    * {@inheritDoc}
1230    *
1231    * <p>The iterator generated by the returned collection traverses the values
1232    * for one key, followed by the values of a second key, and so on.
1233    *
1234    * <p>Each entry is an immutable snapshot of a key-value mapping in the
1235    * multimap, taken at the time the entry is returned by a method call to the
1236    * collection or its iterator.
1237    */
1238   @Override
1239   public Collection<Map.Entry<K, V>> entries() {
1240     return super.entries();
1241   }
1242 
1243   /**
1244    * Returns an iterator across all key-value map entries, used by {@code
1245    * entries().iterator()} and {@code values().iterator()}. The default
1246    * behavior, which traverses the values for one key, the values for a second
1247    * key, and so on, suffices for most {@code AbstractMapBasedMultimap} implementations.
1248    *
1249    * @return an iterator across map entries
1250    */
1251   @Override
1252   Iterator<Map.Entry<K, V>> entryIterator() {
1253     return new Itr<Map.Entry<K, V>>() {
1254       @Override
1255       Entry<K, V> output(K key, V value) {
1256         return Maps.immutableEntry(key, value);
1257       }
1258     };
1259   }
1260 
1261   @Override
1262   Spliterator<Entry<K, V>> entrySpliterator() {
1263     return CollectSpliterators.flatMap(
1264         map.entrySet().spliterator(),
1265         keyToValueCollectionEntry -> {
1266           K key = keyToValueCollectionEntry.getKey();
1267           Collection<V> valueCollection = keyToValueCollectionEntry.getValue();
1268           return CollectSpliterators.map(
1269               valueCollection.spliterator(), (V value) -> Maps.immutableEntry(key, value));
1270         },
1271         Spliterator.SIZED,
1272         size());
1273   }
1274 
1275   @Override
1276   public void forEach(BiConsumer<? super K, ? super V> action) {
1277     checkNotNull(action);
1278     map.forEach(
1279         (key, valueCollection) -> valueCollection.forEach(value -> action.accept(key, value)));
1280   }
1281 
1282   @Override
1283   Map<K, Collection<V>> createAsMap() {
1284     if (map instanceof NavigableMap) {
1285       return new NavigableAsMap((NavigableMap<K, Collection<V>>) map);
1286     } else if (map instanceof SortedMap) {
1287       return new SortedAsMap((SortedMap<K, Collection<V>>) map);
1288     } else {
1289       return new AsMap(map);
1290     }
1291   }
1292 
1293   @WeakOuter
1294   private class AsMap extends ViewCachingAbstractMap<K, Collection<V>> {
1295     /**
1296      * Usually the same as map, but smaller for the headMap(), tailMap(), or
1297      * subMap() of a SortedAsMap.
1298      */
1299     final transient Map<K, Collection<V>> submap;
1300 
1301     AsMap(Map<K, Collection<V>> submap) {
1302       this.submap = submap;
1303     }
1304 
1305     @Override
1306     protected Set<Entry<K, Collection<V>>> createEntrySet() {
1307       return new AsMapEntries();
1308     }
1309 
1310     // The following methods are included for performance.
1311 
1312     @Override
1313     public boolean containsKey(Object key) {
1314       return Maps.safeContainsKey(submap, key);
1315     }
1316 
1317     @Override
1318     public Collection<V> get(Object key) {
1319       Collection<V> collection = Maps.safeGet(submap, key);
1320       if (collection == null) {
1321         return null;
1322       }
1323       @SuppressWarnings("unchecked")
1324       K k = (K) key;
1325       return wrapCollection(k, collection);
1326     }
1327 
1328     @Override
1329     public Set<K> keySet() {
1330       return AbstractMapBasedMultimap.this.keySet();
1331     }
1332 
1333     @Override
1334     public int size() {
1335       return submap.size();
1336     }
1337 
1338     @Override
1339     public Collection<V> remove(Object key) {
1340       Collection<V> collection = submap.remove(key);
1341       if (collection == null) {
1342         return null;
1343       }
1344 
1345       Collection<V> output = createCollection();
1346       output.addAll(collection);
1347       totalSize -= collection.size();
1348       collection.clear();
1349       return output;
1350     }
1351 
1352     @Override
1353     public boolean equals(@Nullable Object object) {
1354       return this == object || submap.equals(object);
1355     }
1356 
1357     @Override
1358     public int hashCode() {
1359       return submap.hashCode();
1360     }
1361 
1362     @Override
1363     public String toString() {
1364       return submap.toString();
1365     }
1366 
1367     @Override
1368     public void clear() {
1369       if (submap == map) {
1370         AbstractMapBasedMultimap.this.clear();
1371       } else {
1372         Iterators.clear(new AsMapIterator());
1373       }
1374     }
1375 
1376     Entry<K, Collection<V>> wrapEntry(Entry<K, Collection<V>> entry) {
1377       K key = entry.getKey();
1378       return Maps.immutableEntry(key, wrapCollection(key, entry.getValue()));
1379     }
1380 
1381     @WeakOuter
1382     class AsMapEntries extends Maps.EntrySet<K, Collection<V>> {
1383       @Override
1384       Map<K, Collection<V>> map() {
1385         return AsMap.this;
1386       }
1387 
1388       @Override
1389       public Iterator<Map.Entry<K, Collection<V>>> iterator() {
1390         return new AsMapIterator();
1391       }
1392 
1393       @Override
1394       public Spliterator<Entry<K, Collection<V>>> spliterator() {
1395         return CollectSpliterators.map(submap.entrySet().spliterator(), AsMap.this::wrapEntry);
1396       }
1397 
1398       // The following methods are included for performance.
1399 
1400       @Override
1401       public boolean contains(Object o) {
1402         return Collections2.safeContains(submap.entrySet(), o);
1403       }
1404 
1405       @Override
1406       public boolean remove(Object o) {
1407         if (!contains(o)) {
1408           return false;
1409         }
1410         Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
1411         removeValuesForKey(entry.getKey());
1412         return true;
1413       }
1414     }
1415 
1416     /** Iterator across all keys and value collections. */
1417     class AsMapIterator implements Iterator<Map.Entry<K, Collection<V>>> {
1418       final Iterator<Map.Entry<K, Collection<V>>> delegateIterator = submap.entrySet().iterator();
1419       Collection<V> collection;
1420 
1421       @Override
1422       public boolean hasNext() {
1423         return delegateIterator.hasNext();
1424       }
1425 
1426       @Override
1427       public Map.Entry<K, Collection<V>> next() {
1428         Map.Entry<K, Collection<V>> entry = delegateIterator.next();
1429         collection = entry.getValue();
1430         return wrapEntry(entry);
1431       }
1432 
1433       @Override
1434       public void remove() {
1435         delegateIterator.remove();
1436         totalSize -= collection.size();
1437         collection.clear();
1438       }
1439     }
1440   }
1441 
1442   @WeakOuter
1443   private class SortedAsMap extends AsMap implements SortedMap<K, Collection<V>> {
1444     SortedAsMap(SortedMap<K, Collection<V>> submap) {
1445       super(submap);
1446     }
1447 
1448     SortedMap<K, Collection<V>> sortedMap() {
1449       return (SortedMap<K, Collection<V>>) submap;
1450     }
1451 
1452     @Override
1453     public Comparator<? super K> comparator() {
1454       return sortedMap().comparator();
1455     }
1456 
1457     @Override
1458     public K firstKey() {
1459       return sortedMap().firstKey();
1460     }
1461 
1462     @Override
1463     public K lastKey() {
1464       return sortedMap().lastKey();
1465     }
1466 
1467     @Override
1468     public SortedMap<K, Collection<V>> headMap(K toKey) {
1469       return new SortedAsMap(sortedMap().headMap(toKey));
1470     }
1471 
1472     @Override
1473     public SortedMap<K, Collection<V>> subMap(K fromKey, K toKey) {
1474       return new SortedAsMap(sortedMap().subMap(fromKey, toKey));
1475     }
1476 
1477     @Override
1478     public SortedMap<K, Collection<V>> tailMap(K fromKey) {
1479       return new SortedAsMap(sortedMap().tailMap(fromKey));
1480     }
1481 
1482     SortedSet<K> sortedKeySet;
1483 
1484     // returns a SortedSet, even though returning a Set would be sufficient to
1485     // satisfy the SortedMap.keySet() interface
1486     @Override
1487     public SortedSet<K> keySet() {
1488       SortedSet<K> result = sortedKeySet;
1489       return (result == null) ? sortedKeySet = createKeySet() : result;
1490     }
1491 
1492     @Override
1493     SortedSet<K> createKeySet() {
1494       return new SortedKeySet(sortedMap());
1495     }
1496   }
1497 
1498   class NavigableAsMap extends SortedAsMap implements NavigableMap<K, Collection<V>> {
1499 
1500     NavigableAsMap(NavigableMap<K, Collection<V>> submap) {
1501       super(submap);
1502     }
1503 
1504     @Override
1505     NavigableMap<K, Collection<V>> sortedMap() {
1506       return (NavigableMap<K, Collection<V>>) super.sortedMap();
1507     }
1508 
1509     @Override
1510     public Entry<K, Collection<V>> lowerEntry(K key) {
1511       Entry<K, Collection<V>> entry = sortedMap().lowerEntry(key);
1512       return (entry == null) ? null : wrapEntry(entry);
1513     }
1514 
1515     @Override
1516     public K lowerKey(K key) {
1517       return sortedMap().lowerKey(key);
1518     }
1519 
1520     @Override
1521     public Entry<K, Collection<V>> floorEntry(K key) {
1522       Entry<K, Collection<V>> entry = sortedMap().floorEntry(key);
1523       return (entry == null) ? null : wrapEntry(entry);
1524     }
1525 
1526     @Override
1527     public K floorKey(K key) {
1528       return sortedMap().floorKey(key);
1529     }
1530 
1531     @Override
1532     public Entry<K, Collection<V>> ceilingEntry(K key) {
1533       Entry<K, Collection<V>> entry = sortedMap().ceilingEntry(key);
1534       return (entry == null) ? null : wrapEntry(entry);
1535     }
1536 
1537     @Override
1538     public K ceilingKey(K key) {
1539       return sortedMap().ceilingKey(key);
1540     }
1541 
1542     @Override
1543     public Entry<K, Collection<V>> higherEntry(K key) {
1544       Entry<K, Collection<V>> entry = sortedMap().higherEntry(key);
1545       return (entry == null) ? null : wrapEntry(entry);
1546     }
1547 
1548     @Override
1549     public K higherKey(K key) {
1550       return sortedMap().higherKey(key);
1551     }
1552 
1553     @Override
1554     public Entry<K, Collection<V>> firstEntry() {
1555       Entry<K, Collection<V>> entry = sortedMap().firstEntry();
1556       return (entry == null) ? null : wrapEntry(entry);
1557     }
1558 
1559     @Override
1560     public Entry<K, Collection<V>> lastEntry() {
1561       Entry<K, Collection<V>> entry = sortedMap().lastEntry();
1562       return (entry == null) ? null : wrapEntry(entry);
1563     }
1564 
1565     @Override
1566     public Entry<K, Collection<V>> pollFirstEntry() {
1567       return pollAsMapEntry(entrySet().iterator());
1568     }
1569 
1570     @Override
1571     public Entry<K, Collection<V>> pollLastEntry() {
1572       return pollAsMapEntry(descendingMap().entrySet().iterator());
1573     }
1574 
1575     Map.Entry<K, Collection<V>> pollAsMapEntry(Iterator<Entry<K, Collection<V>>> entryIterator) {
1576       if (!entryIterator.hasNext()) {
1577         return null;
1578       }
1579       Entry<K, Collection<V>> entry = entryIterator.next();
1580       Collection<V> output = createCollection();
1581       output.addAll(entry.getValue());
1582       entryIterator.remove();
1583       return Maps.immutableEntry(entry.getKey(), unmodifiableCollectionSubclass(output));
1584     }
1585 
1586     @Override
1587     public NavigableMap<K, Collection<V>> descendingMap() {
1588       return new NavigableAsMap(sortedMap().descendingMap());
1589     }
1590 
1591     @Override
1592     public NavigableSet<K> keySet() {
1593       return (NavigableSet<K>) super.keySet();
1594     }
1595 
1596     @Override
1597     NavigableSet<K> createKeySet() {
1598       return new NavigableKeySet(sortedMap());
1599     }
1600 
1601     @Override
1602     public NavigableSet<K> navigableKeySet() {
1603       return keySet();
1604     }
1605 
1606     @Override
1607     public NavigableSet<K> descendingKeySet() {
1608       return descendingMap().navigableKeySet();
1609     }
1610 
1611     @Override
1612     public NavigableMap<K, Collection<V>> subMap(K fromKey, K toKey) {
1613       return subMap(fromKey, true, toKey, false);
1614     }
1615 
1616     @Override
1617     public NavigableMap<K, Collection<V>> subMap(
1618         K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
1619       return new NavigableAsMap(sortedMap().subMap(fromKey, fromInclusive, toKey, toInclusive));
1620     }
1621 
1622     @Override
1623     public NavigableMap<K, Collection<V>> headMap(K toKey) {
1624       return headMap(toKey, false);
1625     }
1626 
1627     @Override
1628     public NavigableMap<K, Collection<V>> headMap(K toKey, boolean inclusive) {
1629       return new NavigableAsMap(sortedMap().headMap(toKey, inclusive));
1630     }
1631 
1632     @Override
1633     public NavigableMap<K, Collection<V>> tailMap(K fromKey) {
1634       return tailMap(fromKey, true);
1635     }
1636 
1637     @Override
1638     public NavigableMap<K, Collection<V>> tailMap(K fromKey, boolean inclusive) {
1639       return new NavigableAsMap(sortedMap().tailMap(fromKey, inclusive));
1640     }
1641   }
1642 
1643   private static final long serialVersionUID = 2447537837011683357L;
1644 }