package nextrek.imagecache;

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

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

/**
 * ICSLinkedHashMap is an implementation of {@link Map} that guarantees iteration order.
 * All optional operations are supported.
 * 
 * <p>
 * All elements are permitted as keys or values, including null.
 * 
 * <p>
 * Entries are kept in a doubly-linked list. The iteration order is, by default, the order in which keys were inserted. Reinserting an already-present key doesn't change the order. If the three argument constructor is used, and {@code accessOrder} is
 * specified as {@code true}, the iteration will be in the order that entries were accessed. The access order is affected by {@code put}, {@code get}, and {@code putAll} operations, but not by operations on the collection views.
 * 
 * <p>
 * Note: the implementation of {@code ICSLinkedHashMap} is not synchronized. If one thread of several threads accessing an instance modifies the map structurally, access to the map needs to be synchronized. For insertion-ordered instances a structural
 * modification is an operation that removes or adds an entry. Access-ordered instances also are structurally modified by {@code put}, {@code get}, and {@code putAll} since these methods change the order of the entries. Changes in the value of an entry are
 * not structural changes.
 * 
 * <p>
 * The {@code Iterator} created by calling the {@code iterator} method may throw a {@code ConcurrentModificationException} if the map is structurally changed while an iterator is used to iterate over the elements. Only the {@code remove} method that is
 * provided by the iterator allows for removal of elements during iteration. It is not possible to guarantee that this mechanism works in all cases of unsynchronized concurrent modification. It should only be used for debugging purposes.
 */
public class ICSLinkedHashMap<K, V> extends ICSHashMap<K, V> {

    private final class EntryIterator extends LinkedHashIterator<Map.Entry<K, V>> {
        public final Map.Entry<K, V> next() {
            return nextEntry();
        }
    }

    private final class KeyIterator extends LinkedHashIterator<K> {
        public final K next() {
            return nextEntry().key;
        }
    }

    /**
     * LinkedEntry adds nxt/prv double-links to plain HashMapEntry.
     */
    static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
        LinkedEntry<K, V> nxt;
        LinkedEntry<K, V> prv;

        /** Create the header entry */
        LinkedEntry() {
            super(null, null, 0, null);
            nxt = prv = this;
        }

        /** Create a normal entry */
        LinkedEntry(final K key, final V value, final int hash, final HashMapEntry<K, V> next, final LinkedEntry<K, V> nxt, final LinkedEntry<K, V> prv) {
            super(key, value, hash, next);
            this.nxt = nxt;
            this.prv = prv;
        }
    }

    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        int expectedModCount = modCount;
        LinkedEntry<K, V> lastReturned = null;
        LinkedEntry<K, V> next = header.nxt;

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

        final LinkedEntry<K, V> nextEntry() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            final LinkedEntry<K, V> e = next;
            if (e == header) {
                throw new NoSuchElementException();
            }
            next = e.nxt;
            return lastReturned = e;
        }

        public final void remove() {
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (lastReturned == null) {
                throw new IllegalStateException();
            }
            ICSLinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            expectedModCount = modCount;
        }
    }

    private final class ValueIterator extends LinkedHashIterator<V> {
        public final V next() {
            return nextEntry().value;
        }
    }

    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * True if access ordered, false if insertion ordered.
     */
    private final boolean accessOrder;

    /**
     * A dummy entry in the circular linked list of entries in the map.
     * The first real entry is header.nxt, and the last is header.prv.
     * If the map is empty, header.nxt == header && header.prv == header.
     */
    transient LinkedEntry<K, V> header;

    /**
     * Constructs a new empty {@code ICSLinkedHashMap} instance.
     */
    public ICSLinkedHashMap() {
        init();
        accessOrder = false;
    }

    /**
     * Constructs a new {@code ICSLinkedHashMap} instance with the specified
     * capacity.
     * 
     * @param initialCapacity
     *            the initial capacity of this map.
     * @exception IllegalArgumentException
     *                when the capacity is less than zero.
     */
    public ICSLinkedHashMap(final int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Constructs a new {@code ICSLinkedHashMap} instance with the specified
     * capacity and load factor.
     * 
     * @param initialCapacity
     *            the initial capacity of this map.
     * @param loadFactor
     *            the initial load factor.
     * @throws IllegalArgumentException
     *             when the capacity is less than zero or the load factor is
     *             less or equal to zero.
     */
    public ICSLinkedHashMap(final int initialCapacity, final float loadFactor) {
        this(initialCapacity, loadFactor, false);
    }

    /**
     * Constructs a new {@code ICSLinkedHashMap} instance with the specified
     * capacity, load factor and a flag specifying the ordering behavior.
     * 
     * @param initialCapacity
     *            the initial capacity of this hash map.
     * @param loadFactor
     *            the initial load factor.
     * @param accessOrder
     *            {@code true} if the ordering should be done based on the last
     *            access (from least-recently accessed to most-recently
     *            accessed), and {@code false} if the ordering should be the
     *            order in which the entries were inserted.
     * @throws IllegalArgumentException
     *             when the capacity is less than zero or the load factor is
     *             less or equal to zero.
     */
    public ICSLinkedHashMap(final int initialCapacity, final float loadFactor, final boolean accessOrder) {
        super(initialCapacity, loadFactor);
        init();
        this.accessOrder = accessOrder;
    }

    /**
     * Constructs a new {@code ICSLinkedHashMap} instance containing the mappings
     * from the specified map. The order of the elements is preserved.
     * 
     * @param map
     *            the mappings to add.
     */
    public ICSLinkedHashMap(final Map<? extends K, ? extends V> map) {
        this(capacityForInitSize(map.size()));
        constructorPutAll(map);
    }

    /**
     * Evicts eldest entry if instructed, creates a new entry and links it in
     * as head of linked list. This method should call constructorNewEntry
     * (instead of duplicating code) if the performance of your VM permits.
     * 
     * <p>
     * It may seem strange that this method is tasked with adding the entry to the hash table (which is properly the province of our superclass). The alternative of passing the "next" link in to this method and returning the newly created element does not
     * work! If we remove an (eldest) entry that happens to be the first entry in the same bucket as the newly created entry, the "next" link would become invalid, and the resulting hash table corrupt.
     */
    @Override
    void addNewEntry(final K key, final V value, final int hash, final int index) {
        final LinkedEntry<K, V> header = this.header;

        // Remove eldest entry if instructed to do so.
        final LinkedEntry<K, V> eldest = header.nxt;
        if ((eldest != header) && removeEldestEntry(eldest)) {
            remove(eldest.key);
        }

        // Create new entry, link it on to list, and put it into table
        final LinkedEntry<K, V> oldTail = header.prv;
        final LinkedEntry<K, V> newTail = new LinkedEntry<K, V>(key, value, hash, table[index], header, oldTail);
        table[index] = oldTail.nxt = header.prv = newTail;
    }

    @Override
    void addNewEntryForNullKey(final V value) {
        final LinkedEntry<K, V> header = this.header;

        // Remove eldest entry if instructed to do so.
        final LinkedEntry<K, V> eldest = header.nxt;
        if ((eldest != header) && removeEldestEntry(eldest)) {
            remove(eldest.key);
        }

        // Create new entry, link it on to list, and put it into table
        final LinkedEntry<K, V> oldTail = header.prv;
        final LinkedEntry<K, V> newTail = new LinkedEntry<K, V>(null, value, 0, null, header, oldTail);
        entryForNullKey = oldTail.nxt = header.prv = newTail;
    }

    @Override
    public void clear() {
        super.clear();

        // Clear all links to help GC
        final LinkedEntry<K, V> header = this.header;
        for (LinkedEntry<K, V> e = header.nxt; e != header;) {
            final LinkedEntry<K, V> nxt = e.nxt;
            e.nxt = e.prv = null;
            e = nxt;
        }

        header.nxt = header.prv = header;
    }

    /**
     * As above, but without eviction.
     */
    @Override
    HashMapEntry<K, V> constructorNewEntry(final K key, final V value, final int hash, final HashMapEntry<K, V> next) {
        final LinkedEntry<K, V> header = this.header;
        final LinkedEntry<K, V> oldTail = header.prv;
        final LinkedEntry<K, V> newTail = new LinkedEntry<K, V>(key, value, hash, next, header, oldTail);
        return oldTail.nxt = header.prv = newTail;
    }

    /**
     * This override is done for ICSLinkedHashMap performance: iteration is cheaper
     * via ICSLinkedHashMap nxt links.
     */
    @Override
    public boolean containsValue(final Object value) {
        if (value == null) {
            for (LinkedEntry<K, V> header = this.header, e = header.nxt; e != header; e = e.nxt) {
                if (e.value == null) {
                    return true;
                }
            }
            return false;
        }

        // value is non-null
        for (LinkedEntry<K, V> header = this.header, e = header.nxt; e != header; e = e.nxt) {
            if (value.equals(e.value)) {
                return true;
            }
        }
        return false;
    }

    /**
     * Returns the eldest entry in the map, or {@code null} if the map is empty.
     * 
     * @hide
     */
    public Entry<K, V> eldest() {
        final LinkedEntry<K, V> eldest = header.nxt;
        return eldest != header ? eldest : null;
    }

    /**
     * Returns the value of the mapping with the specified key.
     * 
     * @param key
     *            the key.
     * @return the value of the mapping with the specified key, or {@code null} if no mapping for the specified key is found.
     */
    @Override
    public V get(final Object key) {
        /*
         * This method is overridden to eliminate the need for a polymorphic
         * invocation in superclass at the expense of code duplication.
         */
        if (key == null) {
            final HashMapEntry<K, V> e = entryForNullKey;
            if (e == null) {
                return null;
            }
            if (accessOrder) {
                makeTail((LinkedEntry<K, V>) e);
            }
            return e.value;
        }

        // Doug Lea's supplemental secondaryHash function (inlined)
        int hash = key.hashCode();
        hash ^= (hash >>> 20) ^ (hash >>> 12);
        hash ^= (hash >>> 7) ^ (hash >>> 4);

        final HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)]; e != null; e = e.next) {
            final K eKey = e.key;
            if ((eKey == key) || ((e.hash == hash) && key.equals(eKey))) {
                if (accessOrder) {
                    makeTail((LinkedEntry<K, V>) e);
                }
                return e.value;
            }
        }
        return null;
    }

    @Override
    void init() {
        header = new LinkedEntry<K, V>();
    }

    /**
     * Relinks the given entry to the tail of the list. Under access ordering,
     * this method is invoked whenever the value of a pre-existing entry is
     * read by Map.get or modified by Map.put.
     */
    private void makeTail(final LinkedEntry<K, V> e) {
        // Unlink e
        e.prv.nxt = e.nxt;
        e.nxt.prv = e.prv;

        // Relink e as tail
        final LinkedEntry<K, V> header = this.header;
        final LinkedEntry<K, V> oldTail = header.prv;
        e.nxt = header;
        e.prv = oldTail;
        oldTail.nxt = header.prv = e;
        modCount++;
    }

    @Override
    Iterator<Map.Entry<K, V>> newEntryIterator() {
        return new EntryIterator();
    }

    // Override view iterator methods to generate correct iteration order
    @Override
    Iterator<K> newKeyIterator() {
        return new KeyIterator();
    }

    @Override
    Iterator<V> newValueIterator() {
        return new ValueIterator();
    }

    @Override
    void postRemove(final HashMapEntry<K, V> e) {
        final LinkedEntry<K, V> le = (LinkedEntry<K, V>) e;
        le.prv.nxt = le.nxt;
        le.nxt.prv = le.prv;
        le.nxt = le.prv = null; // Help the GC (for performance)
    }

    @Override
    void preModify(final HashMapEntry<K, V> e) {
        if (accessOrder) {
            makeTail((LinkedEntry<K, V>) e);
        }
    }

    protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
        return false;
    }
}