/*
 * Copyright (c) 2010, 2013, 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 jdk.nashorn.internal.runtime;

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import jdk.nashorn.internal.runtime.options.Options;

Immutable hash map implementation for properties. Properties are keyed on strings
or symbols (ES6). Copying and cloning is avoided by relying on immutability.

When adding an element to a hash table, only the head of a bin list is updated, thus
an add only requires the cloning of the bins array and adding an element to the head
of the bin list.  Similarly for removal, only a portion of a bin list is updated.
 For large tables with hundreds or thousands of elements, even just cloning the bins array when adding properties is an expensive operation. For this case, we put new elements in a separate list called ElementQueue. The list component is merged into the hash table at regular intervals during element insertion to keep it from growing too long. Also, when a map with a queue component is queried repeatedly, the map will replace itself with a pure hash table version of itself to optimize lookup performance. 

A separate chronological list is kept for quick generation of keys and values, and,
for rehashing. For very small maps where the overhead of the hash table would
outweigh its benefits we deliberately avoid creating a hash structure and use the
chronological list alone for element storage.

Details:

The main goal is to be able to retrieve properties from a map quickly, keying on
the property name (String or Symbol). A secondary, but important goal, is to keep
maps immutable, so that a map can be shared by multiple objects in a context.
Sharing maps allows objects to be categorized as having similar properties, a
fact that call site guards rely on.  In this discussion, immutability allows us
to significantly reduce the amount of duplication we have in our maps.

The simplest of immutable maps is a basic singly linked list.  New properties
are simply added to the head of the list.  Ancestor maps are not affected by the
addition, since they continue to refer to their own head.  Searching is done by
walking linearly though the elements until a match is found, O(N).

A hash map can be thought of as an optimization of a linked list map, where the
linked list is broken into fragments based on hashCode(key) .  An array is use
to quickly reference these fragments, indexing on hashCode(key) mod tableSize
(tableSize is typically a power of 2 so that the mod is a fast masking
operation.)  If the size of the table is sufficient large, then search time
approaches O(1).  In fact, most bins in a hash table are typically empty or
contain a one element list.

For immutable hash maps, we can think of the hash map as an array of the shorter
linked list maps.  If we add an element to the head of one of those lists,  it
doesn't affect any ancestor maps.  Thus adding an element to an immutable hash
map only requires cloning the array and inserting an element at the head of one
of the bins.

Using Java HashMaps we don't have enough control over the entries to allow us to
implement this technique, so we are forced to clone the entire hash map.

Removing elements is done similarly.  We clone the array and then only modify
the bin containing the removed element.  More often than not, the list contains
only one element (or is very short), so this is not very costly.  When the list
has several items, we need to clone the list portion prior to the removed item.

Another requirement of property maps is that we need to be able to gather all
properties in chronological (add) order.  We have been using LinkedHashMap to
provide this.  For the implementation of immutable hash map, we use a singly
linked list that is linked in reverse chronological order.  This means we simply
add new entries to the head of the list.  If we need to work with the list in
forward order, it's simply a matter of allocating an array (size is known) and
back filling in reverse order.  Removal of elements from the chronological list
is trickier.  LinkedHashMap uses a doubly linked list to give constant time
removal. Immutable hash maps can't do that and maintain immutability.  So we
manage the chronological list the same way we manage the bins, cloning up to the
point of removal.  Don't panic.  This cost is more than offset by the cost of
cloning an entire LinkedHashMap.  Plus removal is far more rare than addition.

One more optimization.  Maps with a small number of entries don't use the hash
map at all, the chronological list is used instead.

So the benefits from immutable arrays are; fewer objects and less copying.  For
immutable hash map, when no removal is involved, the number of elements per
property is two (bin + chronological elements).  For LinkedHashMap it is one
(larger element) times the number of maps that refer to the property.  For
immutable hash map, addition is constant time.  For LinkedHashMap it's O(N+C)
since we have to clone the older map.
/**
 * Immutable hash map implementation for properties. Properties are keyed on strings
 * or symbols (ES6). Copying and cloning is avoided by relying on immutability.
 * <p>
 * When adding an element to a hash table, only the head of a bin list is updated, thus
 * an add only requires the cloning of the bins array and adding an element to the head
 * of the bin list.  Similarly for removal, only a portion of a bin list is updated.
 * <p>
 * For large tables with hundreds or thousands of elements, even just cloning the bins
 * array when adding properties is an expensive operation. For this case, we put new
 * elements in a separate list called {@link ElementQueue}.
 * The list component is merged into the hash table at regular intervals during element
 * insertion to keep it from growing too long. Also, when a map with a queue component
 * is queried repeatedly, the map will replace itself with a pure hash table version
 * of itself to optimize lookup performance.
 * <p>
 * A separate chronological list is kept for quick generation of keys and values, and,
 * for rehashing. For very small maps where the overhead of the hash table would
 * outweigh its benefits we deliberately avoid creating a hash structure and use the
 * chronological list alone for element storage.
 * <p>
 * Details:
 * <p>
 * The main goal is to be able to retrieve properties from a map quickly, keying on
 * the property name (String or Symbol). A secondary, but important goal, is to keep
 * maps immutable, so that a map can be shared by multiple objects in a context.
 * Sharing maps allows objects to be categorized as having similar properties, a
 * fact that call site guards rely on.  In this discussion, immutability allows us
 * to significantly reduce the amount of duplication we have in our maps.
 * <p>
 * The simplest of immutable maps is a basic singly linked list.  New properties
 * are simply added to the head of the list.  Ancestor maps are not affected by the
 * addition, since they continue to refer to their own head.  Searching is done by
 * walking linearly though the elements until a match is found, O(N).
 * <p>
 * A hash map can be thought of as an optimization of a linked list map, where the
 * linked list is broken into fragments based on hashCode(key) .  An array is use
 * to quickly reference these fragments, indexing on hashCode(key) mod tableSize
 * (tableSize is typically a power of 2 so that the mod is a fast masking
 * operation.)  If the size of the table is sufficient large, then search time
 * approaches O(1).  In fact, most bins in a hash table are typically empty or
 * contain a one element list.
 * <p>
 * For immutable hash maps, we can think of the hash map as an array of the shorter
 * linked list maps.  If we add an element to the head of one of those lists,  it
 * doesn't affect any ancestor maps.  Thus adding an element to an immutable hash
 * map only requires cloning the array and inserting an element at the head of one
 * of the bins.
 * <p>
 * Using Java HashMaps we don't have enough control over the entries to allow us to
 * implement this technique, so we are forced to clone the entire hash map.
 * <p>
 * Removing elements is done similarly.  We clone the array and then only modify
 * the bin containing the removed element.  More often than not, the list contains
 * only one element (or is very short), so this is not very costly.  When the list
 * has several items, we need to clone the list portion prior to the removed item.
 * <p>
 * Another requirement of property maps is that we need to be able to gather all
 * properties in chronological (add) order.  We have been using LinkedHashMap to
 * provide this.  For the implementation of immutable hash map, we use a singly
 * linked list that is linked in reverse chronological order.  This means we simply
 * add new entries to the head of the list.  If we need to work with the list in
 * forward order, it's simply a matter of allocating an array (size is known) and
 * back filling in reverse order.  Removal of elements from the chronological list
 * is trickier.  LinkedHashMap uses a doubly linked list to give constant time
 * removal. Immutable hash maps can't do that and maintain immutability.  So we
 * manage the chronological list the same way we manage the bins, cloning up to the
 * point of removal.  Don't panic.  This cost is more than offset by the cost of
 * cloning an entire LinkedHashMap.  Plus removal is far more rare than addition.
 * <p>
 * One more optimization.  Maps with a small number of entries don't use the hash
 * map at all, the chronological list is used instead.
 * <p>
 * So the benefits from immutable arrays are; fewer objects and less copying.  For
 * immutable hash map, when no removal is involved, the number of elements per
 * property is two (bin + chronological elements).  For LinkedHashMap it is one
 * (larger element) times the number of maps that refer to the property.  For
 * immutable hash map, addition is constant time.  For LinkedHashMap it's O(N+C)
 * since we have to clone the older map.
 */
public final class PropertyHashMap implements Map <Object, Property> {
    
Number of initial bins. Power of 2. /** Number of initial bins. Power of 2. */
    private static final int INITIAL_BINS = 32;

    
Threshold before using bins. /** Threshold before using bins. */
    private static final int LIST_THRESHOLD = 8;

    
Threshold before adding new elements to queue instead of directly adding to hash bins. /** Threshold before adding new elements to queue instead of directly adding to hash bins. */
    private static final int QUEUE_THRESHOLD = Options.getIntProperty("nashorn.propmap.queue.threshold", 500);

    
Initial map. /** Initial map. */
    public static final PropertyHashMap EMPTY_HASHMAP = new PropertyHashMap();

    
Number of properties in the map. /** Number of properties in the map. */
    private final int size;

    
Threshold before growing the bins. /** Threshold before growing the bins. */
    private final int threshold;

    
Reverse list of all properties. /** Reverse list of all properties. */
    private final Element list;

    
Hash map bins. /** Hash map bins. */
    private Element[] bins;

    
Queue for adding elements to large maps with delayed hashing. /** Queue for adding elements to large maps with delayed hashing. */
    private ElementQueue queue;

    
All properties as an array (lazy). /** All properties as an array (lazy). */
    private Property[] properties;

    
Empty map constructor.
/**
     * Empty map constructor.
     */
    private PropertyHashMap() {
        this.size      = 0;
        this.threshold = 0;
        this.bins      = null;
        this.queue     = null;
        this.list      = null;
    }

    
Constructor used internally to create new maps
Params:
map – the new map/**
     * Constructor used internally to create new maps
     *
     * @param map the new map
     */
    private PropertyHashMap(final MapBuilder map) {
        this.size      = map.size;
        if (map.qhead == null) {
            this.bins = map.bins;
            this.queue = null;
        } else {
            this.bins = null;
            this.queue = new ElementQueue(map.qhead, map.bins);
        }
        this.list      = map.list;
        this.threshold = map.bins != null ? threeQuarters(map.bins.length) : 0;
    }

    
Clone a property map, replacing a property with a new one in the same place,
which is important for property iterations if a property changes types
Params:
property –    old property
newProperty – new property
Returns:
new property map/**
     * Clone a property map, replacing a property with a new one in the same place,
     * which is important for property iterations if a property changes types
     * @param property    old property
     * @param newProperty new property
     * @return new property map
     */
    public PropertyHashMap immutableReplace(final Property property, final Property newProperty) {
        assert property.getKey().equals(newProperty.getKey()) : "replacing properties with different keys: '" + property.getKey() + "' != '" + newProperty.getKey() + "'";
        assert findElement(property.getKey()) != null         : "replacing property that doesn't exist in map: '" + property.getKey() + "'";
        final MapBuilder builder = newMapBuilder(size);
        builder.replaceProperty(property.getKey(), newProperty);
        return new PropertyHashMap(builder);
    }

    
Clone a PropertyHashMap and add a Property. 
Params:
property – Property to add.
Returns:
New PropertyHashMap./**
     * Clone a {@link PropertyHashMap} and add a {@link Property}.
     *
     * @param property {@link Property} to add.
     *
     * @return New {@link PropertyHashMap}.
     */
    public PropertyHashMap immutableAdd(final Property property) {
        final int newSize = size + 1;
        MapBuilder builder = newMapBuilder(newSize);
        builder.addProperty(property);
        return new PropertyHashMap(builder);
    }

    
Clone a PropertyHashMap and add an array of properties. 
Params:
newProperties – Properties to add.
Returns:
New PropertyHashMap./**
     * Clone a {@link PropertyHashMap} and add an array of properties.
     *
     * @param newProperties Properties to add.
     *
     * @return New {@link PropertyHashMap}.
     */
    public PropertyHashMap immutableAdd(final Property... newProperties) {
        final int newSize = size + newProperties.length;
        MapBuilder builder = newMapBuilder(newSize);
        for (final Property property : newProperties) {
            builder.addProperty(property);
        }
        return new PropertyHashMap(builder);
    }

    
Clone a PropertyHashMap and add a collection of properties. 
Params:
newProperties – Properties to add.
Returns:
New PropertyHashMap./**
     * Clone a {@link PropertyHashMap} and add a collection of properties.
     *
     * @param newProperties Properties to add.
     *
     * @return New {@link PropertyHashMap}.
     */
    public PropertyHashMap immutableAdd(final Collection<Property> newProperties) {
        if (newProperties != null) {
            final int newSize = size + newProperties.size();
            MapBuilder builder = newMapBuilder(newSize);
            for (final Property property : newProperties) {
                builder.addProperty(property);
            }
            return new PropertyHashMap(builder);
        }
        return this;
    }

    
Clone a PropertyHashMap and remove a Property based on its key. 
Params:
key – Key of Property to remove.
Returns:
New PropertyHashMap./**
     * Clone a {@link PropertyHashMap} and remove a {@link Property} based on its key.
     *
     * @param key Key of {@link Property} to remove.
     *
     * @return New {@link PropertyHashMap}.
     */
    public PropertyHashMap immutableRemove(final Object key) {
        MapBuilder builder = newMapBuilder(size);
        builder.removeProperty(key);
        if (builder.size < size) {
            return builder.size != 0 ? new PropertyHashMap(builder) : EMPTY_HASHMAP;
        }
        return this;
    }

    
Find a Property in the PropertyHashMap. 
Params:
key – Key of Property to find.
Returns:
Property matching key or null if not found./**
     * Find a {@link Property} in the {@link PropertyHashMap}.
     *
     * @param key Key of {@link Property} to find.
     *
     * @return {@link Property} matching key or {@code null} if not found.
     */
    public Property find(final Object key) {
        final Element element = findElement(key);
        return element != null ? element.getProperty() : null;
    }

    
Return an array of properties in chronological order of adding.
Returns:
Array of all properties./**
     * Return an array of properties in chronological order of adding.
     *
     * @return Array of all properties.
     */
    Property[] getProperties() {
        if (properties == null) {
            final Property[] array = new Property[size];
            int i = size;
            for (Element element = list; element != null; element = element.getLink()) {
                array[--i] = element.getProperty();
            }
            properties = array;
        }
        return properties;
    }

    
Returns the bin index from the key.
Params:
bins –     The bins array.
key –  Property key.
Returns:
The bin index./**
     * Returns the bin index from the key.
     *
     * @param bins     The bins array.
     * @param key      {@link Property} key.
     *
     * @return The bin index.
     */
    private static int binIndex(final Element[] bins, final Object key) {
        return  key.hashCode() & bins.length - 1;
    }

    
Calculate the number of bins needed to contain n properties.
Params:
n – Number of elements.
Returns:
Number of bins required./**
     * Calculate the number of bins needed to contain n properties.
     *
     * @param n Number of elements.
     *
     * @return Number of bins required.
     */
    private static int binsNeeded(final int n) {
        // 50% padding
        return 1 << 32 - Integer.numberOfLeadingZeros(n + (n >>> 1) | INITIAL_BINS - 1);
    }

    
Used to calculate the current capacity of the bins.
Params:
n – Number of bin slots.
Returns:
75% of n./**
     * Used to calculate the current capacity of the bins.
     *
     * @param n Number of bin slots.
     *
     * @return 75% of n.
     */
    private static int threeQuarters(final int n) {
        return (n >>> 1) + (n >>> 2);
    }

    
Regenerate the bin table after changing the number of bins.
Params:
list –    // List of all properties.
binSize – // New size of bins.
Returns:
Populated bins./**
     * Regenerate the bin table after changing the number of bins.
     *
     * @param list    // List of all properties.
     * @param binSize // New size of bins.
     *
     * @return Populated bins.
     */
    private static Element[] rehash(final Element list, final int binSize) {
        final Element[] newBins = new Element[binSize];
        for (Element element = list; element != null; element = element.getLink()) {
            final Property property = element.getProperty();
            final Object   key      = property.getKey();
            final int      binIndex = binIndex(newBins, key);

            newBins[binIndex] = new Element(newBins[binIndex], property);
        }
        return newBins;
    }

    
Locate an element based on key.
Params:
key – Element key.
Returns:
Element matching key or null if not found./**
     * Locate an element based on key.
     *
     * @param key {@link Element} key.
     *
     * @return {@link Element} matching key or {@code null} if not found.
     */
    private Element findElement(final Object key) {
        if (queue != null) {
            return queue.find(key);
        } else if (bins != null) {
            final int binIndex = binIndex(bins, key);
            return findElement(bins[binIndex], key);
        }
        return findElement(list, key);
    }

    
Locate an Element based on key from a specific list. 
Params:
elementList – Head of Element list
key –  Element key.
Returns:
Element matching key or null if not found./**
     * Locate an {@link Element} based on key from a specific list.
     *
     * @param elementList Head of {@link Element} list
     * @param key         {@link Element} key.
     * @return {@link Element} matching key or {@code null} if not found.
     */
    private static Element findElement(final Element elementList, final Object key) {
        final int hashCode = key.hashCode();
        for (Element element = elementList; element != null; element = element.getLink()) {
            if (element.match(key, hashCode)) {
                return element;
            }
        }
        return null;
    }

    
Create a MapBuilder to add new elements to. 
Params:
newSize – New size of PropertyHashMap.
Returns:
MapBuilder for the new size./**
     * Create a {@code MapBuilder} to add new elements to.
     *
     * @param newSize New size of {@link PropertyHashMap}.
     *
     * @return {@link MapBuilder} for the new size.
     */
    private MapBuilder newMapBuilder(final int newSize) {
        if (bins == null && newSize < LIST_THRESHOLD) {
            return new MapBuilder(bins, list, size, false);
        } else if (newSize > threshold) {
            return new MapBuilder(rehash(list, binsNeeded(newSize)), list, size, true);
        } else if (shouldCloneBins(size, newSize)) {
            return new MapBuilder(cloneBins(), list, size, true);
        } else if (queue == null) {
            return new MapBuilder(bins, list, size, false);
        } else {
            return new MapBuilder(queue, list, size, false);
        }
    }

    
Create a cloned or new bins array and merge the elements in the queue into it if there are any.
Returns:
the cloned bins array/**
     * Create a cloned or new bins array and merge the elements in the queue into it if there are any.
     *
     * @return the cloned bins array
     */
    private Element[] cloneBins() {
        if (queue != null) {
            return queue.cloneAndMergeBins();
        }

        return bins.clone();
    }

    
Used on insertion to determine whether the bins array should be cloned, or we should keep
using the ancestor's bins array and put new elements into the queue.
Params:
oldSize – the old map size
newSize – the new map size
Returns:
whether to clone the bins array/**
     * Used on insertion to determine whether the bins array should be cloned, or we should keep
     * using the ancestor's bins array and put new elements into the queue.
     *
     * @param oldSize the old map size
     * @param newSize the new map size
     * @return whether to clone the bins array
     */
    private boolean shouldCloneBins(final int oldSize, final int newSize) {
        // For maps with less than QUEUE_THRESHOLD elements we clone the bins array on every insertion.
        // Above that threshold we put new elements into the queue and only merge every 512  elements.
        return newSize < QUEUE_THRESHOLD || (newSize >>> 9) > (oldSize >>> 9);
    }

    
Removes an Element from a specific list, avoiding duplication. 
Params:
list – List to remove from.
key –  Key of Element to remove.
Returns:
New list with Element removed./**
     * Removes an {@link Element} from a specific list, avoiding duplication.
     *
     * @param list List to remove from.
     * @param key  Key of {@link Element} to remove.
     *
     * @return New list with {@link Element} removed.
     */
    private static Element removeFromList(final Element list, final Object key) {
        if (list == null) {
            return null;
        }
        final int hashCode = key.hashCode();
        if (list.match(key, hashCode)) {
            return list.getLink();
        }
        final Element head = new Element(null, list.getProperty());
        Element previous = head;
        for (Element element = list.getLink(); element != null; element = element.getLink()) {
            if (element.match(key, hashCode)) {
                previous.setLink(element.getLink());
                return head;
            }
            final Element next = new Element(null, element.getProperty());
            previous.setLink(next);
            previous = next;
        }
        return list;
    }

    // for element x. if x get link matches,
    private static Element replaceInList(final Element list, final Object key, final Property property) {
        assert list != null;
        final int hashCode = key.hashCode();

        if (list.match(key, hashCode)) {
            return new Element(list.getLink(), property);
        }

        final Element head = new Element(null, list.getProperty());
        Element previous = head;
        for (Element element = list.getLink(); element != null; element = element.getLink()) {
            if (element.match(key, hashCode)) {
                previous.setLink(new Element(element.getLink(), property));
                return head;
            }
            final Element next = new Element(null, element.getProperty());
            previous.setLink(next);
            previous = next;
        }
        return list;
    }


    /*
     * Map implementation
     */

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

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean containsKey(final Object key) {
        assert key instanceof String || key instanceof Symbol;
        return findElement(key) != null;
    }

    @Override
    public boolean containsValue(final Object value) {
        if (value instanceof Property) {
            final Property property = (Property) value;
            final Element element = findElement(property.getKey());
            return element != null && element.getProperty().equals(value);
        }
        return false;
    }

    @Override
    public Property get(final Object key) {
        assert key instanceof String || key instanceof Symbol;
        final Element element = findElement(key);
        return element != null ? element.getProperty() : null;
    }

    @Override
    public Property put(final Object key, final Property value) {
        throw new UnsupportedOperationException("Immutable map.");
    }

    @Override
    public Property remove(final Object key) {
        throw new UnsupportedOperationException("Immutable map.");
    }

    @Override
    public void putAll(final Map<? extends Object, ? extends Property> m) {
        throw new UnsupportedOperationException("Immutable map.");
    }

    @Override
    public void clear() {
        throw new UnsupportedOperationException("Immutable map.");
    }

    @Override
    public Set<Object> keySet() {
        final HashSet<Object> set = new HashSet<>();
        for (Element element = list; element != null; element = element.getLink()) {
            set.add(element.getKey());
        }
        return Collections.unmodifiableSet(set);
    }

    @Override
    public Collection<Property> values() {
        return Collections.unmodifiableList(Arrays.asList(getProperties()));
    }

    @Override
    public Set<Entry<Object, Property>> entrySet() {
        final HashSet<Entry<Object, Property>> set = new HashSet<>();
        for (Element element = list; element != null; element = element.getLink()) {
            set.add(element);
        }
        return Collections.unmodifiableSet(set);
    }

    
List map element.
/**
     * List map element.
     */
    static final class Element implements Entry<Object, Property> {
        
Link for list construction. /** Link for list construction. */
        private Element link;

        
Element property. /** Element property. */
        private final Property property;

        
Element key. Kept separate for performance.) /** Element key. Kept separate for performance.) */
        private final Object key;

        
Element key hash code. /** Element key hash code. */
        private final int hashCode;

        /*
         * Constructors
         */

        Element(final Element link, final Property property) {
            this.link     = link;
            this.property = property;
            this.key      = property.getKey();
            this.hashCode = this.key.hashCode();
        }

        boolean match(final Object otherKey, final int otherHashCode) {
            return this.hashCode == otherHashCode && this.key.equals(otherKey);
        }

        /*
         * Entry implmentation.
         */

        @Override
        public boolean equals(final Object other) {
            assert property != null && other != null;
            return other instanceof Element && property.equals(((Element)other).property);
        }

        @Override
        public Object getKey() {
            return key;
        }

        @Override
        public Property getValue() {
            return property;
        }

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

        @Override
        public Property setValue(final Property value) {
            throw new UnsupportedOperationException("Immutable map.");
        }

        @Override
        public String toString() {
            final StringBuffer sb = new StringBuffer();

            sb.append('[');

            Element elem = this;
            do {
                sb.append(elem.getValue());
                elem = elem.link;
                if (elem != null) {
                    sb.append(" -> ");
                }
            } while (elem != null);

            sb.append(']');

            return sb.toString();
        }

        /*
         * Accessors
         */

        Element getLink() {
            return link;
        }

        void setLink(final Element link) {
            this.link = link;
        }

        Property getProperty() {
            return property;
        }
    }

    
A hybrid map/list structure to add elements to the map without the need to clone and rehash the main table.
This is used for large maps to reduce the overhead of adding elements. Instances of this class can replace
themselves with a pure hash map version of themselves to optimize query performance.
/**
     * A hybrid map/list structure to add elements to the map without the need to clone and rehash the main table.
     * This is used for large maps to reduce the overhead of adding elements. Instances of this class can replace
     * themselves with a pure hash map version of themselves to optimize query performance.
     */
    private class ElementQueue {

        
List of elements not merged into bins /** List of elements not merged into bins */
        private final Element qhead;

        
Our own bins array. Differs from original PropertyHashMap bins when queue is merged. /** Our own bins array. Differs from original PropertyHashMap bins when queue is merged. */
        private final Element[] qbins;

        
Count searches to trigger merging of queue into bins. /** Count searches to trigger merging of queue into bins. */
        int searchCount = 0;

        ElementQueue(final Element qhead, final Element[] qbins) {
            this.qhead = qhead;
            this.qbins = qbins;
        }

        Element find(final Object key) {
            final int binIndex = binIndex(qbins, key);
            final Element element = findElement(qbins[binIndex], key);
            if (element != null) {
                return element;
            }
            if (qhead != null) {
                if (++searchCount > 2) {
                    // Merge the queue into the hash bins if this map is queried more than a few times
                    final Element[] newBins = cloneAndMergeBins();
                    assert newBins != qbins;
                    PropertyHashMap.this.queue = new ElementQueue(null, newBins);
                    return PropertyHashMap.this.queue.find(key);
                }
                return findElement(qhead, key);
            }
            return null;
        }

        
Create a cloned or new bins array and merge the elements in the queue into it if there are any.
Returns:
the cloned bins array/**
         * Create a cloned or new bins array and merge the elements in the queue into it if there are any.
         *
         * @return the cloned bins array
         */
        private Element[] cloneAndMergeBins() {
            if (qhead == null) {
                return qbins;
            }

            final Element[] newBins = qbins.clone();

            for (Element element = qhead; element != null; element = element.getLink()) {
                final Property property = element.getProperty();
                final Object key = property.getKey();
                final int binIndex = binIndex(newBins, key);

                newBins[binIndex] = new Element(newBins[binIndex], property);
            }

            return newBins;
        }

    }

    
A builder class used for adding, replacing, or removing elements.
/**
     * A builder class used for adding, replacing, or removing elements.
     */
    private static class MapBuilder {

        
Bins array - may be shared with map that created us. /** Bins array - may be shared with map that created us. */
        private Element[] bins;
        
Whether our bins are shared /** Whether our bins are shared */
        private boolean hasOwnBins;

        
Queue of unmerged elements /** Queue of unmerged elements */
        private Element qhead;

        
Full property list. /** Full property list. */
        private Element list;

        
Number of properties. /** Number of properties. */
        private int size;

        MapBuilder(final Element[] bins, final Element list, final int size, final boolean hasOwnBins) {
            this.bins  = bins;
            this.hasOwnBins = hasOwnBins;
            this.list  = list;
            this.qhead = null;
            this.size  = size;
        }

        MapBuilder(final ElementQueue queue, final Element list, final int size, final boolean hasOwnBins) {
            this.bins  = queue.qbins;
            this.hasOwnBins = hasOwnBins;
            this.list  = list;
            this.qhead = queue.qhead;
            this.size  = size;
        }

        
Add a Property. Removes duplicates if necessary. 
Params:
property – Property to add./**
         * Add a {@link Property}. Removes duplicates if necessary.
         *
         * @param property {@link Property} to add.
         */
        private void addProperty(final Property property) {
            final Object key = property.getKey();

            if (bins != null) {
                final int binIndex = binIndex(bins, key);
                if (findElement(bins[binIndex], key) != null) {
                    ensureOwnBins();
                    bins[binIndex] = removeExistingElement(bins[binIndex], key);
                } else if (findElement(qhead, key) != null) {
                    qhead = removeExistingElement(qhead, key);
                }
                if (hasOwnBins) {
                    bins[binIndex] = new Element(bins[binIndex], property);
                } else {
                    qhead = new Element(qhead, property);
                }
            } else {
                if (findElement(list, key) != null) {
                    list = removeFromList(list, key);
                    size--;
                }
            }

            list = new Element(list, property);
            size++;
        }

        
Replace an existing Property with a new one with the same key. 
Params:
key – the property key
property – the property to replace the old one with/**
         * Replace an existing {@link Property} with a new one with the same key.
         *
         * @param key the property key
         * @param property the property to replace the old one with
         */
        private void replaceProperty(final Object key, final Property property) {

            if (bins != null) {
                final int binIndex = binIndex(bins, key);
                Element bin = bins[binIndex];
                if (findElement(bin, key) != null) {
                    ensureOwnBins();
                    bins[binIndex] = replaceInList(bin, key, property);
                } else if (qhead != null) {
                    qhead = replaceInList(qhead, key, property);
                }
            }

            list = replaceInList(list, key, property);
        }

        
Remove a Property based on its key. 
Params:
key – Key of Property to remove./**
         * Remove a {@link Property} based on its key.
         *
         * @param key Key of {@link Property} to remove.
         */
        void removeProperty(final Object key) {

            if (bins != null) {
                final int binIndex = binIndex(bins, key);
                final Element bin = bins[binIndex];
                if (findElement(bin, key) != null) { ;
                    if (size >= LIST_THRESHOLD) {
                        ensureOwnBins();
                        bins[binIndex] = removeFromList(bin, key);
                    } else {
                        // Go back to list-only representation for small maps
                        bins = null;
                        qhead = null;
                    }
                } else if (findElement(qhead, key) != null) {
                    qhead = removeFromList(qhead, key);
                }
            }

            list = removeFromList(list, key);
            size--;
        }

        
Removes an element known to exist from an element list and the main list and decreases size. 
Params:
element – the element list
key – the key to remove
Returns:
the new element list/**
         * Removes an element known to exist from an element list and the main {@code list} and decreases {@code size}.
         *
         * @param element the element list
         * @param key the key to remove
         * @return the new element list
         */
        private Element removeExistingElement(Element element, Object key) {
            size--;
            list = removeFromList(list, key);
            return removeFromList(element, key);
        }

        
Make sure we own the bins we have, cloning them if necessary.
/**
         * Make sure we own the bins we have, cloning them if necessary.
         */
        private void ensureOwnBins() {
            if (!hasOwnBins) {
                bins = bins.clone();
            }
            hasOwnBins = true;
        }
    }

}