1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4.map;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.ObjectOutputStream;
22 import java.io.Serializable;
23 import java.util.AbstractList;
24 import java.util.Collection;
25 import java.util.Iterator;
26 import java.util.List;
27 import java.util.ListIterator;
28 import java.util.Map;
29 import java.util.function.Predicate;
30
31 import org.apache.commons.collections4.CollectionUtils;
32 import org.apache.commons.collections4.iterators.UnmodifiableIterator;
33 import org.apache.commons.collections4.iterators.UnmodifiableListIterator;
34 import org.apache.commons.collections4.list.UnmodifiableList;
35
36 /**
37 * A {@code Map} implementation that maintains the order of the entries.
38 * In this implementation order is maintained by original insertion.
39 * <p>
40 * This implementation improves on the JDK1.4 LinkedHashMap by adding the
41 * {@link org.apache.commons.collections4.MapIterator MapIterator}
42 * functionality, additional convenience methods and allowing
43 * bidirectional iteration. It also implements {@code OrderedMap}.
44 * In addition, non-interface methods are provided to access the map by index.
45 * </p>
46 * <p>
47 * The {@code orderedMapIterator()} method provides direct access to a
48 * bidirectional iterator. The iterators from the other views can also be cast
49 * to {@code OrderedIterator} if required.
50 * </p>
51 * <p>
52 * All the available iterators can be reset back to the start by casting to
53 * {@code ResettableIterator} and calling {@code reset()}.
54 * </p>
55 * <p>
56 * The implementation is also designed to be subclassed, with lots of useful
57 * methods exposed.
58 * </p>
59 * <p>
60 * <strong>Note that LinkedMap is not synchronized and is not thread-safe.</strong>
61 * If you wish to use this map from multiple threads concurrently, you must use
62 * appropriate synchronization. The simplest approach is to wrap this map
63 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
64 * exceptions when accessed by concurrent threads without synchronization.
65 * </p>
66 *
67 * @param <K> the type of the keys in this map
68 * @param <V> the type of the values in this map
69 * @since 3.0
70 */
71 public class LinkedMap<K, V> extends AbstractLinkedMap<K, V> implements Serializable, Cloneable {
72
73 /**
74 * List view of map.
75 */
76 static class LinkedMapList<K> extends AbstractList<K> {
77
78 private final LinkedMap<K, ?> parent;
79
80 LinkedMapList(final LinkedMap<K, ?> parent) {
81 this.parent = parent;
82 }
83
84 @Override
85 public void clear() {
86 throw new UnsupportedOperationException();
87 }
88
89 @Override
90 public boolean contains(final Object obj) {
91 return parent.containsKey(obj);
92 }
93
94 @Override
95 public boolean containsAll(final Collection<?> coll) {
96 return parent.keySet().containsAll(coll);
97 }
98
99 @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 }