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