/*

 * Copyright 1998-2000 Sun Microsystems, Inc.  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.  Sun designates this

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

 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 */

package com.sun.tools.jdi;

import java.io.*;

import java.util.*;

/**

 * Hash table based implementation of the Map interface.  This implementation

 * provides all of the optional Map operations, and permits null values and

 * the null key.  (HashMap is roughly equivalent to Hashtable, except that it

 * is unsynchronized and permits nulls.) In addition, elements in the map are

 * ordered and doubly linked together.

 * <p>

 * This implementation provides constant-time performance for the basic

 * operations (get and put), assuming the the hash function disperses the

 * elements properly among the buckets.  Iteration over Collection views

 * requires time proportional to its size (the number of key-value mappings)

 * and returns elements in the order they are linked. In a HashMap the

 * iteration would require time  proportional to the capacity of the map

 * plus the map size.

 * <p>

 * An instance of LinkedHashMap has two parameters that affect its efficiency:

 * its <i>capacity</i> and its <i>load factor</i>. The load factor should be

 * between 0.0 and 1.0. When the number of mappings in the LinkedHashMap exceeds

 * the product of the load factor and the current capacity, the capacity is

 * increased by calling the rehash method which requires time proportional

 * to the number of key-value mappings in the map. Larger load factors

 * use memory more efficiently, at the expense of larger expected time per

 * lookup.

 * <p>

 * If many mappings are to be stored in a LinkedHashMap, creating it with a

 * sufficiently large capacity will allow the mappings to be stored more

 * efficiently than letting it perform automatic rehashing as needed to grow

 * the table.

 * <p>

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

 * multiple threads access a LinkedHashMap concurrently, and at least one of the

 * threads modifies the LinkedHashMap structurally, it <em>must</em> 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 is already contained in the Table is not a structural

 * modification.)  This is typically accomplished by synchronizing on some

 * object that naturally encapsulates the LinkedHashMap.  If no such object

 * exists, the LinkedHashMap should be "wrapped" using the

 * Collections.synchronizedSet method.  This is best done at creation time, to

 * prevent accidental unsynchronized access to the LinkedHashMap:

 * <pre>

 *      Map m = Collections.synchronizedMap(new LinkedHashMap(...));

 * </pre>

 * <p>

 * The Iterators returned by the iterator methods of the Collections returned

 * by all of LinkedHashMap's "collection view methods" are <em>fail-fast</em>:

 * if the LinkedHashMap is structurally modified at any time after the Iterator

 * is created, in any way except through the Iterator's own remove or add

 * methods, the Iterator will throw a 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.

 *

 * @author  Josh Bloch

 * @author  Arthur van Hoff

 * @author  Zhenghua Li

 * @see     Object#hashCode()

 * @see     java.util.Collection

 * @see     java.util.Map

 * @see     java.util.TreeMap

 * @see     java.util.Hashtable

 * @see     java.util.HashMap

 */

import java.io.Serializable;

public class LinkedHashMap extends AbstractMap implements Map, Serializable {

    /**

     * The hash table data.

     */

    private transient Entry table[];

    /**

     * The head of the double linked list.

     */

    private transient Entry header;

    /**

     * The total number of mappings in the hash table.

     */

    private transient int count;

    /**

     * Rehashes the table when count exceeds this threshold.

     */

    private int threshold;

    /**

     * The load factor for the LinkedHashMap.

     */

    private float loadFactor;

    /**

     * The number of times this LinkedHashMap has been structurally modified

     * Structural modifications are those that change the number of mappings in

     * the LinkedHashMap or otherwise modify its internal structure (e.g.,

     * rehash).  This field is used to make iterators on Collection-views of

     * the LinkedHashMap fail-fast.  (See ConcurrentModificationException).

     */

    private transient int modCount = 0;

    /**

     * Constructs a new, empty LinkedHashMap with the specified initial

     * capacity and the specified load factor.

     *

     * @param      initialCapacity   the initial capacity of the LinkedHashMap.

     * @param      loadFactor        a number between 0.0 and 1.0.

     * @exception  IllegalArgumentException  if the initial capacity is less

     *               than or equal to zero, or if the load factor is less than

     *               or equal to zero.

     */

    public LinkedHashMap(int initialCapacity, float loadFactor) {

        if (initialCapacity < 0)

            throw new IllegalArgumentException("Illegal Initial Capacity: "+

                                               initialCapacity);

        if ((loadFactor > 1) || (loadFactor <= 0))

            throw new IllegalArgumentException("Illegal Load factor: "+

                                               loadFactor);

        if (initialCapacity==0)

            initialCapacity = 1;

        this.loadFactor = loadFactor;

        table = new Entry[initialCapacity];

        threshold = (int)(initialCapacity * loadFactor);

        header = new Entry(-1, null, null, null);

        header.before = header.after = header;

    }

    /**

     * Constructs a new, empty LinkedHashMap with the specified initial capacity

     * and default load factor.

     *

     * @param   initialCapacity   the initial capacity of the LinkedHashMap.

     */

    public LinkedHashMap(int initialCapacity) {

        this(initialCapacity, 0.75f);

    }

    /**

     * Constructs a new, empty LinkedHashMap with a default capacity and load

     * factor.

     */

    public LinkedHashMap() {

        this(101, 0.75f);

    }

    /**

     * Constructs a new LinkedHashMap with the same mappings as the given

     * Map.  The LinkedHashMap is created with a capacity of thrice the number

     * of mappings in the given Map or 11 (whichever is greater), and a

     * default load factor.

     */

    public LinkedHashMap(Map t) {

        this(Math.max(3*t.size(), 11), 0.75f);

        putAll(t);

    }

    /**

     * Returns the number of key-value mappings in this Map.

     */

    public int size() {

        return count;

    }

    /**

     * Returns true if this Map contains no key-value mappings.

     */

    public boolean isEmpty() {

        return count == 0;

    }

    /**

     * Returns true if this LinkedHashMap maps one or more keys to the specified

     * value.

     *

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

     */

    public boolean containsValue(Object value) {

        if (value==null) {

            for (Entry e = header.after; e != header; e = e.after)

                if (e.value==null)

                    return true;

        } else {

            for (Entry e = header.after; e != header; e = e.after)

                if (value.equals(e.value))

                    return true;

        }

        return false;

    }

    /**

     * Returns true if this LinkedHashMap contains a mapping for the specified

     * key.

     *

     * @param key key whose presence in this Map is to be tested.

     */

    public boolean containsKey(Object key) {

        Entry tab[] = table;

        if (key != null) {

            int hash = key.hashCode();

            int index = (hash & 0x7FFFFFFF) % tab.length;

            for (Entry e = tab[index]; e != null; e = e.next)

                if (e.hash==hash && e.key.equals(key))

                    return true;

        } else {

            for (Entry e = tab[0]; e != null; e = e.next)

                if (e.key==null)

                    return true;

        }

        return false;

    }

    /**

     * Returns the value to which this LinkedHashMap maps the specified key.

     * Returns null if the LinkedHashMap contains no mapping for this key.

     * A return value of null does not <em>necessarily</em> indicate that the

     * LinkedHashMap contains no mapping for the key; it's also possible that

     * the LinkedHashMap explicitly maps the key to null.  The containsKey

     * operation may be used to distinguish these two cases.

     *

     * @param key key whose associated value is to be returned.

     */

    public Object get(Object key) {

        Entry e = getEntry(key);

        return e==null ? null : e.value;

    }

    /**

     * Returns the entry associated with the specified key in the LinkedHashMap.

     * Returns null if the LinkedHashMap contains no mapping for this key.

     */

    private Entry getEntry(Object key) {

        Entry tab[] = table;

        if (key != null) {

            int hash = key.hashCode();

            int index = (hash & 0x7FFFFFFF) % tab.length;

            for (Entry e = tab[index]; e != null; e = e.next)

                if ((e.hash == hash) && e.key.equals(key))

                    return e;

        } else {

            for (Entry e = tab[0]; e != null; e = e.next)

                if (e.key==null)

                    return e;

        }

        return null;

    }

    /**

     * Rehashes the contents of the LinkedHashMap into a LinkedHashMap with a

     * larger capacity. This method is called automatically when the

     * number of keys in the LinkedHashMap exceeds this LinkedHashMap's capacity

     * and load factor.

     */

    private void rehash() {

        int oldCapacity = table.length;

        Entry oldMap[] = table;

        int newCapacity = oldCapacity * 2 + 1;

        Entry newMap[] = new Entry[newCapacity];

        modCount++;

        threshold = (int)(newCapacity * loadFactor);

        table = newMap;

        for (Entry e = header.after; e != header; e = e.after) {

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;

            e.next = newMap[index];

            newMap[index] = e;

        }

    }

    /**

     * Remove an entry from the linked list.

     */

    private void listRemove(Entry entry) {

        if (entry == null) {

            return;

        }

        entry.before.after = entry.after;

        entry.after.before = entry.before;

    }

   /**

    * Add the specified entry before the specified existing entry to

    * the linked list.

    */

    private void listAddBefore(Entry entry, Entry existEntry) {

        entry.after = existEntry;

        entry.before = existEntry.before;

        entry.before.after = entry;

        entry.after.before = entry;

    }

    /**

     * Returns the position of the mapping for the specified key

     * in the ordered map.

     *

     * @param key the specified key.

     * @return index of the key mapping.

     */

    public int indexOf(Object key) {

        int i = 0;

        if (key == null) {

            for (Entry e = header.after; e != header; e = e.after, i++)

                if (e.key == null)

                    return i;

        } else {

            for (Entry e = header.after; e != header; e = e.after, i++)

                if(key.equals(e.key))

                    return i;

        }

        return -1;

    }

    /**

     * Associates the specified value with the specified key in this

     * LinkedHashMap. If the LinkedHashMap previously contained a mapping for

     * this key, the old value is replaced and the position of this mapping

     * entry in the double linked list remains the same. Otherwise, a new

     * mapping entry is created and inserted into the list before the specified

     * existing mapping entry. The method returns the previous value associated

     * with the specified key, or null if there was no mapping for key.  A null

     * return can also indicate that the LinkedHashMap previously associated

     * null with the specified key.

     */

    private Object putAhead(Object key, Object value, Entry existEntry) {

        // Makes sure the key is not already in the LinkedHashMap.

        Entry tab[] = table;

        int hash = 0;

        int index = 0;

        if (key != null) {

            hash = key.hashCode();

            index = (hash & 0x7FFFFFFF) % tab.length;

            for (Entry e = tab[index] ; e != null ; e = e.next) {

                if ((e.hash == hash) && e.key.equals(key)) {

                    Object old = e.value;

                    e.value = value;

                    return old;

                }

            }

        } else {

            for (Entry e = tab[0] ; e != null ; e = e.next) {

                if (e.key == null) {

                    Object old = e.value;

                    e.value = value;

                    return old;

                }

            }

        }

        modCount++;

        if (count >= threshold) {

            // Rehash the table if the threshold is exceeded

            rehash();

            tab = table;

            index = (hash & 0x7FFFFFFF) % tab.length;

        }

        // Creates the new entry.

        Entry e = new Entry(hash, key, value, tab[index]);

        tab[index] = e;

        listAddBefore(e, existEntry);

        count++;

        return null;

    }

    /**

     * Associates the specified value with the specified key in this

     * LinkedHashMap and position the mapping at the specified index.

     * If the LinkedHashMap previously contained a mapping for this key,

     * the old value is replaced and the position of this mapping entry

     * in the double linked list remains the same. Otherwise, a new mapping

     * entry is created and inserted into the list at the specified

     * position.

     *

     * @param index     the position to put the key-value mapping.

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

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

     * @return previous value associated with specified key, or null if there

     *         was no mapping for key.  A null return can also indicate that

     *         the LinkedHashMap previously associated null with the specified

     *         key.

     */

    public Object put(int index, Object key, Object value) {

        if (index < 0 || index > count)

            throw new IndexOutOfBoundsException();

        Entry e = header.after;

        if (index == count)

            return putAhead(key, value, header); //fast approach for append

        else {

            for (int i = 0; i < index; i++)

                e = e.after;

            return putAhead(key, value, e);

        }

    }

    /**

     * Associates the specified value with the specified key in this

     * LinkedHashMap. If the LinkedHashMap previously contained a mapping for

     * this key, the old value is replaced. The mapping entry is also appended

     * to the end of the ordered linked list.

     *

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

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

     * @return previous value associated with specified key, or null if there

     *         was no mapping for key.  A null return can also indicate that

     *         the LinkedHashMap previously associated null with the specified

     *         key.

     */

    public Object put(Object key, Object value) {

        return putAhead(key, value, header);

    }

    /**

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

     * The mapping would also be removed from the double linked list.

     *

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

     * @return previous value associated with specified key, or null if there

     *         was no mapping for key.  A null return can also indicate that

     *         the LinkedHashMap previously associated null with the specified

     *         key.

     */

    public Object remove(Object key) {

        Entry tab[] = table;

        if (key != null) {

            int hash = key.hashCode();

            int index = (hash & 0x7FFFFFFF) % tab.length;

            for (Entry e = tab[index], prev = null; e != null;

                 prev = e, e = e.next) {

                if ((e.hash == hash) && e.key.equals(key)) {

                    modCount++;

                    if (prev != null)

                        prev.next = e.next;

                    else

                        tab[index] = e.next;

                    count--;

                    Object oldValue = e.value;

                    e.value = null;

                    listRemove(e);

                    return oldValue;

                }

            }

        } else {

            for (Entry e = tab[0], prev = null; e != null;

                 prev = e, e = e.next) {

                if (e.key == null) {

                    modCount++;

                    if (prev != null)

                        prev.next = e.next;

                    else

                        tab[0] = e.next;

                    count--;

                    Object oldValue = e.value;

                    e.value = null;

                    listRemove(e);

                    return oldValue;

                }

            }

        }

        return null;

    }

    /**

     * Copies all of the mappings from the specified Map to this LinkedHashMap

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

     * any of the keys currently in the specified Map.

     *

      * @param t Mappings to be stored in this Map.

     */

    public void putAll(Map t) {

        Iterator i = t.entrySet().iterator();

        while (i.hasNext()) {

            Map.Entry e = (Map.Entry) i.next();

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

        }

    }

    /**

     * Removes all mappings from this LinkedHashMap.

     */

    public void clear() {

        Entry tab[] = table;

        modCount++;

        for (int index = tab.length; --index >= 0; )

            tab[index] = null;

        count = 0;

        header.before = header.after = header;

    }