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    }