/*
 * Copyright (C) 2007 The Guava Authors
 *
 * 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 com.google.common.collect;

import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;
import static com.google.common.collect.CollectPreconditions.checkNonnegative;
import static com.google.common.collect.Hashing.closedTableSize;
import static com.google.common.collect.Hashing.smearedHash;
import static com.google.common.collect.Maps.capacity;
import static java.util.Objects.requireNonNull;

import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.annotations.J2ktIncompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.j2objc.annotations.WeakOuter;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.AbstractMap.SimpleImmutableEntry;
import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Set;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Consumer;
import org.jspecify.annotations.Nullable;

/**
 * Implementation of {@code Multimap} that does not allow duplicate key-value entries and that
 * returns collections whose iterators follow the ordering in which the data was added to the
 * multimap.
 *
 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code asMap} iterate through
 * the keys in the order they were first added to the multimap. Similarly, {@code get}, {@code
 * removeAll}, and {@code replaceValues} return collections that iterate through the values in the
 * order they were added. The collections generated by {@code entries} and {@code values} iterate
 * across the key-value mappings in the order they were added to the multimap.
 *
 * <p>The iteration ordering of the collections generated by {@code keySet}, {@code keys}, and
 * {@code asMap} has a few subtleties. As long as the set of keys remains unchanged, adding or
 * removing mappings does not affect the key iteration order. However, if you remove all values
 * associated with a key and then add the key back to the multimap, that key will come last in the
 * key iteration order.
 *
 * <p>The multimap does not store duplicate key-value pairs. Adding a new key-value pair equal to an
 * existing key-value pair has no effect.
 *
 * <p>Keys and values may be null. All optional multimap methods are supported, and all returned
 * views are modifiable.
 *
 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent
 * read operations will work correctly. To allow concurrent update operations, wrap your multimap
 * with a call to {@link Multimaps#synchronizedSetMultimap}.
 *
 * <p><b>Warning:</b> Do not modify either a key <i>or a value</i> of a {@code LinkedHashMultimap}
 * in a way that affects its {@link Object#equals} behavior. Undefined behavior and bugs will
 * result.
 *
 * <p>See the Guava User Guide article on <a href=
 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">{@code Multimap}</a>.
 *
 * @author Jared Levy
 * @author Louis Wasserman
 * @since 2.0
 */
@GwtCompatible
public final class LinkedHashMultimap<K extends @Nullable Object, V extends @Nullable Object>
    extends AbstractSetMultimap<K, V> {

  /** Creates a new, empty {@code LinkedHashMultimap} with the default initial capacities. */
  public static <K extends @Nullable Object, V extends @Nullable Object>
      LinkedHashMultimap<K, V> create() {
    return new LinkedHashMultimap<>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY);
  }

  /**
   * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold the specified
   * numbers of keys and values without rehashing.
   *
   * @param expectedKeys the expected number of distinct keys
   * @param expectedValuesPerKey the expected average number of values per key
   * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is
   *     negative
   */
  public static <K extends @Nullable Object, V extends @Nullable Object>
      LinkedHashMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) {
    return new LinkedHashMultimap<>(capacity(expectedKeys), capacity(expectedValuesPerKey));
  }

  /**
   * Constructs a {@code LinkedHashMultimap} with the same mappings as the specified multimap. If a
   * key-value mapping appears multiple times in the input multimap, it only appears once in the
   * constructed multimap. The new multimap has the same {@link Multimap#entries()} iteration order
   * as the input multimap, except for excluding duplicate mappings.
   *
   * @param multimap the multimap whose contents are copied to this multimap
   */
  public static <K extends @Nullable Object, V extends @Nullable Object>
      LinkedHashMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) {
    LinkedHashMultimap<K, V> result = create(multimap.keySet().size(), DEFAULT_VALUE_SET_CAPACITY);
    result.putAll(multimap);
    return result;
  }

  /**
   * LinkedHashMultimap entries are in no less than three coexisting linked lists: a bucket in the
   * hash table for a {@code Set<V>} associated with a key, the linked list of insertion-ordered
   * entries in that {@code Set<V>}, and the linked list of entries in the LinkedHashMultimap as a
   * whole.
   */
  @VisibleForTesting
  static final class ValueEntry<K extends @Nullable Object, V extends @Nullable Object>
      extends SimpleImmutableEntry<K, V> {
    final int smearedValueHash;

    @Nullable ValueEntry<K, V> nextInValueBucket;

    private @Nullable ValueEntry<K, V> predecessorInValueSet;
    private @Nullable ValueEntry<K, V> successorInValueSet;

    private @Nullable ValueEntry<K, V> predecessorInMultimap;
    private @Nullable ValueEntry<K, V> successorInMultimap;

    ValueEntry(
        @ParametricNullness K key,
        @ParametricNullness V value,
        int smearedValueHash,
        @Nullable ValueEntry<K, V> nextInValueBucket) {
      super(key, value);
      this.smearedValueHash = smearedValueHash;
      this.nextInValueBucket = nextInValueBucket;
    }

    boolean matchesValue(@Nullable Object v, int smearedVHash) {
      return smearedValueHash == smearedVHash && Objects.equals(getValue(), v);
    }
  }

  private static final int DEFAULT_KEY_CAPACITY = 16;
  private static final int DEFAULT_VALUE_SET_CAPACITY = 2;
  @VisibleForTesting static final double VALUE_SET_LOAD_FACTOR = 1.0;

  /**
   * Maximum allowed false positive probability of detecting a hash flooding attack given random
   * input.
   */
  @VisibleForTesting(
      )
  static final double HASH_FLOODING_FPP = 0.001;

  /**
   * Maximum allowed length of a hash table bucket before falling back to a j.u.HashMap-based
   * implementation. Experimentally determined.
   */
  private static final int MAX_HASH_BUCKET_LENGTH = 9;

  @VisibleForTesting transient int valueSetCapacity;
  private transient MultimapIterationChain<K, V> multimapIterationChain =
      new MultimapIterationChain<>();

  private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
    super(Platform.newLinkedHashMapWithExpectedSize(keyCapacity));
    checkNonnegative(valueSetCapacity, "expectedValuesPerKey");

    this.valueSetCapacity = valueSetCapacity;
  }

  /**
   * {@inheritDoc}
   *
   * <p>Creates an empty {@code LinkedHashSet} for a collection of values for one key.
   *
   * @return a new {@code LinkedHashSet} containing a collection of values for one key
   */
  @Override
  Set<V> createCollection() {
    return Platform.newLinkedHashSetWithExpectedSize(valueSetCapacity);
  }

  /**
   * {@inheritDoc}
   *
   * <p>Creates a decorated insertion-ordered set that also keeps track of the order in which
   * key-value pairs are added to the multimap.
   *
   * @param key key to associate with values in the collection
   * @return a new decorated set containing a collection of values for one key
   */
  @Override
  Collection<V> createCollection(@ParametricNullness K key) {
    return new ValueSet(key, valueSetCapacity);
  }

  /**
   * {@inheritDoc}
   *
   * <p>If {@code values} is not empty and the multimap already contains a mapping for {@code key},
   * the {@code keySet()} ordering is unchanged. However, the provided values always come last in
   * the {@link #entries()} and {@link #values()} iteration orderings.
   */
  @CanIgnoreReturnValue
  @Override
  public Set<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) {
    return super.replaceValues(key, values);
  }

  /**
   * Returns a set of all key-value pairs. Changes to the returned set will update the underlying
   * multimap, and vice versa. The entries set does not support the {@code add} or {@code addAll}
   * operations.
   *
   * <p>The iterator generated by the returned set traverses the entries in the order they were
   * added to the multimap.
   *
   * <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.
   */
  @Override
  public Set<Entry<K, V>> entries() {
    return super.entries();
  }

  /**
   * Returns a view collection of all <i>distinct</i> keys contained in this multimap. Note that the
   * key set contains a key if and only if this multimap maps that key to at least one value.
   *
   * <p>The iterator generated by the returned set traverses the keys in the order they were first
   * added to the multimap.
   *
   * <p>Changes to the returned set will update the underlying multimap, and vice versa. However,
   * <i>adding</i> to the returned set is not possible.
   */
  @Override
  public Set<K> keySet() {
    return super.keySet();
  }

  /**
   * Returns a collection of all values in the multimap. Changes to the returned collection will
   * update the underlying multimap, and vice versa.
   *
   * <p>The iterator generated by the returned collection traverses the values in the order they
   * were added to the multimap.
   */
  @Override
  public Collection<V> values() {
    return super.values();
  }

  @VisibleForTesting
  @WeakOuter
  final class ValueSet extends Sets.ImprovedAbstractSet<V> {
    /*
     * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
     * consumption.
     */

    @ParametricNullness private final K key;

    /*
     * Either a `@Nullable ValueEntry<K, V>[]` or, if hash flooding has been detected, a `Map<V,
     * ValueEntry<K, V>>`.
     */
    private Object hashTable;

    private int size = 0;
    private int modCount = 0;

    private @Nullable ValueEntry<K, V> firstEntry;
    private @Nullable ValueEntry<K, V> lastEntry;

    ValueSet(@ParametricNullness K key, int expectedValues) {
      this.key = key;
      // Round expected values up to a power of 2 to get the table size.
      int tableSize = closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR);

      @SuppressWarnings({"rawtypes", "unchecked"})
      @Nullable ValueEntry<K, V>[] hashTable = new @Nullable ValueEntry[tableSize];
      this.hashTable = hashTable;
    }

    // The only place we put a Map in is convertToHashFloodingResistantImplementation.
    @SuppressWarnings("unchecked")
    @VisibleForTesting
    @Nullable Map<V, ValueEntry<K, V>> delegateOrNull() {
      if (hashTable instanceof Map) {
        return (Map<V, ValueEntry<K, V>>) hashTable;
      }
      return null;
    }

    // The only places we put an array in are the constructor and rehashIfNecessary.
    @SuppressWarnings("unchecked")
    @VisibleForTesting
    @Nullable ValueEntry<K, V>[] hashTableArray() {
      return (@Nullable ValueEntry<K, V>[]) hashTable;
    }

    @VisibleForTesting
    void convertToHashFloodingResistantImplementation() {
      Map<V, ValueEntry<K, V>> newDelegate = new HashMap<>(hashTableArray().length, 1.0f);
      for (ValueEntry<K, V> entry = firstEntry; entry != null; entry = entry.successorInValueSet) {
        newDelegate.put(entry.getValue(), entry);
        entry.nextInValueBucket = null;
      }
      this.hashTable = newDelegate;
    }

    private void succeedsInValueSet(
        @Nullable ValueEntry<K, V> pred, @Nullable ValueEntry<K, V> succ) {
      if (pred == null) {
        firstEntry = succ;
      } else {
        pred.successorInValueSet = succ;
      }
      if (succ == null) {
        lastEntry = pred;
      } else {
        succ.predecessorInValueSet = pred;
      }
    }

    private void deleteEntryExceptFromHashTable(ValueEntry<K, V> entry) {
      succeedsInValueSet(entry.predecessorInValueSet, entry.successorInValueSet);
      multimapIterationChain.delete(entry);
      // TODO(cpovirk): See the TODO in clear() about clearing links from removed entries.
      size--;
      modCount++;
    }

    private ValueEntry<K, V> addEntryExceptToHashTable(
        @ParametricNullness V value,
        int smearedHash,
        @Nullable ValueEntry<K, V> nextInValueBucket) {
      ValueEntry<K, V> newEntry = new ValueEntry<>(key, value, smearedHash, nextInValueBucket);
      succeedsInValueSet(lastEntry, newEntry);
      lastEntry = newEntry;
      multimapIterationChain.append(newEntry);
      size++;
      modCount++;
      return newEntry;
    }

    @Override
    public Iterator<V> iterator() {
      return new Iterator<V>() {
        @Nullable ValueEntry<K, V> nextEntry = firstEntry;
        @Nullable ValueEntry<K, V> toRemove;
        int expectedModCount = modCount;

        void checkForComodification() {
          if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
          }
        }

        @Override
        public boolean hasNext() {
          checkForComodification();
          return nextEntry != null;
        }

        @Override
        @ParametricNullness
        public V next() {
          checkForComodification();
          ValueEntry<K, V> entry = nextEntry;
          if (entry == null) {
            throw new NoSuchElementException();
          }
          V result = entry.getValue();
          toRemove = entry;
          nextEntry = entry.successorInValueSet;
          return result;
        }

        @Override
        public void remove() {
          checkForComodification();
          checkState(toRemove != null, "no calls to next() since the last call to remove()");
          ValueSet.this.remove(toRemove.getValue());
          expectedModCount = modCount;
          toRemove = null;
        }
      };
    }

    @Override
    public void forEach(Consumer<? super V> action) {
      checkNotNull(action);
      for (ValueEntry<K, V> entry = firstEntry; entry != null; entry = entry.successorInValueSet) {
        action.accept(entry.getValue());
      }
    }

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

    @Override
    public boolean contains(@Nullable Object o) {
      Map<V, ValueEntry<K, V>> delegate = delegateOrNull();
      if (delegate != null) {
        return delegate.containsKey(o);
      }

      @Nullable ValueEntry<K, V>[] hashTable = hashTableArray();
      int smearedHash = smearedHash(o);
      for (ValueEntry<K, V> entry = hashTable[smearedHash & (hashTable.length - 1)];
          entry != null;
          entry = entry.nextInValueBucket) {
        if (entry.matchesValue(o, smearedHash)) {
          return true;
        }
      }
      return false;
    }

    @Override
    public boolean add(@ParametricNullness V value) {
      int smearedHash = smearedHash(value);

      Map<V, ValueEntry<K, V>> delegate = delegateOrNull();
      if (delegate != null) {
        if (delegate.containsKey(value)) {
          return false;
        }
        ValueEntry<K, V> newEntry =
            addEntryExceptToHashTable(value, smearedHash, /* nextInValueBucket= */ null);
        delegate.put(value, newEntry);
        return true;
      }

      @Nullable ValueEntry<K, V>[] hashTable = hashTableArray();
      int mask = hashTable.length - 1;
      int bucket = smearedHash & mask;
      ValueEntry<K, V> rowHead = hashTable[bucket];
      int bucketLength = 0;
      for (ValueEntry<K, V> entry = rowHead; entry != null; entry = entry.nextInValueBucket) {
        if (entry.matchesValue(value, smearedHash)) {
          return false;
        }
        bucketLength++;
      }

      hashTable[bucket] = addEntryExceptToHashTable(value, smearedHash, rowHead);
      if (bucketLength >= MAX_HASH_BUCKET_LENGTH) {
        convertToHashFloodingResistantImplementation();
      } else {
        rehashIfNecessary(hashTable);
      }
      return true;
    }

    private void rehashIfNecessary(@Nullable ValueEntry<K, V>[] oldHashTable) {
      if (Hashing.needsResizing(size, oldHashTable.length, VALUE_SET_LOAD_FACTOR)) {
        @SuppressWarnings("unchecked")
        @Nullable ValueEntry<K, V>[] hashTable =
            (@Nullable ValueEntry<K, V>[]) new ValueEntry<?, ?>[oldHashTable.length * 2];
        this.hashTable = hashTable;
        int mask = hashTable.length - 1;
        for (ValueEntry<K, V> entry = firstEntry;
            entry != null;
            entry = entry.successorInValueSet) {
          int bucket = entry.smearedValueHash & mask;
          entry.nextInValueBucket = hashTable[bucket];
          hashTable[bucket] = entry;
        }
      }
    }

    @CanIgnoreReturnValue
    @Override
    public boolean remove(@Nullable Object o) {
      Map<V, ValueEntry<K, V>> delegate = delegateOrNull();
      if (delegate != null) {
        ValueEntry<K, V> entry = delegate.remove(o);
        if (entry != null) {
          deleteEntryExceptFromHashTable(entry);
          return true;
        }
        return false;
      }

      @Nullable ValueEntry<K, V>[] hashTable = hashTableArray();
      int smearedHash = smearedHash(o);
      int bucket = smearedHash & (hashTable.length - 1);
      ValueEntry<K, V> prev = null;
      for (ValueEntry<K, V> entry = hashTable[bucket];
          entry != null;
          prev = entry, entry = entry.nextInValueBucket) {
        if (entry.matchesValue(o, smearedHash)) {
          if (prev == null) {
            // first entry in the bucket
            hashTable[bucket] = entry.nextInValueBucket;
          } else {
            prev.nextInValueBucket = entry.nextInValueBucket;
          }
          deleteEntryExceptFromHashTable(entry);
          return true;
        }
      }
      return false;
    }

    @Override
    public void clear() {
      Map<V, ValueEntry<K, V>> delegate = delegateOrNull();
      if (delegate != null) {
        delegate.clear();
      } else {
        Arrays.fill(hashTableArray(), null);
      }
      size = 0;
      for (ValueEntry<K, V> entry = firstEntry; entry != null; entry = entry.successorInValueSet) {
        multimapIterationChain.delete(entry);
        /*
         * TODO(cpovirk): Also clear *InValueSet (after reading next), *InMultimap, and
         * nextInValueBucket (both here and in remove)? Because entryIterator() returns ValueEntry
         * instances directly to callers of entries(), a caller that retains a removed Entry can
         * otherwise keep the rest of the multimap's entries alive through those links (similar to
         * what cl/846336997 fixed for HashBiMap). However, entryIterator() does not currently check
         * for concurrent modification, so clearing successorInMultimap on removal could cause an
         * in-progress entryIterator() to stop early if its nextEntry is removed externally.
         */
      }
      firstEntry = null;
      lastEntry = null;
      modCount++;
    }
  }

  @Override
  Iterator<Entry<K, V>> entryIterator() {
    return new Iterator<Entry<K, V>>() {
      @Nullable ValueEntry<K, V> nextEntry = multimapIterationChain.firstEntry;
      @Nullable ValueEntry<K, V> toRemove;

      @Override
      public boolean hasNext() {
        return nextEntry != null;
      }

      @Override
      public Entry<K, V> next() {
        ValueEntry<K, V> entry = nextEntry;
        if (entry == null) {
          throw new NoSuchElementException();
        }
        toRemove = entry;
        nextEntry = entry.successorInMultimap;
        return entry;
      }

      @Override
      public void remove() {
        checkState(toRemove != null, "no calls to next() since the last call to remove()");
        LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
        toRemove = null;
      }
    };
  }

  @Override
  Spliterator<Entry<K, V>> entrySpliterator() {
    return Spliterators.spliterator(
        entries(), Spliterator.DISTINCT | Spliterator.ORDERED | Spliterator.NONNULL);
  }

  @Override
  Iterator<V> valueIterator() {
    return Maps.valueIterator(entryIterator());
  }

  @Override
  Spliterator<V> valueSpliterator() {
    return CollectSpliterators.map(entrySpliterator(), Spliterator.ORDERED, Entry::getValue);
  }

  /**
   * @serialData the expected values per key, the number of distinct keys, the number of entries,
   *     and the entries in order
   */
  @GwtIncompatible
  @J2ktIncompatible
    private void writeObject(ObjectOutputStream stream) throws IOException {
    stream.defaultWriteObject();
    stream.writeInt(keySet().size());
    for (K key : keySet()) {
      stream.writeObject(key);
    }
    stream.writeInt(size());
    for (Entry<K, V> entry : entries()) {
      stream.writeObject(entry.getKey());
      stream.writeObject(entry.getValue());
    }
  }

  @GwtIncompatible
  @J2ktIncompatible
    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
    stream.defaultReadObject();
    multimapIterationChain = new MultimapIterationChain<>();
    valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
    int distinctKeys = stream.readInt();
    Map<K, Collection<V>> map = Platform.newLinkedHashMapWithExpectedSize(12);
    for (int i = 0; i < distinctKeys; i++) {
      @SuppressWarnings("unchecked")
      K key = (K) stream.readObject();
      map.put(key, createCollection(key));
    }
    int entries = stream.readInt();
    for (int i = 0; i < entries; i++) {
      @SuppressWarnings("unchecked")
      K key = (K) stream.readObject();
      @SuppressWarnings("unchecked")
      V value = (V) stream.readObject();
      /*
       * requireNonNull is safe for a properly serialized multimap: We've already inserted a
       * collection for each key that we expect.
       */
      requireNonNull(map.get(key)).add(value);
    }
    setMap(map);
  }

  private static final class MultimapIterationChain<
      K extends @Nullable Object, V extends @Nullable Object> {
    @Nullable ValueEntry<K, V> firstEntry;
    @Nullable ValueEntry<K, V> lastEntry;

    void succeeds(@Nullable ValueEntry<K, V> pred, @Nullable ValueEntry<K, V> succ) {
      if (pred == null) {
        firstEntry = succ;
      } else {
        pred.successorInMultimap = succ;
      }
      if (succ == null) {
        lastEntry = pred;
      } else {
        succ.predecessorInMultimap = pred;
      }
    }

    void delete(ValueEntry<K, V> entry) {
      succeeds(entry.predecessorInMultimap, entry.successorInMultimap);
    }

    void append(ValueEntry<K, V> newEntry) {
      succeeds(lastEntry, newEntry);
      lastEntry = newEntry;
    }
  }

  @GwtIncompatible @J2ktIncompatible private static final long serialVersionUID = 1;
}