    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 *
    054 * @param <K> the type of the keys in this map
    055 * @param <V> the type of the values in this map
    056 * @since 4.1
    057 */
    058public abstract class AbstractMultiValuedMap<K, V> implements MultiValuedMap<K, V> {
    059
    060    /** The values view */
    061    private transient Collection<V> valuesView;
    062
    063    /** The EntryValues view */
    064    private transient EntryValues entryValuesView;
    065
    066    /** The KeyMultiSet view */
    067    private transient MultiSet<K> keysMultiSetView;
    068
    069    /** The AsMap view */
    070    private transient AsMap asMapView;
    071
    072    /** The map used to store the data */
    073    private transient Map<K, Collection<V>> map;
    074
    075    /**
    076     * Constructor needed for subclass serialisation.
    077     */
    078    protected AbstractMultiValuedMap() {
    079        super();
    080    }
    081
    082    /**
    083     * Constructor that wraps (not copies).
    084     *
    085     * @param map  the map to wrap, must not be null
    086     * @throws NullPointerException if the map is null
    087     */
    088    @SuppressWarnings("unchecked")
    089    protected AbstractMultiValuedMap(final Map<K, ? extends Collection<V>> map) {
    090        if (map == null) {
    091            throw new NullPointerException("Map must not be null.");
    092        }
    093        this.map = (Map<K, Collection<V>>) map;
    094    }
    095
    096    // -----------------------------------------------------------------------
    097    /**
    098     * Gets the map being wrapped.
    099     *
    100     * @return the wrapped map
    101     */
    102    protected Map<K, ? extends Collection<V>> getMap() {
    103        return map;
    104    }
    105
    106    /**
    107     * Sets the map being wrapped.
    108     * <p>
    109     * <b>NOTE:</b> this method should only be used during deserialization
    110     *
    111     * @param map the map to wrap
    112     */
    113    @SuppressWarnings("unchecked")
    114    protected void setMap(final Map<K, ? extends Collection<V>> map) {
    115        this.map = (Map<K, Collection<V>>) map;
    116    }
    117
    118    protected abstract Collection<V> createCollection();
    119
    120    // -----------------------------------------------------------------------
    121    @Override
    122    public boolean containsKey(final Object key) {
    123        return getMap().containsKey(key);
    124    }
    125
    126    @Override
    127    public boolean containsValue(final Object value) {
    128        return values().contains(value);
    129    }
    130
    131    @Override
    132    public boolean containsMapping(final Object key, final Object value) {
    133        final Collection<V> coll = getMap().get(key);
    134        return coll != null && coll.contains(value);
    135    }
    136
    137    @Override
    138    public Collection<Entry<K, V>> entries() {
    139        return entryValuesView != null ? entryValuesView : (entryValuesView = new EntryValues());
    140    }
    141
    142    /**
    143     * Gets the collection of values associated with the specified key. This
    144     * would return an empty collection in case the mapping is not present
    145     *
    146     * @param key the key to retrieve
    147     * @return the {@code Collection} of values, will return an empty {@code Collection} for no mapping
    148     */
    149    @Override
    150    public Collection<V> get(final K key) {
    151        return wrappedCollection(key);
    152    }
    153
    154    Collection<V> wrappedCollection(final K key) {
    155        return new WrappedCollection(key);
    156    }
    157
    158    /**
    159     * Removes all values associated with the specified key.
    160     * <p>
    161     * A subsequent <code>get(Object)</code> would return an empty collection.
    162     *
    163     * @param key  the key to remove values from
    164     * @return the <code>Collection</code> of values removed, will return an
    165     *   empty, unmodifiable collection for no mapping found
    166     */
    167    @Override
    168    public Collection<V> remove(final Object key) {
    169        return CollectionUtils.emptyIfNull(getMap().remove(key));
    170    }
    171
    172    /**
    173     * Removes a specific key/value mapping from the multi-valued map.
    174     * <p>
    175     * The value is removed from the collection mapped to the specified key.
    176     * Other values attached to that key are unaffected.
    177     * <p>
    178     * If the last value for a key is removed, an empty collection would be
    179     * returned from a subsequent {@link #get(Object)}.
    180     *
    181     * @param key the key to remove from
    182     * @param value the value to remove
    183     * @return true if the mapping was removed, false otherwise
    184     */
    185    @Override
    186    public boolean removeMapping(final Object key, final Object value) {
    187        final Collection<V> coll = getMap().get(key);
    188        if (coll == null) {
    189            return false;
    190        }
    191        final boolean changed = coll.remove(value);
    192        if (coll.isEmpty()) {
    193            getMap().remove(key);
    194        }
    195        return changed;
    196    }
    197
    198    @Override
    199    public boolean isEmpty() {
    200        return getMap().isEmpty();
    201    }
    202
    203    @Override
    204    public Set<K> keySet() {
    205        return getMap().keySet();
    206    }
    207
    208    /**
    209     * {@inheritDoc}
    210     * <p>
    211     * This implementation does <b>not</b> cache the total size
    212     * of the multi-valued map, but rather calculates it by iterating
    213     * over the entries of the underlying map.
    214     */
    215    @Override
    216    public int size() {
    217        // the total size should be cached to improve performance
    218        // but this requires that all modifications of the multimap
    219        // (including the wrapped collections and entry/value
    220        // collections) are tracked.
    221        int size = 0;
    222        for (final Collection<V> col : getMap().values()) {
    223            size += col.size();
    224        }
    225        return size;
    226    }
    227
    228    /**
    229     * Gets a collection containing all the values in the map.
    230     * <p>
    231     * Returns a collection containing all the values from all keys.
    232     *
    233     * @return a collection view of the values contained in this map
    234     */
    235    @Override
    236    public Collection<V> values() {
    237        final Collection<V> vs = valuesView;
    238        return vs != null ? vs : (valuesView = new Values());
    239    }
    240
    241    @Override
    242    public void clear() {
    243        getMap().clear();
    244    }
    245
    246    /**
    247     * Adds the value to the collection associated with the specified key.
    248     * <p>
    249     * Unlike a normal <code>Map</code> the previous value is not replaced.
    250     * Instead the new value is added to the collection stored against the key.
    251     *
    252     * @param key the key to store against
    253     * @param value the value to add to the collection at the key
    254     * @return the value added if the map changed and null if the map did not change
    255     */
    256    @Override
    257    public boolean put(final K key, final V value) {
    258        Collection<V> coll = getMap().get(key);
    259        if (coll == null) {
    260            coll = createCollection();
    261            if (coll.add(value)) {
    262                map.put(key, coll);
    263                return true;
    264            }
    265            return false;
    266        }
    267        return coll.add(value);
    268    }
    269
    270    /**
    271     * Copies all of the mappings from the specified map to this map. The effect
    272     * of this call is equivalent to that of calling {@link #put(Object,Object)
    273     * put(k, v)} on this map once for each mapping from key {@code k} to value
    274     * {@code v} in the specified map. The behavior of this operation is
    275     * undefined if the specified map is modified while the operation is in
    276     * progress.
    277     *
    278     * @param map mappings to be stored in this map, may not be null
    279     * @return true if the map changed as a result of this operation
    280     * @throws NullPointerException if map is null
    281     */
    282    @Override
    283    public boolean putAll(final Map<? extends K, ? extends V> map) {
    284        if (map == null) {
    285            throw new NullPointerException("Map must not be null.");
    286        }
    287        boolean changed = false;
    288        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
    289            changed |= put(entry.getKey(), entry.getValue());
    290        }
    291        return changed;
    292    }
    293
    294    /**
    295     * Copies all of the mappings from the specified MultiValuedMap to this map.
    296     * The effect of this call is equivalent to that of calling
    297     * {@link #put(Object,Object) put(k, v)} on this map once for each mapping
    298     * from key {@code k} to value {@code v} in the specified map. The
    299     * behavior of this operation is undefined if the specified map is modified
    300     * while the operation is in progress.
    301     *
    302     * @param map mappings to be stored in this map, may not be null
    303     * @return true if the map changed as a result of this operation
    304     * @throws NullPointerException if map is null
    305     */
    306    @Override
    307    public boolean putAll(final MultiValuedMap<? extends K, ? extends V> map) {
    308        if (map == null) {
    309            throw new NullPointerException("Map must not be null.");
    310        }
    311        boolean changed = false;
    312        for (final Map.Entry<? extends K, ? extends V> entry : map.entries()) {
    313            changed |= put(entry.getKey(), entry.getValue());
    314        }
    315        return changed;
    316    }
    317
    318    /**
    319     * Returns a {@link MultiSet} view of the key mapping contained in this map.
    320     * <p>
    321     * Returns a MultiSet of keys with its values count as the count of the MultiSet.
    322     * This multiset is backed by the map, so any changes in the map is reflected here.
    323     * Any method which modifies this multiset like {@code add}, {@code remove},
    324     * {@link Iterator#remove()} etc throws {@code UnsupportedOperationException}.
    325     *
    326     * @return a bag view of the key mapping contained in this map
    327     */
    328    @Override
    329    public MultiSet<K> keys() {
    330        if (keysMultiSetView == null) {
    331            keysMultiSetView = UnmodifiableMultiSet.unmodifiableMultiSet(new KeysMultiSet());
    332        }
    333        return keysMultiSetView;
    334    }
    335
    336    @Override
    337    public Map<K, Collection<V>> asMap() {
    338        return asMapView != null ? asMapView : (asMapView = new AsMap(map));
    339    }
    340
    341    /**
    342     * Adds Iterable values to the collection associated with the specified key.
    343     *
    344     * @param key the key to store against
    345     * @param values the values to add to the collection at the key, may not be null
    346     * @return true if this map changed
    347     * @throws NullPointerException if values is null
    348     */
    349    @Override
    350    public boolean putAll(final K key, final Iterable<? extends V> values) {
    351        if (values == null) {
    352            throw new NullPointerException("Values must not be null.");
    353        }
    354
    355        if (values instanceof Collection<?>) {
    356            final Collection<? extends V> valueCollection = (Collection<? extends V>) values;
    357            return !valueCollection.isEmpty() && get(key).addAll(valueCollection);
    358        }
    359        final Iterator<? extends V> it = values.iterator();
    360        return it.hasNext() && CollectionUtils.addAll(get(key), it);
    361    }
    362
    363    @Override
    364    public MapIterator<K, V> mapIterator() {
    365        if (size() == 0) {
    366            return EmptyMapIterator.emptyMapIterator();
    367        }
    368        return new MultiValuedMapIterator();
    369    }
    370
    371    @Override
    372    public boolean equals(final Object obj) {
    373        if (this == obj) {
    374            return true;
    375        }
    376        if (obj instanceof MultiValuedMap) {
    377            return asMap().equals(((MultiValuedMap<?, ?>) obj).asMap());
    378        }
    379        return false;
    380    }
    381
    382    @Override
    383    public int hashCode() {
    384        return getMap().hashCode();
    385    }
    386
    387    @Override
    388    public String toString() {
    389        return getMap().toString();
    390    }
    391
    392    // -----------------------------------------------------------------------
    393
    394    /**
    395     * Wrapped collection to handle add and remove on the collection returned
    396     * by get(object).
    397     * <p>
    398     * Currently, the wrapped collection is not cached and has to be retrieved
    399     * from the underlying map. This is safe, but not very efficient and
    400     * should be improved in subsequent releases. For this purpose, the
    401     * scope of this collection is set to package private to simplify later
    402     * refactoring.
    403     */
    404    class WrappedCollection implements Collection<V> {
    405
    406        protected final K key;
    407
    408        public WrappedCollection(final K key) {
    409            this.key = key;
    410        }
    411
    412        protected Collection<V> getMapping() {
    413            return getMap().get(key);
    414        }
    415
    416        @Override
    417        public boolean add(final V value) {
    418            Collection<V> coll = getMapping();
    419            if (coll == null) {
    420                coll = createCollection();
    421                AbstractMultiValuedMap.this.map.put(key, coll);
    422            }
    423            return coll.add(value);
    424        }
    425
    426        @Override
    427        public boolean addAll(final Collection<? extends V> other) {
    428            Collection<V> coll = getMapping();
    429            if (coll == null) {
    430                coll = createCollection();
    431                AbstractMultiValuedMap.this.map.put(key, coll);
    432            }
    433            return coll.addAll(other);
    434        }
    435
    436        @Override
    437        public void clear() {
    438            final Collection<V> coll = getMapping();
    439            if (coll != null) {
    440                coll.clear();
    441                AbstractMultiValuedMap.this.remove(key);
    442            }
    443        }
    444
    445        @Override
    446        @SuppressWarnings("unchecked")
    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 ? false : coll.contains(obj);
    465        }
    466
    467        @Override
    468        public boolean containsAll(final Collection<?> other) {
    469            final Collection<V> coll = getMapping();
    470            return coll == null ? false : coll.containsAll(other);
    471        }
    472
    473        @Override
    474        public boolean isEmpty() {
    475            final Collection<V> coll = getMapping();
    476            return coll == null ? true : 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}