/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.collections4.map;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

import org.apache.commons.collections4.OrderedIterator;
import org.apache.commons.collections4.OrderedMap;
import org.apache.commons.collections4.OrderedMapIterator;
import org.apache.commons.collections4.ResettableIterator;
import org.apache.commons.collections4.iterators.EmptyOrderedIterator;
import org.apache.commons.collections4.iterators.EmptyOrderedMapIterator;

An abstract implementation of a hash-based map that links entries to create an
ordered map and which provides numerous points for subclasses to override.

This class implements all the features necessary for a subclass linked
hash-based map. Key-value entries are stored in instances of the
LinkEntry class which can be overridden and replaced.
The iterators can similarly be replaced, without the need to replace the KeySet,
EntrySet and Values view classes.

Overridable methods are provided to change the default hashing behaviour, and
to change how entries are added to and removed from the map. Hopefully, all you
need for unusual subclasses is here.

This implementation maintains order by original insertion, but subclasses
may work differently. The OrderedMap interface is implemented
to provide access to bidirectional iteration and extra convenience methods.

The orderedMapIterator() method provides direct access to a
bidirectional iterator. The iterators from the other views can also be cast
to OrderedIterator if required.

All the available iterators can be reset back to the start by casting to
ResettableIterator and calling reset().

The implementation is also designed to be subclassed, with lots of useful
methods exposed.
Type parameters:
<K> – the type of the keys in this map
<V> – the type of the values in this map
Since:
3.0/**
 * An abstract implementation of a hash-based map that links entries to create an
 * ordered map and which provides numerous points for subclasses to override.
 * <p>
 * This class implements all the features necessary for a subclass linked
 * hash-based map. Key-value entries are stored in instances of the
 * <code>LinkEntry</code> class which can be overridden and replaced.
 * The iterators can similarly be replaced, without the need to replace the KeySet,
 * EntrySet and Values view classes.
 * <p>
 * Overridable methods are provided to change the default hashing behaviour, and
 * to change how entries are added to and removed from the map. Hopefully, all you
 * need for unusual subclasses is here.
 * <p>
 * This implementation maintains order by original insertion, but subclasses
 * may work differently. The <code>OrderedMap</code> interface is implemented
 * to provide access to bidirectional iteration and extra convenience methods.
 * <p>
 * The <code>orderedMapIterator()</code> method provides direct access to a
 * bidirectional iterator. The iterators from the other views can also be cast
 * to <code>OrderedIterator</code> if required.
 * <p>
 * All the available iterators can be reset back to the start by casting to
 * <code>ResettableIterator</code> and calling <code>reset()</code>.
 * <p>
 * The implementation is also designed to be subclassed, with lots of useful
 * methods exposed.
 *
 * @param <K> the type of the keys in this map
 * @param <V> the type of the values in this map
 * @since 3.0
 */
public abstract class AbstractLinkedMap<K, V> extends AbstractHashedMap<K, V> implements OrderedMap<K, V> {

    
Header in the linked list /** Header in the linked list */
    transient LinkEntry<K, V> header;

    
Constructor only used in deserialization, do not use otherwise.
/**
     * Constructor only used in deserialization, do not use otherwise.
     */
    protected AbstractLinkedMap() {
        super();
    }

    
Constructor which performs no validation on the passed in parameters.
Params:
initialCapacity –  the initial capacity, must be a power of two
loadFactor –  the load factor, must be > 0.0f and generally < 1.0f
threshold –  the threshold, must be sensible/**
     * Constructor which performs no validation on the passed in parameters.
     *
     * @param initialCapacity  the initial capacity, must be a power of two
     * @param loadFactor  the load factor, must be &gt; 0.0f and generally &lt; 1.0f
     * @param threshold  the threshold, must be sensible
     */
    protected AbstractLinkedMap(final int initialCapacity, final float loadFactor, final int threshold) {
        super(initialCapacity, loadFactor, threshold);
    }

    
Constructs a new, empty map with the specified initial capacity.
Params:
initialCapacity –  the initial capacity
Throws:
IllegalArgumentException – if the initial capacity is negative/**
     * Constructs a new, empty map with the specified initial capacity.
     *
     * @param initialCapacity  the initial capacity
     * @throws IllegalArgumentException if the initial capacity is negative
     */
    protected AbstractLinkedMap(final int initialCapacity) {
        super(initialCapacity);
    }

    
Constructs a new, empty map with the specified initial capacity and
load factor.
Params:
initialCapacity –  the initial capacity
loadFactor –  the load factor
Throws:
IllegalArgumentException – if the initial capacity is negative
IllegalArgumentException – if the load factor is less than zero/**
     * Constructs a new, empty map with the specified initial capacity and
     * load factor.
     *
     * @param initialCapacity  the initial capacity
     * @param loadFactor  the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     * @throws IllegalArgumentException if the load factor is less than zero
     */
    protected AbstractLinkedMap(final int initialCapacity, final float loadFactor) {
        super(initialCapacity, loadFactor);
    }

    
Constructor copying elements from another map.
Params:
map –  the map to copy
Throws:
NullPointerException – if the map is null/**
     * Constructor copying elements from another map.
     *
     * @param map  the map to copy
     * @throws NullPointerException if the map is null
     */
    protected AbstractLinkedMap(final Map<? extends K, ? extends V> map) {
        super(map);
    }

    
Initialise this subclass during construction.
 NOTE: As from v3.2 this method calls createEntry(HashEntry, int, Object, Object) to create the map entry object. /**
     * Initialise this subclass during construction.
     * <p>
     * NOTE: As from v3.2 this method calls
     * {@link #createEntry(HashEntry, int, Object, Object)} to create
     * the map entry object.
     */
    @Override
    protected void init() {
        header = createEntry(null, -1, null, null);
        header.before = header.after = header;
    }

    //-----------------------------------------------------------------------
    
Checks whether the map contains the specified value.
Params:
value –  the value to search for
Returns:
true if the map contains the value/**
     * Checks whether the map contains the specified value.
     *
     * @param value  the value to search for
     * @return true if the map contains the value
     */
    @Override
    public boolean containsValue(final Object value) {
        // override uses faster iterator
        if (value == null) {
            for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) {
                if (entry.getValue() == null) {
                    return true;
                }
            }
        } else {
            for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) {
                if (isEqualValue(value, entry.getValue())) {
                    return true;
                }
            }
        }
        return false;
    }

    
Clears the map, resetting the size to zero and nullifying references
to avoid garbage collection issues.
/**
     * Clears the map, resetting the size to zero and nullifying references
     * to avoid garbage collection issues.
     */
    @Override
    public void clear() {
        // override to reset the linked list
        super.clear();
        header.before = header.after = header;
    }

    //-----------------------------------------------------------------------
    
Gets the first key in the map, which is the first inserted.
Returns:
the eldest key/**
     * Gets the first key in the map, which is the first inserted.
     *
     * @return the eldest key
     */
    @Override
    public K firstKey() {
        if (size == 0) {
            throw new NoSuchElementException("Map is empty");
        }
        return header.after.getKey();
    }

    
Gets the last key in the map, which is the most recently inserted.
Returns:
the most recently inserted key/**
     * Gets the last key in the map, which is the most recently inserted.
     *
     * @return the most recently inserted key
     */
    @Override
    public K lastKey() {
        if (size == 0) {
            throw new NoSuchElementException("Map is empty");
        }
        return header.before.getKey();
    }

    
Gets the next key in sequence.
Params:
key –  the key to get after
Returns:
the next key/**
     * Gets the next key in sequence.
     *
     * @param key  the key to get after
     * @return the next key
     */
    @Override
    public K nextKey(final Object key) {
        final LinkEntry<K, V> entry = getEntry(key);
        return entry == null || entry.after == header ? null : entry.after.getKey();
    }

    @Override
    protected LinkEntry<K, V> getEntry(final Object key) {
        return (LinkEntry<K, V>) super.getEntry(key);
    }

    
Gets the previous key in sequence.
Params:
key –  the key to get before
Returns:
the previous key/**
     * Gets the previous key in sequence.
     *
     * @param key  the key to get before
     * @return the previous key
     */
    @Override
    public K previousKey(final Object key) {
        final LinkEntry<K, V> entry = getEntry(key);
        return entry == null || entry.before == header ? null : entry.before.getKey();
    }

    //-----------------------------------------------------------------------
    
Gets the key at the specified index.
Params:
index –  the index to retrieve
Throws:
IndexOutOfBoundsException – if the index is invalid
Returns:
the key at the specified index/**
     * Gets the key at the specified index.
     *
     * @param index  the index to retrieve
     * @return the key at the specified index
     * @throws IndexOutOfBoundsException if the index is invalid
     */
    protected LinkEntry<K, V> getEntry(final int index) {
        if (index < 0) {
            throw new IndexOutOfBoundsException("Index " + index + " is less than zero");
        }
        if (index >= size) {
            throw new IndexOutOfBoundsException("Index " + index + " is invalid for size " + size);
        }
        LinkEntry<K, V> entry;
        if (index < size / 2) {
            // Search forwards
            entry = header.after;
            for (int currentIndex = 0; currentIndex < index; currentIndex++) {
                entry = entry.after;
            }
        } else {
            // Search backwards
            entry = header;
            for (int currentIndex = size; currentIndex > index; currentIndex--) {
                entry = entry.before;
            }
        }
        return entry;
    }

    
Adds an entry into this map, maintaining insertion order.

This implementation adds the entry to the data storage table and
to the end of the linked list.
Params:
entry –  the entry to add
hashIndex –  the index into the data array to store at/**
     * Adds an entry into this map, maintaining insertion order.
     * <p>
     * This implementation adds the entry to the data storage table and
     * to the end of the linked list.
     *
     * @param entry  the entry to add
     * @param hashIndex  the index into the data array to store at
     */
    @Override
    protected void addEntry(final HashEntry<K, V> entry, final int hashIndex) {
        final LinkEntry<K, V> link = (LinkEntry<K, V>) entry;
        link.after  = header;
        link.before = header.before;
        header.before.after = link;
        header.before = link;
        data[hashIndex] = link;
    }

    
Creates an entry to store the data.

This implementation creates a new LinkEntry instance.
Params:
next –  the next entry in sequence
hashCode –  the hash code to use
key –  the key to store
value –  the value to store
Returns:
the newly created entry/**
     * Creates an entry to store the data.
     * <p>
     * This implementation creates a new LinkEntry instance.
     *
     * @param next  the next entry in sequence
     * @param hashCode  the hash code to use
     * @param key  the key to store
     * @param value  the value to store
     * @return the newly created entry
     */
    @Override
    protected LinkEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode, final K key, final V value) {
        return new LinkEntry<>(next, hashCode, convertKey(key), value);
    }

    
Removes an entry from the map and the linked list.

This implementation removes the entry from the linked list chain, then
calls the superclass implementation.
Params:
entry –  the entry to remove
hashIndex –  the index into the data structure
previous –  the previous entry in the chain/**
     * Removes an entry from the map and the linked list.
     * <p>
     * This implementation removes the entry from the linked list chain, then
     * calls the superclass implementation.
     *
     * @param entry  the entry to remove
     * @param hashIndex  the index into the data structure
     * @param previous  the previous entry in the chain
     */
    @Override
    protected void removeEntry(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) {
        final LinkEntry<K, V> link = (LinkEntry<K, V>) entry;
        link.before.after = link.after;
        link.after.before = link.before;
        link.after = null;
        link.before = null;
        super.removeEntry(entry, hashIndex, previous);
    }

    //-----------------------------------------------------------------------
    
Gets the before field from a LinkEntry.
Used in subclasses that have no visibility of the field.
Params:
entry –  the entry to query, must not be null
Throws:
NullPointerException – if the entry is null
Returns:
the before field of the entry
Since:
3.1/**
     * Gets the <code>before</code> field from a <code>LinkEntry</code>.
     * Used in subclasses that have no visibility of the field.
     *
     * @param entry  the entry to query, must not be null
     * @return the <code>before</code> field of the entry
     * @throws NullPointerException if the entry is null
     * @since 3.1
     */
    protected LinkEntry<K, V> entryBefore(final LinkEntry<K, V> entry) {
        return entry.before;
    }

    
Gets the after field from a LinkEntry.
Used in subclasses that have no visibility of the field.
Params:
entry –  the entry to query, must not be null
Throws:
NullPointerException – if the entry is null
Returns:
the after field of the entry
Since:
3.1/**
     * Gets the <code>after</code> field from a <code>LinkEntry</code>.
     * Used in subclasses that have no visibility of the field.
     *
     * @param entry  the entry to query, must not be null
     * @return the <code>after</code> field of the entry
     * @throws NullPointerException if the entry is null
     * @since 3.1
     */
    protected LinkEntry<K, V> entryAfter(final LinkEntry<K, V> entry) {
        return entry.after;
    }

    //-----------------------------------------------------------------------
    
{@inheritDoc}
/**
     * {@inheritDoc}
     */
    @Override
    public OrderedMapIterator<K, V> mapIterator() {
        if (size == 0) {
            return EmptyOrderedMapIterator.<K, V>emptyOrderedMapIterator();
        }
        return new LinkMapIterator<>(this);
    }

    
MapIterator implementation.
/**
     * MapIterator implementation.
     */
    protected static class LinkMapIterator<K, V> extends LinkIterator<K, V> implements
            OrderedMapIterator<K, V>, ResettableIterator<K> {

        protected LinkMapIterator(final AbstractLinkedMap<K, V> parent) {
            super(parent);
        }

        @Override
        public K next() {
            return super.nextEntry().getKey();
        }

        @Override
        public K previous() {
            return super.previousEntry().getKey();
        }

        @Override
        public K getKey() {
            final LinkEntry<K, V> current = currentEntry();
            if (current == null) {
                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
            }
            return current.getKey();
        }

        @Override
        public V getValue() {
            final LinkEntry<K, V> current = currentEntry();
            if (current == null) {
                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
            }
            return current.getValue();
        }

        @Override
        public V setValue(final V value) {
            final LinkEntry<K, V> current = currentEntry();
            if (current == null) {
                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
            }
            return current.setValue(value);
        }
    }

    //-----------------------------------------------------------------------
    
Creates an entry set iterator.
Subclasses can override this to return iterators with different properties.
Returns:
the entrySet iterator/**
     * Creates an entry set iterator.
     * Subclasses can override this to return iterators with different properties.
     *
     * @return the entrySet iterator
     */
    @Override
    protected Iterator<Map.Entry<K, V>> createEntrySetIterator() {
        if (size() == 0) {
            return EmptyOrderedIterator.<Map.Entry<K, V>>emptyOrderedIterator();
        }
        return new EntrySetIterator<>(this);
    }

    
EntrySet iterator.
/**
     * EntrySet iterator.
     */
    protected static class EntrySetIterator<K, V> extends LinkIterator<K, V> implements
            OrderedIterator<Map.Entry<K, V>>, ResettableIterator<Map.Entry<K, V>> {

        protected EntrySetIterator(final AbstractLinkedMap<K, V> parent) {
            super(parent);
        }

        @Override
        public Map.Entry<K, V> next() {
            return super.nextEntry();
        }

        @Override
        public Map.Entry<K, V> previous() {
            return super.previousEntry();
        }
    }

    //-----------------------------------------------------------------------
    
Creates a key set iterator.
Subclasses can override this to return iterators with different properties.
Returns:
the keySet iterator/**
     * Creates a key set iterator.
     * Subclasses can override this to return iterators with different properties.
     *
     * @return the keySet iterator
     */
    @Override
    protected Iterator<K> createKeySetIterator() {
        if (size() == 0) {
            return EmptyOrderedIterator.<K>emptyOrderedIterator();
        }
        return new KeySetIterator<>(this);
    }

    
KeySet iterator.
/**
     * KeySet iterator.
     */
    protected static class KeySetIterator<K> extends LinkIterator<K, Object> implements
            OrderedIterator<K>, ResettableIterator<K> {

        @SuppressWarnings("unchecked")
        protected KeySetIterator(final AbstractLinkedMap<K, ?> parent) {
            super((AbstractLinkedMap<K, Object>) parent);
        }

        @Override
        public K next() {
            return super.nextEntry().getKey();
        }

        @Override
        public K previous() {
            return super.previousEntry().getKey();
        }
    }

    //-----------------------------------------------------------------------
    
Creates a values iterator.
Subclasses can override this to return iterators with different properties.
Returns:
the values iterator/**
     * Creates a values iterator.
     * Subclasses can override this to return iterators with different properties.
     *
     * @return the values iterator
     */
    @Override
    protected Iterator<V> createValuesIterator() {
        if (size() == 0) {
            return EmptyOrderedIterator.<V>emptyOrderedIterator();
        }
        return new ValuesIterator<>(this);
    }

    
Values iterator.
/**
     * Values iterator.
     */
    protected static class ValuesIterator<V> extends LinkIterator<Object, V> implements
            OrderedIterator<V>, ResettableIterator<V> {

        @SuppressWarnings("unchecked")
        protected ValuesIterator(final AbstractLinkedMap<?, V> parent) {
            super((AbstractLinkedMap<Object, V>) parent);
        }

        @Override
        public V next() {
            return super.nextEntry().getValue();
        }

        @Override
        public V previous() {
            return super.previousEntry().getValue();
        }
    }

    //-----------------------------------------------------------------------
    
LinkEntry that stores the data.

If you subclass AbstractLinkedMap but not LinkEntry
then you will not be able to access the protected fields.
The entryXxx() methods on AbstractLinkedMap exist
to provide the necessary access.
/**
     * LinkEntry that stores the data.
     * <p>
     * If you subclass <code>AbstractLinkedMap</code> but not <code>LinkEntry</code>
     * then you will not be able to access the protected fields.
     * The <code>entryXxx()</code> methods on <code>AbstractLinkedMap</code> exist
     * to provide the necessary access.
     */
    protected static class LinkEntry<K, V> extends HashEntry<K, V> {
        
The entry before this one in the order /** The entry before this one in the order */
        protected LinkEntry<K, V> before;
        
The entry after this one in the order /** The entry after this one in the order */
        protected LinkEntry<K, V> after;

        
Constructs a new entry.
Params:
next –  the next entry in the hash bucket sequence
hashCode –  the hash code
key –  the key
value –  the value/**
         * Constructs a new entry.
         *
         * @param next  the next entry in the hash bucket sequence
         * @param hashCode  the hash code
         * @param key  the key
         * @param value  the value
         */
        protected LinkEntry(final HashEntry<K, V> next, final int hashCode, final Object key, final V value) {
            super(next, hashCode, key, value);
        }
    }

    
Base Iterator that iterates in link order.
/**
     * Base Iterator that iterates in link order.
     */
    protected static abstract class LinkIterator<K, V> {

        
The parent map /** The parent map */
        protected final AbstractLinkedMap<K, V> parent;
        
The current (last returned) entry /** The current (last returned) entry */
        protected LinkEntry<K, V> last;
        
The next entry /** The next entry */
        protected LinkEntry<K, V> next;
        
The modification count expected /** The modification count expected */
        protected int expectedModCount;

        protected LinkIterator(final AbstractLinkedMap<K, V> parent) {
            super();
            this.parent = parent;
            this.next = parent.header.after;
            this.expectedModCount = parent.modCount;
        }

        public boolean hasNext() {
            return next != parent.header;
        }

        public boolean hasPrevious() {
            return next.before != parent.header;
        }

        protected LinkEntry<K, V> nextEntry() {
            if (parent.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (next == parent.header)  {
                throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY);
            }
            last = next;
            next = next.after;
            return last;
        }

        protected LinkEntry<K, V> previousEntry() {
            if (parent.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            final LinkEntry<K, V> previous = next.before;
            if (previous == parent.header)  {
                throw new NoSuchElementException(AbstractHashedMap.NO_PREVIOUS_ENTRY);
            }
            next = previous;
            last = previous;
            return last;
        }

        protected LinkEntry<K, V> currentEntry() {
            return last;
        }

        public void remove() {
            if (last == null) {
                throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
            }
            if (parent.modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            parent.remove(last.getKey());
            last = null;
            expectedModCount = parent.modCount;
        }

        public void reset() {
            last = null;
            next = parent.header.after;
        }

        @Override
        public String toString() {
            if (last != null) {
                return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
            }
            return "Iterator[]";
        }
    }

}