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