/*
 * 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.collect.testing.Helpers.mapEntry;
import static com.google.common.truth.Truth.assertThat;
import static com.google.common.truth.Truth.assertWithMessage;
import static java.util.stream.Collectors.toList;

import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.base.Equivalence;
import com.google.common.base.Joiner;
import com.google.common.collect.ImmutableBiMap.Builder;
import com.google.common.collect.testing.MapInterfaceTest;
import com.google.common.collect.testing.features.CollectionFeature;
import com.google.common.collect.testing.features.CollectionSize;
import com.google.common.collect.testing.features.MapFeature;
import com.google.common.collect.testing.google.BiMapGenerators.ImmutableBiMapCopyOfEntriesGenerator;
import com.google.common.collect.testing.google.BiMapGenerators.ImmutableBiMapCopyOfGenerator;
import com.google.common.collect.testing.google.BiMapGenerators.ImmutableBiMapGenerator;
import com.google.common.collect.testing.google.BiMapInverseTester;
import com.google.common.collect.testing.google.BiMapTestSuiteBuilder;
import com.google.common.collect.testing.google.TestStringBiMapGenerator;
import com.google.common.testing.CollectorTester;
import com.google.common.testing.SerializableTester;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.stream.Collector;
import java.util.stream.Stream;
import junit.framework.Test;
import junit.framework.TestCase;
import junit.framework.TestSuite;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Tests for {@link ImmutableBiMap}.
 *
 * @author Jared Levy
 */
@GwtCompatible(emulated = true)
public class ImmutableBiMapTest extends TestCase {

  // TODO: Reduce duplication of ImmutableMapTest code

  @GwtIncompatible // suite
  public static Test suite() {
    TestSuite suite = new TestSuite();

    suite.addTestSuite(MapTests.class);
    suite.addTestSuite(InverseMapTests.class);
    suite.addTestSuite(CreationTests.class);
    suite.addTestSuite(BiMapSpecificTests.class);

    suite.addTest(
        BiMapTestSuiteBuilder.using(new ImmutableBiMapGenerator())
            .named("ImmutableBiMap")
            .withFeatures(
                CollectionSize.ANY,
                CollectionFeature.SERIALIZABLE,
                CollectionFeature.KNOWN_ORDER,
                MapFeature.REJECTS_DUPLICATES_AT_CREATION,
                MapFeature.ALLOWS_ANY_NULL_QUERIES)
            .suppressing(BiMapInverseTester.getInverseSameAfterSerializingMethods())
            .createTestSuite());
    suite.addTest(
        BiMapTestSuiteBuilder.using(
                new TestStringBiMapGenerator() {
                  @Override
                  protected BiMap<String, String> create(Entry<String, String>[] entries) {
                    return ImmutableBiMap.<String, String>builder()
                        .putAll(Arrays.asList(entries))
                        .buildJdkBacked();
                  }
                })
            .named("ImmutableBiMap [JDK backed]")
            .withFeatures(
                CollectionSize.ANY,
                CollectionFeature.SERIALIZABLE,
                CollectionFeature.KNOWN_ORDER,
                MapFeature.REJECTS_DUPLICATES_AT_CREATION,
                MapFeature.ALLOWS_ANY_NULL_QUERIES)
            .suppressing(BiMapInverseTester.getInverseSameAfterSerializingMethods())
            .createTestSuite());
    suite.addTest(
        BiMapTestSuiteBuilder.using(new ImmutableBiMapCopyOfGenerator())
            .named("ImmutableBiMap.copyOf[Map]")
            .withFeatures(
                CollectionSize.ANY,
                CollectionFeature.SERIALIZABLE,
                CollectionFeature.KNOWN_ORDER,
                MapFeature.ALLOWS_ANY_NULL_QUERIES)
            .suppressing(BiMapInverseTester.getInverseSameAfterSerializingMethods())
            .createTestSuite());
    suite.addTest(
        BiMapTestSuiteBuilder.using(new ImmutableBiMapCopyOfEntriesGenerator())
            .named("ImmutableBiMap.copyOf[Iterable<Entry>]")
            .withFeatures(
                CollectionSize.ANY,
                CollectionFeature.SERIALIZABLE,
                CollectionFeature.KNOWN_ORDER,
                MapFeature.REJECTS_DUPLICATES_AT_CREATION,
                MapFeature.ALLOWS_ANY_NULL_QUERIES)
            .suppressing(BiMapInverseTester.getInverseSameAfterSerializingMethods())
            .createTestSuite());

    return suite;
  }

  public abstract static class AbstractMapTests<K, V> extends MapInterfaceTest<K, V> {
    public AbstractMapTests() {
      super(false, false, false, false, false);
    }

    @Override
    protected Map<K, V> makeEmptyMap() {
      throw new UnsupportedOperationException();
    }

    private static final Joiner joiner = Joiner.on(", ");

    @Override
    protected void assertMoreInvariants(Map<K, V> map) {

      BiMap<K, V> bimap = (BiMap<K, V>) map;

      for (Entry<K, V> entry : map.entrySet()) {
        assertEquals(entry.getKey() + "=" + entry.getValue(), entry.toString());
        assertEquals(entry.getKey(), bimap.inverse().get(entry.getValue()));
      }

      assertEquals("{" + joiner.join(map.entrySet()) + "}", map.toString());
      assertEquals("[" + joiner.join(map.entrySet()) + "]", map.entrySet().toString());
      assertEquals("[" + joiner.join(map.keySet()) + "]", map.keySet().toString());
      assertEquals("[" + joiner.join(map.values()) + "]", map.values().toString());

      assertEquals(Sets.newHashSet(map.entrySet()), map.entrySet());
      assertEquals(Sets.newHashSet(map.keySet()), map.keySet());
    }
  }

  public static class MapTests extends AbstractMapTests<String, Integer> {
    @Override
    protected Map<String, Integer> makeEmptyMap() {
      return ImmutableBiMap.of();
    }

    @Override
    protected Map<String, Integer> makePopulatedMap() {
      return ImmutableBiMap.of("one", 1, "two", 2, "three", 3);
    }

    @Override
    protected String getKeyNotInPopulatedMap() {
      return "minus one";
    }

    @Override
    protected Integer getValueNotInPopulatedMap() {
      return -1;
    }
  }

  public static class InverseMapTests extends AbstractMapTests<String, Integer> {
    @Override
    protected Map<String, Integer> makeEmptyMap() {
      return ImmutableBiMap.of();
    }

    @Override
    protected Map<String, Integer> makePopulatedMap() {
      return ImmutableBiMap.of(1, "one", 2, "two", 3, "three").inverse();
    }

    @Override
    protected String getKeyNotInPopulatedMap() {
      return "minus one";
    }

    @Override
    protected Integer getValueNotInPopulatedMap() {
      return -1;
    }
  }

  public static class CreationTests extends TestCase {
    public void testEmptyBuilder() {
      ImmutableBiMap<String, Integer> map = new Builder<String, Integer>().build();
      assertEquals(Collections.<String, Integer>emptyMap(), map);
      assertEquals(Collections.<Integer, String>emptyMap(), map.inverse());
      assertSame(ImmutableBiMap.of(), map);
    }

    public void testSingletonBuilder() {
      ImmutableBiMap<String, Integer> map = new Builder<String, Integer>().put("one", 1).build();
      assertMapEquals(map, "one", 1);
      assertMapEquals(map.inverse(), 1, "one");
    }

    public void testBuilder_withImmutableEntry() {
      ImmutableBiMap<String, Integer> map =
          new Builder<String, Integer>().put(Maps.immutableEntry("one", 1)).build();
      assertMapEquals(map, "one", 1);
    }

    public void testBuilder() {
      ImmutableBiMap<String, Integer> map =
          ImmutableBiMap.<String, Integer>builder()
              .put("one", 1)
              .put("two", 2)
              .put("three", 3)
              .put("four", 4)
              .put("five", 5)
              .build();
      assertMapEquals(map, "one", 1, "two", 2, "three", 3, "four", 4, "five", 5);
      assertMapEquals(map.inverse(), 1, "one", 2, "two", 3, "three", 4, "four", 5, "five");
    }

    @GwtIncompatible
    public void testBuilderExactlySizedReusesArray() {
      ImmutableBiMap.Builder<Integer, Integer> builder = ImmutableBiMap.builderWithExpectedSize(10);
      Entry<Integer, Integer>[] builderArray = builder.entries;
      for (int i = 0; i < 10; i++) {
        builder.put(i, i);
      }
      Entry<Integer, Integer>[] builderArrayAfterPuts = builder.entries;
      RegularImmutableBiMap<Integer, Integer> map =
          (RegularImmutableBiMap<Integer, Integer>) builder.build();
      Entry<Integer, Integer>[] mapInternalArray = map.entries;
      assertSame(builderArray, builderArrayAfterPuts);
      assertSame(builderArray, mapInternalArray);
    }

    public void testBuilder_orderEntriesByValue() {
      ImmutableBiMap<String, Integer> map =
          ImmutableBiMap.<String, Integer>builder()
              .orderEntriesByValue(Ordering.natural())
              .put("three", 3)
              .put("one", 1)
              .put("five", 5)
              .put("four", 4)
              .put("two", 2)
              .build();
      assertMapEquals(map, "one", 1, "two", 2, "three", 3, "four", 4, "five", 5);
      assertMapEquals(map.inverse(), 1, "one", 2, "two", 3, "three", 4, "four", 5, "five");
    }

    public void testBuilder_orderEntriesByValueAfterExactSizeBuild() {
      ImmutableBiMap.Builder<String, Integer> builder =
          new ImmutableBiMap.Builder<String, Integer>(2).put("four", 4).put("one", 1);
      ImmutableMap<String, Integer> keyOrdered = builder.build();
      ImmutableMap<String, Integer> valueOrdered =
          builder.orderEntriesByValue(Ordering.natural()).build();
      assertMapEquals(keyOrdered, "four", 4, "one", 1);
      assertMapEquals(valueOrdered, "one", 1, "four", 4);
    }

    public void testBuilder_orderEntriesByValue_usedTwiceFails() {
      ImmutableBiMap.Builder<String, Integer> builder =
          new Builder<String, Integer>().orderEntriesByValue(Ordering.natural());
      try {
        builder.orderEntriesByValue(Ordering.natural());
        fail("Expected IllegalStateException");
      } catch (IllegalStateException expected) {
      }
    }

    public void testBuilderPutAllWithEmptyMap() {
      ImmutableBiMap<String, Integer> map =
          new Builder<String, Integer>().putAll(Collections.<String, Integer>emptyMap()).build();
      assertEquals(Collections.<String, Integer>emptyMap(), map);
    }

    public void testBuilderPutAll() {
      Map<String, Integer> toPut = new LinkedHashMap<>();
      toPut.put("one", 1);
      toPut.put("two", 2);
      toPut.put("three", 3);
      Map<String, Integer> moreToPut = new LinkedHashMap<>();
      moreToPut.put("four", 4);
      moreToPut.put("five", 5);

      ImmutableBiMap<String, Integer> map =
          new Builder<String, Integer>().putAll(toPut).putAll(moreToPut).build();
      assertMapEquals(map, "one", 1, "two", 2, "three", 3, "four", 4, "five", 5);
      assertMapEquals(map.inverse(), 1, "one", 2, "two", 3, "three", 4, "four", 5, "five");
    }

    public void testBuilderReuse() {
      Builder<String, Integer> builder = new Builder<>();
      ImmutableBiMap<String, Integer> mapOne = builder.put("one", 1).put("two", 2).build();
      ImmutableBiMap<String, Integer> mapTwo = builder.put("three", 3).put("four", 4).build();

      assertMapEquals(mapOne, "one", 1, "two", 2);
      assertMapEquals(mapOne.inverse(), 1, "one", 2, "two");
      assertMapEquals(mapTwo, "one", 1, "two", 2, "three", 3, "four", 4);
      assertMapEquals(mapTwo.inverse(), 1, "one", 2, "two", 3, "three", 4, "four");
    }

    public void testBuilderPutNullKey() {
      Builder<String, Integer> builder = new Builder<>();
      try {
        builder.put(null, 1);
        fail();
      } catch (NullPointerException expected) {
      }
    }

    public void testBuilderPutNullValue() {
      Builder<String, Integer> builder = new Builder<>();
      try {
        builder.put("one", null);
        fail();
      } catch (NullPointerException expected) {
      }
    }

    public void testBuilderPutNullKeyViaPutAll() {
      Builder<String, Integer> builder = new Builder<>();
      try {
        builder.putAll(Collections.<String, Integer>singletonMap(null, 1));
        fail();
      } catch (NullPointerException expected) {
      }
    }

    public void testBuilderPutNullValueViaPutAll() {
      Builder<String, Integer> builder = new Builder<>();
      try {
        builder.putAll(Collections.<String, Integer>singletonMap("one", null));
        fail();
      } catch (NullPointerException expected) {
      }
    }

    public void testPuttingTheSameKeyTwiceThrowsOnBuild() {
      Builder<String, Integer> builder =
          new Builder<String, Integer>()
              .put("one", 1)
              .put("one", 1); // throwing on this line would be even better

      try {
        builder.build();
        fail();
      } catch (IllegalArgumentException expected) {
        assertThat(expected.getMessage()).contains("one");
      }
    }

    public void testOf() {
      assertMapEquals(ImmutableBiMap.of("one", 1), "one", 1);
      assertMapEquals(ImmutableBiMap.of("one", 1).inverse(), 1, "one");
      assertMapEquals(ImmutableBiMap.of("one", 1, "two", 2), "one", 1, "two", 2);
      assertMapEquals(ImmutableBiMap.of("one", 1, "two", 2).inverse(), 1, "one", 2, "two");
      assertMapEquals(
          ImmutableBiMap.of("one", 1, "two", 2, "three", 3), "one", 1, "two", 2, "three", 3);
      assertMapEquals(
          ImmutableBiMap.of("one", 1, "two", 2, "three", 3).inverse(),
          1,
          "one",
          2,
          "two",
          3,
          "three");
      assertMapEquals(
          ImmutableBiMap.of("one", 1, "two", 2, "three", 3, "four", 4),
          "one",
          1,
          "two",
          2,
          "three",
          3,
          "four",
          4);
      assertMapEquals(
          ImmutableBiMap.of("one", 1, "two", 2, "three", 3, "four", 4).inverse(),
          1,
          "one",
          2,
          "two",
          3,
          "three",
          4,
          "four");
      assertMapEquals(
          ImmutableBiMap.of("one", 1, "two", 2, "three", 3, "four", 4, "five", 5),
          "one",
          1,
          "two",
          2,
          "three",
          3,
          "four",
          4,
          "five",
          5);
      assertMapEquals(
          ImmutableBiMap.of("one", 1, "two", 2, "three", 3, "four", 4, "five", 5).inverse(),
          1,
          "one",
          2,
          "two",
          3,
          "three",
          4,
          "four",
          5,
          "five");
    }

    public void testOfNullKey() {
      try {
        ImmutableBiMap.of(null, 1);
        fail();
      } catch (NullPointerException expected) {
      }

      try {
        ImmutableBiMap.of("one", 1, null, 2);
        fail();
      } catch (NullPointerException expected) {
      }
    }

    public void testOfNullValue() {
      try {
        ImmutableBiMap.of("one", null);
        fail();
      } catch (NullPointerException expected) {
      }

      try {
        ImmutableBiMap.of("one", 1, "two", null);
        fail();
      } catch (NullPointerException expected) {
      }
    }

    public void testOfWithDuplicateKey() {
      try {
        ImmutableBiMap.of("one", 1, "one", 1);
        fail();
      } catch (IllegalArgumentException expected) {
        assertThat(expected.getMessage()).contains("one");
      }
    }

    public void testCopyOfEmptyMap() {
      ImmutableBiMap<String, Integer> copy =
          ImmutableBiMap.copyOf(Collections.<String, Integer>emptyMap());
      assertEquals(Collections.<String, Integer>emptyMap(), copy);
      assertSame(copy, ImmutableBiMap.copyOf(copy));
      assertSame(ImmutableBiMap.of(), copy);
    }

    public void testCopyOfSingletonMap() {
      ImmutableBiMap<String, Integer> copy =
          ImmutableBiMap.copyOf(Collections.singletonMap("one", 1));
      assertMapEquals(copy, "one", 1);
      assertSame(copy, ImmutableBiMap.copyOf(copy));
    }

    public void testCopyOf() {
      Map<String, Integer> original = new LinkedHashMap<>();
      original.put("one", 1);
      original.put("two", 2);
      original.put("three", 3);

      ImmutableBiMap<String, Integer> copy = ImmutableBiMap.copyOf(original);
      assertMapEquals(copy, "one", 1, "two", 2, "three", 3);
      assertSame(copy, ImmutableBiMap.copyOf(copy));
    }

    public void testEmpty() {
      ImmutableBiMap<String, Integer> bimap = ImmutableBiMap.of();
      assertEquals(Collections.<String, Integer>emptyMap(), bimap);
      assertEquals(Collections.<String, Integer>emptyMap(), bimap.inverse());
    }

    public void testFromHashMap() {
      Map<String, Integer> hashMap = Maps.newLinkedHashMap();
      hashMap.put("one", 1);
      hashMap.put("two", 2);
      ImmutableBiMap<String, Integer> bimap =
          ImmutableBiMap.copyOf(ImmutableMap.of("one", 1, "two", 2));
      assertMapEquals(bimap, "one", 1, "two", 2);
      assertMapEquals(bimap.inverse(), 1, "one", 2, "two");
    }

    public void testFromImmutableMap() {
      ImmutableBiMap<String, Integer> bimap =
          ImmutableBiMap.copyOf(
              new ImmutableMap.Builder<String, Integer>()
                  .put("one", 1)
                  .put("two", 2)
                  .put("three", 3)
                  .put("four", 4)
                  .put("five", 5)
                  .build());
      assertMapEquals(bimap, "one", 1, "two", 2, "three", 3, "four", 4, "five", 5);
      assertMapEquals(bimap.inverse(), 1, "one", 2, "two", 3, "three", 4, "four", 5, "five");
    }

    public void testDuplicateValues() {
      ImmutableMap<String, Integer> map =
          new ImmutableMap.Builder<String, Integer>()
              .put("one", 1)
              .put("two", 2)
              .put("uno", 1)
              .put("dos", 2)
              .build();

      try {
        ImmutableBiMap.copyOf(map);
        fail();
      } catch (IllegalArgumentException expected) {
        assertThat(expected.getMessage()).contains("1");
      }
    }

    public void testToImmutableBiMap() {
      Collector<Entry<String, Integer>, ?, ImmutableBiMap<String, Integer>> collector =
          ImmutableBiMap.toImmutableBiMap(Entry::getKey, Entry::getValue);
      Equivalence<ImmutableBiMap<String, Integer>> equivalence =
          Equivalence.equals()
              .<Entry<String, Integer>>pairwise()
              .onResultOf(ImmutableBiMap::entrySet);
      CollectorTester.of(collector, equivalence)
          .expectCollects(
              ImmutableBiMap.of("one", 1, "two", 2, "three", 3),
              mapEntry("one", 1),
              mapEntry("two", 2),
              mapEntry("three", 3));
    }

    public void testToImmutableBiMap_exceptionOnDuplicateKey() {
      Collector<Entry<String, Integer>, ?, ImmutableBiMap<String, Integer>> collector =
          ImmutableBiMap.toImmutableBiMap(Entry::getKey, Entry::getValue);
      try {
        Stream.of(mapEntry("one", 1), mapEntry("one", 11)).collect(collector);
        fail("Expected IllegalArgumentException");
      } catch (IllegalArgumentException expected) {
      }
    }
  }

  public static class BiMapSpecificTests extends TestCase {

    public void testForcePut() {
      BiMap<String, Integer> bimap = ImmutableBiMap.copyOf(ImmutableMap.of("one", 1, "two", 2));
      try {
        bimap.forcePut("three", 3);
        fail();
      } catch (UnsupportedOperationException expected) {
      }
    }

    public void testKeySet() {
      ImmutableBiMap<String, Integer> bimap =
          ImmutableBiMap.copyOf(ImmutableMap.of("one", 1, "two", 2, "three", 3, "four", 4));
      Set<String> keys = bimap.keySet();
      assertEquals(Sets.newHashSet("one", "two", "three", "four"), keys);
      assertThat(keys).containsExactly("one", "two", "three", "four").inOrder();
    }

    public void testValues() {
      ImmutableBiMap<String, Integer> bimap =
          ImmutableBiMap.copyOf(ImmutableMap.of("one", 1, "two", 2, "three", 3, "four", 4));
      Set<Integer> values = bimap.values();
      assertEquals(Sets.newHashSet(1, 2, 3, 4), values);
      assertThat(values).containsExactly(1, 2, 3, 4).inOrder();
    }

    public void testDoubleInverse() {
      ImmutableBiMap<String, Integer> bimap =
          ImmutableBiMap.copyOf(ImmutableMap.of("one", 1, "two", 2));
      assertSame(bimap, bimap.inverse().inverse());
    }

    @GwtIncompatible // SerializableTester
    public void testEmptySerialization() {
      ImmutableBiMap<String, Integer> bimap = ImmutableBiMap.of();
      assertSame(bimap, SerializableTester.reserializeAndAssert(bimap));
    }

    @GwtIncompatible // SerializableTester
    public void testSerialization() {
      ImmutableBiMap<String, Integer> bimap =
          ImmutableBiMap.copyOf(ImmutableMap.of("one", 1, "two", 2));
      ImmutableBiMap<String, Integer> copy = SerializableTester.reserializeAndAssert(bimap);
      assertEquals(Integer.valueOf(1), copy.get("one"));
      assertEquals("one", copy.inverse().get(1));
      assertSame(copy, copy.inverse().inverse());
    }

    @GwtIncompatible // SerializableTester
    public void testInverseSerialization() {
      ImmutableBiMap<String, Integer> bimap =
          ImmutableBiMap.copyOf(ImmutableMap.of(1, "one", 2, "two")).inverse();
      ImmutableBiMap<String, Integer> copy = SerializableTester.reserializeAndAssert(bimap);
      assertEquals(Integer.valueOf(1), copy.get("one"));
      assertEquals("one", copy.inverse().get(1));
      assertSame(copy, copy.inverse().inverse());
    }
  }

  private static <K, V> void assertMapEquals(Map<K, V> map, Object... alternatingKeysAndValues) {
    int i = 0;
    for (Entry<K, V> entry : map.entrySet()) {
      assertEquals(alternatingKeysAndValues[i++], entry.getKey());
      assertEquals(alternatingKeysAndValues[i++], entry.getValue());
    }
  }

  /**
   * A Comparable wrapper around a String which executes callbacks on calls to hashCode, equals, and
   * compareTo.
   */
  private static class CountsHashCodeAndEquals implements Comparable<CountsHashCodeAndEquals> {
    private final String delegateString;
    private final Runnable onHashCode;
    private final Runnable onEquals;
    private final Runnable onCompareTo;

    CountsHashCodeAndEquals(
        String delegateString, Runnable onHashCode, Runnable onEquals, Runnable onCompareTo) {
      this.delegateString = delegateString;
      this.onHashCode = onHashCode;
      this.onEquals = onEquals;
      this.onCompareTo = onCompareTo;
    }

    @Override
    public int hashCode() {
      onHashCode.run();
      return delegateString.hashCode();
    }

    @Override
    public boolean equals(@Nullable Object other) {
      onEquals.run();
      return other instanceof CountsHashCodeAndEquals
          && delegateString.equals(((CountsHashCodeAndEquals) other).delegateString);
    }

    @Override
    public int compareTo(CountsHashCodeAndEquals o) {
      onCompareTo.run();
      return delegateString.compareTo(o.delegateString);
    }
  }

  /** A holder of counters for calls to hashCode, equals, and compareTo. */
  private static final class CallsCounter {
    long hashCode;
    long equals;
    long compareTo;

    long total() {
      return hashCode + equals + compareTo;
    }

    void zero() {
      hashCode = 0;
      equals = 0;
      compareTo = 0;
    }
  }

  /** All the ways to create an ImmutableBiMap. */
  enum ConstructionPathway {
    COPY_OF_MAP {
      @Override
      ImmutableBiMap<?, ?> create(List<? extends Entry<?, ?>> entries, CallsCounter counter) {
        Map<Object, Object> sourceMap = new LinkedHashMap<>();
        for (Entry<?, ?> entry : entries) {
          if (sourceMap.put(entry.getKey(), entry.getValue()) != null) {
            throw new UnsupportedOperationException("duplicate key");
          }
        }
        counter.zero();
        return ImmutableBiMap.copyOf(sourceMap);
      }
    },
    COPY_OF_ENTRIES {
      @Override
      ImmutableBiMap<?, ?> create(List<? extends Entry<?, ?>> entries, CallsCounter counter) {
        return ImmutableBiMap.copyOf(entries);
      }
    },
    BUILDER_PUT_ONE_BY_ONE {
      @Override
      ImmutableBiMap<?, ?> create(List<? extends Entry<?, ?>> entries, CallsCounter counter) {
        ImmutableBiMap.Builder<Object, Object> builder = ImmutableBiMap.builder();
        for (Entry<?, ?> entry : entries) {
          builder.put(entry.getKey(), entry.getValue());
        }
        return builder.build();
      }
    },
    BUILDER_PUT_ENTRY_ONE_BY_ONE {
      @Override
      ImmutableBiMap<?, ?> create(List<? extends Entry<?, ?>> entries, CallsCounter counter) {
        ImmutableBiMap.Builder<Object, Object> builder = ImmutableBiMap.builder();
        for (Entry<?, ?> entry : entries) {
          builder.put(entry);
        }
        return builder.build();
      }
    },
    BUILDER_PUT_ALL_MAP {
      @Override
      ImmutableBiMap<?, ?> create(List<? extends Entry<?, ?>> entries, CallsCounter counter) {
        Map<Object, Object> sourceMap = new LinkedHashMap<>();
        for (Entry<?, ?> entry : entries) {
          if (sourceMap.put(entry.getKey(), entry.getValue()) != null) {
            throw new UnsupportedOperationException("duplicate key");
          }
        }
        counter.zero();
        ImmutableBiMap.Builder<Object, Object> builder = ImmutableBiMap.builder();
        builder.putAll(sourceMap);
        return builder.build();
      }
    },
    BUILDER_PUT_ALL_ENTRIES {
      @Override
      ImmutableBiMap<?, ?> create(List<? extends Entry<?, ?>> entries, CallsCounter counter) {
        ImmutableBiMap.Builder<Object, Object> builder = ImmutableBiMap.builder();
        builder.putAll(entries);
        return builder.build();
      }
    },
    FORCE_JDK {
      @Override
      ImmutableBiMap<?, ?> create(List<? extends Entry<?, ?>> entries, CallsCounter counter) {
        ImmutableBiMap.Builder<Object, Object> builder = ImmutableBiMap.builder();
        builder.putAll(entries);
        return builder.buildJdkBacked();
      }
    };

    @CanIgnoreReturnValue
    abstract ImmutableBiMap<?, ?> create(List<? extends Entry<?, ?>> entries, CallsCounter counter);
  }

  /**
   * Returns a list of objects with the same hash code, of size 2^power, counting calls to equals,
   * hashCode, and compareTo in counter.
   */
  static List<CountsHashCodeAndEquals> createAdversarialObjects(int power, CallsCounter counter) {
    String str1 = "Aa";
    String str2 = "BB";
    assertEquals(str1.hashCode(), str2.hashCode());
    List<String> haveSameHashes2 = Arrays.asList(str1, str2);
    List<CountsHashCodeAndEquals> result =
        Lists.newArrayList(
            Lists.transform(
                Lists.cartesianProduct(Collections.nCopies(power, haveSameHashes2)),
                strs ->
                    new CountsHashCodeAndEquals(
                        String.join("", strs),
                        () -> counter.hashCode++,
                        () -> counter.equals++,
                        () -> counter.compareTo++)));
    assertEquals(
        result.get(0).delegateString.hashCode(),
        result.get(result.size() - 1).delegateString.hashCode());
    return result;
  }

  enum AdversaryType {
    ADVERSARIAL_KEYS {
      @Override
      List<? extends Entry<?, ?>> createAdversarialEntries(int power, CallsCounter counter) {
        return createAdversarialObjects(power, counter).stream()
            .map(k -> Maps.immutableEntry(k, new Object()))
            .collect(toList());
      }
    },
    ADVERSARIAL_VALUES {
      @Override
      List<? extends Entry<?, ?>> createAdversarialEntries(int power, CallsCounter counter) {
        return createAdversarialObjects(power, counter).stream()
            .map(k -> Maps.immutableEntry(new Object(), k))
            .collect(toList());
      }
    },
    ADVERSARIAL_KEYS_AND_VALUES {
      @Override
      List<? extends Entry<?, ?>> createAdversarialEntries(int power, CallsCounter counter) {
        List<?> keys = createAdversarialObjects(power, counter);
        List<?> values = createAdversarialObjects(power, counter);
        return Streams.zip(keys.stream(), values.stream(), Maps::immutableEntry).collect(toList());
      }
    };

    abstract List<? extends Entry<?, ?>> createAdversarialEntries(int power, CallsCounter counter);
  }

  @GwtIncompatible
  public void testResistsHashFloodingInConstruction() {
    for (AdversaryType adversary : AdversaryType.values()) {
      CallsCounter smallCounter = new CallsCounter();
      List<? extends Entry<?, ?>> smallEntries =
          adversary.createAdversarialEntries(10, smallCounter);
      int smallSize = smallEntries.size();

      CallsCounter largeCounter = new CallsCounter();
      List<? extends Entry<?, ?>> largeEntries =
          adversary.createAdversarialEntries(15, largeCounter);
      int largeSize = largeEntries.size();

      for (ConstructionPathway pathway : ConstructionPathway.values()) {
        smallCounter.zero();
        pathway.create(smallEntries, smallCounter);
        long smallOps = smallCounter.total();

        largeCounter.zero();
        pathway.create(largeEntries, largeCounter);
        long largeOps = largeCounter.total();

        double ratio = (double) largeOps / smallOps;
        assertWithMessage(
                "ratio of equals/hashCode/compareTo operations to build an ImmutableBiMap with %s"
                    + " via %s with %s entries versus %s entries",
                adversary, pathway, largeSize, smallSize)
            .that(ratio)
            .isAtMost(2 * (largeSize * Math.log(largeSize)) / (smallSize * Math.log(smallSize)));
        // allow up to 2x wobble in the constant factors
      }
    }
  }

  @GwtIncompatible
  public void testResistsHashFloodingOnForwardGet() {
    for (AdversaryType adversary : AdversaryType.values()) {
      CallsCounter smallCounter = new CallsCounter();
      List<? extends Entry<?, ?>> smallEntries =
          adversary.createAdversarialEntries(10, smallCounter);
      ImmutableBiMap<?, ?> smallMap =
          ConstructionPathway.COPY_OF_ENTRIES.create(smallEntries, smallCounter);
      int smallSize = smallEntries.size();
      long smallOps = worstCaseQueryOperations(smallMap, smallCounter);

      CallsCounter largeCounter = new CallsCounter();
      List<? extends Entry<?, ?>> largeEntries =
          adversary.createAdversarialEntries(15, largeCounter);
      ImmutableBiMap<?, ?> largeMap =
          ConstructionPathway.COPY_OF_ENTRIES.create(largeEntries, largeCounter);
      int largeSize = largeEntries.size();
      long largeOps = worstCaseQueryOperations(largeMap, largeCounter);

      if (smallOps == 0 && largeOps == 0) {
        continue; // no queries on the CHCAE objects
      }

      double ratio = (double) largeOps / smallOps;
      assertWithMessage(
              "Ratio of worst case get operations for an ImmutableBiMap with %s of size "
                  + "%s versus %s",
              adversary, largeSize, smallSize)
          .that(ratio)
          .isAtMost(2 * Math.log(largeSize) / Math.log(smallSize));
      // allow up to 2x wobble in the constant factors
    }
  }

  @GwtIncompatible
  public void testResistsHashFloodingOnInverseGet() {
    for (AdversaryType adversary : AdversaryType.values()) {
      CallsCounter smallCounter = new CallsCounter();
      List<? extends Entry<?, ?>> smallEntries =
          adversary.createAdversarialEntries(10, smallCounter);
      ImmutableBiMap<?, ?> smallMap =
          ConstructionPathway.COPY_OF_ENTRIES.create(smallEntries, smallCounter);
      int smallSize = smallEntries.size();
      long smallOps = worstCaseQueryOperations(smallMap.inverse(), smallCounter);

      CallsCounter largeCounter = new CallsCounter();
      List<? extends Entry<?, ?>> largeEntries =
          adversary.createAdversarialEntries(15, largeCounter);
      ImmutableBiMap<?, ?> largeMap =
          ConstructionPathway.COPY_OF_ENTRIES.create(largeEntries, largeCounter);
      int largeSize = largeEntries.size();
      long largeOps = worstCaseQueryOperations(largeMap.inverse(), largeCounter);

      if (smallOps == 0 && largeOps == 0) {
        continue; // no queries on the CHCAE objects
      }
      double ratio = (double) largeOps / smallOps;
      assertWithMessage(
              "Ratio of worst case get operations for an ImmutableBiMap with %s of size "
                  + "%s versus %s",
              adversary, largeSize, smallSize)
          .that(ratio)
          .isAtMost(2 * Math.log(largeSize) / Math.log(smallSize));
      // allow up to 2x wobble in the constant factors
    }
  }

  private static long worstCaseQueryOperations(Map<?, ?> map, CallsCounter counter) {
    long worstCalls = 0;
    for (Object k : map.keySet()) {
      counter.zero();
      Object unused = map.get(k);
      worstCalls = Math.max(worstCalls, counter.total());
    }
    return worstCalls;
  }
}
