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