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