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