user/test/com/google/gwt/emultest/java/util/TestMap.java

// CHECKSTYLE_OFF: Copyrighted to ASF
/*
 * Copyright 1999-2004 The Apache Software Foundation
 *
 * 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.
 */
// CHECKSTYLE_ON
package com.google.gwt.emultest.java.util;

import com.google.gwt.testing.TestUtils;
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.Set;
import jsinterop.annotations.JsPackage;
import jsinterop.annotations.JsProperty;

/**
 * Tests base {@link java.util.Map} methods and contracts.
 * <p>
 * The forces at work here are similar to those in {@link TestCollection}.
 * If your class implements the full Map interface, including optional
 * operations, simply extend this class, and implement the {@link
 * #makeEmptyMap()} method.
 * <p>
 * On the other hand, if your map implemenation is weird, you may have to
 * override one or more of the other protected methods.  They're described
 * below.<P>
 *
 * <B>Entry Population Methods</B><P>
 *
 * Override these methods if your map requires special entries:
 *
 * <UL>
 * <LI>{@link #getSampleKeys()}
 * <LI>{@link #getSampleValues()}
 * <LI>{@link #getNewSampleValues()}
 * <LI>{@link #getOtherKeys()}
 * <LI>{@link #getOtherValues()}
 * </UL>
 *
 * <B>Supported Operation Methods</B><P>
 *
 * Override these methods if your map doesn't support certain operations:
 *
 * <UL>
 * <LI> {@link #useDuplicateValues()}
 * <LI> {@link #useNullKey()}
 * <LI> {@link #useNullValue()}
 * <LI> {@link #isAddRemoveModifiable()}
 * <LI> {@link #isChangeable()}
 * </UL>
 *
 * <B>Fixture Methods</B><P>
 *
 * For tests on modification operations (puts and removes), fixtures are used
 * to verify that that operation results in correct state for the map and its
 * collection views.  Basically, the modification is performed against your
 * map implementation, and an identical modification is performed against
 * a <I>confirmed</I> map implementation.  A confirmed map implementation is
 * something like <Code>java.util.HashMap</Code>, which is known to conform
 * exactly to the {@link Map} contract.  After the modification takes place
 * on both your map implementation and the confirmed map implementation, the
 * two maps are compared to see if their state is identical.  The comparison
 * also compares the collection views to make sure they're still the same.<P>
 *
 * The upshot of all that is that <I>any</I> test that modifies the map in
 * <I>any</I> way will verify that <I>all</I> of the map's state is still
 * correct, including the state of its collection views.  So for instance
 * if a key is removed by the map's key set's iterator, then the entry set
 * is checked to make sure the key/value pair no longer appears.<P>
 *
 * The {@link #map} field holds an instance of your collection implementation.
 * The {@link #entrySet}, {@link #keySet} and {@link #collectionValues} fields hold
 * that map's collection views.  And the {@link #confirmed} field holds
 * an instance of the confirmed collection implementation.  The
 * {@link #resetEmpty()} and {@link #resetFull()} methods set these fields to
 * empty or full maps, so that tests can proceed from a known state.<P>
 *
 * After a modification operation to both {@link #map} and {@link #confirmed},
 * the {@link #verify()} method is invoked to compare the results.  The {@link
 * verify()} method calls separate methods to verify the map and its three
 * collection views ({@link verifyMap(), {@link verifyEntrySet()}, {@link
 * verifyKeySet()}, and {@link verifyValues()}).  You may want to override one
 * of the verification methodsto perform additional verifications.  For
 * instance, {@link TestDoubleOrderedMap} would want override its {@link
 * #verifyValues()} method to verify that the values are unique and in
 * ascending order.<P>
 *
 * <B>Other Notes</B><P>
 *
 * If your {@link Map} fails one of these tests by design, you may still use
 * this base set of cases.  Simply override the test case (method) your {@link
 * Map} fails and/or the methods that define the assumptions used by the test
 * cases.  For example, if your map does not allow duplicate values, override
 * {@link #useDuplicateValues()} and have it return <code>false</code>
 */
@SuppressWarnings({"unchecked", "rawtypes"})
abstract class TestMap extends TestObject {

  // These instance variables are initialized with the reset method.
  // Tests for map methods that alter the map (put, putAll, remove)
  // first call reset() to create the map and its views; then perform
  // the modification on the map; perform the same modification on the
  // confirmed; and then call verify() to ensure that the map is equal
  // to the confirmed, that the already-constructed collection views
  // are still equal to the confirmed's collection views.

  /** Map created by reset(). */
  protected Map map;

  /** Entry set of map created by reset(). */
  protected Set entrySet;

  /** Key set of map created by reset(). */
  protected Set keySet;

  /** Values collection of map created by reset(). */
  protected Collection collectionValues;

  /** HashMap created by reset(). */
  protected Map confirmed;

  /**
   * Override if your map does not allow a <code>null</code> key. The default implementation returns
   * <code>true</code>
   */
  protected boolean useNullKey() {
    return true;
  }

  /**
   * Override if your map does not allow <code>null</code> values. The default implementation
   * returns <code>true</code>.
   */
  protected boolean useNullValue() {
    return true;
  }

  /**
   * Override if your map does not allow duplicate values. The default implementation returns <code>
   * true</code>.
   */
  protected boolean useDuplicateValues() {
    return true;
  }

  /**
   * Override if your map allows its mappings to be changed to new values. The default
   * implementation returns <code>true</code>.
   */
  protected boolean isChangeable() {
    return true;
  }

  /**
   * Override if your map does not allow add/remove modifications. The default implementation
   * returns <code>true</code>.
   */
  protected boolean isAddRemoveModifiable() {
    return true;
  }

  /**
   * Override if your map allows concurrent modifications. The default implementation returns <code>
   * true</code>.
   */
  protected boolean isFailFastExpected() {
    return true;
  }

  /**
   * Returns the set of keys in the mappings used to test the map. This method must return an array
   * with the same length as {@link #getSampleValues()} and all array elements must be different.
   * The default implementation constructs a set of String keys, and includes a single null key if
   * {@link #useNullKey()} returns <code>true</code>.
   */
  protected Object[] getSampleKeys() {
    Object[] result = {
      "blah",
      "foo",
      "bar",
      "baz",
      "tmp",
      "gosh",
      "golly",
      "gee",
      "hello",
      "goodbye",
      "we'll",
      "see",
      "you",
      "all",
      "again",
      "key",
      "key2",
      useNullKey() ? null : "nonnullkey"
    };
    return result;
  }

  protected Object[] getOtherKeys() {
    return TestCollection.getOtherNonNullStringElements();
  }

  protected Object[] getOtherValues() {
    return TestCollection.getOtherNonNullStringElements();
  }

  /**
   * Returns the set of values in the mappings used to test the map. This method must return an
   * array with the same length as {@link #getSampleKeys()}. The default implementation contructs a
   * set of String values and includes a single null value if {@link #useNullValue()} returns <code>
   * true</code>, and includes two values that are the same if {@link #useDuplicateValues()} returns
   * <code>true</code>.
   */
  protected Object[] getSampleValues() {
    Object[] result = {
      "blahv",
      "foov",
      "barv",
      "bazv",
      "tmpv",
      "goshv",
      "gollyv",
      "geev",
      "hellov",
      "goodbyev",
      "we'llv",
      "seev",
      "youv",
      "allv",
      "againv",
      useNullValue() ? null : "nonnullvalue",
      "value",
      useDuplicateValues() ? "value" : "value2",
    };
    return result;
  }

  /**
   * Returns a the set of values that can be used to replace the values returned from {@link
   * #getSampleValues()}. This method must return an array with the same length as {@link
   * #getSampleValues()}. The values returned from this method should not be the same as those
   * returned from {@link #getSampleValues()}. The default implementation constructs a set of String
   * values and includes a single null value if {@link #useNullValue()} returns <code>true</code>,
   * and includes two values that are the same if {@link #useDuplicateValues()} returns <code>true
   * </code>.
   */
  protected Object[] getNewSampleValues() {
    Object[] result = {
      useNullValue() ? null : "newnonnullvalue",
      "newvalue",
      useDuplicateValues() ? "newvalue" : "newvalue2",
      "newblahv",
      "newfoov",
      "newbarv",
      "newbazv",
      "newtmpv",
      "newgoshv",
      "newgollyv",
      "newgeev",
      "newhellov",
      "newgoodbyev",
      "newwe'llv",
      "newseev",
      "newyouv",
      "newallv",
      "newagainv",
    };
    return result;
  }

  /**
   * Helper method to add all the mappings described by {@link #getSampleKeys()} and {@link
   * #getSampleValues()}.
   */
  protected void addSampleMappings(Map m) {

    Object[] keys = getSampleKeys();
    Object[] values = getSampleValues();

    for (int i = 0; i < keys.length; i++) {
      try {
        m.put(keys[i], values[i]);
      } catch (NullPointerException exception) {
        assertTrue(
            "NullPointerException only allowed to be thrown "
                + "if either the key or value is null.",
            keys[i] == null || values[i] == null);

        if (keys[i] == null) {
          if (useNullKey()) {
            throw new Error(
                "NullPointerException on null key, but "
                    + "useNullKey is not overridden to return false.",
                exception);
          }
        } else if (values[i] == null) {
          if (useNullValue()) {
            throw new Error(
                "NullPointerException on null value, but "
                    + "useNullValue is not overridden to return false.",
                exception);
          }
        } else {
          // Unknown reason for NullPointer.
          throw exception;
        }
      }
    }
    assertEquals("size must reflect number of mappings added.", keys.length, m.size());
  }

  /** Return a new, empty {@link Map} to be used for testing. */
  protected abstract Map makeEmptyMap();

  protected Map makeConfirmedMap() {
    return new HashMap();
  }

  /**
   * Return a new, populated map. The mappings in the map should match the keys and values returned
   * from {@link #getSampleKeys()} and {@link #getSampleValues()}. The default implementation uses
   * makeEmptyMap() and calls {@link #addSampleMappings()} to add all the mappings to the map.
   */
  protected Map makeFullMap() {
    Map m = makeEmptyMap();
    addSampleMappings(m);
    return m;
  }

  @Override
  public Object makeObject() {
    return makeEmptyMap();
  }

  public void testSpecialKeysValues() {
    String[] keys = {"toString", "constructor", "__proto__", "", "null"};
    Object[] values = {new Object(), new Object(), new Object(), new Object(), null};

    Map map = makeEmptyMap();

    assertMap(map, keys, values);

    Object[] undefineds = new Object[values.length];
    Arrays.fill(undefineds, getUndefined());
    assertMap(map, keys, undefineds);
  }

  private void assertMap(Map map, String[] keys, Object[] values) {
    assertEmptyMap(map, keys, values);

    // Fill the map with special keys/values.
    for (int i = 0; i < keys.length; i++) {
      map.put(keys[i], values[i]);
    }

    // Assert the map with filled in keys/values
    for (int i = 0; i < keys.length; i++) {
      assertTrue(keys[i], map.containsKey(keys[i]));
      assertTrue(keys[i], map.containsValue(values[i]));
      assertSame(keys[i], values[i], map.get(keys[i]));
    }
    assertEquals(map.toString(), keys.length, map.size());

    // Remove the keys and assert the results
    for (int i = 0; i < keys.length; i++) {
      assertSame(keys[i], values[i], map.remove(keys[i]));
    }
    assertEmptyMap(map, keys, values);
  }

  private static void assertEmptyMap(Map map, final String[] keys, final Object[] values) {
    for (int i = 0; i < keys.length; i++) {
      assertFalse(keys[i], map.containsKey(keys[i]));
      assertFalse(keys[i], map.containsValue(values[i]));
      assertNull(keys[i], map.get(keys[i]));
    }
  }

  private static Object getUndefined() {
    if (TestUtils.isJvm()) {
      return null;
    }
    return getUndefinedImpl();
  }

  @JsProperty(name = "undefined", namespace = JsPackage.GLOBAL)
  private static native Object getUndefinedImpl();

  /**
   * Test to ensure the test setup is working properly. This method checks to ensure that the
   * getSampleKeys and getSampleValues methods are returning results that look appropriate. That is,
   * they both return a non-null array of equal length. The keys array must not have any duplicate
   * values, and may only contain a (single) null key if useNullKey() returns true. The values array
   * must only have a null value if useNullValue() is true and may only have duplicate values if
   * useDuplicateValues() returns true.
   */
  public void testSampleMappings() {
    Object[] keys = getSampleKeys();
    Object[] values = getSampleValues();
    Object[] newValues = getNewSampleValues();

    assertNotNull("failure in test: Must have keys returned from " + "getSampleKeys.", keys);

    assertTrue(
        "failure in test: Must have values returned from " + "getSampleValues.", values != null);

    // verify keys and values have equivalent lengths (in case getSampleX are
    // overridden)
    assertEquals(
        "failure in test: not the same number of sample " + "keys and values.",
        keys.length,
        values.length);

    assertEquals(
        "failure in test: not the same number of values and new values.",
        values.length,
        newValues.length);

    // verify there aren't duplicate keys, and check values
    for (int i = 0; i < keys.length - 1; i++) {
      for (int j = i + 1; j < keys.length; j++) {
        assertTrue("failure in test: duplicate null keys.", (keys[i] != null || keys[j] != null));
        assertTrue(
            "failure in test: duplicate non-null key.",
            (keys[i] == null
                || keys[j] == null
                || (!keys[i].equals(keys[j]) && !keys[j].equals(keys[i]))));
      }
      assertTrue(
          "failure in test: found null key, but useNullKey " + "is false.",
          keys[i] != null || useNullKey());
      assertTrue(
          "failure in test: found null value, but useNullValue " + "is false.",
          values[i] != null || useNullValue());
      assertTrue(
          "failure in test: found null new value, but useNullValue " + "is false.",
          newValues[i] != null || useNullValue());
      assertTrue(
          "failure in test: values should not be the same as new value",
          values[i] != newValues[i] && (values[i] == null || !values[i].equals(newValues[i])));
    }
  }

  // tests begin here.  Each test adds a little bit of tested functionality.
  // Many methods assume previous methods passed.  That is, they do not
  // exhaustively recheck things that have already been checked in a previous
  // test methods.

  /**
   * Test to ensure that makeEmptyMap and makeFull returns a new non-null map with each invocation.
   */
  public void testMakeMap() {
    Map em = makeEmptyMap();
    assertTrue("failure in test: makeEmptyMap must return a non-null map.", em != null);

    Map em2 = makeEmptyMap();
    assertTrue("failure in test: makeEmptyMap must return a non-null map.", em != null);

    assertTrue(
        "failure in test: makeEmptyMap must return a new map " + "with each invocation.",
        em != em2);

    Map fm = makeFullMap();
    assertTrue("failure in test: makeFullMap must return a non-null map.", fm != null);

    Map fm2 = makeFullMap();
    assertTrue("failure in test: makeFullMap must return a non-null map.", fm != null);

    assertTrue(
        "failure in test: makeFullMap must return a new map " + "with each invocation.", fm != fm2);
  }

  /** Tests Map.isEmpty() */
  public void testMapIsEmpty() {

    resetEmpty();
    assertEquals("Map.isEmpty() should return true with an empty map", true, map.isEmpty());
    verify();

    resetFull();
    assertEquals("Map.isEmpty() should return false with a non-empty map", false, map.isEmpty());
    verify();
  }

  /** Tests Map.size() */
  public void testMapSize() {
    resetEmpty();
    assertEquals("Map.size() should be 0 with an empty map", 0, map.size());
    verify();

    resetFull();
    assertEquals(
        "Map.size() should equal the number of entries " + "in the map",
        getSampleKeys().length,
        map.size());
    verify();
  }

  /**
   * Tests {@link Map#clear()}. If the map {@link #isAddRemoveModifiable() can add and remove
   * elements}, then {@link Map#size()} and {@link Map#isEmpty()} are used to ensure that map has no
   * elements after a call to clear. If the map does not support adding and removing elements, this
   * method checks to ensure clear throws an UnsupportedOperationException.
   */
  public void testMapClear() {
    if (!isAddRemoveModifiable()) {
      return;
    }

    resetEmpty();
    map.clear();
    confirmed.clear();
    verify();

    resetFull();
    map.clear();
    confirmed.clear();
    verify();
  }

  /**
   * Tests Map.containsKey(Object) by verifying it returns false for all sample keys on a map
   * created using an empty map and returns true for all sample keys returned on a full map.
   */
  public void testMapContainsKey() {
    Object[] keys = getSampleKeys();

    resetEmpty();
    for (int i = 0; i < keys.length; i++) {
      assertTrue("Map must not contain key when map is empty", !map.containsKey(keys[i]));
    }
    verify();

    resetFull();
    for (int i = 0; i < keys.length; i++) {
      assertTrue(
          "Map must contain key for a mapping in the map. " + "Missing: " + keys[i],
          map.containsKey(keys[i]));
    }
    verify();
  }

  /**
   * Tests Map.containsValue(Object) by verifying it returns false for all sample values on an empty
   * map and returns true for all sample values on a full map.
   */
  public void testMapContainsValue() {
    Object[] values = getSampleValues();

    resetEmpty();
    for (int i = 0; i < values.length; i++) {
      assertTrue("Empty map must not contain value", !map.containsValue(values[i]));
    }
    verify();

    resetFull();
    for (int i = 0; i < values.length; i++) {
      assertTrue("Map must contain value for a mapping in the map.", map.containsValue(values[i]));
    }
    verify();
  }

  /** Tests Map.equals(Object) */
  public void testMapEquals() {
    resetEmpty();
    assertTrue("Empty maps unequal.", map.equals(confirmed));
    verify();

    resetFull();
    assertTrue("Full maps unequal.", map.equals(confirmed));
    verify();

    resetFull();
    // modify the HashMap created from the full map and make sure this
    // change results in map.equals() to return false.
    Iterator iter = confirmed.keySet().iterator();
    iter.next();
    iter.remove();
    assertTrue("Different maps equal.", !map.equals(confirmed));

    resetFull();
    assertTrue("equals(null) returned true.", !map.equals(null));
    assertTrue("equals(new Object()) returned true.", !map.equals(new Object()));
    verify();
  }

  /** Tests Map.get(Object) */
  public void testMapGet() {
    resetEmpty();

    Object[] keys = getSampleKeys();
    Object[] values = getSampleValues();

    for (int i = 0; i < keys.length; i++) {
      assertTrue("Empty map.get() should return null.", map.get(keys[i]) == null);
    }
    verify();

    resetFull();
    for (int i = 0; i < keys.length; i++) {
      assertEquals("Full map.get() should return value from mapping.", values[i], map.get(keys[i]));
    }
  }

  /** Tests Map.hashCode() */
  public void testMapHashCode() {
    resetEmpty();
    assertTrue("Empty maps have different hashCodes.", map.hashCode() == confirmed.hashCode());

    resetFull();
    assertTrue("Equal maps have different hashCodes.", map.hashCode() == confirmed.hashCode());
  }

  /**
   * Tests Map.toString(). Since the format of the string returned by the toString() method is not
   * defined in the Map interface, there is no common way to test the results of the toString()
   * method. Thereforce, it is encouraged that Map implementations override this test with one that
   * checks the format matches any format defined in its API. This default implementation just
   * verifies that the toString() method does not return null.
   */
  public void testMapToString() {
    resetEmpty();
    assertTrue("Empty map toString() should not return null", map.toString() != null);
    verify();

    resetFull();
    assertTrue("Empty map toString() should not return null", map.toString() != null);
    verify();
  }

  /** Tests Map.put(Object, Object) */
  public void testMapPut() {
    if (!isAddRemoveModifiable()) {
      return;
    }

    resetEmpty();

    Object[] keys = getSampleKeys();
    Object[] values = getSampleValues();
    Object[] newValues = getNewSampleValues();

    for (int i = 0; i < keys.length; i++) {
      Object o = map.put(keys[i], values[i]);
      confirmed.put(keys[i], values[i]);
      verify();
      assertTrue("First map.put should return null", o == null);
      assertTrue("Map should contain key after put", map.containsKey(keys[i]));
      assertTrue("Map should contain value after put", map.containsValue(values[i]));
    }

    for (int i = 0; i < keys.length; i++) {
      Object o = map.put(keys[i], newValues[i]);
      confirmed.put(keys[i], newValues[i]);
      verify();
      assertEquals("Second map.put should return previous value", values[i], o);
      assertTrue("Map should still contain key after put", map.containsKey(keys[i]));
      assertTrue("Map should contain new value after put", map.containsValue(newValues[i]));

      // if duplicates are allowed, we're not guarunteed that the value
      // no longer exists, so don't try checking that.
      if (!useDuplicateValues()) {
        assertTrue(
            "Map should not contain old value after second put", !map.containsValue(values[i]));
      }
    }
  }

  /** Tests Map.putAll(Collection) */
  public void testMapPutAll() {
    if (!isAddRemoveModifiable()) {
      return;
    }

    resetEmpty();

    Map m2 = makeFullMap();

    map.putAll(m2);
    confirmed.putAll(m2);
    verify();

    resetEmpty();

    m2 = new HashMap();
    Object[] keys = getSampleKeys();
    Object[] values = getSampleValues();
    for (int i = 0; i < keys.length; i++) {
      m2.put(keys[i], values[i]);
    }

    map.putAll(m2);
    confirmed.putAll(m2);
    verify();
  }

  /** Tests Map.remove(Object) */
  public void testMapRemove() {
    if (!isAddRemoveModifiable()) {
      return;
    }

    resetEmpty();

    Object[] keys = getSampleKeys();
    Object[] values = getSampleValues();
    for (int i = 0; i < keys.length; i++) {
      Object o = map.remove(keys[i]);
      assertTrue("First map.remove should return null", o == null);
    }
    verify();

    resetFull();

    for (int i = 0; i < keys.length; i++) {
      Object o = map.remove(keys[i]);
      confirmed.remove(keys[i]);
      verify();

      assertEquals("map.remove with valid key should return value", values[i], o);
    }

    Object[] other = getOtherKeys();

    resetFull();
    int size = map.size();
    for (int i = 0; i < other.length; i++) {
      Object o = map.remove(other[i]);
      assertEquals("map.remove for nonexistent key should return null", o, null);
      assertEquals("map.remove for nonexistent key should not " + "shrink map", size, map.size());
    }
    verify();
  }

  public void testFailFastEntrySet() {
    if (!isAddRemoveModifiable()) {
      return;
    }
    if (!isFailFastExpected()) {
      return;
    }
    resetFull();
    Iterator<Map.Entry> it = map.entrySet().iterator();
    final Map.Entry val = it.next();
    map.remove(val.getKey());
    try {
      it.next();
      fail();
    } catch (ConcurrentModificationException expected) {
    }

    resetFull();
    it = map.entrySet().iterator();
    it.next();
    map.clear();
    try {
      it.next();
      fail();
    } catch (ConcurrentModificationException expected) {
    }
  }

  public void testFailFastKeySet() {
    if (!isAddRemoveModifiable()) {
      return;
    }
    if (!isFailFastExpected()) {
      return;
    }
    resetFull();
    Iterator it = map.keySet().iterator();
    final Object val = it.next();
    map.remove(val);
    try {
      it.next();
      fail();
    } catch (ConcurrentModificationException expected) {
    }

    resetFull();
    it = map.keySet().iterator();
    it.next();
    map.clear();
    try {
      it.next();
      fail();
    } catch (ConcurrentModificationException expected) {
    }
  }

  public void testFailFastValues() {
    if (!isAddRemoveModifiable()) {
      return;
    }
    if (!isFailFastExpected()) {
      return;
    }
    resetFull();
    Iterator it = map.values().iterator();
    it.next();
    map.remove(map.keySet().iterator().next());
    try {
      it.next();
      fail();
    } catch (ConcurrentModificationException expected) {
    }

    resetFull();
    it = map.values().iterator();
    it.next();
    map.clear();
    try {
      it.next();
      fail();
    } catch (ConcurrentModificationException expected) {
    }
  }

  /**
   * Utility methods to create an array of Map.Entry objects out of the given key and value arrays.
   *
   * <p>
   *
   * @param keys the array of keys
   * @param values the array of values
   * @return an array of Map.Entry of those keys to those values
   */
  private Map.Entry[] makeEntryArray(Object[] keys, Object[] values) {
    Map.Entry[] result = new Map.Entry[keys.length];
    for (int i = 0; i < keys.length; i++) {
      result[i] = new DefaultMapEntry(keys[i], values[i]);
    }
    return result;
  }

  class TestMapEntrySet extends TestSet {
    public TestMapEntrySet() {
      super("");
    }

    // Have to implement manually; entrySet doesn't support addAll
    @Override
    protected Object[] getFullElements() {
      Object[] k = getSampleKeys();
      Object[] v = getSampleValues();
      return makeEntryArray(k, v);
    }

    // Have to implement manually; entrySet doesn't support addAll
    @Override
    protected Object[] getOtherElements() {
      Object[] k = getOtherKeys();
      Object[] v = getOtherValues();
      return makeEntryArray(k, v);
    }

    @Override
    protected Set makeEmptySet() {
      return makeEmptyMap().entrySet();
    }

    @Override
    protected Set makeFullSet() {
      return makeFullMap().entrySet();
    }

    @Override
    protected boolean isAddSupported() {
      // Collection views don't support add operations.
      return false;
    }

    @Override
    protected boolean isRemoveSupported() {
      // Entry set should only support remove if map does
      return isAddRemoveModifiable();
    }

    @Override
    protected void resetFull() {
      TestMap.this.resetFull();
      collection = map.entrySet();
      TestMapEntrySet.this.confirmed = TestMap.this.confirmed.entrySet();
    }

    @Override
    protected void resetEmpty() {
      TestMap.this.resetEmpty();
      collection = map.entrySet();
      TestMapEntrySet.this.confirmed = TestMap.this.confirmed.entrySet();
    }

    @Override
    protected void verify() {
      super.verify();
      TestMap.this.verify();
    }
  }

  class TestMapKeySet extends TestSet {
    public TestMapKeySet() {
      super("");
    }

    @Override
    protected Object[] getFullElements() {
      return getSampleKeys();
    }

    @Override
    protected Object[] getOtherElements() {
      return getOtherKeys();
    }

    @Override
    protected Set makeEmptySet() {
      return makeEmptyMap().keySet();
    }

    @Override
    protected Set makeFullSet() {
      return makeFullMap().keySet();
    }

    @Override
    protected boolean isAddSupported() {
      return false;
    }

    @Override
    protected boolean isRemoveSupported() {
      return isAddRemoveModifiable();
    }

    @Override
    protected void resetEmpty() {
      TestMap.this.resetEmpty();
      collection = map.keySet();
      TestMapKeySet.this.confirmed = TestMap.this.confirmed.keySet();
    }

    @Override
    protected void resetFull() {
      TestMap.this.resetFull();
      collection = map.keySet();
      TestMapKeySet.this.confirmed = TestMap.this.confirmed.keySet();
    }

    @Override
    protected void verify() {
      super.verify();
      TestMap.this.verify();
    }
  }

  class TestMapValues extends TestCollection {
    public TestMapValues() {}

    @Override
    protected Object[] getFullElements() {
      return getSampleValues();
    }

    @Override
    protected Object[] getOtherElements() {
      return getOtherValues();
    }

    @Override
    protected Collection makeCollection() {
      return makeEmptyMap().values();
    }

    @Override
    protected Collection makeFullCollection() {
      return makeFullMap().values();
    }

    @Override
    protected boolean isAddSupported() {
      return false;
    }

    @Override
    protected boolean isRemoveSupported() {
      return isAddRemoveModifiable();
    }

    @Override
    protected boolean areEqualElementsDistinguishable() {
      // equal values are associated with different keys, so they are
      // distinguishable.
      return true;
    }

    @Override
    protected Collection makeConfirmedCollection() {
      // never gets called, reset methods are overridden
      return null;
    }

    @Override
    protected Collection makeConfirmedFullCollection() {
      // never gets called, reset methods are overridden
      return null;
    }

    @Override
    protected void resetFull() {
      TestMap.this.resetFull();
      collection = map.values();
      TestMapValues.this.confirmed = TestMap.this.confirmed.values();
    }

    @Override
    protected void resetEmpty() {
      TestMap.this.resetEmpty();
      collection = map.values();
      TestMapValues.this.confirmed = TestMap.this.confirmed.values();
    }

    @Override
    protected void verify() {
      super.verify();
      TestMap.this.verify();
    }

    // TODO: should test that a remove on the values collection view
    // removes the proper mapping and not just any mapping that may have
    // the value equal to the value returned from the values iterator.
  }

  /**
   * Resets the {@link #map}, {@link #entrySet}, {@link #keySet}, {@link #collectionValues} and
   * {@link #confirmed} fields to empty.
   */
  protected void resetEmpty() {
    this.map = makeEmptyMap();
    views();
    this.confirmed = makeConfirmedMap();
  }

  /**
   * Resets the {@link #map}, {@link #entrySet}, {@link #keySet}, {@link #collectionValues} and
   * {@link #confirmed} fields to full.
   */
  protected void resetFull() {
    this.map = makeFullMap();
    views();
    this.confirmed = makeConfirmedMap();
    Object[] k = getSampleKeys();
    Object[] v = getSampleValues();
    for (int i = 0; i < k.length; i++) {
      confirmed.put(k[i], v[i]);
    }
  }

  /** Resets the collection view fields. */
  private void views() {
    this.keySet = map.keySet();
    this.collectionValues = map.values();
    this.entrySet = map.entrySet();
  }

  /**
   * Verifies that {@link #map} is still equal to {@link #confirmed}. This method checks that the
   * map is equal to the HashMap, <I>and</I> that the map's collection views are still equal to the
   * HashMap's collection views. An <Code>equals</Code> test is done on the maps and their
   * collection views; their size and <Code>isEmpty</Code> results are compared; their hashCodes are
   * compared; and <Code>containsAll</Code> tests are run on the collection views.
   */
  protected void verify() {
    verifyMap();
    verifyEntrySet();
    verifyKeySet();
  }

  protected void verifyMap() {
    int size = confirmed.size();
    boolean empty = confirmed.isEmpty();
    assertEquals("Map should be same size as HashMap", size, map.size());
    assertEquals("Map should be empty if HashMap is", empty, map.isEmpty());
    assertEquals("hashCodes should be the same", confirmed.hashCode(), map.hashCode());
    // this fails for LRUMap because confirmed.equals() somehow modifies
    // map, causing concurrent modification exceptions.
    // assertEquals("Map should still equal HashMap", confirmed, map);
    // this works though and performs the same verification:
    assertTrue("Map should still equal HashMap", map.equals(confirmed));
    // TODO: this should really be rexamined to figure out why LRU map
    // behaves like it does (the equals shouldn't modify since all accesses
    // by the confirmed collection should be through an iterator, thus not
    // causing LRUMap to change).
  }

  protected void verifyEntrySet() {
    int size = confirmed.size();
    boolean empty = confirmed.isEmpty();
    assertEquals("entrySet should be same size as HashMap's", size, entrySet.size());
    assertEquals("entrySet should be empty if HashMap is", empty, entrySet.isEmpty());
    assertTrue(
        "entrySet should contain all HashMap's elements",
        entrySet.containsAll(confirmed.entrySet()));
    assertEquals(
        "entrySet hashCodes should be the same",
        confirmed.entrySet().hashCode(),
        entrySet.hashCode());
    assertEquals("Map's entry set should still equal HashMap's", confirmed.entrySet(), entrySet);
  }

  protected void verifyKeySet() {
    int size = confirmed.size();
    boolean empty = confirmed.isEmpty();
    assertEquals("keySet should be same size as HashMap's", size, keySet.size());
    assertEquals("keySet should be empty if HashMap is", empty, keySet.isEmpty());
    assertTrue(
        "keySet should contain all HashMap's elements", keySet.containsAll(confirmed.keySet()));
    assertEquals(
        "keySet hashCodes should be the same", confirmed.keySet().hashCode(), keySet.hashCode());
    assertEquals("Map's key set should still equal HashMap's", confirmed.keySet(), keySet);
  }
}