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.collections.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
30 import org.apache.commons.collections.iterators.UnmodifiableIterator;
31 import org.apache.commons.collections.iterators.UnmodifiableListIterator;
32 import org.apache.commons.collections.list.UnmodifiableList;
33
34 /**
35 * A <code>Map</code> implementation that maintains the order of the entries.
36 * In this implementation order is maintained by original insertion.
37 * <p>
38 * This implementation improves on the JDK1.4 LinkedHashMap by adding the
39 * {@link org.apache.commons.collections.MapIterator MapIterator}
40 * functionality, additional convenience methods and allowing
41 * bidirectional iteration. It also implements <code>OrderedMap</code>.
42 * In addition, non-interface methods are provided to access the map by index.
43 * <p>
44 * The <code>orderedMapIterator()</code> method provides direct access to a
45 * bidirectional iterator. The iterators from the other views can also be cast
46 * to <code>OrderedIterator</code> if required.
47 * <p>
48 * All the available iterators can be reset back to the start by casting to
49 * <code>ResettableIterator</code> and calling <code>reset()</code>.
50 * <p>
51 * The implementation is also designed to be subclassed, with lots of useful
52 * methods exposed.
53 * <p>
54 * <strong>Note that LinkedMap is not synchronized and is not thread-safe.</strong>
55 * If you wish to use this map from multiple threads concurrently, you must use
56 * appropriate synchronization. The simplest approach is to wrap this map
57 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
58 * exceptions when accessed by concurrent threads without synchronization.
59 *
60 * @since 3.0
61 * @version $Id: LinkedMap.java 1429905 2013-01-07 17:15:14Z ggregory $
62 */
63 public class LinkedMap<K, V> extends AbstractLinkedMap<K, V> implements Serializable, Cloneable {
64
65 /** Serialisation version */
66 private static final long serialVersionUID = 9077234323521161066L;
67
68 /**
69 * Constructs a new empty map with default size and load factor.
70 */
71 public LinkedMap() {
72 super(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_THRESHOLD);
73 }
74
75 /**
76 * Constructs a new, empty map with the specified initial capacity.
77 *
78 * @param initialCapacity the initial capacity
79 * @throws IllegalArgumentException if the initial capacity is negative
80 */
81 public LinkedMap(final int initialCapacity) {
82 super(initialCapacity);
83 }
84
85 /**
86 * Constructs a new, empty map with the specified initial capacity and
87 * load factor.
88 *
89 * @param initialCapacity the initial capacity
90 * @param loadFactor the load factor
91 * @throws IllegalArgumentException if the initial capacity is negative
92 * @throws IllegalArgumentException if the load factor is less than zero
93 */
94 public LinkedMap(final int initialCapacity, final float loadFactor) {
95 super(initialCapacity, loadFactor);
96 }
97
98 /**
99 * 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<K, 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 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 }