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