/*
 * Copyright (C) 2007 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.jboss.solder.util.collections;

import java.io.Serializable;
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.RandomAccess;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;

import static org.jboss.solder.util.collections.Preconditions.checkArgument;
import static org.jboss.solder.util.collections.Preconditions.checkState;

/**
 * Basic implementation of the {@link Multimap} interface. This class represents
 * a multimap as a map that associates each key with a collection of values. All
 * methods of {@link Multimap} are supported, including those specified as
 * optional in the interface.
 * <p/>
 * <p/>
 * To implement a multimap, a subclass must define the method
 * {@link #createCollection()}, which creates an empty collection of values for
 * a key.
 * <p/>
 * <p/>
 * The multimap constructor takes a map that has a single entry for each
 * distinct key. When you insert a key-value pair with a key that isn't already
 * in the multimap, {@code AbstractMultimap} calls {@link #createCollection()}
 * to create the collection of values for that key. The subclass should not call
 * {@link #createCollection()} directly, and a new instance should be created
 * every time the method is called.
 * <p/>
 * <p/>
 * For example, the subclass could pass a {@link java.util.TreeMap} during
 * construction, and {@link #createCollection()} could return a
 * {@link java.util.TreeSet}, in which case the multimap's iterators would
 * propagate through the keys and values in sorted order.
 * <p/>
 * <p/>
 * Keys and values may be null, as long as the underlying collection classes
 * support null elements.
 * <p/>
 * <p/>
 * The collections created by {@link #createCollection()} may or may not allow
 * duplicates. If the collection, such as a {@link Set}, does not support
 * duplicates, an added key-value pair will replace an existing pair with the
 * same key and value, if such a pair is present. With collections like
 * {@link List} that allow duplicates, the collection will keep the existing
 * key-value pairs while adding a new pair.
 * <p/>
 * <p/>
 * This class is not threadsafe when any concurrent operations update the
 * multimap, even if the underlying map and {@link #createCollection()} method
 * return threadsafe classes. Concurrent read operations will work correctly. To
 * allow concurrent update operations, wrap your multimap with a call to
 * Multimaps#synchronizedMultimap.
 * <p/>
 * <p/>
 * For serialization to work, the subclass must specify explicit {@code
 * readObject} and {@code writeObject} methods.
 *
 * @author Jared Levy
 */
abstract class AbstractMultimap<K, V> implements Multimap<K, V>, Serializable {
    /*
    * Here's an outline of the overall design.
    *
    * The map variable contains the collection of values associated with each
    * key. When a key-value pair is added to a multimap that didn't previously
    * contain any values for that key, a new collection generated by
    * createCollection is added to the map. That same collection instance
    * remains in the map as long as the multimap has any values for the key. If
    * all values for the key are removed, the key and collection are removed
    * from the map.
    *
    * The get method returns a WrappedCollection, which decorates the collection
    * in the map (if the key is present) or an empty collection (if the key is
    * not present). When the collection delegate in the WrappedCollection is
    * empty, the multimap may contain subsequently added values for that key. To
    * handle that situation, the WrappedCollection checks whether map contains
    * an entry for the provided key, and if so replaces the delegate.
    */

    transient Map<K, Collection<V>> map;
    transient int totalSize;

    /**
     * Creates a new multimap that uses the provided map.
     *
     * @param map place to store the mapping from each key to its corresponding
     *            values
     * @throws IllegalArgumentException if {@code map} is not empty
     */
    protected AbstractMultimap(Map<K, Collection<V>> map) {
        checkArgument(map.isEmpty());
        this.map = map;
    }

    /**
     * Used during deserialization only.
     */
    final void setMap(Map<K, Collection<V>> map) {
        this.map = map;
        totalSize = 0;
        for (Collection<V> values : map.values()) {
            checkArgument(!values.isEmpty());
            totalSize += values.size();
        }
    }

    /**
     * Creates the collection of values for a single key.
     * <p/>
     * <p/>
     * Collections with weak, soft, or phantom references are not supported. Each
     * call to {@code createCollection} should create a new instance.
     * <p/>
     * <p/>
     * The returned collection class determines whether duplicate key-value pairs
     * are allowed.
     *
     * @return an empty collection of values
     */
    abstract Collection<V> createCollection();

    /**
     * Creates the collection of values for an explicitly provided key. By
     * default, it simply calls {@link #createCollection()}, which is the correct
     * behavior for most implementations. The LinkedHashMultimap class overrides
     * it.
     *
     * @param key key to associate with values in the collection
     * @return an empty collection of values
     */
    Collection<V> createCollection(K key) {
        return createCollection();
    }

    Map<K, Collection<V>> backingMap() {
        return map;
    }

    // Query Operations

    public int size() {
        return totalSize;
    }

    public boolean isEmpty() {
        return totalSize == 0;
    }

    public boolean containsKey(Object key) {
        return map.containsKey(key);
    }

    public boolean containsValue(Object value) {
        for (Collection<V> collection : map.values()) {
            if (collection.contains(value)) {
                return true;
            }
        }

        return false;
    }

    public boolean containsEntry(Object key, Object value) {
        Collection<V> collection = map.get(key);
        return collection != null && collection.contains(value);
    }

    // Modification Operations

    public boolean put(K key, V value) {
        Collection<V> collection = getOrCreateCollection(key);

        if (collection.add(value)) {
            totalSize++;
            return true;
        } else {
            return false;
        }
    }

    private Collection<V> getOrCreateCollection(K key) {
        Collection<V> collection = map.get(key);
        if (collection == null) {
            collection = createCollection(key);
            map.put(key, collection);
        }
        return collection;
    }

    public boolean remove(Object key, Object value) {
        Collection<V> collection = map.get(key);
        if (collection == null) {
            return false;
        }

        boolean changed = collection.remove(value);
        if (changed) {
            totalSize--;
            if (collection.isEmpty()) {
                map.remove(key);
            }
        }
        return changed;
    }

    // Bulk Operations

    public boolean putAll(K key, Iterable<? extends V> values) {
        if (!values.iterator().hasNext()) {
            return false;
        }
        Collection<V> collection = getOrCreateCollection(key);
        int oldSize = collection.size();

        boolean changed = false;
        if (values instanceof Collection<?>) {
            Collection<? extends V> c = (Collection<? extends V>) values;
            changed = collection.addAll(c);
        } else {
            for (V value : values) {
                changed |= collection.add(value);
            }
        }

        totalSize += (collection.size() - oldSize);
        return changed;
    }

    public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
        boolean changed = false;
        for (Map.Entry<? extends K, ? extends V> entry : multimap.entries()) {
            changed |= put(entry.getKey(), entry.getValue());
        }
        return changed;
    }

    /**
     * {@inheritDoc}
     * <p/>
     * <p/>
     * The returned collection is immutable.
     */
    public Collection<V> replaceValues(K key, Iterable<? extends V> values) {
        Iterator<? extends V> iterator = values.iterator();
        if (!iterator.hasNext()) {
            return removeAll(key);
        }

        Collection<V> collection = getOrCreateCollection(key);
        Collection<V> oldValues = createCollection();
        oldValues.addAll(collection);

        totalSize -= collection.size();
        collection.clear();

        while (iterator.hasNext()) {
            if (collection.add(iterator.next())) {
                totalSize++;
            }
        }

        return unmodifiableCollectionSubclass(oldValues);
    }

    /**
     * {@inheritDoc}
     * <p/>
     * <p/>
     * The returned collection is immutable.
     */
    public Collection<V> removeAll(Object key) {
        Collection<V> collection = map.remove(key);
        Collection<V> output = createCollection();

        if (collection != null) {
            output.addAll(collection);
            totalSize -= collection.size();
            collection.clear();
        }

        return unmodifiableCollectionSubclass(output);
    }

    private Collection<V> unmodifiableCollectionSubclass(Collection<V> collection) {
        if (collection instanceof SortedSet<?>) {
            return Collections.unmodifiableSortedSet((SortedSet<V>) collection);
        } else if (collection instanceof Set<?>) {
            return Collections.unmodifiableSet((Set<V>) collection);
        } else if (collection instanceof List<?>) {
            return Collections.unmodifiableList((List<V>) collection);
        } else {
            return Collections.unmodifiableCollection(collection);
        }
    }

    public void clear() {
        // Clear each collection, to make previously returned collections empty.
        for (Collection<V> collection : map.values()) {
            collection.clear();
        }
        map.clear();
        totalSize = 0;
    }

    // Views

    /**
     * {@inheritDoc}
     * <p/>
     * <p/>
     * The returned collection is not serializable.
     */
    public Collection<V> get(K key) {
        Collection<V> collection = map.get(key);
        if (collection == null) {
            collection = createCollection(key);
        }
        return wrapCollection(key, collection);
    }

    /**
     * Generates a decorated collection that remains consistent with the values
     * in the multimap for the provided key. Changes to the multimap may alter
     * the returned collection, and vice versa.
     */
    private Collection<V> wrapCollection(K key, Collection<V> collection) {
        if (collection instanceof SortedSet<?>) {
            return new WrappedSortedSet(key, (SortedSet<V>) collection, null);
        } else if (collection instanceof Set<?>) {
            return new WrappedSet(key, (Set<V>) collection);
        } else if (collection instanceof List<?>) {
            return wrapList(key, (List<V>) collection, null);
        } else {
            return new WrappedCollection<K, V>(this, key, collection, null);
        }
    }

    List<V> wrapList(K key, List<V> list, WrappedCollection<K, V> ancestor) {
        return (list instanceof RandomAccess) ? new RandomAccessWrappedList(key, list, ancestor) : new WrappedList<K, V>(this, key, list, ancestor);
    }

    Iterator<V> iteratorOrListIterator(Collection<V> collection) {
        return (collection instanceof List<?>) ? ((List<V>) collection).listIterator() : collection.iterator();
    }

    /**
     * Set decorator that stays in sync with the multimap values for a key.
     */
    private class WrappedSet extends WrappedCollection<K, V> implements Set<V> {
        WrappedSet(K key, Set<V> delegate) {
            super(AbstractMultimap.this, key, delegate, null);
        }
    }

    /**
     * SortedSet decorator that stays in sync with the multimap values for a key.
     */
    private class WrappedSortedSet extends WrappedCollection<K, V> implements SortedSet<V> {
        WrappedSortedSet(K key, SortedSet<V> delegate, WrappedCollection<K, V> ancestor) {
            super(AbstractMultimap.this, key, delegate, ancestor);
        }

        SortedSet<V> getSortedSetDelegate() {
            return (SortedSet<V>) getDelegate();
        }

        public Comparator<? super V> comparator() {
            return getSortedSetDelegate().comparator();
        }

        public V first() {
            refreshIfEmpty();
            return getSortedSetDelegate().first();
        }

        public V last() {
            refreshIfEmpty();
            return getSortedSetDelegate().last();
        }

        public SortedSet<V> headSet(V toElement) {
            refreshIfEmpty();
            return new WrappedSortedSet(getKey(), getSortedSetDelegate().headSet(toElement), (getAncestor() == null) ? this : getAncestor());
        }

        public SortedSet<V> subSet(V fromElement, V toElement) {
            refreshIfEmpty();
            return new WrappedSortedSet(getKey(), getSortedSetDelegate().subSet(fromElement, toElement), (getAncestor() == null) ? this : getAncestor());
        }

        public SortedSet<V> tailSet(V fromElement) {
            refreshIfEmpty();
            return new WrappedSortedSet(getKey(), getSortedSetDelegate().tailSet(fromElement), (getAncestor() == null) ? this : getAncestor());
        }
    }

    /**
     * List decorator that stays in sync with the multimap values for a key and
     * supports rapid random access.
     */
    private class RandomAccessWrappedList extends WrappedList<K, V> implements RandomAccess {
        RandomAccessWrappedList(K key, List<V> delegate, WrappedCollection<K, V> ancestor) {
            super(AbstractMultimap.this, key, delegate, ancestor);
        }
    }

    private transient Set<K> keySet;

    public Set<K> keySet() {
        Set<K> result = keySet;
        return (result == null) ? keySet = createKeySet() : result;
    }

    private Set<K> createKeySet() {
        return (map instanceof SortedMap<?, ?>) ? new SortedKeySet((SortedMap<K, Collection<V>>) map) : new KeySet(map);
    }

    private class KeySet extends AbstractSet<K> {

        /**
         * This is usually the same as map, except when someone requests a
         * subcollection of a {@link SortedKeySet}.
         */
        final Map<K, Collection<V>> subMap;

        KeySet(final Map<K, Collection<V>> subMap) {
            this.subMap = subMap;
        }

        @Override
        public int size() {
            return subMap.size();
        }

        @Override
        public Iterator<K> iterator() {
            return new Iterator<K>() {
                final Iterator<Map.Entry<K, Collection<V>>> entryIterator = subMap.entrySet().iterator();
                Map.Entry<K, Collection<V>> entry;

                public boolean hasNext() {
                    return entryIterator.hasNext();
                }

                public K next() {
                    entry = entryIterator.next();
                    return entry.getKey();
                }

                public void remove() {
                    checkState(entry != null);
                    Collection<V> collection = entry.getValue();
                    entryIterator.remove();
                    totalSize -= collection.size();
                    collection.clear();
                }
            };
        }

        // The following methods are included for better performance.

        @Override
        public boolean contains(Object key) {
            return subMap.containsKey(key);
        }

        @Override
        public boolean remove(Object key) {
            int count = 0;
            Collection<V> collection = subMap.remove(key);
            if (collection != null) {
                count = collection.size();
                collection.clear();
                totalSize -= count;
            }
            return count > 0;
        }

        @Override
        public boolean containsAll(Collection<?> c) {
            return subMap.keySet().containsAll(c);
        }

        @Override
        public boolean equals(Object object) {
            return this == object || this.subMap.keySet().equals(object);
        }

        @Override
        public int hashCode() {
            return subMap.keySet().hashCode();
        }
    }

    private class SortedKeySet extends KeySet implements SortedSet<K> {

        SortedKeySet(SortedMap<K, Collection<V>> subMap) {
            super(subMap);
        }

        SortedMap<K, Collection<V>> sortedMap() {
            return (SortedMap<K, Collection<V>>) subMap;
        }

        public Comparator<? super K> comparator() {
            return sortedMap().comparator();
        }

        public K first() {
            return sortedMap().firstKey();
        }

        public SortedSet<K> headSet(K toElement) {
            return new SortedKeySet(sortedMap().headMap(toElement));
        }

        public K last() {
            return sortedMap().lastKey();
        }

        public SortedSet<K> subSet(K fromElement, K toElement) {
            return new SortedKeySet(sortedMap().subMap(fromElement, toElement));
        }

        public SortedSet<K> tailSet(K fromElement) {
            return new SortedKeySet(sortedMap().tailMap(fromElement));
        }
    }

    private transient Multiset<K> multiset;

    public Multiset<K> keys() {
        Multiset<K> result = multiset;
        return (result == null) ? multiset = new MultisetView() : result;
    }

    /**
     * Multiset view that stays in sync with the multimap keys.
     */
    private class MultisetView extends AbstractMultiset<K> {

        @Override
        public int remove(Object key, int occurrences) {
            if (occurrences == 0) {
                return count(key);
            }
            checkArgument(occurrences > 0);

            Collection<V> collection;
            try {
                collection = map.get(key);
            } catch (NullPointerException e) {
                return 0;
            } catch (ClassCastException e) {
                return 0;
            }

            if (collection == null) {
                return 0;
            }
            int count = collection.size();

            if (occurrences >= count) {
                return removeValuesForKey(key);
            }

            Iterator<V> iterator = collection.iterator();
            for (int i = 0; i < occurrences; i++) {
                iterator.next();
                iterator.remove();
            }
            totalSize -= occurrences;
            return count;
        }

        @Override
        public Set<K> elementSet() {
            return AbstractMultimap.this.keySet();
        }

        transient Set<Multiset.Entry<K>> entrySet;

        @Override
        public Set<Multiset.Entry<K>> entrySet() {
            Set<Multiset.Entry<K>> result = entrySet;
            return (result == null) ? entrySet = new EntrySet() : result;
        }

        private class EntrySet extends AbstractSet<Multiset.Entry<K>> {
            @Override
            public Iterator<Multiset.Entry<K>> iterator() {
                return new MultisetEntryIterator();
            }

            @Override
            public int size() {
                return map.size();
            }

            // The following methods are included for better performance.

            @Override
            public boolean contains(Object o) {
                if (!(o instanceof Multiset.Entry<?>)) {
                    return false;
                }
                Multiset.Entry<?> entry = (Multiset.Entry<?>) o;
                Collection<V> collection = map.get(entry.getElement());
                return (collection != null) && (collection.size() == entry.getCount());
            }

            @Override
            public void clear() {
                AbstractMultimap.this.clear();
            }

            @Override
            public boolean remove(Object o) {
                return contains(o) && (removeValuesForKey(((Multiset.Entry<?>) o).getElement()) > 0);
            }
        }

        @Override
        public Iterator<K> iterator() {
            return new MultisetKeyIterator();
        }

        // The following methods are included for better performance.

        @Override
        public int count(Object key) {
            try {
                Collection<V> collection = map.get(key);
                return (collection == null) ? 0 : collection.size();
            } catch (NullPointerException e) {
                return 0;
            } catch (ClassCastException e) {
                return 0;
            }
        }

        @Override
        public int size() {
            return totalSize;
        }

        @Override
        public void clear() {
            AbstractMultimap.this.clear();
        }
    }

    /**
     * Removes all values for the provided key. Unlike {@link #removeAll}, it
     * returns the number of removed mappings.
     */
    private int removeValuesForKey(Object key) {
        Collection<V> collection;
        try {
            collection = map.remove(key);
        } catch (NullPointerException e) {
            return 0;
        } catch (ClassCastException e) {
            return 0;
        }

        int count = 0;
        if (collection != null) {
            count = collection.size();
            collection.clear();
            totalSize -= count;
        }
        return count;
    }

    /**
     * Iterator across each key, repeating once per value.
     */
    private class MultisetEntryIterator implements Iterator<Multiset.Entry<K>> {
        final Iterator<Map.Entry<K, Collection<V>>> asMapIterator = asMap().entrySet().iterator();

        public boolean hasNext() {
            return asMapIterator.hasNext();
        }

        public Multiset.Entry<K> next() {
            return new MultisetEntry(asMapIterator.next());
        }

        public void remove() {
            asMapIterator.remove();
        }
    }

    private class MultisetEntry extends Multisets.AbstractEntry<K> {
        final Map.Entry<K, Collection<V>> entry;

        public MultisetEntry(Map.Entry<K, Collection<V>> entry) {
            this.entry = entry;
        }

        public K getElement() {
            return entry.getKey();
        }

        public int getCount() {
            return entry.getValue().size();
        }
    }

    /**
     * Iterator across each key, repeating once per value.
     */
    private class MultisetKeyIterator implements Iterator<K> {
        final Iterator<Map.Entry<K, V>> entryIterator = entries().iterator();

        public boolean hasNext() {
            return entryIterator.hasNext();
        }

        public K next() {
            return entryIterator.next().getKey();
        }

        public void remove() {
            entryIterator.remove();
        }
    }

    private transient Collection<V> valuesCollection;

    /**
     * {@inheritDoc}
     * <p/>
     * <p/>
     * The iterator generated by the returned collection traverses the values for
     * one key, followed by the values of a second key, and so on.
     */
    public Collection<V> values() {
        Collection<V> result = valuesCollection;
        return (result == null) ? valuesCollection = new Values() : result;
    }

    private class Values extends AbstractCollection<V> {
        @Override
        public Iterator<V> iterator() {
            return new ValueIterator();
        }

        @Override
        public int size() {
            return totalSize;
        }

        // The following methods are included to improve performance.

        @Override
        public void clear() {
            AbstractMultimap.this.clear();
        }

        @Override
        public boolean contains(Object value) {
            return containsValue(value);
        }
    }

    /**
     * Iterator across all values.
     */
    private class ValueIterator implements Iterator<V> {
        final Iterator<Map.Entry<K, V>> entryIterator = createEntryIterator();

        public boolean hasNext() {
            return entryIterator.hasNext();
        }

        public V next() {
            return entryIterator.next().getValue();
        }

        public void remove() {
            entryIterator.remove();
        }
    }

    private transient Collection<Map.Entry<K, V>> entries;

    // TODO: should we copy this javadoc to each concrete class, so that classes
    // like LinkedHashMultimap that need to say something different are still
    // able to {@inheritDoc} all the way from Multimap?

    /**
     * {@inheritDoc}
     * <p/>
     * <p/>
     * The iterator generated by the returned collection traverses the values for
     * one key, followed by the values of a second key, and so on.
     * <p/>
     * <p/>
     * Each entry is an immutable snapshot of a key-value mapping in the
     * multimap, taken at the time the entry is returned by a method call to the
     * collection or its iterator.
     */
    public Collection<Map.Entry<K, V>> entries() {
        Collection<Map.Entry<K, V>> result = entries;
        return (entries == null) ? entries = createEntries() : result;
    }

    private Collection<Map.Entry<K, V>> createEntries() {
        // TODO: can we refactor so we're not doing "this instanceof"?
        return (this instanceof SetMultimap<?, ?>) ? new EntrySet() : new Entries();
    }

    /**
     * Entries for multimap.
     */
    private class Entries extends AbstractCollection<Map.Entry<K, V>> {
        @Override
        public Iterator<Map.Entry<K, V>> iterator() {
            return createEntryIterator();
        }

        @Override
        public int size() {
            return totalSize;
        }

        // The following methods are included to improve performance.

        @Override
        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry<?, ?>)) {
                return false;
            }
            Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
            return containsEntry(entry.getKey(), entry.getValue());
        }

        @Override
        public void clear() {
            AbstractMultimap.this.clear();
        }

        @Override
        public boolean remove(Object o) {
            if (!(o instanceof Map.Entry<?, ?>)) {
                return false;
            }
            Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
            return AbstractMultimap.this.remove(entry.getKey(), entry.getValue());
        }
    }

    /**
     * Returns an iterator across all key-value map entries, used by {@code
     * entries().iterator()} and {@code values().iterator()}. The default
     * behavior, which traverses the values for one key, the values for a second
     * key, and so on, suffices for most {@code AbstractMultimap}
     * implementations.
     *
     * @return an iterator across map entries
     */
    Iterator<Map.Entry<K, V>> createEntryIterator() {
        return new EntryIterator();
    }

    /**
     * Iterator across all key-value pairs.
     */
    private class EntryIterator implements Iterator<Map.Entry<K, V>> {
        final Iterator<Map.Entry<K, Collection<V>>> keyIterator;
        K key;
        Collection<V> collection;
        Iterator<V> valueIterator;

        EntryIterator() {
            keyIterator = map.entrySet().iterator();
            if (keyIterator.hasNext()) {
                findValueIteratorAndKey();
            } else {
                valueIterator = Iterators.emptyModifiableIterator();
            }
        }

        void findValueIteratorAndKey() {
            Map.Entry<K, Collection<V>> entry = keyIterator.next();
            key = entry.getKey();
            collection = entry.getValue();
            valueIterator = collection.iterator();
        }

        public boolean hasNext() {
            return keyIterator.hasNext() || valueIterator.hasNext();
        }

        public Map.Entry<K, V> next() {
            if (!valueIterator.hasNext()) {
                findValueIteratorAndKey();
            }
            return Maps.immutableEntry(key, valueIterator.next());
        }

        public void remove() {
            valueIterator.remove();
            if (collection.isEmpty()) {
                keyIterator.remove();
            }
            totalSize--;
        }
    }

    /**
     * Entry set for a {@link SetMultimap}.
     */
    private class EntrySet extends Entries implements Set<Map.Entry<K, V>> {
        @Override
        public boolean equals(Object object) {
            return Collections2.setEquals(this, object);
        }

        @Override
        public int hashCode() {
            return Sets.hashCodeImpl(this);
        }
    }

    private transient Map<K, Collection<V>> asMap;

    public Map<K, Collection<V>> asMap() {
        Map<K, Collection<V>> result = asMap;
        return (result == null) ? asMap = createAsMap() : result;
    }

    private Map<K, Collection<V>> createAsMap() {
        return (map instanceof SortedMap<?, ?>) ? new SortedAsMap((SortedMap<K, Collection<V>>) map) : new AsMap(map);
    }

    private class AsMap extends AbstractMap<K, Collection<V>> {
        /**
         * Usually the same as map, but smaller for the headMap(), tailMap(), or
         * subMap() of a SortedAsMap.
         */
        final transient Map<K, Collection<V>> submap;

        AsMap(Map<K, Collection<V>> submap) {
            this.submap = submap;
        }

        transient Set<Map.Entry<K, Collection<V>>> entrySet;

        @Override
        public Set<Map.Entry<K, Collection<V>>> entrySet() {
            Set<Map.Entry<K, Collection<V>>> result = entrySet;
            return (entrySet == null) ? entrySet = new AsMapEntries() : result;
        }

        // The following methods are included for performance.

        @Override
        public boolean containsKey(Object key) {
            return submap.containsKey(key);
        }

        @Override
        public Collection<V> get(Object key) {
            Collection<V> collection = submap.get(key);
            if (collection == null) {
                return null;
            }
            @SuppressWarnings("unchecked")
            K k = (K) key;
            return wrapCollection(k, collection);
        }

        @Override
        public Set<K> keySet() {
            return AbstractMultimap.this.keySet();
        }

        @Override
        public Collection<V> remove(Object key) {
            Collection<V> collection = submap.remove(key);
            if (collection == null) {
                return null;
            }

            Collection<V> output = createCollection();
            output.addAll(collection);
            totalSize -= collection.size();
            collection.clear();
            return output;
        }

        @Override
        public boolean equals(Object object) {
            return this == object || submap.equals(object);
        }

        @Override
        public int hashCode() {
            return submap.hashCode();
        }

        @Override
        public String toString() {
            return submap.toString();
        }

        class AsMapEntries extends AbstractSet<Map.Entry<K, Collection<V>>> {
            @Override
            public Iterator<Map.Entry<K, Collection<V>>> iterator() {
                return new AsMapIterator();
            }

            @Override
            public int size() {
                return submap.size();
            }

            // The following methods are included for performance.

            @Override
            public boolean contains(Object o) {
                return submap.entrySet().contains(o);
            }

            @Override
            public boolean remove(Object o) {
                if (!contains(o)) {
                    return false;
                }
                Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
                removeValuesForKey(entry.getKey());
                return true;
            }
        }

        /**
         * Iterator across all keys and value collections.
         */
        class AsMapIterator implements Iterator<Map.Entry<K, Collection<V>>> {
            final Iterator<Map.Entry<K, Collection<V>>> delegateIterator = submap.entrySet().iterator();
            Collection<V> collection;

            public boolean hasNext() {
                return delegateIterator.hasNext();
            }

            public Map.Entry<K, Collection<V>> next() {
                Map.Entry<K, Collection<V>> entry = delegateIterator.next();
                K key = entry.getKey();
                collection = entry.getValue();
                return Maps.immutableEntry(key, wrapCollection(key, collection));
            }

            public void remove() {
                delegateIterator.remove();
                totalSize -= collection.size();
                collection.clear();
            }
        }
    }

    private class SortedAsMap extends AsMap implements SortedMap<K, Collection<V>> {
        SortedAsMap(SortedMap<K, Collection<V>> submap) {
            super(submap);
        }

        SortedMap<K, Collection<V>> sortedMap() {
            return (SortedMap<K, Collection<V>>) submap;
        }

        public Comparator<? super K> comparator() {
            return sortedMap().comparator();
        }

        public K firstKey() {
            return sortedMap().firstKey();
        }

        public K lastKey() {
            return sortedMap().lastKey();
        }

        public SortedMap<K, Collection<V>> headMap(K toKey) {
            return new SortedAsMap(sortedMap().headMap(toKey));
        }

        public SortedMap<K, Collection<V>> subMap(K fromKey, K toKey) {
            return new SortedAsMap(sortedMap().subMap(fromKey, toKey));
        }

        public SortedMap<K, Collection<V>> tailMap(K fromKey) {
            return new SortedAsMap(sortedMap().tailMap(fromKey));
        }

        SortedSet<K> sortedKeySet;

        // returns a SortedSet, even though returning a Set would be sufficient to
        // satisfy the SortedMap.keySet() interface
        @Override
        public SortedSet<K> keySet() {
            SortedSet<K> result = sortedKeySet;
            return (result == null) ? sortedKeySet = new SortedKeySet(sortedMap()) : result;
        }
    }

    // Comparison and hashing

    @Override
    public boolean equals(Object object) {
        if (object == this) {
            return true;
        }
        if (object instanceof Multimap<?, ?>) {
            Multimap<?, ?> that = (Multimap<?, ?>) object;
            return this.map.equals(that.asMap());
        }
        return false;
    }

    /**
     * Returns the hash code for this multimap.
     * <p/>
     * <p/>
     * The hash code of a multimap is defined as the hash code of the map view,
     * as returned by {@link Multimap#asMap}.
     *
     * @see Map#hashCode
     */
    @Override
    public int hashCode() {
        return map.hashCode();
    }

    /**
     * Returns a string representation of the multimap, generated by calling
     * {@code toString} on the map returned by {@link Multimap#asMap}.
     *
     * @return a string representation of the multimap
     */
    @Override
    public String toString() {
        return map.toString();
    }

    private static final long serialVersionUID = 2447537837011683357L;
}
