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    /** Serialisation 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     * An alternative to this method is to use {@link #keySet()}.
232     *
233     * @see #keySet()
234     * @return The ordered list of keys.
235     */
236    public List<K> asList() {
237        return new LinkedMapList<>(this);
238    }
239
240    /**
241     * Clones the map without cloning the keys or values.
242     *
243     * @return a shallow clone
244     */
245    @Override
246    public LinkedMap<K, V> clone() {
247        return (LinkedMap<K, V>) super.clone();
248    }
249
250    /**
251     * Gets the key at the specified index.
252     *
253     * @param index  the index to retrieve
254     * @return the key at the specified index
255     * @throws IndexOutOfBoundsException if the index is invalid
256     */
257    public K get(final int index) {
258        return getEntry(index).getKey();
259    }
260
261    /**
262     * Gets the value at the specified index.
263     *
264     * @param index  the index to retrieve
265     * @return the value at the specified index
266     * @throws IndexOutOfBoundsException if the index is invalid
267     */
268    public V getValue(final int index) {
269        return getEntry(index).getValue();
270    }
271
272    /**
273     * Gets the index of the specified key.
274     *
275     * @param key  the key to find the index of
276     * @return the index, or -1 if not found
277     */
278    public int indexOf(Object key) {
279        key = convertKey(key);
280        int i = 0;
281        for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after, i++) {
282            if (isEqualKey(key, entry.key)) {
283                return i;
284            }
285        }
286        return CollectionUtils.INDEX_NOT_FOUND;
287    }
288
289    /**
290     * Read the map in using a custom routine.
291     *
292     * @param in the input stream
293     * @throws IOException if an error occurs while reading from the stream
294     * @throws ClassNotFoundException if an object read from the stream can not be loaded
295     */
296    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
297        in.defaultReadObject();
298        doReadObject(in);
299    }
300
301    /**
302     * Removes the element at the specified index.
303     *
304     * @param index  the index of the object to remove
305     * @return the previous value corresponding the {@code key},
306     *  or {@code null} if none existed
307     * @throws IndexOutOfBoundsException if the index is invalid
308     */
309    public V remove(final int index) {
310        return remove(get(index));
311    }
312
313    /**
314     * Write the map out using a custom routine.
315     *
316     * @param out  the output stream
317     * @throws IOException if an error occurs while writing to the stream
318     */
319    private void writeObject(final ObjectOutputStream out) throws IOException {
320        out.defaultWriteObject();
321        doWriteObject(out);
322    }
323
324}