    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.collections4.map;
    018
    019import java.io.IOException;
    020import java.io.ObjectInputStream;
    021import java.io.ObjectOutputStream;
    022import java.io.Serializable;
    023import java.util.AbstractList;
    024import java.util.AbstractSet;
    025import java.util.ArrayList;
    026import java.util.Collection;
    027import java.util.HashMap;
    028import java.util.Iterator;
    029import java.util.List;
    030import java.util.ListIterator;
    031import java.util.Map;
    032import java.util.NoSuchElementException;
    033import java.util.Set;
    034
    035import org.apache.commons.collections4.OrderedMap;
    036import org.apache.commons.collections4.OrderedMapIterator;
    037import org.apache.commons.collections4.ResettableIterator;
    038import org.apache.commons.collections4.iterators.AbstractUntypedIteratorDecorator;
    039import org.apache.commons.collections4.keyvalue.AbstractMapEntry;
    040import org.apache.commons.collections4.list.UnmodifiableList;
    041
    042/**
    043 * Decorates a <code>Map</code> to ensure that the order of addition is retained
    044 * using a <code>List</code> to maintain order.
    045 * <p>
    046 * The order will be used via the iterators and toArray methods on the views.
    047 * The order is also returned by the <code>MapIterator</code>.
    048 * The <code>orderedMapIterator()</code> method accesses an iterator that can
    049 * iterate both forwards and backwards through the map.
    050 * In addition, non-interface methods are provided to access the map by index.
    051 * <p>
    052 * If an object is added to the Map for a second time, it will remain in the
    053 * original position in the iteration.
    054 * <p>
    055 * <strong>Note that ListOrderedMap is not synchronized and is not thread-safe.</strong>
    056 * If you wish to use this map from multiple threads concurrently, you must use
    057 * appropriate synchronization. The simplest approach is to wrap this map
    058 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
    059 * exceptions when accessed by concurrent threads without synchronization.
    060 * <p>
    061 * <strong>Note that ListOrderedMap doesn't work with
    062 * {@link java.util.IdentityHashMap IdentityHashMap}, {@link CaseInsensitiveMap},
    063 * or similar maps that violate the general contract of {@link java.util.Map}.</strong>
    064 * The <code>ListOrderedMap</code> (or, more precisely, the underlying <code>List</code>)
    065 * is relying on {@link Object#equals(Object) equals()}. This is fine, as long as the
    066 * decorated <code>Map</code> is also based on {@link Object#equals(Object) equals()},
    067 * and {@link Object#hashCode() hashCode()}, which
    068 * {@link java.util.IdentityHashMap IdentityHashMap}, and
    069 * {@link CaseInsensitiveMap} don't: The former uses <code>==</code>, and
    070 * the latter uses {@link Object#equals(Object) equals()} on a lower-cased
    071 * key.
    072 * <p>
    073 * This class is {@link Serializable} starting with Commons Collections 3.1.
    074 *
    075 * @param <K> the type of the keys in this map
    076 * @param <V> the type of the values in this map
    077 * @since 3.0
    078 */
    079public class ListOrderedMap<K, V>
    080        extends AbstractMapDecorator<K, V>
    081        implements OrderedMap<K, V>, Serializable {
    082
    083    /** Serialization version */
    084    private static final long serialVersionUID = 2728177751851003750L;
    085
    086    /** Internal list to hold the sequence of objects */
    087    private final List<K> insertOrder = new ArrayList<>();
    088
    089    /**
    090     * Factory method to create an ordered map.
    091     * <p>
    092     * An <code>ArrayList</code> is used to retain order.
    093     *
    094     * @param <K>  the key type
    095     * @param <V>  the value type
    096     * @param map  the map to decorate, must not be null
    097     * @return a new list ordered map
    098     * @throws NullPointerException if map is null
    099     * @since 4.0
    100     */
    101    public static <K, V> ListOrderedMap<K, V> listOrderedMap(final Map<K, V> map) {
    102        return new ListOrderedMap<>(map);
    103    }
    104
    105    //-----------------------------------------------------------------------
    106    /**
    107     * Constructs a new empty <code>ListOrderedMap</code> that decorates
    108     * a <code>HashMap</code>.
    109     *
    110     * @since 3.1
    111     */
    112    public ListOrderedMap() {
    113        this(new HashMap<K, V>());
    114    }
    115
    116    /**
    117     * Constructor that wraps (not copies).
    118     *
    119     * @param map  the map to decorate, must not be null
    120     * @throws NullPointerException if map is null
    121     */
    122    protected ListOrderedMap(final Map<K, V> map) {
    123        super(map);
    124        insertOrder.addAll(decorated().keySet());
    125    }
    126
    127    //-----------------------------------------------------------------------
    128    /**
    129     * Write the map out using a custom routine.
    130     *
    131     * @param out  the output stream
    132     * @throws IOException if an error occurs while writing to the stream
    133     * @since 3.1
    134     */
    135    private void writeObject(final ObjectOutputStream out) throws IOException {
    136        out.defaultWriteObject();
    137        out.writeObject(map);
    138    }
    139
    140    /**
    141     * Read the map in using a custom routine.
    142     *
    143     * @param in  the input stream
    144     * @throws IOException if an error occurs while reading from the stream
    145     * @throws ClassNotFoundException if an object read from the stream can not be loaded
    146     * @since 3.1
    147     */
    148    @SuppressWarnings("unchecked") // (1) should only fail if input stream is incorrect
    149    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    150        in.defaultReadObject();
    151        map = (Map<K, V>) in.readObject(); // (1)
    152    }
    153
    154    // Implement OrderedMap
    155    //-----------------------------------------------------------------------
    156    @Override
    157    public OrderedMapIterator<K, V> mapIterator() {
    158        return new ListOrderedMapIterator<>(this);
    159    }
    160
    161    /**
    162     * Gets the first key in this map by insert order.
    163     *
    164     * @return the first key currently in this map
    165     * @throws NoSuchElementException if this map is empty
    166     */
    167    @Override
    168    public K firstKey() {
    169        if (size() == 0) {
    170            throw new NoSuchElementException("Map is empty");
    171        }
    172        return insertOrder.get(0);
    173    }
    174
    175    /**
    176     * Gets the last key in this map by insert order.
    177     *
    178     * @return the last key currently in this map
    179     * @throws NoSuchElementException if this map is empty
    180     */
    181    @Override
    182    public K lastKey() {
    183        if (size() == 0) {
    184            throw new NoSuchElementException("Map is empty");
    185        }
    186        return insertOrder.get(size() - 1);
    187    }
    188
    189    /**
    190     * Gets the next key to the one specified using insert order.
    191     * This method performs a list search to find the key and is O(n).
    192     *
    193     * @param key  the key to find previous for
    194     * @return the next key, null if no match or at start
    195     */
    196    @Override
    197    public K nextKey(final Object key) {
    198        final int index = insertOrder.indexOf(key);
    199        if (index >= 0 && index < size() - 1) {
    200            return insertOrder.get(index + 1);
    201        }
    202        return null;
    203    }
    204
    205    /**
    206     * Gets the previous key to the one specified using insert order.
    207     * This method performs a list search to find the key and is O(n).
    208     *
    209     * @param key  the key to find previous for
    210     * @return the previous key, null if no match or at start
    211     */
    212    @Override
    213    public K previousKey(final Object key) {
    214        final int index = insertOrder.indexOf(key);
    215        if (index > 0) {
    216            return insertOrder.get(index - 1);
    217        }
    218        return null;
    219    }
    220
    221    //-----------------------------------------------------------------------
    222    @Override
    223    public V put(final K key, final V value) {
    224        if (decorated().containsKey(key)) {
    225            // re-adding doesn't change order
    226            return decorated().put(key, value);
    227        }
    228        // first add, so add to both map and list
    229        final V result = decorated().put(key, value);
    230        insertOrder.add(key);
    231        return result;
    232    }
    233
    234    @Override
    235    public void putAll(final Map<? extends K, ? extends V> map) {
    236        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
    237            put(entry.getKey(), entry.getValue());
    238        }
    239    }
    240
    241    /**
    242     * Puts the values contained in a supplied Map into the Map starting at
    243     * the specified index.
    244     *
    245     * @param index the index in the Map to start at.
    246     * @param map the Map containing the entries to be added.
    247     * @throws IndexOutOfBoundsException if the index is out of range [0, size]
    248     */
    249    public void putAll(int index, final Map<? extends K, ? extends V> map) {
    250        if (index < 0 || index > insertOrder.size()) {
    251            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size());
    252        }
    253        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
    254            final K key = entry.getKey();
    255            final boolean contains = containsKey(key);
    256            // The return value of put is null if the key did not exist OR the value was null
    257            // so it cannot be used to determine whether the key was added
    258            put(index, entry.getKey(), entry.getValue());
    259            if (!contains) {
    260                // if no key was replaced, increment the index
    261                index++;
    262            } else {
    263                // otherwise put the next item after the currently inserted key
    264                index = indexOf(entry.getKey()) + 1;
    265            }
    266        }
    267    }
    268
    269    @Override
    270    public V remove(final Object key) {
    271        V result = null;
    272        if (decorated().containsKey(key)) {
    273            result = decorated().remove(key);
    274            insertOrder.remove(key);
    275        }
    276        return result;
    277    }
    278
    279    @Override
    280    public void clear() {
    281        decorated().clear();
    282        insertOrder.clear();
    283    }
    284
    285    //-----------------------------------------------------------------------
    286    /**
    287     * Gets a view over the keys in the map.
    288     * <p>
    289     * The Collection will be ordered by object insertion into the map.
    290     *
    291     * @see #keyList()
    292     * @return the fully modifiable collection view over the keys
    293     */
    294    @Override
    295    public Set<K> keySet() {
    296        return new KeySetView<>(this);
    297    }
    298
    299    /**
    300     * Gets a view over the keys in the map as a List.
    301     * <p>
    302     * The List will be ordered by object insertion into the map.
    303     * The List is unmodifiable.
    304     *
    305     * @see #keySet()
    306     * @return the unmodifiable list view over the keys
    307     * @since 3.2
    308     */
    309    public List<K> keyList() {
    310        return UnmodifiableList.unmodifiableList(insertOrder);
    311    }
    312
    313    /**
    314     * Gets a view over the values in the map.
    315     * <p>
    316     * The Collection will be ordered by object insertion into the map.
    317     * <p>
    318     * From Commons Collections 3.2, this Collection can be cast
    319     * to a list, see {@link #valueList()}
    320     *
    321     * @see #valueList()
    322     * @return the fully modifiable collection view over the values
    323     */
    324    @Override
    325    public Collection<V> values() {
    326        return new ValuesView<>(this);
    327    }
    328
    329    /**
    330     * Gets a view over the values in the map as a List.
    331     * <p>
    332     * The List will be ordered by object insertion into the map.
    333     * The List supports remove and set, but does not support add.
    334     *
    335     * @see #values()
    336     * @return the partially modifiable list view over the values
    337     * @since 3.2
    338     */
    339    public List<V> valueList() {
    340        return new ValuesView<>(this);
    341    }
    342
    343    /**
    344     * Gets a view over the entries in the map.
    345     * <p>
    346     * The Set will be ordered by object insertion into the map.
    347     *
    348     * @return the fully modifiable set view over the entries
    349     */
    350    @Override
    351    public Set<Map.Entry<K, V>> entrySet() {
    352        return new EntrySetView<>(this, this.insertOrder);
    353    }
    354
    355    //-----------------------------------------------------------------------
    356    /**
    357     * Returns the Map as a string.
    358     *
    359     * @return the Map as a String
    360     */
    361    @Override
    362    public String toString() {
    363        if (isEmpty()) {
    364            return "{}";
    365        }
    366        final StringBuilder buf = new StringBuilder();
    367        buf.append('{');
    368        boolean first = true;
    369        for (final Map.Entry<K, V> entry : entrySet()) {
    370            final K key = entry.getKey();
    371            final V value = entry.getValue();
    372            if (first) {
    373                first = false;
    374            } else {
    375                buf.append(", ");
    376            }
    377            buf.append(key == this ? "(this Map)" : key);
    378            buf.append('=');
    379            buf.append(value == this ? "(this Map)" : value);
    380        }
    381        buf.append('}');
    382        return buf.toString();
    383    }
    384
    385    //-----------------------------------------------------------------------
    386    /**
    387     * Gets the key at the specified index.
    388     *
    389     * @param index  the index to retrieve
    390     * @return the key at the specified index
    391     * @throws IndexOutOfBoundsException if the index is invalid
    392     */
    393    public K get(final int index) {
    394        return insertOrder.get(index);
    395    }
    396
    397    /**
    398     * Gets the value at the specified index.
    399     *
    400     * @param index  the index to retrieve
    401     * @return the key at the specified index
    402     * @throws IndexOutOfBoundsException if the index is invalid
    403     */
    404    public V getValue(final int index) {
    405        return get(insertOrder.get(index));
    406    }
    407
    408    /**
    409     * Gets the index of the specified key.
    410     *
    411     * @param key  the key to find the index of
    412     * @return the index, or -1 if not found
    413     */
    414    public int indexOf(final Object key) {
    415        return insertOrder.indexOf(key);
    416    }
    417
    418    /**
    419     * Sets the value at the specified index.
    420     *
    421     * @param index  the index of the value to set
    422     * @param value  the new value to set
    423     * @return the previous value at that index
    424     * @throws IndexOutOfBoundsException if the index is invalid
    425     * @since 3.2
    426     */
    427    public V setValue(final int index, final V value) {
    428        final K key = insertOrder.get(index);
    429        return put(key, value);
    430    }
    431
    432    /**
    433     * Puts a key-value mapping into the map at the specified index.
    434     * <p>
    435     * If the map already contains the key, then the original mapping
    436     * is removed and the new mapping added at the specified index.
    437     * The remove may change the effect of the index. The index is
    438     * always calculated relative to the original state of the map.
    439     * <p>
    440     * Thus the steps are: (1) remove the existing key-value mapping,
    441     * then (2) insert the new key-value mapping at the position it
    442     * would have been inserted had the remove not occurred.
    443     *
    444     * @param index  the index at which the mapping should be inserted
    445     * @param key  the key
    446     * @param value  the value
    447     * @return the value previously mapped to the key
    448     * @throws IndexOutOfBoundsException if the index is out of range [0, size]
    449     * @since 3.2
    450     */
    451    public V put(int index, final K key, final V value) {
    452        if (index < 0 || index > insertOrder.size()) {
    453            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size());
    454        }
    455
    456        final Map<K, V> m = decorated();
    457        if (m.containsKey(key)) {
    458            final V result = m.remove(key);
    459            final int pos = insertOrder.indexOf(key);
    460            insertOrder.remove(pos);
    461            if (pos < index) {
    462                index--;
    463            }
    464            insertOrder.add(index, key);
    465            m.put(key, value);
    466            return result;
    467        }
    468        insertOrder.add(index, key);
    469        m.put(key, value);
    470        return null;
    471    }
    472
    473    /**
    474     * Removes the element at the specified index.
    475     *
    476     * @param index  the index of the object to remove
    477     * @return the removed value, or <code>null</code> if none existed
    478     * @throws IndexOutOfBoundsException if the index is invalid
    479     */
    480    public V remove(final int index) {
    481        return remove(get(index));
    482    }
    483
    484    /**
    485     * Gets an unmodifiable List view of the keys which changes as the map changes.
    486     * <p>
    487     * The returned list is unmodifiable because changes to the values of
    488     * the list (using {@link java.util.ListIterator#set(Object)}) will
    489     * effectively remove the value from the list and reinsert that value at
    490     * the end of the list, which is an unexpected side effect of changing the
    491     * value of a list.  This occurs because changing the key, changes when the
    492     * mapping is added to the map and thus where it appears in the list.
    493     * <p>
    494     * An alternative to this method is to use the better named
    495     * {@link #keyList()} or {@link #keySet()}.
    496     *
    497     * @see #keyList()
    498     * @see #keySet()
    499     * @return The ordered list of keys.
    500     */
    501    public List<K> asList() {
    502        return keyList();
    503    }
    504
    505    //-----------------------------------------------------------------------
    506    static class ValuesView<V> extends AbstractList<V> {
    507        private final ListOrderedMap<Object, V> parent;
    508
    509        @SuppressWarnings("unchecked")
    510        ValuesView(final ListOrderedMap<?, V> parent) {
    511            super();
    512            this.parent = (ListOrderedMap<Object, V>) parent;
    513        }
    514
    515        @Override
    516        public int size() {
    517            return this.parent.size();
    518        }
    519
    520        @Override
    521        public boolean contains(final Object value) {
    522            return this.parent.containsValue(value);
    523        }
    524
    525        @Override
    526        public void clear() {
    527            this.parent.clear();
    528        }
    529
    530        @Override
    531        public Iterator<V> iterator() {
    532            return new AbstractUntypedIteratorDecorator<Map.Entry<Object, V>, V>(parent.entrySet().iterator()) {
    533                @Override
    534                public V next() {
    535                    return getIterator().next().getValue();
    536                }
    537            };
    538        }
    539
    540        @Override
    541        public V get(final int index) {
    542            return this.parent.getValue(index);
    543        }
    544
    545        @Override
    546        public V set(final int index, final V value) {
    547            return this.parent.setValue(index, value);
    548        }
    549
    550        @Override
    551        public V remove(final int index) {
    552            return this.parent.remove(index);
    553        }
    554    }
    555
    556    //-----------------------------------------------------------------------
    557    static class KeySetView<K> extends AbstractSet<K> {
    558        private final ListOrderedMap<K, Object> parent;
    559
    560        @SuppressWarnings("unchecked")
    561        KeySetView(final ListOrderedMap<K, ?> parent) {
    562            super();
    563            this.parent = (ListOrderedMap<K, Object>) parent;
    564        }
    565
    566        @Override
    567        public int size() {
    568            return this.parent.size();
    569        }
    570
    571        @Override
    572        public boolean contains(final Object value) {
    573            return this.parent.containsKey(value);
    574        }
    575
    576        @Override
    577        public void clear() {
    578            this.parent.clear();
    579        }
    580
    581        @Override
    582        public Iterator<K> iterator() {
    583            return new AbstractUntypedIteratorDecorator<Map.Entry<K, Object>, K>(parent.entrySet().iterator()) {
    584                @Override
    585                public K next() {
    586                    return getIterator().next().getKey();
    587                }
    588            };
    589        }
    590    }
    591
    592    //-----------------------------------------------------------------------
    593    static class EntrySetView<K, V> extends AbstractSet<Map.Entry<K, V>> {
    594        private final ListOrderedMap<K, V> parent;
    595        private final List<K> insertOrder;
    596        private Set<Map.Entry<K, V>> entrySet;
    597
    598        public EntrySetView(final ListOrderedMap<K, V> parent, final List<K> insertOrder) {
    599            super();
    600            this.parent = parent;
    601            this.insertOrder = insertOrder;
    602        }
    603
    604        private Set<Map.Entry<K, V>> getEntrySet() {
    605            if (entrySet == null) {
    606                entrySet = parent.decorated().entrySet();
    607            }
    608            return entrySet;
    609        }
    610
    611        @Override
    612        public int size() {
    613            return this.parent.size();
    614        }
    615        @Override
    616        public boolean isEmpty() {
    617            return this.parent.isEmpty();
    618        }
    619
    620        @Override
    621        public boolean contains(final Object obj) {
    622            return getEntrySet().contains(obj);
    623        }
    624
    625        @Override
    626        public boolean containsAll(final Collection<?> coll) {
    627            return getEntrySet().containsAll(coll);
    628        }
    629
    630        @Override
    631        @SuppressWarnings("unchecked")
    632        public boolean remove(final Object obj) {
    633            if (obj instanceof Map.Entry == false) {
    634                return false;
    635            }
    636            if (getEntrySet().contains(obj)) {
    637                final Object key = ((Map.Entry<K, V>) obj).getKey();
    638                parent.remove(key);
    639                return true;
    640            }
    641            return false;
    642        }
    643
    644        @Override
    645        public void clear() {
    646            this.parent.clear();
    647        }
    648
    649        @Override
    650        public boolean equals(final Object obj) {
    651            if (obj == this) {
    652                return true;
    653            }
    654            return getEntrySet().equals(obj);
    655        }
    656
    657        @Override
    658        public int hashCode() {
    659            return getEntrySet().hashCode();
    660        }
    661
    662        @Override
    663        public String toString() {
    664            return getEntrySet().toString();
    665        }
    666
    667        @Override
    668        public Iterator<Map.Entry<K, V>> iterator() {
    669            return new ListOrderedIterator<>(parent, insertOrder);
    670        }
    671    }
    672
    673    //-----------------------------------------------------------------------
    674    static class ListOrderedIterator<K, V> extends AbstractUntypedIteratorDecorator<K, Map.Entry<K, V>> {
    675        private final ListOrderedMap<K, V> parent;
    676        private K last = null;
    677
    678        ListOrderedIterator(final ListOrderedMap<K, V> parent, final List<K> insertOrder) {
    679            super(insertOrder.iterator());
    680            this.parent = parent;
    681        }
    682
    683        @Override
    684        public Map.Entry<K, V> next() {
    685            last = getIterator().next();
    686            return new ListOrderedMapEntry<>(parent, last);
    687        }
    688
    689        @Override
    690        public void remove() {
    691            super.remove();
    692            parent.decorated().remove(last);
    693        }
    694    }
    695
    696    //-----------------------------------------------------------------------
    697    static class ListOrderedMapEntry<K, V> extends AbstractMapEntry<K, V> {
    698        private final ListOrderedMap<K, V> parent;
    699
    700        ListOrderedMapEntry(final ListOrderedMap<K, V> parent, final K key) {
    701            super(key, null);
    702            this.parent = parent;
    703        }
    704
    705        @Override
    706        public V getValue() {
    707            return parent.get(getKey());
    708        }
    709
    710        @Override
    711        public V setValue(final V value) {
    712            return parent.decorated().put(getKey(), value);
    713        }
    714    }
    715
    716    //-----------------------------------------------------------------------
    717    static class ListOrderedMapIterator<K, V> implements OrderedMapIterator<K, V>, ResettableIterator<K> {
    718        private final ListOrderedMap<K, V> parent;
    719        private ListIterator<K> iterator;
    720        private K last = null;
    721        private boolean readable = false;
    722
    723        ListOrderedMapIterator(final ListOrderedMap<K, V> parent) {
    724            super();
    725            this.parent = parent;
    726            this.iterator = parent.insertOrder.listIterator();
    727        }
    728
    729        @Override
    730        public boolean hasNext() {
    731            return iterator.hasNext();
    732        }
    733
    734        @Override
    735        public K next() {
    736            last = iterator.next();
    737            readable = true;
    738            return last;
    739        }
    740
    741        @Override
    742        public boolean hasPrevious() {
    743            return iterator.hasPrevious();
    744        }
    745
    746        @Override
    747        public K previous() {
    748            last = iterator.previous();
    749            readable = true;
    750            return last;
    751        }
    752
    753        @Override
    754        public void remove() {
    755            if (readable == false) {
    756                throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
    757            }
    758            iterator.remove();
    759            parent.map.remove(last);
    760            readable = false;
    761        }
    762
    763        @Override
    764        public K getKey() {
    765            if (readable == false) {
    766                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
    767            }
    768            return last;
    769        }
    770
    771        @Override
    772        public V getValue() {
    773            if (readable == false) {
    774                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
    775            }
    776            return parent.get(last);
    777        }
    778
    779        @Override
    780        public V setValue(final V value) {
    781            if (readable == false) {
    782                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
    783            }
    784            return parent.map.put(last, value);
    785        }
    786
    787        @Override
    788        public void reset() {
    789            iterator = parent.insertOrder.listIterator();
    790            last = null;
    791            readable = false;
    792        }
    793
    794        @Override
    795        public String toString() {
    796            if (readable == true) {
    797                return "Iterator[" + getKey() + "=" + getValue() + "]";
    798            }
    799            return "Iterator[]";
    800        }
    801    }
    802
    803}