    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 *      https://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.Collection;
    025import java.util.Iterator;
    026import java.util.List;
    027import java.util.ListIterator;
    028import java.util.Map;
    029import java.util.function.Predicate;
    030
    031import org.apache.commons.collections4.CollectionUtils;
    032import org.apache.commons.collections4.MapIterator;
    033import org.apache.commons.collections4.iterators.UnmodifiableIterator;
    034import org.apache.commons.collections4.iterators.UnmodifiableListIterator;
    035import org.apache.commons.collections4.list.UnmodifiableList;
    036
    037/**
    038 * A {@code Map} implementation that maintains the order of the entries.
    039 * In this implementation order is maintained by original insertion.
    040 * <p>
    041 * This implementation improves on the JDK1.4 LinkedHashMap by adding the
    042 * {@link MapIterator MapIterator}
    043 * functionality, additional convenience methods and allowing
    044 * bidirectional iteration. It also implements {@code OrderedMap}.
    045 * In addition, non-interface methods are provided to access the map by index.
    046 * </p>
    047 * <p>
    048 * The {@code orderedMapIterator()} method provides direct access to a
    049 * bidirectional iterator. The iterators from the other views can also be cast
    050 * to {@code OrderedIterator} if required.
    051 * </p>
    052 * <p>
    053 * All the available iterators can be reset back to the start by casting to
    054 * {@code ResettableIterator} and calling {@code reset()}.
    055 * </p>
    056 * <p>
    057 * The implementation is also designed to be subclassed, with lots of useful
    058 * methods exposed.
    059 * </p>
    060 * <p>
    061 * <strong>Note that LinkedMap is not synchronized and is not thread-safe.</strong>
    062 * If you wish to use this map from multiple threads concurrently, you must use
    063 * appropriate synchronization. The simplest approach is to wrap this map
    064 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
    065 * exceptions when accessed by concurrent threads without synchronization.
    066 * </p>
    067 *
    068 * @param <K> The type of the keys in this map
    069 * @param <V> The type of the values in this map
    070 * @since 3.0
    071 */
    072public class LinkedMap<K, V> extends AbstractLinkedMap<K, V> implements Serializable, Cloneable {
    073
    074    /**
    075     * List view of map.
    076     */
    077    static class LinkedMapList<K> extends AbstractList<K> {
    078
    079        private final LinkedMap<K, ?> parent;
    080
    081        LinkedMapList(final LinkedMap<K, ?> parent) {
    082            this.parent = parent;
    083        }
    084
    085        /**
    086         * Always throws {@link UnsupportedOperationException}.
    087         *
    088         * @throws UnsupportedOperationException Always thrown.
    089         */
    090        @Override
    091        public void clear() {
    092            throw new UnsupportedOperationException();
    093        }
    094
    095        @Override
    096        public boolean contains(final Object obj) {
    097            return parent.containsKey(obj);
    098        }
    099
    100        @Override
    101        public boolean containsAll(final Collection<?> coll) {
    102            return parent.keySet().containsAll(coll);
    103        }
    104
    105        @Override
    106        public K get(final int index) {
    107            return parent.get(index);
    108        }
    109
    110        @Override
    111        public int indexOf(final Object obj) {
    112            return parent.indexOf(obj);
    113        }
    114
    115        @Override
    116        public Iterator<K> iterator() {
    117            return UnmodifiableIterator.unmodifiableIterator(parent.keySet().iterator());
    118        }
    119
    120        @Override
    121        public int lastIndexOf(final Object obj) {
    122            return parent.indexOf(obj);
    123        }
    124
    125        @Override
    126        public ListIterator<K> listIterator() {
    127            return UnmodifiableListIterator.unmodifiableListIterator(super.listIterator());
    128        }
    129
    130        @Override
    131        public ListIterator<K> listIterator(final int fromIndex) {
    132            return UnmodifiableListIterator.unmodifiableListIterator(super.listIterator(fromIndex));
    133        }
    134
    135        /**
    136         * Always throws {@link UnsupportedOperationException}.
    137         *
    138         * @param index Ignored.
    139         * @throws UnsupportedOperationException Always thrown.
    140         */
    141        @Override
    142        public K remove(final int index) {
    143            throw new UnsupportedOperationException();
    144        }
    145
    146        /**
    147         * Always throws {@link UnsupportedOperationException}.
    148         *
    149         * @param obj Ignored.
    150         * @throws UnsupportedOperationException Always thrown.
    151         */
    152        @Override
    153        public boolean remove(final Object obj) {
    154            throw new UnsupportedOperationException();
    155        }
    156
    157        /**
    158         * Always throws {@link UnsupportedOperationException}.
    159         *
    160         * @param coll Ignored.
    161         * @throws UnsupportedOperationException Always thrown.
    162         */
    163        @Override
    164        public boolean removeAll(final Collection<?> coll) {
    165            throw new UnsupportedOperationException();
    166        }
    167
    168        /**
    169         * Always throws {@link UnsupportedOperationException}.
    170         *
    171         * @param filter Ignored.
    172         * @throws UnsupportedOperationException Always thrown.
    173         * @since 4.4
    174         */
    175        @Override
    176        public boolean removeIf(final Predicate<? super K> filter) {
    177            throw new UnsupportedOperationException();
    178        }
    179
    180        /**
    181         * Always throws {@link UnsupportedOperationException}.
    182         *
    183         * @param coll Ignored.
    184         * @throws UnsupportedOperationException Always thrown.
    185         */
    186        @Override
    187        public boolean retainAll(final Collection<?> coll) {
    188            throw new UnsupportedOperationException();
    189        }
    190
    191        @Override
    192        public int size() {
    193            return parent.size();
    194        }
    195
    196        @Override
    197        public List<K> subList(final int fromIndexInclusive, final int toIndexExclusive) {
    198            return UnmodifiableList.unmodifiableList(super.subList(fromIndexInclusive, toIndexExclusive));
    199        }
    200
    201        @Override
    202        public Object[] toArray() {
    203            return parent.keySet().toArray();
    204        }
    205
    206        @Override
    207        public <T> T[] toArray(final T[] array) {
    208            return parent.keySet().toArray(array);
    209        }
    210    }
    211
    212    /** Serialization version */
    213    private static final long serialVersionUID = 9077234323521161066L;
    214
    215    /**
    216     * Constructs a new empty map with default size and load factor.
    217     */
    218    public LinkedMap() {
    219        super(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_THRESHOLD);
    220    }
    221
    222    /**
    223     * Constructs a new, empty map with the specified initial capacity.
    224     *
    225     * @param initialCapacity  The initial capacity
    226     * @throws IllegalArgumentException if the initial capacity is negative
    227     */
    228    public LinkedMap(final int initialCapacity) {
    229        super(initialCapacity);
    230    }
    231
    232    /**
    233     * Constructs a new, empty map with the specified initial capacity and
    234     * load factor.
    235     *
    236     * @param initialCapacity  The initial capacity
    237     * @param loadFactor  The load factor
    238     * @throws IllegalArgumentException if the initial capacity is negative
    239     * @throws IllegalArgumentException if the load factor is less than zero
    240     */
    241    public LinkedMap(final int initialCapacity, final float loadFactor) {
    242        super(initialCapacity, loadFactor);
    243    }
    244
    245    /**
    246     * Constructor copying elements from another map.
    247     *
    248     * @param map  The map to copy
    249     * @throws NullPointerException if the map is null
    250     */
    251    public LinkedMap(final Map<? extends K, ? extends V> map) {
    252        super(map);
    253    }
    254
    255    /**
    256     * Gets an unmodifiable List view of the keys.
    257     * <p>
    258     * The returned list is unmodifiable because changes to the values of
    259     * the list (using {@link java.util.ListIterator#set(Object)}) will
    260     * effectively remove the value from the list and reinsert that value at
    261     * the end of the list, which is an unexpected side effect of changing the
    262     * value of a list.  This occurs because changing the key, changes when the
    263     * mapping is added to the map and thus where it appears in the list.
    264     * </p>
    265     * <p>
    266     * An alternative to this method is to use {@link #keySet()}.
    267     * </p>
    268     *
    269     * @see #keySet()
    270     * @return The ordered list of keys.
    271     */
    272    public List<K> asList() {
    273        return new LinkedMapList<>(this);
    274    }
    275
    276    /**
    277     * Clones the map without cloning the keys or values.
    278     *
    279     * @return A shallow clone
    280     */
    281    @Override
    282    public LinkedMap<K, V> clone() {
    283        return (LinkedMap<K, V>) super.clone();
    284    }
    285
    286    /**
    287     * Gets the key at the specified index.
    288     *
    289     * @param index  The index to retrieve
    290     * @return The key at the specified index
    291     * @throws IndexOutOfBoundsException if the index is invalid
    292     */
    293    public K get(final int index) {
    294        return getEntry(index).getKey();
    295    }
    296
    297    /**
    298     * Gets the value at the specified index.
    299     *
    300     * @param index  The index to retrieve
    301     * @return The value at the specified index
    302     * @throws IndexOutOfBoundsException if the index is invalid
    303     */
    304    public V getValue(final int index) {
    305        return getEntry(index).getValue();
    306    }
    307
    308    /**
    309     * Gets the index of the specified key.
    310     *
    311     * @param key  The key to find the index of
    312     * @return The index, or -1 if not found
    313     */
    314    public int indexOf(Object key) {
    315        key = convertKey(key);
    316        int i = 0;
    317        for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after, i++) {
    318            if (isEqualKey(key, entry.key)) {
    319                return i;
    320            }
    321        }
    322        return CollectionUtils.INDEX_NOT_FOUND;
    323    }
    324
    325    /**
    326     * Deserializes the map in using a custom routine.
    327     *
    328     * @param in The input stream
    329     * @throws IOException Thrown if an error occurs while reading from the stream
    330     * @throws ClassNotFoundException if an object read from the stream cannot be loaded
    331     */
    332    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    333        in.defaultReadObject();
    334        doReadObject(in);
    335    }
    336
    337    /**
    338     * Removes the element at the specified index.
    339     *
    340     * @param index  The index of the object to remove
    341     * @return The previous value corresponding the {@code key},
    342     *  or {@code null} if none existed
    343     * @throws IndexOutOfBoundsException if the index is invalid
    344     */
    345    public V remove(final int index) {
    346        return remove(get(index));
    347    }
    348
    349    /**
    350     * Serializes this object to an ObjectOutputStream.
    351     *
    352     * @param out The target ObjectOutputStream.
    353     * @throws IOException thrown when an I/O errors occur writing to the target stream.
    354     */
    355    private void writeObject(final ObjectOutputStream out) throws IOException {
    356        out.defaultWriteObject();
    357        doWriteObject(out);
    358    }
    359
    360}