/*
 * 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.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.AbstractList;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

import org.apache.commons.collections4.OrderedMap;
import org.apache.commons.collections4.OrderedMapIterator;
import org.apache.commons.collections4.ResettableIterator;
import org.apache.commons.collections4.iterators.AbstractUntypedIteratorDecorator;
import org.apache.commons.collections4.keyvalue.AbstractMapEntry;
import org.apache.commons.collections4.list.UnmodifiableList;

Decorates a Map to ensure that the order of addition is retained
using a List to maintain order.

The order will be used via the iterators and toArray methods on the views.
The order is also returned by the MapIterator.
The orderedMapIterator() method accesses an iterator that can
iterate both forwards and backwards through the map.
In addition, non-interface methods are provided to access the map by index.


If an object is added to the Map for a second time, it will remain in the
original position in the iteration.


Note that ListOrderedMap is not synchronized and is not thread-safe. If you wish to use this map from multiple threads concurrently, you must use appropriate synchronization. The simplest approach is to wrap this map using Collections.synchronizedMap(Map<Object,Object>). This class may throw exceptions when accessed by concurrent threads without synchronization. 

Note that ListOrderedMap doesn't work with IdentityHashMap, CaseInsensitiveMap, or similar maps that violate the general contract of Map.
The ListOrderedMap (or, more precisely, the underlying List) is relying on equals(). This is fine, as long as the decorated Map is also based on equals(), and hashCode(), which IdentityHashMap, and CaseInsensitiveMap don't: The former uses ==, and the latter uses equals() on a lower-cased key. 
 This class is Serializable starting with Commons Collections 3.1. 
Type parameters:
<K> – the type of the keys in this map
<V> – the type of the values in this map
Since:
3.0/**
 * Decorates a <code>Map</code> to ensure that the order of addition is retained
 * using a <code>List</code> to maintain order.
 * <p>
 * The order will be used via the iterators and toArray methods on the views.
 * The order is also returned by the <code>MapIterator</code>.
 * The <code>orderedMapIterator()</code> method accesses an iterator that can
 * iterate both forwards and backwards through the map.
 * In addition, non-interface methods are provided to access the map by index.
 * </p>
 * <p>
 * If an object is added to the Map for a second time, it will remain in the
 * original position in the iteration.
 * </p>
 * <p>
 * <strong>Note that ListOrderedMap is not synchronized and is not thread-safe.</strong>
 * If you wish to use this map from multiple threads concurrently, you must use
 * appropriate synchronization. The simplest approach is to wrap this map
 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
 * exceptions when accessed by concurrent threads without synchronization.
 * </p>
 * <p>
 * <strong>Note that ListOrderedMap doesn't work with
 * {@link java.util.IdentityHashMap IdentityHashMap}, {@link CaseInsensitiveMap},
 * or similar maps that violate the general contract of {@link java.util.Map}.</strong>
 * The <code>ListOrderedMap</code> (or, more precisely, the underlying <code>List</code>)
 * is relying on {@link Object#equals(Object) equals()}. This is fine, as long as the
 * decorated <code>Map</code> is also based on {@link Object#equals(Object) equals()},
 * and {@link Object#hashCode() hashCode()}, which
 * {@link java.util.IdentityHashMap IdentityHashMap}, and
 * {@link CaseInsensitiveMap} don't: The former uses <code>==</code>, and
 * the latter uses {@link Object#equals(Object) equals()} on a lower-cased
 * key.
 * </p>
 * <p>
 * This class is {@link Serializable} starting with Commons Collections 3.1.
 * </p>
 *
 * @param <K> the type of the keys in this map
 * @param <V> the type of the values in this map
 * @since 3.0
 */
public class ListOrderedMap<K, V>
        extends AbstractMapDecorator<K, V>
        implements OrderedMap<K, V>, Serializable {

    
Serialization version /** Serialization version */
    private static final long serialVersionUID = 2728177751851003750L;

    
Internal list to hold the sequence of objects /** Internal list to hold the sequence of objects */
    private final List<K> insertOrder = new ArrayList<>();

    
Factory method to create an ordered map.

An ArrayList is used to retain order.
Params:
map –  the map to decorate, must not be null
Type parameters:
<K> –  the key type
<V> –  the value type
Throws:
NullPointerException – if map is null
Returns:
a new list ordered map
Since:
4.0/**
     * Factory method to create an ordered map.
     * <p>
     * An <code>ArrayList</code> is used to retain order.
     *
     * @param <K>  the key type
     * @param <V>  the value type
     * @param map  the map to decorate, must not be null
     * @return a new list ordered map
     * @throws NullPointerException if map is null
     * @since 4.0
     */
    public static <K, V> ListOrderedMap<K, V> listOrderedMap(final Map<K, V> map) {
        return new ListOrderedMap<>(map);
    }

    //-----------------------------------------------------------------------
    
Constructs a new empty ListOrderedMap that decorates
a HashMap.
Since:
3.1/**
     * Constructs a new empty <code>ListOrderedMap</code> that decorates
     * a <code>HashMap</code>.
     *
     * @since 3.1
     */
    public ListOrderedMap() {
        this(new HashMap<K, V>());
    }

    
Constructor that wraps (not copies).
Params:
map –  the map to decorate, must not be null
Throws:
NullPointerException – if map is null/**
     * Constructor that wraps (not copies).
     *
     * @param map  the map to decorate, must not be null
     * @throws NullPointerException if map is null
     */
    protected ListOrderedMap(final Map<K, V> map) {
        super(map);
        insertOrder.addAll(decorated().keySet());
    }

    //-----------------------------------------------------------------------
    
Write the map out using a custom routine.
Params:
out –  the output stream
Throws:
IOException – if an error occurs while writing to the stream
Since:
3.1/**
     * Write the map out using a custom routine.
     *
     * @param out  the output stream
     * @throws IOException if an error occurs while writing to the stream
     * @since 3.1
     */
    private void writeObject(final ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeObject(map);
    }

    
Read the map in using a custom routine.
Params:
in –  the input stream
Throws:
IOException – if an error occurs while reading from the stream
ClassNotFoundException – if an object read from the stream can not be loaded
Since:
3.1/**
     * Read the map in using a custom routine.
     *
     * @param in  the input stream
     * @throws IOException if an error occurs while reading from the stream
     * @throws ClassNotFoundException if an object read from the stream can not be loaded
     * @since 3.1
     */
    @SuppressWarnings("unchecked") // (1) should only fail if input stream is incorrect
    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        map = (Map<K, V>) in.readObject(); // (1)
    }

    // Implement OrderedMap
    //-----------------------------------------------------------------------
    @Override
    public OrderedMapIterator<K, V> mapIterator() {
        return new ListOrderedMapIterator<>(this);
    }

    
Gets the first key in this map by insert order.
Throws:
NoSuchElementException – if this map is empty
Returns:
the first key currently in this map/**
     * Gets the first key in this map by insert order.
     *
     * @return the first key currently in this map
     * @throws NoSuchElementException if this map is empty
     */
    @Override
    public K firstKey() {
        if (size() == 0) {
            throw new NoSuchElementException("Map is empty");
        }
        return insertOrder.get(0);
    }

    
Gets the last key in this map by insert order.
Throws:
NoSuchElementException – if this map is empty
Returns:
the last key currently in this map/**
     * Gets the last key in this map by insert order.
     *
     * @return the last key currently in this map
     * @throws NoSuchElementException if this map is empty
     */
    @Override
    public K lastKey() {
        if (size() == 0) {
            throw new NoSuchElementException("Map is empty");
        }
        return insertOrder.get(size() - 1);
    }

    
Gets the next key to the one specified using insert order.
This method performs a list search to find the key and is O(n).
Params:
key –  the key to find previous for
Returns:
the next key, null if no match or at start/**
     * Gets the next key to the one specified using insert order.
     * This method performs a list search to find the key and is O(n).
     *
     * @param key  the key to find previous for
     * @return the next key, null if no match or at start
     */
    @Override
    public K nextKey(final Object key) {
        final int index = insertOrder.indexOf(key);
        if (index >= 0 && index < size() - 1) {
            return insertOrder.get(index + 1);
        }
        return null;
    }

    
Gets the previous key to the one specified using insert order.
This method performs a list search to find the key and is O(n).
Params:
key –  the key to find previous for
Returns:
the previous key, null if no match or at start/**
     * Gets the previous key to the one specified using insert order.
     * This method performs a list search to find the key and is O(n).
     *
     * @param key  the key to find previous for
     * @return the previous key, null if no match or at start
     */
    @Override
    public K previousKey(final Object key) {
        final int index = insertOrder.indexOf(key);
        if (index > 0) {
            return insertOrder.get(index - 1);
        }
        return null;
    }

    //-----------------------------------------------------------------------
    @Override
    public V put(final K key, final V value) {
        if (decorated().containsKey(key)) {
            // re-adding doesn't change order
            return decorated().put(key, value);
        }
        // first add, so add to both map and list
        final V result = decorated().put(key, value);
        insertOrder.add(key);
        return result;
    }

    @Override
    public void putAll(final Map<? extends K, ? extends V> map) {
        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    
Puts the values contained in a supplied Map into the Map starting at
the specified index.
Params:
index – the index in the Map to start at.
map – the Map containing the entries to be added.
Throws:
IndexOutOfBoundsException – if the index is out of range [0, size]/**
     * Puts the values contained in a supplied Map into the Map starting at
     * the specified index.
     *
     * @param index the index in the Map to start at.
     * @param map the Map containing the entries to be added.
     * @throws IndexOutOfBoundsException if the index is out of range [0, size]
     */
    public void putAll(int index, final Map<? extends K, ? extends V> map) {
        if (index < 0 || index > insertOrder.size()) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size());
        }
        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
            final K key = entry.getKey();
            final boolean contains = containsKey(key);
            // The return value of put is null if the key did not exist OR the value was null
            // so it cannot be used to determine whether the key was added
            put(index, entry.getKey(), entry.getValue());
            if (!contains) {
                // if no key was replaced, increment the index
                index++;
            } else {
                // otherwise put the next item after the currently inserted key
                index = indexOf(entry.getKey()) + 1;
            }
        }
    }

    @Override
    public V remove(final Object key) {
        V result = null;
        if (decorated().containsKey(key)) {
            result = decorated().remove(key);
            insertOrder.remove(key);
        }
        return result;
    }

    @Override
    public void clear() {
        decorated().clear();
        insertOrder.clear();
    }

    //-----------------------------------------------------------------------
    
Gets a view over the keys in the map.

The Collection will be ordered by object insertion into the map.
See Also:
keyList()
Returns:
the fully modifiable collection view over the keys/**
     * Gets a view over the keys in the map.
     * <p>
     * The Collection will be ordered by object insertion into the map.
     *
     * @see #keyList()
     * @return the fully modifiable collection view over the keys
     */
    @Override
    public Set<K> keySet() {
        return new KeySetView<>(this);
    }

    
Gets a view over the keys in the map as a List.

The List will be ordered by object insertion into the map.
The List is unmodifiable.
See Also:
keySet()
Returns:
the unmodifiable list view over the keys
Since:
3.2/**
     * Gets a view over the keys in the map as a List.
     * <p>
     * The List will be ordered by object insertion into the map.
     * The List is unmodifiable.
     *
     * @see #keySet()
     * @return the unmodifiable list view over the keys
     * @since 3.2
     */
    public List<K> keyList() {
        return UnmodifiableList.unmodifiableList(insertOrder);
    }

    
Gets a view over the values in the map.

The Collection will be ordered by object insertion into the map.
 From Commons Collections 3.2, this Collection can be cast to a list, see valueList() 
See Also:
valueList()
Returns:
the fully modifiable collection view over the values/**
     * Gets a view over the values in the map.
     * <p>
     * The Collection will be ordered by object insertion into the map.
     * <p>
     * From Commons Collections 3.2, this Collection can be cast
     * to a list, see {@link #valueList()}
     *
     * @see #valueList()
     * @return the fully modifiable collection view over the values
     */
    @Override
    public Collection<V> values() {
        return new ValuesView<>(this);
    }

    
Gets a view over the values in the map as a List.

The List will be ordered by object insertion into the map.
The List supports remove and set, but does not support add.
See Also:
values()
Returns:
the partially modifiable list view over the values
Since:
3.2/**
     * Gets a view over the values in the map as a List.
     * <p>
     * The List will be ordered by object insertion into the map.
     * The List supports remove and set, but does not support add.
     *
     * @see #values()
     * @return the partially modifiable list view over the values
     * @since 3.2
     */
    public List<V> valueList() {
        return new ValuesView<>(this);
    }

    
Gets a view over the entries in the map.

The Set will be ordered by object insertion into the map.
Returns:
the fully modifiable set view over the entries/**
     * Gets a view over the entries in the map.
     * <p>
     * The Set will be ordered by object insertion into the map.
     *
     * @return the fully modifiable set view over the entries
     */
    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        return new EntrySetView<>(this, this.insertOrder);
    }

    //-----------------------------------------------------------------------
    
Returns the Map as a string.
Returns:
the Map as a String/**
     * Returns the Map as a string.
     *
     * @return the Map as a String
     */
    @Override
    public String toString() {
        if (isEmpty()) {
            return "{}";
        }
        final StringBuilder buf = new StringBuilder();
        buf.append('{');
        boolean first = true;
        for (final Map.Entry<K, V> entry : entrySet()) {
            final K key = entry.getKey();
            final V value = entry.getValue();
            if (first) {
                first = false;
            } else {
                buf.append(", ");
            }
            buf.append(key == this ? "(this Map)" : key);
            buf.append('=');
            buf.append(value == this ? "(this Map)" : value);
        }
        buf.append('}');
        return buf.toString();
    }

    //-----------------------------------------------------------------------
    
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
     */
    public K get(final int index) {
        return insertOrder.get(index);
    }

    
Gets the value 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 value at the specified index.
     *
     * @param index  the index to retrieve
     * @return the key at the specified index
     * @throws IndexOutOfBoundsException if the index is invalid
     */
    public V getValue(final int index) {
        return get(insertOrder.get(index));
    }

    
Gets the index of the specified key.
Params:
key –  the key to find the index of
Returns:
the index, or -1 if not found/**
     * Gets the index of the specified key.
     *
     * @param key  the key to find the index of
     * @return the index, or -1 if not found
     */
    public int indexOf(final Object key) {
        return insertOrder.indexOf(key);
    }

    
Sets the value at the specified index.
Params:
index –  the index of the value to set
value –  the new value to set
Throws:
IndexOutOfBoundsException – if the index is invalid
Returns:
the previous value at that index
Since:
3.2/**
     * Sets the value at the specified index.
     *
     * @param index  the index of the value to set
     * @param value  the new value to set
     * @return the previous value at that index
     * @throws IndexOutOfBoundsException if the index is invalid
     * @since 3.2
     */
    public V setValue(final int index, final V value) {
        final K key = insertOrder.get(index);
        return put(key, value);
    }

    
Puts a key-value mapping into the map at the specified index.

If the map already contains the key, then the original mapping
is removed and the new mapping added at the specified index.
The remove may change the effect of the index. The index is
always calculated relative to the original state of the map.

Thus the steps are: (1) remove the existing key-value mapping,
then (2) insert the new key-value mapping at the position it
would have been inserted had the remove not occurred.
Params:
index –  the index at which the mapping should be inserted
key –  the key
value –  the value
Throws:
IndexOutOfBoundsException – if the index is out of range [0, size]
Returns:
the value previously mapped to the key
Since:
3.2/**
     * Puts a key-value mapping into the map at the specified index.
     * <p>
     * If the map already contains the key, then the original mapping
     * is removed and the new mapping added at the specified index.
     * The remove may change the effect of the index. The index is
     * always calculated relative to the original state of the map.
     * <p>
     * Thus the steps are: (1) remove the existing key-value mapping,
     * then (2) insert the new key-value mapping at the position it
     * would have been inserted had the remove not occurred.
     *
     * @param index  the index at which the mapping should be inserted
     * @param key  the key
     * @param value  the value
     * @return the value previously mapped to the key
     * @throws IndexOutOfBoundsException if the index is out of range [0, size]
     * @since 3.2
     */
    public V put(int index, final K key, final V value) {
        if (index < 0 || index > insertOrder.size()) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size());
        }

        final Map<K, V> m = decorated();
        if (m.containsKey(key)) {
            final V result = m.remove(key);
            final int pos = insertOrder.indexOf(key);
            insertOrder.remove(pos);
            if (pos < index) {
                index--;
            }
            insertOrder.add(index, key);
            m.put(key, value);
            return result;
        }
        insertOrder.add(index, key);
        m.put(key, value);
        return null;
    }

    
Removes the element at the specified index.
Params:
index –  the index of the object to remove
Throws:
IndexOutOfBoundsException – if the index is invalid
Returns:
the removed value, or null if none existed/**
     * Removes the element at the specified index.
     *
     * @param index  the index of the object to remove
     * @return the removed value, or <code>null</code> if none existed
     * @throws IndexOutOfBoundsException if the index is invalid
     */
    public V remove(final int index) {
        return remove(get(index));
    }

    
Gets an unmodifiable List view of the keys which changes as the map changes.
 The returned list is unmodifiable because changes to the values of the list (using ListIterator.set(Object)) will effectively remove the value from the list and reinsert that value at the end of the list, which is an unexpected side effect of changing the value of a list. This occurs because changing the key, changes when the mapping is added to the map and thus where it appears in the list. 
 An alternative to this method is to use the better named keyList() or keySet(). 
See Also:
keyList()
keySet()
Returns:
The ordered list of keys./**
     * Gets an unmodifiable List view of the keys which changes as the map changes.
     * <p>
     * The returned list is unmodifiable because changes to the values of
     * the list (using {@link java.util.ListIterator#set(Object)}) will
     * effectively remove the value from the list and reinsert that value at
     * the end of the list, which is an unexpected side effect of changing the
     * value of a list.  This occurs because changing the key, changes when the
     * mapping is added to the map and thus where it appears in the list.
     * <p>
     * An alternative to this method is to use the better named
     * {@link #keyList()} or {@link #keySet()}.
     *
     * @see #keyList()
     * @see #keySet()
     * @return The ordered list of keys.
     */
    public List<K> asList() {
        return keyList();
    }

    //-----------------------------------------------------------------------
    static class ValuesView<V> extends AbstractList<V> {
        private final ListOrderedMap<Object, V> parent;

        @SuppressWarnings("unchecked")
        ValuesView(final ListOrderedMap<?, V> parent) {
            super();
            this.parent = (ListOrderedMap<Object, V>) parent;
        }

        @Override
        public int size() {
            return this.parent.size();
        }

        @Override
        public boolean contains(final Object value) {
            return this.parent.containsValue(value);
        }

        @Override
        public void clear() {
            this.parent.clear();
        }

        @Override
        public Iterator<V> iterator() {
            return new AbstractUntypedIteratorDecorator<Map.Entry<Object, V>, V>(parent.entrySet().iterator()) {
                @Override
                public V next() {
                    return getIterator().next().getValue();
                }
            };
        }

        @Override
        public V get(final int index) {
            return this.parent.getValue(index);
        }

        @Override
        public V set(final int index, final V value) {
            return this.parent.setValue(index, value);
        }

        @Override
        public V remove(final int index) {
            return this.parent.remove(index);
        }
    }

    //-----------------------------------------------------------------------
    static class KeySetView<K> extends AbstractSet<K> {
        private final ListOrderedMap<K, Object> parent;

        @SuppressWarnings("unchecked")
        KeySetView(final ListOrderedMap<K, ?> parent) {
            super();
            this.parent = (ListOrderedMap<K, Object>) parent;
        }

        @Override
        public int size() {
            return this.parent.size();
        }

        @Override
        public boolean contains(final Object value) {
            return this.parent.containsKey(value);
        }

        @Override
        public void clear() {
            this.parent.clear();
        }

        @Override
        public Iterator<K> iterator() {
            return new AbstractUntypedIteratorDecorator<Map.Entry<K, Object>, K>(parent.entrySet().iterator()) {
                @Override
                public K next() {
                    return getIterator().next().getKey();
                }
            };
        }
    }

    //-----------------------------------------------------------------------
    static class EntrySetView<K, V> extends AbstractSet<Map.Entry<K, V>> {
        private final ListOrderedMap<K, V> parent;
        private final List<K> insertOrder;
        private Set<Map.Entry<K, V>> entrySet;

        public EntrySetView(final ListOrderedMap<K, V> parent, final List<K> insertOrder) {
            super();
            this.parent = parent;
            this.insertOrder = insertOrder;
        }

        private Set<Map.Entry<K, V>> getEntrySet() {
            if (entrySet == null) {
                entrySet = parent.decorated().entrySet();
            }
            return entrySet;
        }

        @Override
        public int size() {
            return this.parent.size();
        }
        @Override
        public boolean isEmpty() {
            return this.parent.isEmpty();
        }

        @Override
        public boolean contains(final Object obj) {
            return getEntrySet().contains(obj);
        }

        @Override
        public boolean containsAll(final Collection<?> coll) {
            return getEntrySet().containsAll(coll);
        }

        @Override
        @SuppressWarnings("unchecked")
        public boolean remove(final Object obj) {
            if (obj instanceof Map.Entry == false) {
                return false;
            }
            if (getEntrySet().contains(obj)) {
                final Object key = ((Map.Entry<K, V>) obj).getKey();
                parent.remove(key);
                return true;
            }
            return false;
        }

        @Override
        public void clear() {
            this.parent.clear();
        }

        @Override
        public boolean equals(final Object obj) {
            if (obj == this) {
                return true;
            }
            return getEntrySet().equals(obj);
        }

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

        @Override
        public String toString() {
            return getEntrySet().toString();
        }

        @Override
        public Iterator<Map.Entry<K, V>> iterator() {
            return new ListOrderedIterator<>(parent, insertOrder);
        }
    }

    //-----------------------------------------------------------------------
    static class ListOrderedIterator<K, V> extends AbstractUntypedIteratorDecorator<K, Map.Entry<K, V>> {
        private final ListOrderedMap<K, V> parent;
        private K last = null;

        ListOrderedIterator(final ListOrderedMap<K, V> parent, final List<K> insertOrder) {
            super(insertOrder.iterator());
            this.parent = parent;
        }

        @Override
        public Map.Entry<K, V> next() {
            last = getIterator().next();
            return new ListOrderedMapEntry<>(parent, last);
        }

        @Override
        public void remove() {
            super.remove();
            parent.decorated().remove(last);
        }
    }

    //-----------------------------------------------------------------------
    static class ListOrderedMapEntry<K, V> extends AbstractMapEntry<K, V> {
        private final ListOrderedMap<K, V> parent;

        ListOrderedMapEntry(final ListOrderedMap<K, V> parent, final K key) {
            super(key, null);
            this.parent = parent;
        }

        @Override
        public V getValue() {
            return parent.get(getKey());
        }

        @Override
        public V setValue(final V value) {
            return parent.decorated().put(getKey(), value);
        }
    }

    //-----------------------------------------------------------------------
    static class ListOrderedMapIterator<K, V> implements OrderedMapIterator<K, V>, ResettableIterator<K> {
        private final ListOrderedMap<K, V> parent;
        private ListIterator<K> iterator;
        private K last = null;
        private boolean readable = false;

        ListOrderedMapIterator(final ListOrderedMap<K, V> parent) {
            super();
            this.parent = parent;
            this.iterator = parent.insertOrder.listIterator();
        }

        @Override
        public boolean hasNext() {
            return iterator.hasNext();
        }

        @Override
        public K next() {
            last = iterator.next();
            readable = true;
            return last;
        }

        @Override
        public boolean hasPrevious() {
            return iterator.hasPrevious();
        }

        @Override
        public K previous() {
            last = iterator.previous();
            readable = true;
            return last;
        }

        @Override
        public void remove() {
            if (readable == false) {
                throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
            }
            iterator.remove();
            parent.map.remove(last);
            readable = false;
        }

        @Override
        public K getKey() {
            if (readable == false) {
                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
            }
            return last;
        }

        @Override
        public V getValue() {
            if (readable == false) {
                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
            }
            return parent.get(last);
        }

        @Override
        public V setValue(final V value) {
            if (readable == false) {
                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
            }
            return parent.map.put(last, value);
        }

        @Override
        public void reset() {
            iterator = parent.insertOrder.listIterator();
            last = null;
            readable = false;
        }

        @Override
        public String toString() {
            if (readable == true) {
                return "Iterator[" + getKey() + "=" + getValue() + "]";
            }
            return "Iterator[]";
        }
    }

}