    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 serialisation.
    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     * Read the map in using a custom routine.
    630     * @param in the input stream
    631     * @throws IOException any of the usual I/O related exceptions
    632     * @throws ClassNotFoundException if the stream contains an object which class cannot be loaded
    633     * @throws ClassCastException if the stream does not contain the correct objects
    634     */
    635    protected void doReadObject(final ObjectInputStream in)
    636            throws IOException, ClassNotFoundException {
    637        final int entrySize = in.readInt();
    638        for (int i = 0; i < entrySize; i++) {
    639            @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
    640            final K key = (K) in.readObject();
    641            final Collection<V> values = get(key);
    642            final int valueSize = in.readInt();
    643            for (int j = 0; j < valueSize; j++) {
    644                @SuppressWarnings("unchecked") // see above
    645                final V value = (V) in.readObject();
    646                values.add(value);
    647            }
    648        }
    649    }
    650
    651    /**
    652     * Write the map out using a custom routine.
    653     * @param out the output stream
    654     * @throws IOException any of the usual I/O related exceptions
    655     */
    656    protected void doWriteObject(final ObjectOutputStream out) throws IOException {
    657        out.writeInt(map.size());
    658        for (final Map.Entry<K, Collection<V>> entry : map.entrySet()) {
    659            out.writeObject(entry.getKey());
    660            out.writeInt(entry.getValue().size());
    661            for (final V value : entry.getValue()) {
    662                out.writeObject(value);
    663            }
    664        }
    665    }
    666
    667    @Override
    668    public Collection<Entry<K, V>> entries() {
    669        return entryValuesView != null ? entryValuesView : (entryValuesView = new EntryValues());
    670    }
    671
    672    @Override
    673    public boolean equals(final Object obj) {
    674        if (this == obj) {
    675            return true;
    676        }
    677        if (obj instanceof MultiValuedMap) {
    678            return asMap().equals(((MultiValuedMap<?, ?>) obj).asMap());
    679        }
    680        return false;
    681    }
    682
    683    /**
    684     * Gets the collection of values associated with the specified key. This
    685     * would return an empty collection in case the mapping is not present
    686     *
    687     * @param key the key to retrieve
    688     * @return the {@code Collection} of values, will return an empty {@code Collection} for no mapping
    689     */
    690    @Override
    691    public Collection<V> get(final K key) {
    692        return wrappedCollection(key);
    693    }
    694
    695    /**
    696     * Gets the map being wrapped.
    697     *
    698     * @return the wrapped map
    699     */
    700    protected Map<K, ? extends Collection<V>> getMap() {
    701        return map;
    702    }
    703
    704    @Override
    705    public int hashCode() {
    706        return getMap().hashCode();
    707    }
    708
    709    @Override
    710    public boolean isEmpty() {
    711        return getMap().isEmpty();
    712    }
    713
    714    /**
    715     * Returns a {@link MultiSet} view of the key mapping contained in this map.
    716     * <p>
    717     * Returns a MultiSet of keys with its values count as the count of the MultiSet.
    718     * This multiset is backed by the map, so any changes in the map is reflected here.
    719     * Any method which modifies this multiset like {@code add}, {@code remove},
    720     * {@link Iterator#remove()} etc throws {@code UnsupportedOperationException}.
    721     *
    722     * @return a bag view of the key mapping contained in this map
    723     */
    724    @Override
    725    public MultiSet<K> keys() {
    726        if (keysMultiSetView == null) {
    727            keysMultiSetView = UnmodifiableMultiSet.unmodifiableMultiSet(new KeysMultiSet());
    728        }
    729        return keysMultiSetView;
    730    }
    731
    732    @Override
    733    public Set<K> keySet() {
    734        return getMap().keySet();
    735    }
    736
    737    @Override
    738    public MapIterator<K, V> mapIterator() {
    739        if (isEmpty()) {
    740            return EmptyMapIterator.emptyMapIterator();
    741        }
    742        return new MultiValuedMapIterator();
    743    }
    744
    745    /**
    746     * Adds the value to the collection associated with the specified key.
    747     * <p>
    748     * Unlike a normal {@code Map} the previous value is not replaced.
    749     * Instead the new value is added to the collection stored against the key.
    750     *
    751     * @param key the key to store against
    752     * @param value the value to add to the collection at the key
    753     * @return the value added if the map changed and null if the map did not change
    754     */
    755    @Override
    756    public boolean put(final K key, final V value) {
    757        Collection<V> coll = getMap().get(key);
    758        if (coll == null) {
    759            coll = createCollection();
    760            if (coll.add(value)) {
    761                map.put(key, coll);
    762                return true;
    763            }
    764            return false;
    765        }
    766        return coll.add(value);
    767    }
    768
    769    /**
    770     * Adds Iterable values to the collection associated with the specified key.
    771     *
    772     * @param key the key to store against
    773     * @param values the values to add to the collection at the key, may not be null
    774     * @return true if this map changed
    775     * @throws NullPointerException if values is null
    776     */
    777    @Override
    778    public boolean putAll(final K key, final Iterable<? extends V> values) {
    779        Objects.requireNonNull(values, "values");
    780
    781        if (values instanceof Collection<?>) {
    782            final Collection<? extends V> valueCollection = (Collection<? extends V>) values;
    783            return !valueCollection.isEmpty() && get(key).addAll(valueCollection);
    784        }
    785        final Iterator<? extends V> it = values.iterator();
    786        return it.hasNext() && CollectionUtils.addAll(get(key), it);
    787    }
    788
    789    /**
    790     * Copies all of the mappings from the specified map to this map. The effect
    791     * of this call is equivalent to that of calling {@link #put(Object,Object)
    792     * put(k, v)} on this map once for each mapping from key {@code k} to value
    793     * {@code v} in the specified map. The behavior of this operation is
    794     * undefined if the specified map is modified while the operation is in
    795     * progress.
    796     *
    797     * @param map mappings to be stored in this map, may not be null
    798     * @return true if the map changed as a result of this operation
    799     * @throws NullPointerException if map is null
    800     */
    801    @Override
    802    public boolean putAll(final Map<? extends K, ? extends V> map) {
    803        Objects.requireNonNull(map, "map");
    804        boolean changed = false;
    805        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
    806            changed |= put(entry.getKey(), entry.getValue());
    807        }
    808        return changed;
    809    }
    810
    811    /**
    812     * Copies all of the mappings from the specified MultiValuedMap to this map.
    813     * The effect of this call is equivalent to that of calling
    814     * {@link #put(Object,Object) put(k, v)} on this map once for each mapping
    815     * from key {@code k} to value {@code v} in the specified map. The
    816     * behavior of this operation is undefined if the specified map is modified
    817     * while the operation is in progress.
    818     *
    819     * @param map mappings to be stored in this map, may not be null
    820     * @return true if the map changed as a result of this operation
    821     * @throws NullPointerException if map is null
    822     */
    823    @Override
    824    public boolean putAll(final MultiValuedMap<? extends K, ? extends V> map) {
    825        Objects.requireNonNull(map, "map");
    826        boolean changed = false;
    827        for (final Map.Entry<? extends K, ? extends V> entry : map.entries()) {
    828            changed |= put(entry.getKey(), entry.getValue());
    829        }
    830        return changed;
    831    }
    832
    833    /**
    834     * Removes all values associated with the specified key.
    835     * <p>
    836     * A subsequent {@code get(Object)} would return an empty collection.
    837     *
    838     * @param key  the key to remove values from
    839     * @return the {@code Collection} of values removed, will return an
    840     *   empty, unmodifiable collection for no mapping found
    841     */
    842    @Override
    843    public Collection<V> remove(final Object key) {
    844        return CollectionUtils.emptyIfNull(getMap().remove(key));
    845    }
    846
    847    /**
    848     * Removes a specific key/value mapping from the multivalued map.
    849     * <p>
    850     * The value is removed from the collection mapped to the specified key.
    851     * Other values attached to that key are unaffected.
    852     * <p>
    853     * If the last value for a key is removed, an empty collection would be
    854     * returned from a subsequent {@link #get(Object)}.
    855     *
    856     * @param key the key to remove from
    857     * @param value the value to remove
    858     * @return true if the mapping was removed, false otherwise
    859     */
    860    @Override
    861    public boolean removeMapping(final Object key, final Object value) {
    862        final Collection<V> coll = getMap().get(key);
    863        if (coll == null) {
    864            return false;
    865        }
    866        final boolean changed = coll.remove(value);
    867        if (coll.isEmpty()) {
    868            getMap().remove(key);
    869        }
    870        return changed;
    871    }
    872
    873    /**
    874     * Sets the map being wrapped.
    875     * <p>
    876     * <strong>NOTE:</strong> this method should only be used during deserialization
    877     *
    878     * @param map the map to wrap
    879     */
    880    @SuppressWarnings("unchecked")
    881    protected void setMap(final Map<K, ? extends Collection<V>> map) {
    882        this.map = (Map<K, Collection<V>>) map;
    883    }
    884
    885    /**
    886     * {@inheritDoc}
    887     * <p>
    888     * This implementation does <strong>not</strong> cache the total size
    889     * of the multivalued map, but rather calculates it by iterating
    890     * over the entries of the underlying map.
    891     */
    892    @Override
    893    public int size() {
    894        // the total size should be cached to improve performance
    895        // but this requires that all modifications of the multimap
    896        // (including the wrapped collections and entry/value
    897        // collections) are tracked.
    898        int size = 0;
    899        for (final Collection<V> col : getMap().values()) {
    900            size += col.size();
    901        }
    902        return size;
    903    }
    904
    905    @Override
    906    public String toString() {
    907        return getMap().toString();
    908    }
    909
    910    /**
    911     * Gets a collection containing all the values in the map.
    912     * <p>
    913     * Returns a collection containing all the values from all keys.
    914     *
    915     * @return a collection view of the values contained in this map
    916     */
    917    @Override
    918    public Collection<V> values() {
    919        final Collection<V> vs = valuesView;
    920        return vs != null ? vs : (valuesView = new Values());
    921    }
    922
    923    Collection<V> wrappedCollection(final K key) {
    924        return new WrappedCollection(key);
    925    }
    926
    927}