/*

 * Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package java.util;

import java.io.*;

/**

 * This class implements the <tt>Map</tt> interface with a hash table, using

 * reference-equality in place of object-equality when comparing keys (and

 * values).  In other words, in an <tt>IdentityHashMap</tt>, two keys

 * <tt>k1</tt> and <tt>k2</tt> are considered equal if and only if

 * <tt>(k1==k2)</tt>.  (In normal <tt>Map</tt> implementations (like

 * <tt>HashMap</tt>) two keys <tt>k1</tt> and <tt>k2</tt> are considered equal

 * if and only if <tt>(k1==null ? k2==null : k1.equals(k2))</tt>.)

 *

 * <p><b>This class is <i>not</i> a general-purpose <tt>Map</tt>

 * implementation!  While this class implements the <tt>Map</tt> interface, it

 * intentionally violates <tt>Map's</tt> general contract, which mandates the

 * use of the <tt>equals</tt> method when comparing objects.  This class is

 * designed for use only in the rare cases wherein reference-equality

 * semantics are required.</b>

 *

 * <p>A typical use of this class is <i>topology-preserving object graph

 * transformations</i>, such as serialization or deep-copying.  To perform such

 * a transformation, a program must maintain a "node table" that keeps track

 * of all the object references that have already been processed.  The node

 * table must not equate distinct objects even if they happen to be equal.

 * Another typical use of this class is to maintain <i>proxy objects</i>.  For

 * example, a debugging facility might wish to maintain a proxy object for

 * each object in the program being debugged.

 *

 * <p>This class provides all of the optional map operations, and permits

 * <tt>null</tt> values and the <tt>null</tt> key.  This class makes no

 * guarantees as to the order of the map; in particular, it does not guarantee

 * that the order will remain constant over time.

 *

 * <p>This class provides constant-time performance for the basic

 * operations (<tt>get</tt> and <tt>put</tt>), assuming the system

 * identity hash function ({@link System#identityHashCode(Object)})

 * disperses elements properly among the buckets.

 *

 * <p>This class has one tuning parameter (which affects performance but not

 * semantics): <i>expected maximum size</i>.  This parameter is the maximum

 * number of key-value mappings that the map is expected to hold.  Internally,

 * this parameter is used to determine the number of buckets initially

 * comprising the hash table.  The precise relationship between the expected

 * maximum size and the number of buckets is unspecified.

 *

 * <p>If the size of the map (the number of key-value mappings) sufficiently

 * exceeds the expected maximum size, the number of buckets is increased

 * Increasing the number of buckets ("rehashing") may be fairly expensive, so

 * it pays to create identity hash maps with a sufficiently large expected

 * maximum size.  On the other hand, iteration over collection views requires

 * time proportional to the number of buckets in the hash table, so it

 * pays not to set the expected maximum size too high if you are especially

 * concerned with iteration performance or memory usage.

 *

 * <p><strong>Note that this implementation is not synchronized.</strong>

 * If multiple threads access an identity hash map concurrently, and at

 * least one of the threads modifies the map structurally, it <i>must</i>

 * be synchronized externally.  (A structural modification is any operation

 * that adds or deletes one or more mappings; merely changing the value

 * associated with a key that an instance already contains is not a

 * structural modification.)  This is typically accomplished by

 * synchronizing on some object that naturally encapsulates the map.

 *

 * If no such object exists, the map should be "wrapped" using the

 * {@link Collections#synchronizedMap Collections.synchronizedMap}

 * method.  This is best done at creation time, to prevent accidental

 * unsynchronized access to the map:<pre>

 *   Map m = Collections.synchronizedMap(new IdentityHashMap(...));</pre>

 *

 * <p>The iterators returned by the <tt>iterator</tt> method of the

 * collections returned by all of this class's "collection view

 * methods" are <i>fail-fast</i>: if the map is structurally modified

 * at any time after the iterator is created, in any way except

 * through the iterator's own <tt>remove</tt> method, the iterator

 * will throw a {@link ConcurrentModificationException}.  Thus, in the

 * face of concurrent modification, the iterator fails quickly and

 * cleanly, rather than risking arbitrary, non-deterministic behavior

 * at an undetermined time in the future.

 *

 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed

 * as it is, generally speaking, impossible to make any hard guarantees in the

 * presence of unsynchronized concurrent modification.  Fail-fast iterators

 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.

 * Therefore, it would be wrong to write a program that depended on this

 * exception for its correctness: <i>fail-fast iterators should be used only

 * to detect bugs.</i>

 *

 * <p>Implementation note: This is a simple <i>linear-probe</i> hash table,

 * as described for example in texts by Sedgewick and Knuth.  The array

 * alternates holding keys and values.  (This has better locality for large

 * tables than does using separate arrays.)  For many JRE implementations

 * and operation mixes, this class will yield better performance than

 * {@link HashMap} (which uses <i>chaining</i> rather than linear-probing).

 *

 * <p>This class is a member of the

 * <a href="{@docRoot}/../technotes/guides/collections/index.html">

 * Java Collections Framework</a>.

 *

 * @see     System#identityHashCode(Object)

 * @see     Object#hashCode()

 * @see     Collection

 * @see     Map

 * @see     HashMap

 * @see     TreeMap

 * @author  Doug Lea and Josh Bloch

 * @since   1.4

 */

public class IdentityHashMap<K,V>

    extends AbstractMap<K,V>

    implements Map<K,V>, java.io.Serializable, Cloneable

{

    /**

     * The initial capacity used by the no-args constructor.

     * MUST be a power of two.  The value 32 corresponds to the

     * (specified) expected maximum size of 21, given a load factor

     * of 2/3.

     */

    private static final int DEFAULT_CAPACITY = 32;

    /**

     * The minimum capacity, used if a lower value is implicitly specified

     * by either of the constructors with arguments.  The value 4 corresponds

     * to an expected maximum size of 2, given a load factor of 2/3.

     * MUST be a power of two.

     */

    private static final int MINIMUM_CAPACITY = 4;

    /**

     * The maximum capacity, used if a higher value is implicitly specified

     * by either of the constructors with arguments.

     * MUST be a power of two <= 1<<29.

     */

    private static final int MAXIMUM_CAPACITY = 1 << 29;

    /**

     * The table, resized as necessary. Length MUST always be a power of two.

     */

    private transient Object[] table;

    /**

     * The number of key-value mappings contained in this identity hash map.

     *

     * @serial

     */

    private int size;

    /**

     * The number of modifications, to support fast-fail iterators

     */

    private transient int modCount;

    /**

     * The next size value at which to resize (capacity * load factor).

     */

    private transient int threshold;

    /**

     * Value representing null keys inside tables.

     */

    private static final Object NULL_KEY = new Object();

    /**

     * Use NULL_KEY for key if it is null.

     */

    private static Object maskNull(Object key) {

        return (key == null ? NULL_KEY : key);

    }

    /**

     * Returns internal representation of null key back to caller as null.

     */

    private static Object unmaskNull(Object key) {

        return (key == NULL_KEY ? null : key);

    }

    /**

     * Constructs a new, empty identity hash map with a default expected

     * maximum size (21).

     */

    public IdentityHashMap() {

        init(DEFAULT_CAPACITY);

    }

    /**

     * Constructs a new, empty map with the specified expected maximum size.

     * Putting more than the expected number of key-value mappings into

     * the map may cause the internal data structure to grow, which may be

     * somewhat time-consuming.

     *

     * @param expectedMaxSize the expected maximum size of the map

     * @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative

     */

    public IdentityHashMap(int expectedMaxSize) {

        if (expectedMaxSize < 0)

            throw new IllegalArgumentException("expectedMaxSize is negative: "

                                               + expectedMaxSize);

        init(capacity(expectedMaxSize));

    }

    /**

     * Returns the appropriate capacity for the specified expected maximum

     * size.  Returns the smallest power of two between MINIMUM_CAPACITY

     * and MAXIMUM_CAPACITY, inclusive, that is greater than

     * (3 * expectedMaxSize)/2, if such a number exists.  Otherwise

     * returns MAXIMUM_CAPACITY.  If (3 * expectedMaxSize)/2 is negative, it

     * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.

     */

    private int capacity(int expectedMaxSize) {

        // Compute min capacity for expectedMaxSize given a load factor of 2/3

        int minCapacity = (3 * expectedMaxSize)/2;

        // Compute the appropriate capacity

        int result;

        if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {

            result = MAXIMUM_CAPACITY;

        } else {

            result = MINIMUM_CAPACITY;

            while (result < minCapacity)

                result <<= 1;

        }

        return result;

    }

    /**

     * Initializes object to be an empty map with the specified initial

     * capacity, which is assumed to be a power of two between

     * MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.

     */

    private void init(int initCapacity) {

        // assert (initCapacity & -initCapacity) == initCapacity; // power of 2

        // assert initCapacity >= MINIMUM_CAPACITY;

        // assert initCapacity <= MAXIMUM_CAPACITY;

        threshold = (initCapacity * 2)/3;

        table = new Object[2 * initCapacity];

    }

    /**

     * Constructs a new identity hash map containing the keys-value mappings

     * in the specified map.

     *

     * @param m the map whose mappings are to be placed into this map

     * @throws NullPointerException if the specified map is null

     */

    public IdentityHashMap(Map<? extends K, ? extends V> m) {

        // Allow for a bit of growth

        this((int) ((1 + m.size()) * 1.1));

        putAll(m);

    }

    /**

     * Returns the number of key-value mappings in this identity hash map.

     *

     * @return the number of key-value mappings in this map

     */

    public int size() {

        return size;

    }

    /**

     * Returns <tt>true</tt> if this identity hash map contains no key-value

     * mappings.

     *

     * @return <tt>true</tt> if this identity hash map contains no key-value

     *         mappings

     */

    public boolean isEmpty() {

        return size == 0;

    }

    /**

     * Returns index for Object x.

     */

    private static int hash(Object x, int length) {

        int h = System.identityHashCode(x);

        // Multiply by -127, and left-shift to use least bit as part of hash

        return ((h << 1) - (h << 8)) & (length - 1);

    }

    /**

     * Circularly traverses table of size len.

     */

    private static int nextKeyIndex(int i, int len) {

        return (i + 2 < len ? i + 2 : 0);

    }

    /**

     * Returns the value to which the specified key is mapped,

     * or {@code null} if this map contains no mapping for the key.

     *

     * <p>More formally, if this map contains a mapping from a key

     * {@code k} to a value {@code v} such that {@code (key == k)},

     * then this method returns {@code v}; otherwise it returns

     * {@code null}.  (There can be at most one such mapping.)

     *

     * <p>A return value of {@code null} does not <i>necessarily</i>

     * indicate that the map contains no mapping for the key; it's also

     * possible that the map explicitly maps the key to {@code null}.

     * The {@link #containsKey containsKey} operation may be used to

     * distinguish these two cases.

     *

     * @see #put(Object, Object)

     */

    public V get(Object key) {

        Object k = maskNull(key);

        Object[] tab = table;

        int len = tab.length;

        int i = hash(k, len);

        while (true) {

            Object item = tab[i];

            if (item == k)

                return (V) tab[i + 1];

            if (item == null)

                return null;

            i = nextKeyIndex(i, len);

        }

    }

    /**

     * Tests whether the specified object reference is a key in this identity

     * hash map.

     *

     * @param   key   possible key

     * @return  <code>true</code> if the specified object reference is a key

     *          in this map

     * @see     #containsValue(Object)

     */

    public boolean containsKey(Object key) {

        Object k = maskNull(key);

        Object[] tab = table;

        int len = tab.length;

        int i = hash(k, len);

        while (true) {

            Object item = tab[i];

            if (item == k)

                return true;

            if (item == null)

                return false;

            i = nextKeyIndex(i, len);

        }

    }

    /**

     * Tests whether the specified object reference is a value in this identity

     * hash map.

     *

     * @param value value whose presence in this map is to be tested

     * @return <tt>true</tt> if this map maps one or more keys to the

     *         specified object reference

     * @see     #containsKey(Object)

     */

    public boolean containsValue(Object value) {

        Object[] tab = table;

        for (int i = 1; i < tab.length; i += 2)

            if (tab[i] == value && tab[i - 1] != null)

                return true;

        return false;

    }

    /**

     * Tests if the specified key-value mapping is in the map.

     *

     * @param   key   possible key

     * @param   value possible value

     * @return  <code>true</code> if and only if the specified key-value

     *          mapping is in the map

     */

    private boolean containsMapping(Object key, Object value) {

        Object k = maskNull(key);

        Object[] tab = table;

        int len = tab.length;

        int i = hash(k, len);

        while (true) {

            Object item = tab[i];

            if (item == k)

                return tab[i + 1] == value;

            if (item == null)

                return false;

            i = nextKeyIndex(i, len);

        }

    }

    /**

     * Associates the specified value with the specified key in this identity

     * hash map.  If the map previously contained a mapping for the key, the

     * old value is replaced.

     *

     * @param key the key with which the specified value is to be associated

     * @param value the value to be associated with the specified key

     * @return the previous value associated with <tt>key</tt>, or

     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.

     *         (A <tt>null</tt> return can also indicate that the map

     *         previously associated <tt>null</tt> with <tt>key</tt>.)

     * @see     Object#equals(Object)

     * @see     #get(Object)

     * @see     #containsKey(Object)

     */

    public V put(K key, V value) {

        Object k = maskNull(key);

        Object[] tab = table;

        int len = tab.length;

        int i = hash(k, len);

        Object item;

        while ( (item = tab[i]) != null) {

            if (item == k) {

                V oldValue = (V) tab[i + 1];

                tab[i + 1] = value;

                return oldValue;

            }

            i = nextKeyIndex(i, len);

        }

        modCount++;

        tab[i] = k;

        tab[i + 1] = value;

        if (++size >= threshold)

            resize(len); // len == 2 * current capacity.

        return null;

    }

    /**

     * Resize the table to hold given capacity.

     *

     * @param newCapacity the new capacity, must be a power of two.

     */

    private void resize(int newCapacity) {

        // assert (newCapacity & -newCapacity) == newCapacity; // power of 2

        int newLength = newCapacity * 2;

        Object[] oldTable = table;

        int oldLength = oldTable.length;

        if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further

            if (threshold == MAXIMUM_CAPACITY-1)

                throw new IllegalStateException("Capacity exhausted.");

            threshold = MAXIMUM_CAPACITY-1;  // Gigantic map!

            return;

        }

        if (oldLength >= newLength)

            return;

        Object[] newTable = new Object[newLength];

        threshold = newLength / 3;

        for (int j = 0; j < oldLength; j += 2) {

            Object key = oldTable[j];

            if (key != null) {

                Object value = oldTable[j+1];

                oldTable[j] = null;

                oldTable[j+1] = null;

                int i = hash(key, newLength);

                while (newTable[i] != null)

                    i = nextKeyIndex(i, newLength);

                newTable[i] = key;

                newTable[i + 1] = value;

            }

        }

        table = newTable;

    }

    /**

     * Copies all of the mappings from the specified map to this map.

     * These mappings will replace any mappings that this map had for

     * any of the keys currently in the specified map.

     *

     * @param m mappings to be stored in this map

     * @throws NullPointerException if the specified map is null

     */

    public void putAll(Map<? extends K, ? extends V> m) {

        int n = m.size();

        if (n == 0)

            return;

        if (n > threshold) // conservatively pre-expand

            resize(capacity(n));

        for (Entry<? extends K, ? extends V> e : m.entrySet())

            put(e.getKey(), e.getValue());

    }

    /**

     * Removes the mapping for this key from this map if present.

     *

     * @param key key whose mapping is to be removed from the map

     * @return the previous value associated with <tt>key</tt>, or

     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.

     *         (A <tt>null</tt> return can also indicate that the map

     *         previously associated <tt>null</tt> with <tt>key</tt>.)

     */

    public V remove(Object key) {

        Object k = maskNull(key);

        Object[] tab = table;

        int len = tab.length;

        int i = hash(k, len);

        while (true) {

            Object item = tab[i];

            if (item == k) {

                modCount++;

                size--;

                V oldValue = (V) tab[i + 1];

                tab[i + 1] = null;

                tab[i] = null;

                closeDeletion(i);

                return oldValue;

            }

            if (item == null)

                return null;

            i = nextKeyIndex(i, len);

        }

    }

    /**

     * Removes the specified key-value mapping from the map if it is present.

     *

     * @param   key   possible key

     * @param   value possible value

     * @return  <code>true</code> if and only if the specified key-value

     *          mapping was in the map

     */

    private boolean removeMapping(Object key, Object value) {

        Object k = maskNull(key);

        Object[] tab = table;

        int len = tab.length;

        int i = hash(k, len);

        while (true) {

            Object item = tab[i];

            if (item == k) {

                if (tab[i + 1] != value)

                    return false;

                modCount++;

                size--;

                tab[i] = null;

                tab[i + 1] = null;

                closeDeletion(i);

                return true;

            }

            if (item == null)

                return false;

            i = nextKeyIndex(i, len);

        }

    }

    /**

     * Rehash all possibly-colliding entries following a

     * deletion. This preserves the linear-probe

     * collision properties required by get, put, etc.

     *

     * @param d the index of a newly empty deleted slot

     */

    private void closeDeletion(int d) {

        // Adapted from Knuth Section 6.4 Algorithm R

        Object[] tab = table;

        int len = tab.length;

        // Look for items to swap into newly vacated slot

        // starting at index immediately following deletion,

        // and continuing until a null slot is seen, indicating

        // the end of a run of possibly-colliding keys.

        Object item;

        for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;

             i = nextKeyIndex(i, len) ) {

            // The following test triggers if the item at slot i (which

            // hashes to be at slot r) should take the spot vacated by d.

            // If so, we swap it in, and then continue with d now at the

            // newly vacated i.  This process will terminate when we hit

            // the null slot at the end of this run.

            // The test is messy because we are using a circular table.

            int r = hash(item, len);

            if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {

                tab[d] = item;

                tab[d + 1] = tab[i + 1];

                tab[i] = null;

                tab[i + 1] = null;

                d = i;

            }

        }

    }

    /**

     * Removes all of the mappings from this map.

     * The map will be empty after this call returns.

     */

    public void clear() {

        modCount++;

        Object[] tab = table;

        for (int i = 0; i < tab.length; i++)

            tab[i] = null;

        size = 0;

    }

    /**

     * Compares the specified object with this map for equality.  Returns

     * <tt>true</tt> if the given object is also a map and the two maps

     * represent identical object-reference mappings.  More formally, this

     * map is equal to another map <tt>m</tt> if and only if

     * <tt>this.entrySet().equals(m.entrySet())</tt>.

     *

     * <p><b>Owing to the reference-equality-based semantics of this map it is

     * possible that the symmetry and transitivity requirements of the

     * <tt>Object.equals</tt> contract may be violated if this map is compared

     * to a normal map.  However, the <tt>Object.equals</tt> contract is

     * guaranteed to hold among <tt>IdentityHashMap</tt> instances.</b>

     *

     * @param  o object to be compared for equality with this map

     * @return <tt>true</tt> if the specified object is equal to this map

     * @see Object#equals(Object)

     */

    public boolean equals(Object o) {

        if (o == this) {

            return true;

        } else if (o instanceof IdentityHashMap) {

            IdentityHashMap m = (IdentityHashMap) o;

            if (m.size() != size)

                return false;

            Object[] tab = m.table;

            for (int i = 0; i < tab.length; i+=2) {

                Object k = tab[i];

                if (k != null && !containsMapping(k, tab[i + 1]))

                    return false;

            }

            return true;

        } else if (o instanceof Map) {

            Map m = (Map)o;

            return entrySet().equals(m.entrySet());

        } else {

            return false;  // o is not a Map

        }

    }

    /**

     * Returns the hash code value for this map.  The hash code of a map is

     * defined to be the sum of the hash codes of each entry in the map's

     * <tt>entrySet()</tt> view.  This ensures that <tt>m1.equals(m2)</tt>

     * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two

     * <tt>IdentityHashMap</tt> instances <tt>m1</tt> and <tt>m2</tt>, as

     * required by the general contract of {@link Object#hashCode}.

     *

     * <p><b>Owing to the reference-equality-based semantics of the

     * <tt>Map.Entry</tt> instances in the set returned by this map's

     * <tt>entrySet</tt> method, it is possible that the contractual

     * requirement of <tt>Object.hashCode</tt> mentioned in the previous

     * paragraph will be violated if one of the two objects being compared is

     * an <tt>IdentityHashMap</tt> instance and the other is a normal map.</b>

     *

     * @return the hash code value for this map

     * @see Object#equals(Object)

     * @see #equals(Object)

     */

    public int hashCode() {

        int result = 0;

        Object[] tab = table;

        for (int i = 0; i < tab.length; i +=2) {

            Object key = tab[i];

            if (key != null) {

                Object k = unmaskNull(key);

                result += System.identityHashCode(k) ^

                          System.identityHashCode(tab[i + 1]);

            }

        }

        return result;

    }

    /**

     * Returns a shallow copy of this identity hash map: the keys and values

     * themselves are not cloned.

     *

     * @return a shallow copy of this map

     */

    public Object clone() {

        try {

            IdentityHashMap<K,V> m = (IdentityHashMap<K,V>) super.clone();

            m.entrySet = null;

            m.table = table.clone();

            return m;

        } catch (CloneNotSupportedException e) {

            throw new InternalError();

        }

    }

    private abstract class IdentityHashMapIterator<T> implements Iterator<T> {

        int index = (size != 0 ? 0 : table.length); // current slot.

        int expectedModCount = modCount; // to support fast-fail

        int lastReturnedIndex = -1;      // to allow remove()

        boolean indexValid; // To avoid unnecessary next computation

        Object[] traversalTable = table; // reference to main table or copy

        public boolean hasNext() {

            Object[] tab = traversalTable;

            for (int i = index; i < tab.length; i+=2) {

                Object key = tab[i];

                if (key != null) {

                    index = i;

                    return indexValid = true;

                }

            }

            index = tab.length;

            return false;

        }

        protected int nextIndex() {

            if (modCount != expectedModCount)

                throw new ConcurrentModificationException();

            if (!indexValid && !hasNext())

                throw new NoSuchElementException();

            indexValid = false;

            lastReturnedIndex = index;

            index += 2;

            return lastReturnedIndex;

        }

        public void remove() {

            if (lastReturnedIndex == -1)

                throw new IllegalStateException();

            if (modCount != expectedModCount)

                throw new ConcurrentModificationException();

            expectedModCount = ++modCount;

            int deletedSlot = lastReturnedIndex;

            lastReturnedIndex = -1;

            // back up index to revisit new contents after deletion

            index = deletedSlot;

            indexValid = false;

            // Removal code proceeds as in closeDeletion except that

            // it must catch the rare case where an element already

            // seen is swapped into a vacant slot that will be later

            // traversed by this iterator. We cannot allow future

            // next() calls to return it again.  The likelihood of

            // this occurring under 2/3 load factor is very slim, but

            // when it does happen, we must make a copy of the rest of

            // the table to use for the rest of the traversal. Since

            // this can only happen when we are near the end of the table,

            // even in these rare cases, this is not very expensive in

            // time or space.

            Object[] tab = traversalTable;

            int len = tab.length;

            int d = deletedSlot;

            K key = (K) tab[d];

            tab[d] = null;        // vacate the slot

            tab[d + 1] = null;

            // If traversing a copy, remove in real table.

            // We can skip gap-closure on copy.

            if (tab != IdentityHashMap.this.table) {

                IdentityHashMap.this.remove(key);

                expectedModCount = modCount;

                return;

            }

            size--;

            Object item;

            for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;

                 i = nextKeyIndex(i, len)) {

                int r = hash(item, len);

                // See closeDeletion for explanation of this conditional

                if ((i < r && (r <= d || d <= i)) ||

                    (r <= d && d <= i)) {

                    // If we are about to swap an already-seen element

                    // into a slot that may later be returned by next(),

                    // then clone the rest of table for use in future

                    // next() calls. It is OK that our copy will have

                    // a gap in the "wrong" place, since it will never

                    // be used for searching anyway.

                    if (i < deletedSlot && d >= deletedSlot &&

                        traversalTable == IdentityHashMap.this.table) {

                        int remaining = len - deletedSlot;

                        Object[] newTable = new Object[remaining];

                        System.arraycopy(tab, deletedSlot,

                                         newTable, 0, remaining);

                        traversalTable = newTable;

                        index = 0;

                    }

                    tab[d] = item;

                    tab[d + 1] = tab[i + 1];

                    tab[i] = null;

                    tab[i + 1] = null;

                    d = i;

                }

            }

        }

    }

    private class KeyIterator extends IdentityHashMapIterator<K> {

        public K next() {

            return (K) unmaskNull(traversalTable[nextIndex()]);

        }

    }

    private class ValueIterator extends IdentityHashMapIterator<V> {

        public V next() {

            return (V) traversalTable[nextIndex() + 1];

        }

    }

    private class EntryIterator

        extends IdentityHashMapIterator<Map.Entry<K,V>>

    {

        private Entry lastReturnedEntry = null;

        public Map.Entry<K,V> next() {

            lastReturnedEntry = new Entry(nextIndex());

            return lastReturnedEntry;

        }

        public void remove() {

            lastReturnedIndex =

                ((null == lastReturnedEntry) ? -1 : lastReturnedEntry.index);

            super.remove();

            lastReturnedEntry.index = lastReturnedIndex;

            lastReturnedEntry = null;

        }

        private class Entry implements Map.Entry<K,V> {

            private int index;

            private Entry(int index) {

                this.index = index;

            }

            public K getKey() {

                checkIndexForEntryUse();

                return (K) unmaskNull(traversalTable[index]);

            }

            public V getValue() {

                checkIndexForEntryUse();

                return (V) traversalTable[index+1];

            }

            public V setValue(V value) {

                checkIndexForEntryUse();

                V oldValue = (V) traversalTable[index+1];

                traversalTable[index+1] = value;

                // if shadowing, force into main table

                if (traversalTable != IdentityHashMap.this.table)

                    put((K) traversalTable[index], value);

                return oldValue;

            }

            public boolean equals(Object o) {

                if (index < 0)

                    return super.equals(o);

                if (!(o instanceof Map.Entry))

                    return false;

                Map.Entry e = (Map.Entry)o;

                return (e.getKey() == unmaskNull(traversalTable[index]) &&

                       e.getValue() == traversalTable[index+1]);

            }

            public int hashCode() {

                if (lastReturnedIndex < 0)

                    return super.hashCode();

                return (System.identityHashCode(unmaskNull(traversalTable[index])) ^

                       System.identityHashCode(traversalTable[index+1]));

            }

            public String toString() {

                if (index < 0)

                    return super.toString();

                return (unmaskNull(traversalTable[index]) + "="

                        + traversalTable[index+1]);

            }

            private void checkIndexForEntryUse() {

                if (index < 0)

                    throw new IllegalStateException("Entry was removed");

            }

        }

    }

    // Views

    /**

     * This field is initialized to contain an instance of the entry set

     * view the first time this view is requested.  The view is stateless,

     * so there's no reason to create more than one.

     */

    private transient Set<Map.Entry<K,V>> entrySet = null;

    /**

     * Returns an identity-based set view of the keys contained in this map.

     * The set is backed by the map, so changes to the map are reflected in

     * the set, and vice-versa.  If the map is modified while an iteration

     * over the set is in progress, the results of the iteration are

     * undefined.  The set supports element removal, which removes the

     * corresponding mapping from the map, via the <tt>Iterator.remove</tt>,

     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and

     * <tt>clear</tt> methods.  It does not support the <tt>add</tt> or

     * <tt>addAll</tt> methods.

     *

     * <p><b>While the object returned by this method implements the

     * <tt>Set</tt> interface, it does <i>not</i> obey <tt>Set's</tt> general

     * contract.  Like its backing map, the set returned by this method

     * defines element equality as reference-equality rather than

     * object-equality.  This affects the behavior of its <tt>contains</tt>,

     * <tt>remove</tt>, <tt>containsAll</tt>, <tt>equals</tt>, and

     * <tt>hashCode</tt> methods.</b>

     *

     * <p><b>The <tt>equals</tt> method of the returned set returns <tt>true</tt>

     * only if the specified object is a set containing exactly the same

     * object references as the returned set.  The symmetry and transitivity

     * requirements of the <tt>Object.equals</tt> contract may be violated if

     * the set returned by this method is compared to a normal set.  However,

     * the <tt>Object.equals</tt> contract is guaranteed to hold among sets

     * returned by this method.</b>

     *

     * <p>The <tt>hashCode</tt> method of the returned set returns the sum of

     * the <i>identity hashcodes</i> of the elements in the set, rather than

     * the sum of their hashcodes.  This is mandated by the change in the

     * semantics of the <tt>equals</tt> method, in order to enforce the

     * general contract of the <tt>Object.hashCode</tt> method among sets

     * returned by this method.

     *

     * @return an identity-based set view of the keys contained in this map

     * @see Object#equals(Object)

     * @see System#identityHashCode(Object)

     */

    public Set<K> keySet() {

        Set<K> ks = keySet;

        if (ks != null)

            return ks;

        else

            return keySet = new KeySet();

    }

    private class KeySet extends AbstractSet<K> {

        public Iterator<K> iterator() {

            return new KeyIterator();

        }

        public int size() {

            return size;

        }

        public boolean contains(Object o) {

            return containsKey(o);

        }

        public boolean remove(Object o) {

            int oldSize = size;

            IdentityHashMap.this.remove(o);

            return size != oldSize;

        }

        /*

         * Must revert from AbstractSet's impl to AbstractCollection's, as

         * the former contains an optimization that results in incorrect

         * behavior when c is a smaller "normal" (non-identity-based) Set.

         */

        public boolean removeAll(Collection<?> c) {

            boolean modified = false;

            for (Iterator<K> i = iterator(); i.hasNext(); ) {

                if (c.contains(i.next())) {

                    i.remove();

                    modified = true;

                }

            }

            return modified;