001: /*
002: * Copyright 2003-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.map;
017:
018: import java.io.IOException;
019: import java.io.ObjectInputStream;
020: import java.io.ObjectOutputStream;
021: import java.io.Serializable;
022: import java.util.AbstractList;
023: import java.util.Collection;
024: import java.util.Iterator;
025: import java.util.List;
026: import java.util.ListIterator;
027: import java.util.Map;
028:
029: import org.apache.commons.collections.iterators.UnmodifiableIterator;
030: import org.apache.commons.collections.iterators.UnmodifiableListIterator;
031: import org.apache.commons.collections.list.UnmodifiableList;
032:
033: /**
034: * A <code>Map</code> implementation that maintains the order of the entries.
035: * In this implementation order is maintained by original insertion.
036: * <p>
037: * This implementation improves on the JDK1.4 LinkedHashMap by adding the
038: * {@link org.apache.commons.collections.MapIterator MapIterator}
039: * functionality, additional convenience methods and allowing
040: * bidirectional iteration. It also implements <code>OrderedMap</code>.
041: * In addition, non-interface methods are provided to access the map by index.
042: * <p>
043: * The <code>orderedMapIterator()</code> method provides direct access to a
044: * bidirectional iterator. The iterators from the other views can also be cast
045: * to <code>OrderedIterator</code> if required.
046: * <p>
047: * All the available iterators can be reset back to the start by casting to
048: * <code>ResettableIterator</code> and calling <code>reset()</code>.
049: * <p>
050: * The implementation is also designed to be subclassed, with lots of useful
051: * methods exposed.
052: * <p>
053: * <strong>Note that LinkedMap is not synchronized and is not thread-safe.</strong>
054: * If you wish to use this map from multiple threads concurrently, you must use
055: * appropriate synchronization. The simplest approach is to wrap this map
056: * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
057: * exceptions when accessed by concurrent threads without synchronization.
058: *
059: * @since Commons Collections 3.0
060: * @version $Revision: 348007 $ $Date: 2005-11-21 22:52:57 +0000 (Mon, 21 Nov 2005) $
061: *
062: * @author Stephen Colebourne
063: */
064: public class LinkedMap extends AbstractLinkedMap implements
065: Serializable, Cloneable {
066:
067: /** Serialisation version */
068: private static final long serialVersionUID = 9077234323521161066L;
069:
070: /**
071: * Constructs a new empty map with default size and load factor.
072: */
073: public LinkedMap() {
074: super (DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_THRESHOLD);
075: }
076:
077: /**
078: * Constructs a new, empty map with the specified initial capacity.
079: *
080: * @param initialCapacity the initial capacity
081: * @throws IllegalArgumentException if the initial capacity is less than one
082: */
083: public LinkedMap(int initialCapacity) {
084: super (initialCapacity);
085: }
086:
087: /**
088: * Constructs a new, empty map with the specified initial capacity and
089: * load factor.
090: *
091: * @param initialCapacity the initial capacity
092: * @param loadFactor the load factor
093: * @throws IllegalArgumentException if the initial capacity is less than one
094: * @throws IllegalArgumentException if the load factor is less than zero
095: */
096: public LinkedMap(int initialCapacity, float loadFactor) {
097: super (initialCapacity, loadFactor);
098: }
099:
100: /**
101: * Constructor copying elements from another map.
102: *
103: * @param map the map to copy
104: * @throws NullPointerException if the map is null
105: */
106: public LinkedMap(Map map) {
107: super (map);
108: }
109:
110: //-----------------------------------------------------------------------
111: /**
112: * Clones the map without cloning the keys or values.
113: *
114: * @return a shallow clone
115: */
116: public Object clone() {
117: return super .clone();
118: }
119:
120: /**
121: * Write the map out using a custom routine.
122: */
123: private void writeObject(ObjectOutputStream out) throws IOException {
124: out.defaultWriteObject();
125: doWriteObject(out);
126: }
127:
128: /**
129: * Read the map in using a custom routine.
130: */
131: private void readObject(ObjectInputStream in) throws IOException,
132: 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()
273: .iterator());
274: }
275:
276: public ListIterator listIterator() {
277: return UnmodifiableListIterator.decorate(super
278: .listIterator());
279: }
280:
281: public ListIterator listIterator(int fromIndex) {
282: return UnmodifiableListIterator.decorate(super
283: .listIterator(fromIndex));
284: }
285:
286: public List subList(int fromIndexInclusive, int toIndexExclusive) {
287: return UnmodifiableList.decorate(super.subList(
288: fromIndexInclusive, toIndexExclusive));
289: }
290: }
291:
292: }
|