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.AbstractSet;
025    import java.util.ArrayList;
026    import java.util.Collection;
027    import java.util.HashMap;
028    import java.util.Iterator;
029    import java.util.List;
030    import java.util.ListIterator;
031    import java.util.Map;
032    import java.util.NoSuchElementException;
033    import java.util.Set;
034    
035    import org.apache.commons.collections.MapIterator;
036    import org.apache.commons.collections.OrderedMap;
037    import org.apache.commons.collections.OrderedMapIterator;
038    import org.apache.commons.collections.ResettableIterator;
039    import org.apache.commons.collections.iterators.AbstractIteratorDecorator;
040    import org.apache.commons.collections.keyvalue.AbstractMapEntry;
041    import org.apache.commons.collections.list.UnmodifiableList;
042    
043    /**
044     * Decorates a <code>Map</code> to ensure that the order of addition is retained
045     * using a <code>List</code> to maintain order.
046     * <p>
047     * The order will be used via the iterators and toArray methods on the views.
048     * The order is also returned by the <code>MapIterator</code>.
049     * The <code>orderedMapIterator()</code> method accesses an iterator that can
050     * iterate both forwards and backwards through the map.
051     * In addition, non-interface methods are provided to access the map by index.
052     * <p>
053     * If an object is added to the Map for a second time, it will remain in the
054     * original position in the iteration.
055     * <p>
056     * <strong>Note that ListOrderedMap is not synchronized and is not thread-safe.</strong>
057     * If you wish to use this map from multiple threads concurrently, you must use
058     * appropriate synchronization. The simplest approach is to wrap this map
059     * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw 
060     * exceptions when accessed by concurrent threads without synchronization.
061     * <p>
062     * This class is Serializable from Commons Collections 3.1.
063     *
064     * @since Commons Collections 3.0
065     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
066     * 
067     * @author Henri Yandell
068     * @author Stephen Colebourne
069     * @author Matt Benson
070     */
071    public class ListOrderedMap
072            extends AbstractMapDecorator
073            implements OrderedMap, Serializable {
074    
075        /** Serialization version */
076        private static final long serialVersionUID = 2728177751851003750L;
077    
078        /** Internal list to hold the sequence of objects */
079        protected final List insertOrder = new ArrayList();
080    
081        /**
082         * Factory method to create an ordered map.
083         * <p>
084         * An <code>ArrayList</code> is used to retain order.
085         * 
086         * @param map  the map to decorate, must not be null
087         * @throws IllegalArgumentException if map is null
088         */
089        public static OrderedMap decorate(Map map) {
090            return new ListOrderedMap(map);
091        }
092    
093        //-----------------------------------------------------------------------
094        /**
095         * Constructs a new empty <code>ListOrderedMap</code> that decorates
096         * a <code>HashMap</code>.
097         * 
098         * @since Commons Collections 3.1
099         */
100        public ListOrderedMap() {
101            this(new HashMap());
102        }
103    
104        /**
105         * Constructor that wraps (not copies).
106         * 
107         * @param map  the map to decorate, must not be null
108         * @throws IllegalArgumentException if map is null
109         */
110        protected ListOrderedMap(Map map) {
111            super(map);
112            insertOrder.addAll(getMap().keySet());
113        }
114    
115        //-----------------------------------------------------------------------
116        /**
117         * Write the map out using a custom routine.
118         * 
119         * @param out  the output stream
120         * @throws IOException
121         * @since Commons Collections 3.1
122         */
123        private void writeObject(ObjectOutputStream out) throws IOException {
124            out.defaultWriteObject();
125            out.writeObject(map);
126        }
127    
128        /**
129         * Read the map in using a custom routine.
130         * 
131         * @param in  the input stream
132         * @throws IOException
133         * @throws ClassNotFoundException
134         * @since Commons Collections 3.1
135         */
136        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
137            in.defaultReadObject();
138            map = (Map) in.readObject();
139        }
140    
141        // Implement OrderedMap
142        //-----------------------------------------------------------------------
143        public MapIterator mapIterator() {
144            return orderedMapIterator();
145        }
146    
147        public OrderedMapIterator orderedMapIterator() {
148            return new ListOrderedMapIterator(this);
149        }
150    
151        /**
152         * Gets the first key in this map by insert order.
153         *
154         * @return the first key currently in this map
155         * @throws NoSuchElementException if this map is empty
156         */
157        public Object firstKey() {
158            if (size() == 0) {
159                throw new NoSuchElementException("Map is empty");
160            }
161            return insertOrder.get(0);
162        }
163    
164        /**
165         * Gets the last key in this map by insert order.
166         *
167         * @return the last key currently in this map
168         * @throws NoSuchElementException if this map is empty
169         */
170        public Object lastKey() {
171            if (size() == 0) {
172                throw new NoSuchElementException("Map is empty");
173            }
174            return insertOrder.get(size() - 1);
175        }
176        
177        /**
178         * Gets the next key to the one specified using insert order.
179         * This method performs a list search to find the key and is O(n).
180         * 
181         * @param key  the key to find previous for
182         * @return the next key, null if no match or at start
183         */
184        public Object nextKey(Object key) {
185            int index = insertOrder.indexOf(key);
186            if (index >= 0 && index < size() - 1) {
187                return insertOrder.get(index + 1);
188            }
189            return null;
190        }
191    
192        /**
193         * Gets the previous key to the one specified using insert order.
194         * This method performs a list search to find the key and is O(n).
195         * 
196         * @param key  the key to find previous for
197         * @return the previous key, null if no match or at start
198         */
199        public Object previousKey(Object key) {
200            int index = insertOrder.indexOf(key);
201            if (index > 0) {
202                return insertOrder.get(index - 1);
203            }
204            return null;
205        }
206    
207        //-----------------------------------------------------------------------
208        public Object put(Object key, Object value) {
209            if (getMap().containsKey(key)) {
210                // re-adding doesn't change order
211                return getMap().put(key, value);
212            } else {
213                // first add, so add to both map and list
214                Object result = getMap().put(key, value);
215                insertOrder.add(key);
216                return result;
217            }
218        }
219    
220        public void putAll(Map map) {
221            for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
222                Map.Entry entry = (Map.Entry) it.next();
223                put(entry.getKey(), entry.getValue());
224            }
225        }
226    
227        public Object remove(Object key) {
228            Object result = getMap().remove(key);
229            insertOrder.remove(key);
230            return result;
231        }
232    
233        public void clear() {
234            getMap().clear();
235            insertOrder.clear();
236        }
237    
238        //-----------------------------------------------------------------------
239        /**
240         * Gets a view over the keys in the map.
241         * <p>
242         * The Collection will be ordered by object insertion into the map.
243         *
244         * @see #keyList()
245         * @return the fully modifiable collection view over the keys
246         */
247        public Set keySet() {
248            return new KeySetView(this);
249        }
250    
251        /**
252         * Gets a view over the keys in the map as a List.
253         * <p>
254         * The List will be ordered by object insertion into the map.
255         * The List is unmodifiable.
256         *
257         * @see #keySet()
258         * @return the unmodifiable list view over the keys
259         * @since Commons Collections 3.2
260         */
261        public List keyList() {
262            return UnmodifiableList.decorate(insertOrder);
263        }
264    
265        /**
266         * Gets a view over the values in the map.
267         * <p>
268         * The Collection will be ordered by object insertion into the map.
269         * <p>
270         * From Commons Collections 3.2, this Collection can be cast
271         * to a list, see {@link #valueList()}
272         *
273         * @see #valueList()
274         * @return the fully modifiable collection view over the values
275         */
276        public Collection values() {
277            return new ValuesView(this);
278        }
279    
280        /**
281         * Gets a view over the values in the map as a List.
282         * <p>
283         * The List will be ordered by object insertion into the map.
284         * The List supports remove and set, but does not support add.
285         *
286         * @see #values()
287         * @return the partially modifiable list view over the values
288         * @since Commons Collections 3.2
289         */
290        public List valueList() {
291            return new ValuesView(this);
292        }
293    
294        /**
295         * Gets a view over the entries in the map.
296         * <p>
297         * The Set will be ordered by object insertion into the map.
298         *
299         * @return the fully modifiable set view over the entries
300         */
301        public Set entrySet() {
302            return new EntrySetView(this, this.insertOrder);
303        }
304    
305        //-----------------------------------------------------------------------
306        /**
307         * Returns the Map as a string.
308         * 
309         * @return the Map as a String
310         */
311        public String toString() {
312            if (isEmpty()) {
313                return "{}";
314            }
315            StringBuffer buf = new StringBuffer();
316            buf.append('{');
317            boolean first = true;
318            Iterator it = entrySet().iterator();
319            while (it.hasNext()) {
320                Map.Entry entry = (Map.Entry) it.next();
321                Object key = entry.getKey();
322                Object value = entry.getValue();
323                if (first) {
324                    first = false;
325                } else {
326                    buf.append(", ");
327                }
328                buf.append(key == this ? "(this Map)" : key);
329                buf.append('=');
330                buf.append(value == this ? "(this Map)" : value);
331            }
332            buf.append('}');
333            return buf.toString();
334        }
335    
336        //-----------------------------------------------------------------------
337        /**
338         * Gets the key at the specified index.
339         * 
340         * @param index  the index to retrieve
341         * @return the key at the specified index
342         * @throws IndexOutOfBoundsException if the index is invalid
343         */
344        public Object get(int index) {
345            return insertOrder.get(index);
346        }
347        
348        /**
349         * Gets the value at the specified index.
350         * 
351         * @param index  the index to retrieve
352         * @return the key at the specified index
353         * @throws IndexOutOfBoundsException if the index is invalid
354         */
355        public Object getValue(int index) {
356            return get(insertOrder.get(index));
357        }
358        
359        /**
360         * Gets the index of the specified key.
361         * 
362         * @param key  the key to find the index of
363         * @return the index, or -1 if not found
364         */
365        public int indexOf(Object key) {
366            return insertOrder.indexOf(key);
367        }
368    
369        /**
370         * Sets the value at the specified index.
371         *
372         * @param index  the index of the value to set
373         * @return the previous value at that index
374         * @throws IndexOutOfBoundsException if the index is invalid
375         * @since Commons Collections 3.2
376         */
377        public Object setValue(int index, Object value) {
378            Object key = insertOrder.get(index);
379            return put(key, value);
380        }
381    
382        /**
383         * Puts a key-value mapping into the map at the specified index.
384         * <p>
385         * If the map already contains the key, then the original mapping
386         * is removed and the new mapping added at the specified index.
387         * The remove may change the effect of the index. The index is
388         * always calculated relative to the original state of the map.
389         * <p>
390         * Thus the steps are: (1) remove the existing key-value mapping,
391         * then (2) insert the new key-value mapping at the position it
392         * would have been inserted had the remove not ocurred.
393         *
394         * @param index  the index at which the mapping should be inserted
395         * @param key  the key
396         * @param value  the value
397         * @return the value previously mapped to the key
398         * @throws IndexOutOfBoundsException if the index is out of range
399         * @since Commons Collections 3.2
400         */
401        public Object put(int index, Object key, Object value) {
402            Map m = getMap();
403            if (m.containsKey(key)) {
404                Object result = m.remove(key);
405                int pos = insertOrder.indexOf(key);
406                insertOrder.remove(pos);
407                if (pos < index) {
408                    index--;
409                }
410                insertOrder.add(index, key);
411                m.put(key, value);
412                return result;
413            } else {
414                insertOrder.add(index, key);
415                m.put(key, value);
416                return null;
417            }
418        }
419    
420        /**
421         * Removes the element at the specified index.
422         *
423         * @param index  the index of the object to remove
424         * @return the removed value, or <code>null</code> if none existed
425         * @throws IndexOutOfBoundsException if the index is invalid
426         */
427        public Object remove(int index) {
428            return remove(get(index));
429        }
430    
431        /**
432         * Gets an unmodifiable List view of the keys which changes as the map changes.
433         * <p>
434         * The returned list is unmodifiable because changes to the values of
435         * the list (using {@link java.util.ListIterator#set(Object)}) will
436         * effectively remove the value from the list and reinsert that value at
437         * the end of the list, which is an unexpected side effect of changing the
438         * value of a list.  This occurs because changing the key, changes when the
439         * mapping is added to the map and thus where it appears in the list.
440         * <p>
441         * An alternative to this method is to use the better named
442         * {@link #keyList()} or {@link #keySet()}.
443         *
444         * @see #keyList()
445         * @see #keySet()
446         * @return The ordered list of keys.  
447         */
448        public List asList() {
449            return keyList();
450        }
451    
452        //-----------------------------------------------------------------------
453        static class ValuesView extends AbstractList {
454            private final ListOrderedMap parent;
455    
456            ValuesView(ListOrderedMap parent) {
457                super();
458                this.parent = parent;
459            }
460    
461            public int size() {
462                return this.parent.size();
463            }
464    
465            public boolean contains(Object value) {
466                return this.parent.containsValue(value);
467            }
468    
469            public void clear() {
470                this.parent.clear();
471            }
472    
473            public Iterator iterator() {
474                return new AbstractIteratorDecorator(parent.entrySet().iterator()) {
475                    public Object next() {
476                        return ((Map.Entry) iterator.next()).getValue();
477                    }
478                };
479            }
480    
481            public Object get(int index) {
482                return this.parent.getValue(index);
483            }
484    
485            public Object set(int index, Object value) {
486                return this.parent.setValue(index, value);
487            }
488    
489            public Object remove(int index) {
490                return this.parent.remove(index);
491            }
492        }
493    
494        //-----------------------------------------------------------------------
495        static class KeySetView extends AbstractSet {
496            private final ListOrderedMap parent;
497    
498            KeySetView(ListOrderedMap parent) {
499                super();
500                this.parent = parent;
501            }
502    
503            public int size() {
504                return this.parent.size();
505            }
506    
507            public boolean contains(Object value) {
508                return this.parent.containsKey(value);
509            }
510    
511            public void clear() {
512                this.parent.clear();
513            }
514    
515            public Iterator iterator() {
516                return new AbstractIteratorDecorator(parent.entrySet().iterator()) {
517                    public Object next() {
518                        return ((Map.Entry) super.next()).getKey();
519                    }
520                };
521            }
522        }
523    
524        //-----------------------------------------------------------------------    
525        static class EntrySetView extends AbstractSet {
526            private final ListOrderedMap parent;
527            private final List insertOrder;
528            private Set entrySet;
529    
530            public EntrySetView(ListOrderedMap parent, List insertOrder) {
531                super();
532                this.parent = parent;
533                this.insertOrder = insertOrder;
534            }
535    
536            private Set getEntrySet() {
537                if (entrySet == null) {
538                    entrySet = parent.getMap().entrySet();
539                }
540                return entrySet;
541            }
542            
543            public int size() {
544                return this.parent.size();
545            }
546            public boolean isEmpty() {
547                return this.parent.isEmpty();
548            }
549    
550            public boolean contains(Object obj) {
551                return getEntrySet().contains(obj);
552            }
553    
554            public boolean containsAll(Collection coll) {
555                return getEntrySet().containsAll(coll);
556            }
557    
558            public boolean remove(Object obj) {
559                if (obj instanceof Map.Entry == false) {
560                    return false;
561                }
562                if (getEntrySet().contains(obj)) {
563                    Object key = ((Map.Entry) obj).getKey();
564                    parent.remove(key);
565                    return true;
566                }
567                return false;
568            }
569    
570            public void clear() {
571                this.parent.clear();
572            }
573            
574            public boolean equals(Object obj) {
575                if (obj == this) {
576                    return true;
577                }
578                return getEntrySet().equals(obj);
579            }
580            
581            public int hashCode() {
582                return getEntrySet().hashCode();
583            }
584    
585            public String toString() {
586                return getEntrySet().toString();
587            }
588            
589            public Iterator iterator() {
590                return new ListOrderedIterator(parent, insertOrder);
591            }
592        }
593        
594        //-----------------------------------------------------------------------
595        static class ListOrderedIterator extends AbstractIteratorDecorator {
596            private final ListOrderedMap parent;
597            private Object last = null;
598            
599            ListOrderedIterator(ListOrderedMap parent, List insertOrder) {
600                super(insertOrder.iterator());
601                this.parent = parent;
602            }
603            
604            public Object next() {
605                last = super.next();
606                return new ListOrderedMapEntry(parent, last);
607            }
608    
609            public void remove() {
610                super.remove();
611                parent.getMap().remove(last);
612            }
613        }
614        
615        //-----------------------------------------------------------------------
616        static class ListOrderedMapEntry extends AbstractMapEntry {
617            private final ListOrderedMap parent;
618            
619            ListOrderedMapEntry(ListOrderedMap parent, Object key) {
620                super(key, null);
621                this.parent = parent;
622            }
623            
624            public Object getValue() {
625                return parent.get(key);
626            }
627    
628            public Object setValue(Object value) {
629                return parent.getMap().put(key, value);
630            }
631        }
632    
633        //-----------------------------------------------------------------------
634        static class ListOrderedMapIterator implements OrderedMapIterator, ResettableIterator {
635            private final ListOrderedMap parent;
636            private ListIterator iterator;
637            private Object last = null;
638            private boolean readable = false;
639            
640            ListOrderedMapIterator(ListOrderedMap parent) {
641                super();
642                this.parent = parent;
643                this.iterator = parent.insertOrder.listIterator();
644            }
645            
646            public boolean hasNext() {
647                return iterator.hasNext();
648            }
649            
650            public Object next() {
651                last = iterator.next();
652                readable = true;
653                return last;
654            }
655            
656            public boolean hasPrevious() {
657                return iterator.hasPrevious();
658            }
659            
660            public Object previous() {
661                last = iterator.previous();
662                readable = true;
663                return last;
664            }
665            
666            public void remove() {
667                if (readable == false) {
668                    throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
669                }
670                iterator.remove();
671                parent.map.remove(last);
672                readable = false;
673            }
674            
675            public Object getKey() {
676                if (readable == false) {
677                    throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
678                }
679                return last;
680            }
681    
682            public Object getValue() {
683                if (readable == false) {
684                    throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
685                }
686                return parent.get(last);
687            }
688            
689            public Object setValue(Object value) {
690                if (readable == false) {
691                    throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
692                }
693                return parent.map.put(last, value);
694            }
695            
696            public void reset() {
697                iterator = parent.insertOrder.listIterator();
698                last = null;
699                readable = false;
700            }
701            
702            public String toString() {
703                if (readable == true) {
704                    return "Iterator[" + getKey() + "=" + getValue() + "]";
705                } else {
706                    return "Iterator[]";
707                }
708            }
709        }
710        
711    }