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