/*
 * 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;

Immutable hash map implementation for properties.  Properties are keyed on strings.
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.

A separate chronological list is kept for quick generation of keys and values, and,
for rehashing.

Details:

The main goal is to be able to retrieve properties from a map quickly, keying on
the property name (String.)  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.
 * 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>
 * A separate chronological list is kept for quick generation of keys and values, and,
 * for rehashing.
 * <p>
 * Details:
 * <p>
 * The main goal is to be able to retrieve properties from a map quickly, keying on
 * the property name (String.)  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;

    
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 final Element[] bins;

    
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.list      = null;
    }

    
Clone Constructor
Params:
map – Original PropertyHashMap./**
     * Clone Constructor
     *
     * @param map Original {@link PropertyHashMap}.
     */
    private PropertyHashMap(final PropertyHashMap map) {
        this.size      = map.size;
        this.threshold = map.threshold;
        this.bins      = map.bins;
        this.list      = map.list;
    }

    
Constructor used internally to extend a map
Params:
size – Size of the new PropertyHashMap.
bins – The hash bins.
list – The Property list./**
     * Constructor used internally to extend a map
     *
     * @param size Size of the new {@link PropertyHashMap}.
     * @param bins The hash bins.
     * @param list The {@link Property} list.
     */
    private PropertyHashMap(final int size, final Element[] bins, final Element list) {
        this.size      = size;
        this.threshold = bins != null ? threeQuarters(bins.length) : 0;
        this.bins      = bins;
        this.list      = list;
    }

    
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() + "'";
        return cloneMap().replaceNoClone(property.getKey(), newProperty);
    }

    
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;
        PropertyHashMap newMap = cloneMap(newSize);
        newMap = newMap.addNoClone(property);
        return newMap;
    }

    
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;
        PropertyHashMap newMap = cloneMap(newSize);
        for (final Property property : newProperties) {
            newMap = newMap.addNoClone(property);
        }
        return newMap;
    }

    
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();
            PropertyHashMap newMap = cloneMap(newSize);
            for (final Property property : newProperties) {
                newMap = newMap.addNoClone(property);
            }
            return newMap;
        }
        return this;
    }

    
Clone a PropertyHashMap and remove a Property. 
Params:
property – Property to remove.
Returns:
New PropertyHashMap./**
     * Clone a {@link PropertyHashMap} and remove a {@link Property}.
     *
     * @param property {@link Property} to remove.
     *
     * @return New {@link PropertyHashMap}.
     */
    public PropertyHashMap immutableRemove(final Property property) {
        return immutableRemove(property.getKey());
    }

    
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) {
        if (bins != null) {
            final int binIndex = binIndex(bins, key);
            final Element bin = bins[binIndex];
            if (findElement(bin, key) != null) {
                final int newSize = size - 1;
                Element[] newBins = null;
                if (newSize >= LIST_THRESHOLD) {
                    newBins = bins.clone();
                    newBins[binIndex] = removeFromList(bin, key);
                }
                final Element newList = removeFromList(list, key);
                return new PropertyHashMap(newSize, newBins, newList);
            }
        } else if (findElement(list, key) != null) {
            final int newSize = size - 1;
            return newSize != 0 ? new PropertyHashMap(newSize, null, removeFromList(list, key)) : 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 (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;
    }


    private PropertyHashMap cloneMap() {
        return new PropertyHashMap(size, bins == null ? null : bins.clone(), list);
    }

    
Clone PropertyHashMap to accommodate new size. 
Params:
newSize – New size of PropertyHashMap.
Returns:
Cloned PropertyHashMap with new size./**
     * Clone {@link PropertyHashMap} to accommodate new size.
     *
     * @param newSize New size of {@link PropertyHashMap}.
     *
     * @return Cloned {@link PropertyHashMap} with new size.
     */
    private PropertyHashMap cloneMap(final int newSize) {
        Element[] newBins;
        if (bins == null && newSize <= LIST_THRESHOLD) {
            newBins = null;
        } else if (newSize > threshold) {
            newBins = rehash(list, binsNeeded(newSize));
        } else {
            newBins = bins.clone();
        }
        return new PropertyHashMap(newSize, newBins, list);
    }



    
Add a Property to a temporary PropertyHashMap, that has been already cloned. Removes duplicates if necessary. 
Params:
property – Property to add.
Returns:
New PropertyHashMap./**
     * Add a {@link Property} to a temporary {@link PropertyHashMap}, that has
     * been already cloned.  Removes duplicates if necessary.
     *
     * @param property {@link Property} to add.
     *
     * @return New {@link PropertyHashMap}.
     */
    private PropertyHashMap addNoClone(final Property property) {
        int newSize = size;
        final Object key = property.getKey();
        Element newList = list;
        if (bins != null) {
            final int binIndex = binIndex(bins, key);
            Element bin = bins[binIndex];
            if (findElement(bin, key) != null) {
                newSize--;
                bin = removeFromList(bin, key);
                newList = removeFromList(list, key);
            }
            bins[binIndex] = new Element(bin, property);
        } else {
            if (findElement(list, key) != null) {
                newSize--;
                newList = removeFromList(list, key);
            }
        }
        newList = new Element(newList, property);
        return new PropertyHashMap(newSize, bins, newList);
    }

    private PropertyHashMap replaceNoClone(final Object key, final Property property) {
        if (bins != null) {
            final int binIndex = binIndex(bins, key);
            Element bin = bins[binIndex];
            bin = replaceInList(bin, key, property);
            bins[binIndex] = bin;
        }
        Element newList = list;
        newList = replaceInList(newList, key, property);
        return new PropertyHashMap(size, bins, newList);
    }

    
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;
        }
    }

}