001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.collections4.multimap;
018
019import java.io.IOException;
020import java.io.ObjectInputStream;
021import java.io.ObjectOutputStream;
022import java.util.AbstractCollection;
023import java.util.AbstractMap;
024import java.util.AbstractSet;
025import java.util.ArrayList;
026import java.util.Collection;
027import java.util.Iterator;
028import java.util.Map;
029import java.util.Map.Entry;
030import java.util.Set;
031
032import org.apache.commons.collections4.CollectionUtils;
033import org.apache.commons.collections4.IteratorUtils;
034import org.apache.commons.collections4.MapIterator;
035import org.apache.commons.collections4.MultiSet;
036import org.apache.commons.collections4.MultiValuedMap;
037import org.apache.commons.collections4.Transformer;
038import org.apache.commons.collections4.iterators.AbstractIteratorDecorator;
039import org.apache.commons.collections4.iterators.EmptyMapIterator;
040import org.apache.commons.collections4.iterators.IteratorChain;
041import org.apache.commons.collections4.iterators.LazyIteratorChain;
042import org.apache.commons.collections4.iterators.TransformIterator;
043import org.apache.commons.collections4.keyvalue.AbstractMapEntry;
044import org.apache.commons.collections4.keyvalue.UnmodifiableMapEntry;
045import org.apache.commons.collections4.multiset.AbstractMultiSet;
046import org.apache.commons.collections4.multiset.UnmodifiableMultiSet;
047
048/**
049 * Abstract implementation of the {@link MultiValuedMap} interface to simplify
050 * the creation of subclass implementations.
051 * <p>
052 * Subclasses specify a Map implementation to use as the internal storage.
053 * </p>
054 *
055 * @param <K> the type of the keys in this map
056 * @param <V> the type of the values in this map
057 * @since 4.1
058 */
059public abstract class AbstractMultiValuedMap<K, V> implements MultiValuedMap<K, V> {
060
061    /** The values view */
062    private transient Collection<V> valuesView;
063
064    /** The EntryValues view */
065    private transient EntryValues entryValuesView;
066
067    /** The KeyMultiSet view */
068    private transient MultiSet<K> keysMultiSetView;
069
070    /** The AsMap view */
071    private transient AsMap asMapView;
072
073    /** The map used to store the data */
074    private transient Map<K, Collection<V>> map;
075
076    /**
077     * Constructor needed for subclass serialisation.
078     */
079    protected AbstractMultiValuedMap() {
080        super();
081    }
082
083    /**
084     * Constructor that wraps (not copies).
085     *
086     * @param map  the map to wrap, must not be null
087     * @throws NullPointerException if the map is null
088     */
089    @SuppressWarnings("unchecked")
090    protected AbstractMultiValuedMap(final Map<K, ? extends Collection<V>> map) {
091        if (map == null) {
092            throw new NullPointerException("Map must not be null.");
093        }
094        this.map = (Map<K, Collection<V>>) map;
095    }
096
097    // -----------------------------------------------------------------------
098    /**
099     * 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}