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 * @since 3.0
061 * @version $Id: LinkedMap.html 887892 2013-11-24 13:43:45Z tn $
062 */
063public class LinkedMap<K, V> extends AbstractLinkedMap<K, V> implements Serializable, Cloneable {
064
065    /** Serialisation version */
066    private static final long serialVersionUID = 9077234323521161066L;
067
068    /**
069     * Constructs a new empty map with default size and load factor.
070     */
071    public LinkedMap() {
072        super(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_THRESHOLD);
073    }
074
075    /**
076     * Constructs a new, empty map with the specified initial capacity.
077     *
078     * @param initialCapacity  the initial capacity
079     * @throws IllegalArgumentException if the initial capacity is negative
080     */
081    public LinkedMap(final int initialCapacity) {
082        super(initialCapacity);
083    }
084
085    /**
086     * Constructs a new, empty map with the specified initial capacity and
087     * load factor.
088     *
089     * @param initialCapacity  the initial capacity
090     * @param loadFactor  the load factor
091     * @throws IllegalArgumentException if the initial capacity is negative
092     * @throws IllegalArgumentException if the load factor is less than zero
093     */
094    public LinkedMap(final int initialCapacity, final float loadFactor) {
095        super(initialCapacity, loadFactor);
096    }
097
098    /**
099     * Constructor copying elements from another map.
100     *
101     * @param map  the map to copy
102     * @throws NullPointerException if the map is null
103     */
104    public LinkedMap(final Map<? extends K, ? extends V> map) {
105        super(map);
106    }
107
108    //-----------------------------------------------------------------------
109    /**
110     * Clones the map without cloning the keys or values.
111     *
112     * @return a shallow clone
113     */
114    @Override
115    public LinkedMap<K, V> clone() {
116        return (LinkedMap<K, V>) super.clone();
117    }
118
119    /**
120     * Write the map out using a custom routine.
121     */
122    private void writeObject(final ObjectOutputStream out) throws IOException {
123        out.defaultWriteObject();
124        doWriteObject(out);
125    }
126
127    /**
128     * Read the map in using a custom routine.
129     */
130    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
131        in.defaultReadObject();
132        doReadObject(in);
133    }
134
135    //-----------------------------------------------------------------------
136    /**
137     * Gets the key at the specified index.
138     *
139     * @param index  the index to retrieve
140     * @return the key at the specified index
141     * @throws IndexOutOfBoundsException if the index is invalid
142     */
143    public K get(final int index) {
144        return getEntry(index).getKey();
145    }
146
147    /**
148     * Gets the value at the specified index.
149     *
150     * @param index  the index to retrieve
151     * @return the value at the specified index
152     * @throws IndexOutOfBoundsException if the index is invalid
153     */
154    public V getValue(final int index) {
155        return getEntry(index).getValue();
156    }
157
158    /**
159     * Gets the index of the specified key.
160     *
161     * @param key  the key to find the index of
162     * @return the index, or -1 if not found
163     */
164    public int indexOf(Object key) {
165        key = convertKey(key);
166        int i = 0;
167        for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after, i++) {
168            if (isEqualKey(key, entry.key)) {
169                return i;
170            }
171        }
172        return -1;
173    }
174
175    /**
176     * Removes the element at the specified index.
177     *
178     * @param index  the index of the object to remove
179     * @return the previous value corresponding the <code>key</code>,
180     *  or <code>null</code> if none existed
181     * @throws IndexOutOfBoundsException if the index is invalid
182     */
183    public V remove(final int index) {
184        return remove(get(index));
185    }
186
187    /**
188     * Gets an unmodifiable List view of the keys.
189     * <p>
190     * The returned list is unmodifiable because changes to the values of
191     * the list (using {@link java.util.ListIterator#set(Object)}) will
192     * effectively remove the value from the list and reinsert that value at
193     * the end of the list, which is an unexpected side effect of changing the
194     * value of a list.  This occurs because changing the key, changes when the
195     * mapping is added to the map and thus where it appears in the list.
196     * <p>
197     * An alternative to this method is to use {@link #keySet()}.
198     *
199     * @see #keySet()
200     * @return The ordered list of keys.
201     */
202    public List<K> asList() {
203        return new LinkedMapList<K>(this);
204    }
205
206    /**
207     * List view of map.
208     */
209    static class LinkedMapList<K> extends AbstractList<K> {
210
211        private final LinkedMap<K, ?> parent;
212
213        LinkedMapList(final LinkedMap<K, ?> parent) {
214            this.parent = parent;
215        }
216
217        @Override
218        public int size() {
219            return parent.size();
220        }
221
222        @Override
223        public K get(final int index) {
224            return parent.get(index);
225        }
226
227        @Override
228        public boolean contains(final Object obj) {
229            return parent.containsKey(obj);
230        }
231
232        @Override
233        public int indexOf(final Object obj) {
234            return parent.indexOf(obj);
235        }
236
237        @Override
238        public int lastIndexOf(final Object obj) {
239            return parent.indexOf(obj);
240        }
241
242        @Override
243        public boolean containsAll(final Collection<?> coll) {
244            return parent.keySet().containsAll(coll);
245        }
246
247        @Override
248        public K remove(final int index) {
249            throw new UnsupportedOperationException();
250        }
251
252        @Override
253        public boolean remove(final Object obj) {
254            throw new UnsupportedOperationException();
255        }
256
257        @Override
258        public boolean removeAll(final Collection<?> coll) {
259            throw new UnsupportedOperationException();
260        }
261
262        @Override
263        public boolean retainAll(final Collection<?> coll) {
264            throw new UnsupportedOperationException();
265        }
266
267        @Override
268        public void clear() {
269            throw new UnsupportedOperationException();
270        }
271
272        @Override
273        public Object[] toArray() {
274            return parent.keySet().toArray();
275        }
276
277        @Override
278        public <T> T[] toArray(final T[] array) {
279            return parent.keySet().toArray(array);
280        }
281
282        @Override
283        public Iterator<K> iterator() {
284            return UnmodifiableIterator.unmodifiableIterator(parent.keySet().iterator());
285        }
286
287        @Override
288        public ListIterator<K> listIterator() {
289            return UnmodifiableListIterator.umodifiableListIterator(super.listIterator());
290        }
291
292        @Override
293        public ListIterator<K> listIterator(final int fromIndex) {
294            return UnmodifiableListIterator.umodifiableListIterator(super.listIterator(fromIndex));
295        }
296
297        @Override
298        public List<K> subList(final int fromIndexInclusive, final int toIndexExclusive) {
299            return UnmodifiableList.unmodifiableList(super.subList(fromIndexInclusive, toIndexExclusive));
300        }
301    }
302
303}