guava-gwt/src-super/com/google/common/collect/super/com/google/common/collect/LinkedHashMultimap.java - platform/external/guava - Git at Google

 /*
  * 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.collect.CollectPreconditions.checkNonnegative;
 import static com.google.common.collect.CollectPreconditions.checkRemove;

 import com.google.common.annotations.GwtCompatible;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Objects;

 import java.util.Arrays;
 import java.util.Collection;
 import java.util.ConcurrentModificationException;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
 import java.util.Map;
 import java.util.NoSuchElementException;
 import java.util.Set;

 import javax.annotation.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>See the Guava User Guide article on <a href=
  * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
  * {@code Multimap}</a>.
  *
  * @author Jared Levy
  * @author Louis Wasserman
  * @since 2.0 (imported from Google Collections Library)
  */
 @GwtCompatible(serializable = true, emulated = true)
 public final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> {

   /**
    * Creates a new, empty {@code LinkedHashMultimap} with the default initial
    * capacities.
    */
   public static <K, V> LinkedHashMultimap<K, V> create() {
     return new LinkedHashMultimap<K, V>(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, V> LinkedHashMultimap<K, V> create(
       int expectedKeys, int expectedValuesPerKey) {
     return new LinkedHashMultimap<K, V>(
         Maps.capacity(expectedKeys),
         Maps.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, V> 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;
   }

   private interface ValueSetLink<K, V> {
     ValueSetLink<K, V> getPredecessorInValueSet();
     ValueSetLink<K, V> getSuccessorInValueSet();

     void setPredecessorInValueSet(ValueSetLink<K, V> entry);
     void setSuccessorInValueSet(ValueSetLink<K, V> entry);
   }

   private static <K, V> void succeedsInValueSet(ValueSetLink<K, V> pred, ValueSetLink<K, V> succ) {
     pred.setSuccessorInValueSet(succ);
     succ.setPredecessorInValueSet(pred);
   }

   private static <K, V> void succeedsInMultimap(
       ValueEntry<K, V> pred, ValueEntry<K, V> succ) {
     pred.setSuccessorInMultimap(succ);
     succ.setPredecessorInMultimap(pred);
   }

   private static <K, V> void deleteFromValueSet(ValueSetLink<K, V> entry) {
     succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet());
   }

   private static <K, V> void deleteFromMultimap(ValueEntry<K, V> entry) {
     succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap());
   }

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

     @Nullable ValueEntry<K, V> nextInValueBucket;

     ValueSetLink<K, V> predecessorInValueSet;
     ValueSetLink<K, V> successorInValueSet;

     ValueEntry<K, V> predecessorInMultimap;
     ValueEntry<K, V> successorInMultimap;

     ValueEntry(@Nullable K key, @Nullable 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.equal(getValue(), v);
     }

     @Override
     public ValueSetLink<K, V> getPredecessorInValueSet() {
       return predecessorInValueSet;
     }

     @Override
     public ValueSetLink<K, V> getSuccessorInValueSet() {
       return successorInValueSet;
     }

     @Override
     public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
       predecessorInValueSet = entry;
     }

     @Override
     public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
       successorInValueSet = entry;
     }

     public ValueEntry<K, V> getPredecessorInMultimap() {
       return predecessorInMultimap;
     }

     public ValueEntry<K, V> getSuccessorInMultimap() {
       return successorInMultimap;
     }

     public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) {
       this.successorInMultimap = multimapSuccessor;
     }

     public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) {
       this.predecessorInMultimap = multimapPredecessor;
     }
   }

   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;

   @VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
   private transient ValueEntry<K, V> multimapHeaderEntry;

   private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
     super(new LinkedHashMap<K, Collection<V>>(keyCapacity));
     checkNonnegative(valueSetCapacity, "expectedValuesPerKey");

     this.valueSetCapacity = valueSetCapacity;
     this.multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
     succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
   }

   /**
    * {@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 new LinkedHashSet<V>(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(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.
    */
   @Override
   public Set<V> replaceValues(@Nullable 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<Map.Entry<K, V>> entries() {
     return super.entries();
   }

   /**
    * 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
   final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
     /*
      * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
      * consumption.
      */

     private final K key;
     @VisibleForTesting ValueEntry<K, V>[] hashTable;
     private int size = 0;
     private int modCount = 0;

     // We use the set object itself as the end of the linked list, avoiding an unnecessary
     // entry object per key.
     private ValueSetLink<K, V> firstEntry;
     private ValueSetLink<K, V> lastEntry;

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

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

     private int mask() {
       return hashTable.length - 1;
     }

     @Override
     public ValueSetLink<K, V> getPredecessorInValueSet() {
       return lastEntry;
     }

     @Override
     public ValueSetLink<K, V> getSuccessorInValueSet() {
       return firstEntry;
     }

     @Override
     public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
       lastEntry = entry;
     }

     @Override
     public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
       firstEntry = entry;
     }

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

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

         @Override
         public boolean hasNext() {
           checkForComodification();
           return nextEntry != ValueSet.this;
         }

         @Override
         public V next() {
           if (!hasNext()) {
             throw new NoSuchElementException();
           }
           ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
           V result = entry.getValue();
           toRemove = entry;
           nextEntry = entry.getSuccessorInValueSet();
           return result;
         }

         @Override
         public void remove() {
           checkForComodification();
           checkRemove(toRemove != null);
           ValueSet.this.remove(toRemove.getValue());
           expectedModCount = modCount;
           toRemove = null;
         }
       };
     }

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

     @Override
     public boolean contains(@Nullable Object o) {
       int smearedHash = Hashing.smearedHash(o);
       for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()]; entry != null;
           entry = entry.nextInValueBucket) {
         if (entry.matchesValue(o, smearedHash)) {
           return true;
         }
       }
       return false;
     }

     @Override
     public boolean add(@Nullable V value) {
       int smearedHash = Hashing.smearedHash(value);
       int bucket = smearedHash & mask();
       ValueEntry<K, V> rowHead = hashTable[bucket];
       for (ValueEntry<K, V> entry = rowHead; entry != null;
           entry = entry.nextInValueBucket) {
         if (entry.matchesValue(value, smearedHash)) {
           return false;
         }
       }

       ValueEntry<K, V> newEntry = new ValueEntry<K, V>(key, value, smearedHash, rowHead);
       succeedsInValueSet(lastEntry, newEntry);
       succeedsInValueSet(newEntry, this);
       succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
       succeedsInMultimap(newEntry, multimapHeaderEntry);
       hashTable[bucket] = newEntry;
       size++;
       modCount++;
       rehashIfNecessary();
       return true;
     }

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

     @Override
     public boolean remove(@Nullable Object o) {
       int smearedHash = Hashing.smearedHash(o);
       int bucket = smearedHash & mask();
       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;
           }
           deleteFromValueSet(entry);
           deleteFromMultimap(entry);
           size--;
           modCount++;
           return true;
         }
       }
       return false;
     }

     @Override
     public void clear() {
       Arrays.fill(hashTable, null);
       size = 0;
       for (ValueSetLink<K, V> entry = firstEntry;
            entry != this; entry = entry.getSuccessorInValueSet()) {
         ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
         deleteFromMultimap(valueEntry);
       }
       succeedsInValueSet(this, this);
       modCount++;
     }
   }

   @Override
   Iterator<Map.Entry<K, V>> entryIterator() {
     return new Iterator<Map.Entry<K, V>>() {
       ValueEntry<K, V> nextEntry = multimapHeaderEntry.successorInMultimap;
       ValueEntry<K, V> toRemove;

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

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

       @Override
       public void remove() {
         checkRemove(toRemove != null);
         LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
         toRemove = null;
       }
     };
   }

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

   @Override
   public void clear() {
     super.clear();
     succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
   }
 }
	/*
	* 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.collect.CollectPreconditions.checkNonnegative;
	import static com.google.common.collect.CollectPreconditions.checkRemove;

	import com.google.common.annotations.GwtCompatible;
	import com.google.common.annotations.VisibleForTesting;
	import com.google.common.base.Objects;

	import java.util.Arrays;
	import java.util.Collection;
	import java.util.ConcurrentModificationException;
	import java.util.Iterator;
	import java.util.LinkedHashMap;
	import java.util.LinkedHashSet;
	import java.util.Map;
	import java.util.NoSuchElementException;
	import java.util.Set;

	import javax.annotation.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>See the Guava User Guide article on <a href=
	* "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
	* {@code Multimap}</a>.
	*
	* @author Jared Levy
	* @author Louis Wasserman
	* @since 2.0 (imported from Google Collections Library)
	*/
	@GwtCompatible(serializable = true, emulated = true)
	public final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> {

	/**
	* Creates a new, empty {@code LinkedHashMultimap} with the default initial
	* capacities.
	*/
	public static <K, V> LinkedHashMultimap<K, V> create() {
	return new LinkedHashMultimap<K, V>(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, V> LinkedHashMultimap<K, V> create(
	int expectedKeys, int expectedValuesPerKey) {
	return new LinkedHashMultimap<K, V>(
	Maps.capacity(expectedKeys),
	Maps.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, V> 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;
	}

	private interface ValueSetLink<K, V> {
	ValueSetLink<K, V> getPredecessorInValueSet();
	ValueSetLink<K, V> getSuccessorInValueSet();

	void setPredecessorInValueSet(ValueSetLink<K, V> entry);
	void setSuccessorInValueSet(ValueSetLink<K, V> entry);
	}

	private static <K, V> void succeedsInValueSet(ValueSetLink<K, V> pred, ValueSetLink<K, V> succ) {
	pred.setSuccessorInValueSet(succ);
	succ.setPredecessorInValueSet(pred);
	}

	private static <K, V> void succeedsInMultimap(
	ValueEntry<K, V> pred, ValueEntry<K, V> succ) {
	pred.setSuccessorInMultimap(succ);
	succ.setPredecessorInMultimap(pred);
	}

	private static <K, V> void deleteFromValueSet(ValueSetLink<K, V> entry) {
	succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet());
	}

	private static <K, V> void deleteFromMultimap(ValueEntry<K, V> entry) {
	succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap());
	}

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

	@Nullable ValueEntry<K, V> nextInValueBucket;

	ValueSetLink<K, V> predecessorInValueSet;
	ValueSetLink<K, V> successorInValueSet;

	ValueEntry<K, V> predecessorInMultimap;
	ValueEntry<K, V> successorInMultimap;

	ValueEntry(@Nullable K key, @Nullable 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.equal(getValue(), v);
	}

	@Override
	public ValueSetLink<K, V> getPredecessorInValueSet() {
	return predecessorInValueSet;
	}

	@Override
	public ValueSetLink<K, V> getSuccessorInValueSet() {
	return successorInValueSet;
	}

	@Override
	public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
	predecessorInValueSet = entry;
	}

	@Override
	public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
	successorInValueSet = entry;
	}

	public ValueEntry<K, V> getPredecessorInMultimap() {
	return predecessorInMultimap;
	}

	public ValueEntry<K, V> getSuccessorInMultimap() {
	return successorInMultimap;
	}

	public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) {
	this.successorInMultimap = multimapSuccessor;
	}

	public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) {
	this.predecessorInMultimap = multimapPredecessor;
	}
	}

	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;

	@VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
	private transient ValueEntry<K, V> multimapHeaderEntry;

	private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
	super(new LinkedHashMap<K, Collection<V>>(keyCapacity));
	checkNonnegative(valueSetCapacity, "expectedValuesPerKey");

	this.valueSetCapacity = valueSetCapacity;
	this.multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
	succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
	}

	/**
	* {@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 new LinkedHashSet<V>(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(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.
	*/
	@Override
	public Set<V> replaceValues(@Nullable 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<Map.Entry<K, V>> entries() {
	return super.entries();
	}

	/**
	* 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
	final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
	/*
	* We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
	* consumption.
	*/

	private final K key;
	@VisibleForTesting ValueEntry<K, V>[] hashTable;
	private int size = 0;
	private int modCount = 0;

	// We use the set object itself as the end of the linked list, avoiding an unnecessary
	// entry object per key.
	private ValueSetLink<K, V> firstEntry;
	private ValueSetLink<K, V> lastEntry;

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

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

	private int mask() {
	return hashTable.length - 1;
	}

	@Override
	public ValueSetLink<K, V> getPredecessorInValueSet() {
	return lastEntry;
	}

	@Override
	public ValueSetLink<K, V> getSuccessorInValueSet() {
	return firstEntry;
	}

	@Override
	public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
	lastEntry = entry;
	}

	@Override
	public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
	firstEntry = entry;
	}

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

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

	@Override
	public boolean hasNext() {
	checkForComodification();
	return nextEntry != ValueSet.this;
	}

	@Override
	public V next() {
	if (!hasNext()) {
	throw new NoSuchElementException();
	}
	ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
	V result = entry.getValue();
	toRemove = entry;
	nextEntry = entry.getSuccessorInValueSet();
	return result;
	}

	@Override
	public void remove() {
	checkForComodification();
	checkRemove(toRemove != null);
	ValueSet.this.remove(toRemove.getValue());
	expectedModCount = modCount;
	toRemove = null;
	}
	};
	}

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

	@Override
	public boolean contains(@Nullable Object o) {
	int smearedHash = Hashing.smearedHash(o);
	for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()]; entry != null;
	entry = entry.nextInValueBucket) {
	if (entry.matchesValue(o, smearedHash)) {
	return true;
	}
	}
	return false;
	}

	@Override
	public boolean add(@Nullable V value) {
	int smearedHash = Hashing.smearedHash(value);
	int bucket = smearedHash & mask();
	ValueEntry<K, V> rowHead = hashTable[bucket];
	for (ValueEntry<K, V> entry = rowHead; entry != null;
	entry = entry.nextInValueBucket) {
	if (entry.matchesValue(value, smearedHash)) {
	return false;
	}
	}

	ValueEntry<K, V> newEntry = new ValueEntry<K, V>(key, value, smearedHash, rowHead);
	succeedsInValueSet(lastEntry, newEntry);
	succeedsInValueSet(newEntry, this);
	succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
	succeedsInMultimap(newEntry, multimapHeaderEntry);
	hashTable[bucket] = newEntry;
	size++;
	modCount++;
	rehashIfNecessary();
	return true;
	}

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

	@Override
	public boolean remove(@Nullable Object o) {
	int smearedHash = Hashing.smearedHash(o);
	int bucket = smearedHash & mask();
	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;
	}
	deleteFromValueSet(entry);
	deleteFromMultimap(entry);
	size--;
	modCount++;
	return true;
	}
	}
	return false;
	}

	@Override
	public void clear() {
	Arrays.fill(hashTable, null);
	size = 0;
	for (ValueSetLink<K, V> entry = firstEntry;
	entry != this; entry = entry.getSuccessorInValueSet()) {
	ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
	deleteFromMultimap(valueEntry);
	}
	succeedsInValueSet(this, this);
	modCount++;
	}
	}

	@Override
	Iterator<Map.Entry<K, V>> entryIterator() {
	return new Iterator<Map.Entry<K, V>>() {
	ValueEntry<K, V> nextEntry = multimapHeaderEntry.successorInMultimap;
	ValueEntry<K, V> toRemove;

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

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

	@Override
	public void remove() {
	checkRemove(toRemove != null);
	LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
	toRemove = null;
	}
	};
	}

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

	@Override
	public void clear() {
	super.clear();
	succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
	}
	}