View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.collections4.multimap;
18  
19  import java.io.IOException;
20  import java.io.ObjectInputStream;
21  import java.io.ObjectOutputStream;
22  import java.util.AbstractCollection;
23  import java.util.AbstractMap;
24  import java.util.AbstractSet;
25  import java.util.ArrayList;
26  import java.util.Collection;
27  import java.util.Iterator;
28  import java.util.Map;
29  import java.util.Map.Entry;
30  import java.util.Set;
31  
32  import org.apache.commons.collections4.CollectionUtils;
33  import org.apache.commons.collections4.IteratorUtils;
34  import org.apache.commons.collections4.MapIterator;
35  import org.apache.commons.collections4.MultiSet;
36  import org.apache.commons.collections4.MultiValuedMap;
37  import org.apache.commons.collections4.Transformer;
38  import org.apache.commons.collections4.iterators.AbstractIteratorDecorator;
39  import org.apache.commons.collections4.iterators.EmptyMapIterator;
40  import org.apache.commons.collections4.iterators.IteratorChain;
41  import org.apache.commons.collections4.iterators.LazyIteratorChain;
42  import org.apache.commons.collections4.iterators.TransformIterator;
43  import org.apache.commons.collections4.keyvalue.AbstractMapEntry;
44  import org.apache.commons.collections4.keyvalue.UnmodifiableMapEntry;
45  import org.apache.commons.collections4.multiset.AbstractMultiSet;
46  import org.apache.commons.collections4.multiset.UnmodifiableMultiSet;
47  
48  /**
49   * Abstract implementation of the {@link MultiValuedMap} interface to simplify
50   * the creation of subclass implementations.
51   * <p>
52   * Subclasses specify a Map implementation to use as the internal storage.
53   * </p>
54   *
55   * @param <K> the type of the keys in this map
56   * @param <V> the type of the values in this map
57   * @since 4.1
58   */
59  public abstract class AbstractMultiValuedMap<K, V> implements MultiValuedMap<K, V> {
60  
61      /** The values view */
62      private transient Collection<V> valuesView;
63  
64      /** The EntryValues view */
65      private transient EntryValues entryValuesView;
66  
67      /** The KeyMultiSet view */
68      private transient MultiSet<K> keysMultiSetView;
69  
70      /** The AsMap view */
71      private transient AsMap asMapView;
72  
73      /** The map used to store the data */
74      private transient Map<K, Collection<V>> map;
75  
76      /**
77       * Constructor needed for subclass serialisation.
78       */
79      protected AbstractMultiValuedMap() {
80          super();
81      }
82  
83      /**
84       * Constructor that wraps (not copies).
85       *
86       * @param map  the map to wrap, must not be null
87       * @throws NullPointerException if the map is null
88       */
89      @SuppressWarnings("unchecked")
90      protected AbstractMultiValuedMap(final Map<K, ? extends Collection<V>> map) {
91          if (map == null) {
92              throw new NullPointerException("Map must not be null.");
93          }
94          this.map = (Map<K, Collection<V>>) map;
95      }
96  
97      // -----------------------------------------------------------------------
98      /**
99       * Gets the map being wrapped.
100      *
101      * @return the wrapped map
102      */
103     protected Map<K, ? extends Collection<V>> getMap() {
104         return map;
105     }
106 
107     /**
108      * Sets the map being wrapped.
109      * <p>
110      * <b>NOTE:</b> this method should only be used during deserialization
111      *
112      * @param map the map to wrap
113      */
114     @SuppressWarnings("unchecked")
115     protected void setMap(final Map<K, ? extends Collection<V>> map) {
116         this.map = (Map<K, Collection<V>>) map;
117     }
118 
119     protected abstract Collection<V> createCollection();
120 
121     // -----------------------------------------------------------------------
122     @Override
123     public boolean containsKey(final Object key) {
124         return getMap().containsKey(key);
125     }
126 
127     @Override
128     public boolean containsValue(final Object value) {
129         return values().contains(value);
130     }
131 
132     @Override
133     public boolean containsMapping(final Object key, final Object value) {
134         final Collection<V> coll = getMap().get(key);
135         return coll != null && coll.contains(value);
136     }
137 
138     @Override
139     public Collection<Entry<K, V>> entries() {
140         return entryValuesView != null ? entryValuesView : (entryValuesView = new EntryValues());
141     }
142 
143     /**
144      * Gets the collection of values associated with the specified key. This
145      * would return an empty collection in case the mapping is not present
146      *
147      * @param key the key to retrieve
148      * @return the {@code Collection} of values, will return an empty {@code Collection} for no mapping
149      */
150     @Override
151     public Collection<V> get(final K key) {
152         return wrappedCollection(key);
153     }
154 
155     Collection<V> wrappedCollection(final K key) {
156         return new WrappedCollection(key);
157     }
158 
159     /**
160      * Removes all values associated with the specified key.
161      * <p>
162      * A subsequent <code>get(Object)</code> would return an empty collection.
163      *
164      * @param key  the key to remove values from
165      * @return the <code>Collection</code> of values removed, will return an
166      *   empty, unmodifiable collection for no mapping found
167      */
168     @Override
169     public Collection<V> remove(final Object key) {
170         return CollectionUtils.emptyIfNull(getMap().remove(key));
171     }
172 
173     /**
174      * Removes a specific key/value mapping from the multi-valued map.
175      * <p>
176      * The value is removed from the collection mapped to the specified key.
177      * Other values attached to that key are unaffected.
178      * <p>
179      * If the last value for a key is removed, an empty collection would be
180      * returned from a subsequent {@link #get(Object)}.
181      *
182      * @param key the key to remove from
183      * @param value the value to remove
184      * @return true if the mapping was removed, false otherwise
185      */
186     @Override
187     public boolean removeMapping(final Object key, final Object value) {
188         final Collection<V> coll = getMap().get(key);
189         if (coll == null) {
190             return false;
191         }
192         final boolean changed = coll.remove(value);
193         if (coll.isEmpty()) {
194             getMap().remove(key);
195         }
196         return changed;
197     }
198 
199     @Override
200     public boolean isEmpty() {
201         return getMap().isEmpty();
202     }
203 
204     @Override
205     public Set<K> keySet() {
206         return getMap().keySet();
207     }
208 
209     /**
210      * {@inheritDoc}
211      * <p>
212      * This implementation does <b>not</b> cache the total size
213      * of the multi-valued map, but rather calculates it by iterating
214      * over the entries of the underlying map.
215      */
216     @Override
217     public int size() {
218         // the total size should be cached to improve performance
219         // but this requires that all modifications of the multimap
220         // (including the wrapped collections and entry/value
221         // collections) are tracked.
222         int size = 0;
223         for (final Collection<V> col : getMap().values()) {
224             size += col.size();
225         }
226         return size;
227     }
228 
229     /**
230      * Gets a collection containing all the values in the map.
231      * <p>
232      * Returns a collection containing all the values from all keys.
233      *
234      * @return a collection view of the values contained in this map
235      */
236     @Override
237     public Collection<V> values() {
238         final Collection<V> vs = valuesView;
239         return vs != null ? vs : (valuesView = new Values());
240     }
241 
242     @Override
243     public void clear() {
244         getMap().clear();
245     }
246 
247     /**
248      * Adds the value to the collection associated with the specified key.
249      * <p>
250      * Unlike a normal <code>Map</code> the previous value is not replaced.
251      * Instead the new value is added to the collection stored against the key.
252      *
253      * @param key the key to store against
254      * @param value the value to add to the collection at the key
255      * @return the value added if the map changed and null if the map did not change
256      */
257     @Override
258     public boolean put(final K key, final V value) {
259         Collection<V> coll = getMap().get(key);
260         if (coll == null) {
261             coll = createCollection();
262             if (coll.add(value)) {
263                 map.put(key, coll);
264                 return true;
265             }
266             return false;
267         }
268         return coll.add(value);
269     }
270 
271     /**
272      * Copies all of the mappings from the specified map to this map. The effect
273      * of this call is equivalent to that of calling {@link #put(Object,Object)
274      * put(k, v)} on this map once for each mapping from key {@code k} to value
275      * {@code v} in the specified map. The behavior of this operation is
276      * undefined if the specified map is modified while the operation is in
277      * progress.
278      *
279      * @param map mappings to be stored in this map, may not be null
280      * @return true if the map changed as a result of this operation
281      * @throws NullPointerException if map is null
282      */
283     @Override
284     public boolean putAll(final Map<? extends K, ? extends V> map) {
285         if (map == null) {
286             throw new NullPointerException("Map must not be null.");
287         }
288         boolean changed = false;
289         for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
290             changed |= put(entry.getKey(), entry.getValue());
291         }
292         return changed;
293     }
294 
295     /**
296      * Copies all of the mappings from the specified MultiValuedMap to this map.
297      * The effect of this call is equivalent to that of calling
298      * {@link #put(Object,Object) put(k, v)} on this map once for each mapping
299      * from key {@code k} to value {@code v} in the specified map. The
300      * behavior of this operation is undefined if the specified map is modified
301      * while the operation is in progress.
302      *
303      * @param map mappings to be stored in this map, may not be null
304      * @return true if the map changed as a result of this operation
305      * @throws NullPointerException if map is null
306      */
307     @Override
308     public boolean putAll(final MultiValuedMap<? extends K, ? extends V> map) {
309         if (map == null) {
310             throw new NullPointerException("Map must not be null.");
311         }
312         boolean changed = false;
313         for (final Map.Entry<? extends K, ? extends V> entry : map.entries()) {
314             changed |= put(entry.getKey(), entry.getValue());
315         }
316         return changed;
317     }
318 
319     /**
320      * Returns a {@link MultiSet} view of the key mapping contained in this map.
321      * <p>
322      * Returns a MultiSet of keys with its values count as the count of the MultiSet.
323      * This multiset is backed by the map, so any changes in the map is reflected here.
324      * Any method which modifies this multiset like {@code add}, {@code remove},
325      * {@link Iterator#remove()} etc throws {@code UnsupportedOperationException}.
326      *
327      * @return a bag view of the key mapping contained in this map
328      */
329     @Override
330     public MultiSet<K> keys() {
331         if (keysMultiSetView == null) {
332             keysMultiSetView = UnmodifiableMultiSet.unmodifiableMultiSet(new KeysMultiSet());
333         }
334         return keysMultiSetView;
335     }
336 
337     @Override
338     public Map<K, Collection<V>> asMap() {
339         return asMapView != null ? asMapView : (asMapView = new AsMap(map));
340     }
341 
342     /**
343      * Adds Iterable values to the collection associated with the specified key.
344      *
345      * @param key the key to store against
346      * @param values the values to add to the collection at the key, may not be null
347      * @return true if this map changed
348      * @throws NullPointerException if values is null
349      */
350     @Override
351     public boolean putAll(final K key, final Iterable<? extends V> values) {
352         if (values == null) {
353             throw new NullPointerException("Values must not be null.");
354         }
355 
356         if (values instanceof Collection<?>) {
357             final Collection<? extends V> valueCollection = (Collection<? extends V>) values;
358             return !valueCollection.isEmpty() && get(key).addAll(valueCollection);
359         }
360         final Iterator<? extends V> it = values.iterator();
361         return it.hasNext() && CollectionUtils.addAll(get(key), it);
362     }
363 
364     @Override
365     public MapIterator<K, V> mapIterator() {
366         if (size() == 0) {
367             return EmptyMapIterator.emptyMapIterator();
368         }
369         return new MultiValuedMapIterator();
370     }
371 
372     @Override
373     public boolean equals(final Object obj) {
374         if (this == obj) {
375             return true;
376         }
377         if (obj instanceof MultiValuedMap) {
378             return asMap().equals(((MultiValuedMap<?, ?>) obj).asMap());
379         }
380         return false;
381     }
382 
383     @Override
384     public int hashCode() {
385         return getMap().hashCode();
386     }
387 
388     @Override
389     public String toString() {
390         return getMap().toString();
391     }
392 
393     // -----------------------------------------------------------------------
394 
395     /**
396      * Wrapped collection to handle add and remove on the collection returned
397      * by get(object).
398      * <p>
399      * Currently, the wrapped collection is not cached and has to be retrieved
400      * from the underlying map. This is safe, but not very efficient and
401      * should be improved in subsequent releases. For this purpose, the
402      * scope of this collection is set to package private to simplify later
403      * refactoring.
404      */
405     class WrappedCollection implements Collection<V> {
406 
407         protected final K key;
408 
409         public WrappedCollection(final K key) {
410             this.key = key;
411         }
412 
413         protected Collection<V> getMapping() {
414             return getMap().get(key);
415         }
416 
417         @Override
418         public boolean add(final V value) {
419             Collection<V> coll = getMapping();
420             if (coll == null) {
421                 coll = createCollection();
422                 AbstractMultiValuedMap.this.map.put(key, coll);
423             }
424             return coll.add(value);
425         }
426 
427         @Override
428         public boolean addAll(final Collection<? extends V> other) {
429             Collection<V> coll = getMapping();
430             if (coll == null) {
431                 coll = createCollection();
432                 AbstractMultiValuedMap.this.map.put(key, coll);
433             }
434             return coll.addAll(other);
435         }
436 
437         @Override
438         public void clear() {
439             final Collection<V> coll = getMapping();
440             if (coll != null) {
441                 coll.clear();
442                 AbstractMultiValuedMap.this.remove(key);
443             }
444         }
445 
446         @Override
447         public Iterator<V> iterator() {
448             final Collection<V> coll = getMapping();
449             if (coll == null) {
450                 return IteratorUtils.EMPTY_ITERATOR;
451             }
452             return new ValuesIterator(key);
453         }
454 
455         @Override
456         public int size() {
457             final Collection<V> coll = getMapping();
458             return coll == null ? 0 : coll.size();
459         }
460 
461         @Override
462         public boolean contains(final Object obj) {
463             final Collection<V> coll = getMapping();
464             return coll != null && coll.contains(obj);
465         }
466 
467         @Override
468         public boolean containsAll(final Collection<?> other) {
469             final Collection<V> coll = getMapping();
470             return coll != null && coll.containsAll(other);
471         }
472 
473         @Override
474         public boolean isEmpty() {
475             final Collection<V> coll = getMapping();
476             return coll == null || coll.isEmpty();
477         }
478 
479         @Override
480         public boolean remove(final Object item) {
481             final Collection<V> coll = getMapping();
482             if (coll == null) {
483                 return false;
484             }
485 
486             final boolean result = coll.remove(item);
487             if (coll.isEmpty()) {
488                 AbstractMultiValuedMap.this.remove(key);
489             }
490             return result;
491         }
492 
493         @Override
494         public boolean removeAll(final Collection<?> c) {
495             final Collection<V> coll = getMapping();
496             if (coll == null) {
497                 return false;
498             }
499 
500             final boolean result = coll.removeAll(c);
501             if (coll.isEmpty()) {
502                 AbstractMultiValuedMap.this.remove(key);
503             }
504             return result;
505         }
506 
507         @Override
508         public boolean retainAll(final Collection<?> c) {
509             final Collection<V> coll = getMapping();
510             if (coll == null) {
511                 return false;
512             }
513 
514             final boolean result = coll.retainAll(c);
515             if (coll.isEmpty()) {
516                 AbstractMultiValuedMap.this.remove(key);
517             }
518             return result;
519         }
520 
521         @Override
522         public Object[] toArray() {
523             final Collection<V> coll = getMapping();
524             if (coll == null) {
525                 return CollectionUtils.EMPTY_COLLECTION.toArray();
526             }
527             return coll.toArray();
528         }
529 
530         @Override
531         @SuppressWarnings("unchecked")
532         public <T> T[] toArray(final T[] a) {
533             final Collection<V> coll = getMapping();
534             if (coll == null) {
535                 return (T[]) CollectionUtils.EMPTY_COLLECTION.toArray(a);
536             }
537             return coll.toArray(a);
538         }
539 
540         @Override
541         public String toString() {
542             final Collection<V> coll = getMapping();
543             if (coll == null) {
544                 return CollectionUtils.EMPTY_COLLECTION.toString();
545             }
546             return coll.toString();
547         }
548 
549     }
550 
551     /**
552      * Inner class that provides a MultiSet<K> keys view.
553      */
554     private class KeysMultiSet extends AbstractMultiSet<K> {
555 
556         @Override
557         public boolean contains(final Object o) {
558             return getMap().containsKey(o);
559         }
560 
561         @Override
562         public boolean isEmpty() {
563             return getMap().isEmpty();
564         }
565 
566         @Override
567         public int size() {
568             return AbstractMultiValuedMap.this.size();
569         }
570 
571         @Override
572         protected int uniqueElements() {
573             return getMap().size();
574         }
575 
576         @Override
577         public int getCount(final Object object) {
578             int count = 0;
579             final Collection<V> col = AbstractMultiValuedMap.this.getMap().get(object);
580             if (col != null) {
581                 count = col.size();
582             }
583             return count;
584         }
585 
586         @Override
587         protected Iterator<MultiSet.Entry<K>> createEntrySetIterator() {
588             final MapEntryTransformer transformer = new MapEntryTransformer();
589             return IteratorUtils.transformedIterator(map.entrySet().iterator(), transformer);
590         }
591 
592         private final class MapEntryTransformer
593             implements Transformer<Map.Entry<K, Collection<V>>, MultiSet.Entry<K>> {
594             @Override
595             public MultiSet.Entry<K> transform(final Map.Entry<K, Collection<V>> mapEntry) {
596                 return new AbstractMultiSet.AbstractEntry<K>() {
597                     @Override
598                     public K getElement() {
599                         return mapEntry.getKey();
600                     }
601 
602                     @Override
603                     public int getCount() {
604                         return mapEntry.getValue().size();
605                     }
606                 };
607             }
608         }
609     }
610 
611     /**
612      * Inner class that provides the Entry<K, V> view
613      */
614     private class EntryValues extends AbstractCollection<Entry<K, V>> {
615 
616         @Override
617         public Iterator<Entry<K, V>> iterator() {
618             return new LazyIteratorChain<Entry<K, V>>() {
619 
620                 final Collection<K> keysCol = new ArrayList<>(getMap().keySet());
621                 final Iterator<K> keyIterator = keysCol.iterator();
622 
623                 @Override
624                 protected Iterator<? extends Entry<K, V>> nextIterator(final int count) {
625                     if (!keyIterator.hasNext()) {
626                         return null;
627                     }
628                     final K key = keyIterator.next();
629                     final Transformer<V, Entry<K, V>> entryTransformer = new Transformer<V, Entry<K, V>>() {
630 
631                         @Override
632                         public Entry<K, V> transform(final V input) {
633                             return new MultiValuedMapEntry(key, input);
634                         }
635 
636                     };
637                     return new TransformIterator<>(new ValuesIterator(key), entryTransformer);
638                 }
639             };
640         }
641 
642         @Override
643         public int size() {
644             return AbstractMultiValuedMap.this.size();
645         }
646 
647     }
648 
649     /**
650      * Inner class for MultiValuedMap Entries.
651      */
652     private class MultiValuedMapEntry extends AbstractMapEntry<K, V> {
653 
654         public MultiValuedMapEntry(final K key, final V value) {
655             super(key, value);
656         }
657 
658         @Override
659         public V setValue(final V value) {
660             throw new UnsupportedOperationException();
661         }
662 
663     }
664 
665     /**
666      * Inner class for MapIterator.
667      */
668     private class MultiValuedMapIterator implements MapIterator<K, V> {
669 
670         private final Iterator<Entry<K, V>> it;
671 
672         private Entry<K, V> current = null;
673 
674         public MultiValuedMapIterator() {
675             this.it = AbstractMultiValuedMap.this.entries().iterator();
676         }
677 
678         @Override
679         public boolean hasNext() {
680             return it.hasNext();
681         }
682 
683         @Override
684         public K next() {
685             current = it.next();
686             return current.getKey();
687         }
688 
689         @Override
690         public K getKey() {
691             if (current == null) {
692                 throw new IllegalStateException();
693             }
694             return current.getKey();
695         }
696 
697         @Override
698         public V getValue() {
699             if (current == null) {
700                 throw new IllegalStateException();
701             }
702             return current.getValue();
703         }
704 
705         @Override
706         public void remove() {
707             it.remove();
708         }
709 
710         @Override
711         public V setValue(final V value) {
712             if (current == null) {
713                 throw new IllegalStateException();
714             }
715             return current.setValue(value);
716         }
717 
718     }
719 
720     /**
721      * Inner class that provides the values view.
722      */
723     private class Values extends AbstractCollection<V> {
724         @Override
725         public Iterator<V> iterator() {
726             final IteratorChain<V> chain = new IteratorChain<>();
727             for (final K k : keySet()) {
728                 chain.addIterator(new ValuesIterator(k));
729             }
730             return chain;
731         }
732 
733         @Override
734         public int size() {
735             return AbstractMultiValuedMap.this.size();
736         }
737 
738         @Override
739         public void clear() {
740             AbstractMultiValuedMap.this.clear();
741         }
742     }
743 
744     /**
745      * Inner class that provides the values iterator.
746      */
747     private class ValuesIterator implements Iterator<V> {
748         private final Object key;
749         private final Collection<V> values;
750         private final Iterator<V> iterator;
751 
752         public ValuesIterator(final Object key) {
753             this.key = key;
754             this.values = getMap().get(key);
755             this.iterator = values.iterator();
756         }
757 
758         @Override
759         public void remove() {
760             iterator.remove();
761             if (values.isEmpty()) {
762                 AbstractMultiValuedMap.this.remove(key);
763             }
764         }
765 
766         @Override
767         public boolean hasNext() {
768             return iterator.hasNext();
769         }
770 
771         @Override
772         public V next() {
773             return iterator.next();
774         }
775     }
776 
777     /**
778      * Inner class that provides the AsMap view.
779      */
780     private class AsMap extends AbstractMap<K, Collection<V>> {
781         final transient Map<K, Collection<V>> decoratedMap;
782 
783         AsMap(final Map<K, Collection<V>> map) {
784           this.decoratedMap = map;
785         }
786 
787         @Override
788         public Set<Map.Entry<K, Collection<V>>> entrySet() {
789           return new AsMapEntrySet();
790         }
791 
792         @Override
793         public boolean containsKey(final Object key) {
794             return decoratedMap.containsKey(key);
795         }
796 
797         @Override
798         public Collection<V> get(final Object key) {
799           final Collection<V> collection = decoratedMap.get(key);
800           if (collection == null) {
801             return null;
802           }
803           @SuppressWarnings("unchecked")
804         final
805           K k = (K) key;
806           return wrappedCollection(k);
807         }
808 
809         @Override
810         public Set<K> keySet() {
811           return AbstractMultiValuedMap.this.keySet();
812         }
813 
814         @Override
815         public int size() {
816           return decoratedMap.size();
817         }
818 
819         @Override
820         public Collection<V> remove(final Object key) {
821           final Collection<V> collection = decoratedMap.remove(key);
822           if (collection == null) {
823             return null;
824           }
825 
826           final Collection<V> output = createCollection();
827           output.addAll(collection);
828           collection.clear();
829           return output;
830         }
831 
832         @Override
833         public boolean equals(final Object object) {
834           return this == object || decoratedMap.equals(object);
835         }
836 
837         @Override
838         public int hashCode() {
839           return decoratedMap.hashCode();
840         }
841 
842         @Override
843         public String toString() {
844           return decoratedMap.toString();
845         }
846 
847         @Override
848         public void clear() {
849             AbstractMultiValuedMap.this.clear();
850         }
851 
852         class AsMapEntrySet extends AbstractSet<Map.Entry<K, Collection<V>>> {
853 
854             @Override
855             public Iterator<Map.Entry<K, Collection<V>>> iterator() {
856                 return new AsMapEntrySetIterator(decoratedMap.entrySet().iterator());
857             }
858 
859             @Override
860             public int size() {
861               return AsMap.this.size();
862             }
863 
864             @Override
865             public void clear() {
866                 AsMap.this.clear();
867             }
868 
869             @Override
870             public boolean contains(final Object o) {
871                 return decoratedMap.entrySet().contains(o);
872             }
873 
874             @Override
875             public boolean remove(final Object o) {
876                 if (!contains(o)) {
877                     return false;
878                 }
879                 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
880                 AbstractMultiValuedMap.this.remove(entry.getKey());
881                 return true;
882             }
883         }
884 
885         /**
886          * EntrySet iterator for the asMap view.
887          */
888         class AsMapEntrySetIterator extends AbstractIteratorDecorator<Map.Entry<K, Collection<V>>> {
889 
890             AsMapEntrySetIterator(final Iterator<Map.Entry<K, Collection<V>>> iterator) {
891                 super(iterator);
892             }
893 
894             @Override
895             public Map.Entry<K, Collection<V>> next() {
896                 final Map.Entry<K, Collection<V>> entry = super.next();
897                 final K key = entry.getKey();
898                 return new UnmodifiableMapEntry<>(key, wrappedCollection(key));
899             }
900         }
901     }
902 
903     //-----------------------------------------------------------------------
904     /**
905      * Write the map out using a custom routine.
906      * @param out the output stream
907      * @throws IOException any of the usual I/O related exceptions
908      */
909     protected void doWriteObject(final ObjectOutputStream out) throws IOException {
910         out.writeInt(map.size());
911         for (final Map.Entry<K, Collection<V>> entry : map.entrySet()) {
912             out.writeObject(entry.getKey());
913             out.writeInt(entry.getValue().size());
914             for (final V value : entry.getValue()) {
915                 out.writeObject(value);
916             }
917         }
918     }
919 
920     /**
921      * Read the map in using a custom routine.
922      * @param in the input stream
923      * @throws IOException any of the usual I/O related exceptions
924      * @throws ClassNotFoundException if the stream contains an object which class can not be loaded
925      * @throws ClassCastException if the stream does not contain the correct objects
926      */
927     protected void doReadObject(final ObjectInputStream in)
928             throws IOException, ClassNotFoundException {
929         final int entrySize = in.readInt();
930         for (int i = 0; i < entrySize; i++) {
931             @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
932             final K key = (K) in.readObject();
933             final Collection<V> values = get(key);
934             final int valueSize = in.readInt();
935             for (int j = 0; j < valueSize; j++) {
936                 @SuppressWarnings("unchecked") // see above
937                 final
938                 V value = (V) in.readObject();
939                 values.add(value);
940             }
941         }
942     }
943 
944 }