guava/src/com/google/common/collect/RegularImmutableBiMap.java - platform/external/guava - Git at Google

 /*
  * Copyright (C) 2008 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.checkPositionIndex;
 import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
 import static com.google.common.collect.ImmutableMapEntry.createEntryArray;
 import static com.google.common.collect.RegularImmutableMap.checkNoConflictInKeyBucket;
 import static java.util.Objects.requireNonNull;

 import com.google.common.annotations.GwtCompatible;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.collect.ImmutableMapEntry.NonTerminalImmutableBiMapEntry;
 import com.google.errorprone.annotations.CanIgnoreReturnValue;
 import com.google.errorprone.annotations.concurrent.LazyInit;
 import com.google.j2objc.annotations.RetainedWith;
 import java.io.Serializable;
 import java.util.function.BiConsumer;
 import java.util.function.Consumer;
 import javax.annotation.CheckForNull;
 import org.checkerframework.checker.nullness.qual.Nullable;

 /**
  * Bimap with zero or more mappings.
  *
  * @author Louis Wasserman
  */
 @GwtCompatible(serializable = true, emulated = true)
 @SuppressWarnings("serial") // uses writeReplace(), not default serialization
 @ElementTypesAreNonnullByDefault
 class RegularImmutableBiMap<K, V> extends ImmutableBiMap<K, V> {
   static final RegularImmutableBiMap<Object, Object> EMPTY =
       new RegularImmutableBiMap<>(
           null, null, (Entry<Object, Object>[]) ImmutableMap.EMPTY_ENTRY_ARRAY, 0, 0);

   static final double MAX_LOAD_FACTOR = 1.2;

   @CheckForNull private final transient @Nullable ImmutableMapEntry<K, V>[] keyTable;
   @CheckForNull private final transient @Nullable ImmutableMapEntry<K, V>[] valueTable;
   @VisibleForTesting final transient Entry<K, V>[] entries;
   private final transient int mask;
   private final transient int hashCode;

   static <K, V> ImmutableBiMap<K, V> fromEntries(Entry<K, V>... entries) {
     return fromEntryArray(entries.length, entries);
   }

   static <K, V> ImmutableBiMap<K, V> fromEntryArray(int n, @Nullable Entry<K, V>[] entryArray) {
     checkPositionIndex(n, entryArray.length);
     int tableSize = Hashing.closedTableSize(n, MAX_LOAD_FACTOR);
     int mask = tableSize - 1;
     @Nullable ImmutableMapEntry<K, V>[] keyTable = createEntryArray(tableSize);
     @Nullable ImmutableMapEntry<K, V>[] valueTable = createEntryArray(tableSize);
     /*
      * The cast is safe: n==entryArray.length means that we have filled the whole array with Entry
      * instances, in which case it is safe to cast it from an array of nullable entries to an array
      * of non-null entries.
      */
     @SuppressWarnings("nullness")
     Entry<K, V>[] entries =
         (n == entryArray.length) ? (Entry<K, V>[]) entryArray : createEntryArray(n);
     int hashCode = 0;

     for (int i = 0; i < n; i++) {
       // requireNonNull is safe because the first `n` elements have been filled in.
       Entry<K, V> entry = requireNonNull(entryArray[i]);
       K key = entry.getKey();
       V value = entry.getValue();
       checkEntryNotNull(key, value);
       int keyHash = key.hashCode();
       int valueHash = value.hashCode();
       int keyBucket = Hashing.smear(keyHash) & mask;
       int valueBucket = Hashing.smear(valueHash) & mask;

       ImmutableMapEntry<K, V> nextInKeyBucket = keyTable[keyBucket];
       int keyBucketLength = checkNoConflictInKeyBucket(key, entry, nextInKeyBucket);
       ImmutableMapEntry<K, V> nextInValueBucket = valueTable[valueBucket];
       int valueBucketLength = checkNoConflictInValueBucket(value, entry, nextInValueBucket);
       if (keyBucketLength > RegularImmutableMap.MAX_HASH_BUCKET_LENGTH
           || valueBucketLength > RegularImmutableMap.MAX_HASH_BUCKET_LENGTH) {
         return JdkBackedImmutableBiMap.create(n, entryArray);
       }
       ImmutableMapEntry<K, V> newEntry =
           (nextInValueBucket == null && nextInKeyBucket == null)
               ? RegularImmutableMap.makeImmutable(entry, key, value)
               : new NonTerminalImmutableBiMapEntry<>(
                   key, value, nextInKeyBucket, nextInValueBucket);
       keyTable[keyBucket] = newEntry;
       valueTable[valueBucket] = newEntry;
       entries[i] = newEntry;
       hashCode += keyHash ^ valueHash;
     }
     return new RegularImmutableBiMap<>(keyTable, valueTable, entries, mask, hashCode);
   }

   private RegularImmutableBiMap(
       @CheckForNull @Nullable ImmutableMapEntry<K, V>[] keyTable,
       @CheckForNull @Nullable ImmutableMapEntry<K, V>[] valueTable,
       Entry<K, V>[] entries,
       int mask,
       int hashCode) {
     this.keyTable = keyTable;
     this.valueTable = valueTable;
     this.entries = entries;
     this.mask = mask;
     this.hashCode = hashCode;
   }

   // checkNoConflictInKeyBucket is static imported from RegularImmutableMap

   /**
    * @return number of entries in this bucket
    * @throws IllegalArgumentException if another entry in the bucket has the same key
    */
   @CanIgnoreReturnValue
   private static int checkNoConflictInValueBucket(
       Object value, Entry<?, ?> entry, @CheckForNull ImmutableMapEntry<?, ?> valueBucketHead) {
     int bucketSize = 0;
     for (; valueBucketHead != null; valueBucketHead = valueBucketHead.getNextInValueBucket()) {
       checkNoConflict(!value.equals(valueBucketHead.getValue()), "value", entry, valueBucketHead);
       bucketSize++;
     }
     return bucketSize;
   }

   @Override
   @CheckForNull
   public V get(@CheckForNull Object key) {
     return RegularImmutableMap.get(key, keyTable, mask);
   }

   @Override
   ImmutableSet<Entry<K, V>> createEntrySet() {
     return isEmpty()
         ? ImmutableSet.<Entry<K, V>>of()
         : new ImmutableMapEntrySet.RegularEntrySet<K, V>(this, entries);
   }

   @Override
   ImmutableSet<K> createKeySet() {
     return new ImmutableMapKeySet<>(this);
   }

   @Override
   public void forEach(BiConsumer<? super K, ? super V> action) {
     checkNotNull(action);
     for (Entry<K, V> entry : entries) {
       action.accept(entry.getKey(), entry.getValue());
     }
   }

   @Override
   boolean isHashCodeFast() {
     return true;
   }

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

   @Override
   boolean isPartialView() {
     return false;
   }

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

   @LazyInit @RetainedWith @CheckForNull private transient ImmutableBiMap<V, K> inverse;

   @Override
   public ImmutableBiMap<V, K> inverse() {
     if (isEmpty()) {
       return ImmutableBiMap.of();
     }
     ImmutableBiMap<V, K> result = inverse;
     return (result == null) ? inverse = new Inverse() : result;
   }

   private final class Inverse extends ImmutableBiMap<V, K> {

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

     @Override
     public ImmutableBiMap<K, V> inverse() {
       return RegularImmutableBiMap.this;
     }

     @Override
     public void forEach(BiConsumer<? super V, ? super K> action) {
       checkNotNull(action);
       RegularImmutableBiMap.this.forEach((k, v) -> action.accept(v, k));
     }

     @Override
     @CheckForNull
     public K get(@CheckForNull Object value) {
       if (value == null || valueTable == null) {
         return null;
       }
       int bucket = Hashing.smear(value.hashCode()) & mask;
       for (ImmutableMapEntry<K, V> entry = valueTable[bucket];
           entry != null;
           entry = entry.getNextInValueBucket()) {
         if (value.equals(entry.getValue())) {
           return entry.getKey();
         }
       }
       return null;
     }

     @Override
     ImmutableSet<V> createKeySet() {
       return new ImmutableMapKeySet<>(this);
     }

     @Override
     ImmutableSet<Entry<V, K>> createEntrySet() {
       return new InverseEntrySet();
     }

     final class InverseEntrySet extends ImmutableMapEntrySet<V, K> {
       @Override
       ImmutableMap<V, K> map() {
         return Inverse.this;
       }

       @Override
       boolean isHashCodeFast() {
         return true;
       }

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

       @Override
       public UnmodifiableIterator<Entry<V, K>> iterator() {
         return asList().iterator();
       }

       @Override
       public void forEach(Consumer<? super Entry<V, K>> action) {
         asList().forEach(action);
       }

       @Override
       ImmutableList<Entry<V, K>> createAsList() {
         return new ImmutableAsList<Entry<V, K>>() {
           @Override
           public Entry<V, K> get(int index) {
             Entry<K, V> entry = entries[index];
             return Maps.immutableEntry(entry.getValue(), entry.getKey());
           }

           @Override
           ImmutableCollection<Entry<V, K>> delegateCollection() {
             return InverseEntrySet.this;
           }
         };
       }
     }

     @Override
     boolean isPartialView() {
       return false;
     }

     @Override
     Object writeReplace() {
       return new InverseSerializedForm<>(RegularImmutableBiMap.this);
     }
   }

   private static class InverseSerializedForm<K, V> implements Serializable {
     private final ImmutableBiMap<K, V> forward;

     InverseSerializedForm(ImmutableBiMap<K, V> forward) {
       this.forward = forward;
     }

     Object readResolve() {
       return forward.inverse();
     }

     private static final long serialVersionUID = 1;
   }
 }
	/*
	* Copyright (C) 2008 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.checkPositionIndex;
	import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
	import static com.google.common.collect.ImmutableMapEntry.createEntryArray;
	import static com.google.common.collect.RegularImmutableMap.checkNoConflictInKeyBucket;
	import static java.util.Objects.requireNonNull;

	import com.google.common.annotations.GwtCompatible;
	import com.google.common.annotations.VisibleForTesting;
	import com.google.common.collect.ImmutableMapEntry.NonTerminalImmutableBiMapEntry;
	import com.google.errorprone.annotations.CanIgnoreReturnValue;
	import com.google.errorprone.annotations.concurrent.LazyInit;
	import com.google.j2objc.annotations.RetainedWith;
	import java.io.Serializable;
	import java.util.function.BiConsumer;
	import java.util.function.Consumer;
	import javax.annotation.CheckForNull;
	import org.checkerframework.checker.nullness.qual.Nullable;

	/**
	* Bimap with zero or more mappings.
	*
	* @author Louis Wasserman
	*/
	@GwtCompatible(serializable = true, emulated = true)
	@SuppressWarnings("serial") // uses writeReplace(), not default serialization
	@ElementTypesAreNonnullByDefault
	class RegularImmutableBiMap<K, V> extends ImmutableBiMap<K, V> {
	static final RegularImmutableBiMap<Object, Object> EMPTY =
	new RegularImmutableBiMap<>(
	null, null, (Entry<Object, Object>[]) ImmutableMap.EMPTY_ENTRY_ARRAY, 0, 0);

	static final double MAX_LOAD_FACTOR = 1.2;

	@CheckForNull private final transient @Nullable ImmutableMapEntry<K, V>[] keyTable;
	@CheckForNull private final transient @Nullable ImmutableMapEntry<K, V>[] valueTable;
	@VisibleForTesting final transient Entry<K, V>[] entries;
	private final transient int mask;
	private final transient int hashCode;

	static <K, V> ImmutableBiMap<K, V> fromEntries(Entry<K, V>... entries) {
	return fromEntryArray(entries.length, entries);
	}

	static <K, V> ImmutableBiMap<K, V> fromEntryArray(int n, @Nullable Entry<K, V>[] entryArray) {
	checkPositionIndex(n, entryArray.length);
	int tableSize = Hashing.closedTableSize(n, MAX_LOAD_FACTOR);
	int mask = tableSize - 1;
	@Nullable ImmutableMapEntry<K, V>[] keyTable = createEntryArray(tableSize);
	@Nullable ImmutableMapEntry<K, V>[] valueTable = createEntryArray(tableSize);
	/*
	* The cast is safe: n==entryArray.length means that we have filled the whole array with Entry
	* instances, in which case it is safe to cast it from an array of nullable entries to an array
	* of non-null entries.
	*/
	@SuppressWarnings("nullness")
	Entry<K, V>[] entries =
	(n == entryArray.length) ? (Entry<K, V>[]) entryArray : createEntryArray(n);
	int hashCode = 0;

	for (int i = 0; i < n; i++) {
	// requireNonNull is safe because the first `n` elements have been filled in.
	Entry<K, V> entry = requireNonNull(entryArray[i]);
	K key = entry.getKey();
	V value = entry.getValue();
	checkEntryNotNull(key, value);
	int keyHash = key.hashCode();
	int valueHash = value.hashCode();
	int keyBucket = Hashing.smear(keyHash) & mask;
	int valueBucket = Hashing.smear(valueHash) & mask;

	ImmutableMapEntry<K, V> nextInKeyBucket = keyTable[keyBucket];
	int keyBucketLength = checkNoConflictInKeyBucket(key, entry, nextInKeyBucket);
	ImmutableMapEntry<K, V> nextInValueBucket = valueTable[valueBucket];
	int valueBucketLength = checkNoConflictInValueBucket(value, entry, nextInValueBucket);
	if (keyBucketLength > RegularImmutableMap.MAX_HASH_BUCKET_LENGTH
	\|\| valueBucketLength > RegularImmutableMap.MAX_HASH_BUCKET_LENGTH) {
	return JdkBackedImmutableBiMap.create(n, entryArray);
	}
	ImmutableMapEntry<K, V> newEntry =
	(nextInValueBucket == null && nextInKeyBucket == null)
	? RegularImmutableMap.makeImmutable(entry, key, value)
	: new NonTerminalImmutableBiMapEntry<>(
	key, value, nextInKeyBucket, nextInValueBucket);
	keyTable[keyBucket] = newEntry;
	valueTable[valueBucket] = newEntry;
	entries[i] = newEntry;
	hashCode += keyHash ^ valueHash;
	}
	return new RegularImmutableBiMap<>(keyTable, valueTable, entries, mask, hashCode);
	}

	private RegularImmutableBiMap(
	@CheckForNull @Nullable ImmutableMapEntry<K, V>[] keyTable,
	@CheckForNull @Nullable ImmutableMapEntry<K, V>[] valueTable,
	Entry<K, V>[] entries,
	int mask,
	int hashCode) {
	this.keyTable = keyTable;
	this.valueTable = valueTable;
	this.entries = entries;
	this.mask = mask;
	this.hashCode = hashCode;
	}

	// checkNoConflictInKeyBucket is static imported from RegularImmutableMap

	/**
	* @return number of entries in this bucket
	* @throws IllegalArgumentException if another entry in the bucket has the same key
	*/
	@CanIgnoreReturnValue
	private static int checkNoConflictInValueBucket(
	Object value, Entry<?, ?> entry, @CheckForNull ImmutableMapEntry<?, ?> valueBucketHead) {
	int bucketSize = 0;
	for (; valueBucketHead != null; valueBucketHead = valueBucketHead.getNextInValueBucket()) {
	checkNoConflict(!value.equals(valueBucketHead.getValue()), "value", entry, valueBucketHead);
	bucketSize++;
	}
	return bucketSize;
	}

	@Override
	@CheckForNull
	public V get(@CheckForNull Object key) {
	return RegularImmutableMap.get(key, keyTable, mask);
	}

	@Override
	ImmutableSet<Entry<K, V>> createEntrySet() {
	return isEmpty()
	? ImmutableSet.<Entry<K, V>>of()
	: new ImmutableMapEntrySet.RegularEntrySet<K, V>(this, entries);
	}

	@Override
	ImmutableSet<K> createKeySet() {
	return new ImmutableMapKeySet<>(this);
	}

	@Override
	public void forEach(BiConsumer<? super K, ? super V> action) {
	checkNotNull(action);
	for (Entry<K, V> entry : entries) {
	action.accept(entry.getKey(), entry.getValue());
	}
	}

	@Override
	boolean isHashCodeFast() {
	return true;
	}

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

	@Override
	boolean isPartialView() {
	return false;
	}

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

	@LazyInit @RetainedWith @CheckForNull private transient ImmutableBiMap<V, K> inverse;

	@Override
	public ImmutableBiMap<V, K> inverse() {
	if (isEmpty()) {
	return ImmutableBiMap.of();
	}
	ImmutableBiMap<V, K> result = inverse;
	return (result == null) ? inverse = new Inverse() : result;
	}

	private final class Inverse extends ImmutableBiMap<V, K> {

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

	@Override
	public ImmutableBiMap<K, V> inverse() {
	return RegularImmutableBiMap.this;
	}

	@Override
	public void forEach(BiConsumer<? super V, ? super K> action) {
	checkNotNull(action);
	RegularImmutableBiMap.this.forEach((k, v) -> action.accept(v, k));
	}

	@Override
	@CheckForNull
	public K get(@CheckForNull Object value) {
	if (value == null \|\| valueTable == null) {
	return null;
	}
	int bucket = Hashing.smear(value.hashCode()) & mask;
	for (ImmutableMapEntry<K, V> entry = valueTable[bucket];
	entry != null;
	entry = entry.getNextInValueBucket()) {
	if (value.equals(entry.getValue())) {
	return entry.getKey();
	}
	}
	return null;
	}

	@Override
	ImmutableSet<V> createKeySet() {
	return new ImmutableMapKeySet<>(this);
	}

	@Override
	ImmutableSet<Entry<V, K>> createEntrySet() {
	return new InverseEntrySet();
	}

	final class InverseEntrySet extends ImmutableMapEntrySet<V, K> {
	@Override
	ImmutableMap<V, K> map() {
	return Inverse.this;
	}

	@Override
	boolean isHashCodeFast() {
	return true;
	}

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

	@Override
	public UnmodifiableIterator<Entry<V, K>> iterator() {
	return asList().iterator();
	}

	@Override
	public void forEach(Consumer<? super Entry<V, K>> action) {
	asList().forEach(action);
	}

	@Override
	ImmutableList<Entry<V, K>> createAsList() {
	return new ImmutableAsList<Entry<V, K>>() {
	@Override
	public Entry<V, K> get(int index) {
	Entry<K, V> entry = entries[index];
	return Maps.immutableEntry(entry.getValue(), entry.getKey());
	}

	@Override
	ImmutableCollection<Entry<V, K>> delegateCollection() {
	return InverseEntrySet.this;
	}
	};
	}
	}

	@Override
	boolean isPartialView() {
	return false;
	}

	@Override
	Object writeReplace() {
	return new InverseSerializedForm<>(RegularImmutableBiMap.this);
	}
	}

	private static class InverseSerializedForm<K, V> implements Serializable {
	private final ImmutableBiMap<K, V> forward;

	InverseSerializedForm(ImmutableBiMap<K, V> forward) {
	this.forward = forward;
	}

	Object readResolve() {
	return forward.inverse();
	}

	private static final long serialVersionUID = 1;
	}
	}