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