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 1015642 2017-07-18 12:10:19Z chtompki $
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 NullPointerException 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 NullPointerException 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    @Override
167    public K firstKey() {
168        if (size() == 0) {
169            throw new NoSuchElementException("Map is empty");
170        }
171        return insertOrder.get(0);
172    }
173
174    /**
175     * Gets the last key in this map by insert order.
176     *
177     * @return the last key currently in this map
178     * @throws NoSuchElementException if this map is empty
179     */
180    @Override
181    public K lastKey() {
182        if (size() == 0) {
183            throw new NoSuchElementException("Map is empty");
184        }
185        return insertOrder.get(size() - 1);
186    }
187
188    /**
189     * Gets the next key to the one specified using insert order.
190     * This method performs a list search to find the key and is O(n).
191     *
192     * @param key  the key to find previous for
193     * @return the next key, null if no match or at start
194     */
195    @Override
196    public K nextKey(final Object key) {
197        final int index = insertOrder.indexOf(key);
198        if (index >= 0 && index < size() - 1) {
199            return insertOrder.get(index + 1);
200        }
201        return null;
202    }
203
204    /**
205     * Gets the previous key to the one specified using insert order.
206     * This method performs a list search to find the key and is O(n).
207     *
208     * @param key  the key to find previous for
209     * @return the previous key, null if no match or at start
210     */
211    @Override
212    public K previousKey(final Object key) {
213        final int index = insertOrder.indexOf(key);
214        if (index > 0) {
215            return insertOrder.get(index - 1);
216        }
217        return null;
218    }
219
220    //-----------------------------------------------------------------------
221    @Override
222    public V put(final K key, final V value) {
223        if (decorated().containsKey(key)) {
224            // re-adding doesn't change order
225            return decorated().put(key, value);
226        }
227        // first add, so add to both map and list
228        final V result = decorated().put(key, value);
229        insertOrder.add(key);
230        return result;
231    }
232
233    @Override
234    public void putAll(final Map<? extends K, ? extends V> map) {
235        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
236            put(entry.getKey(), entry.getValue());
237        }
238    }
239
240    /**
241     * Puts the values contained in a supplied Map into the Map starting at
242     * the specified index.
243     *
244     * @param index the index in the Map to start at.
245     * @param map the Map containing the entries to be added.
246     * @throws IndexOutOfBoundsException if the index is out of range [0, size]
247     */
248    public void putAll(int index, final Map<? extends K, ? extends V> map) {
249        if (index < 0 || index > insertOrder.size()) {
250            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size());
251        }
252        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
253            final K key = entry.getKey();
254            final boolean contains = containsKey(key);
255            // The return value of put is null if the key did not exist OR the value was null
256            // so it cannot be used to determine whether the key was added
257            put(index, entry.getKey(), entry.getValue());
258            if (!contains) {
259                // if no key was replaced, increment the index
260                index++;
261            } else {
262                // otherwise put the next item after the currently inserted key
263                index = indexOf(entry.getKey()) + 1;
264            }
265        }
266    }
267
268    @Override
269    public V remove(final Object key) {
270        V result = null;
271        if (decorated().containsKey(key)) {
272            result = decorated().remove(key);
273            insertOrder.remove(key);
274        }
275        return result;
276    }
277
278    @Override
279    public void clear() {
280        decorated().clear();
281        insertOrder.clear();
282    }
283
284    //-----------------------------------------------------------------------
285    /**
286     * Gets a view over the keys in the map.
287     * <p>
288     * The Collection will be ordered by object insertion into the map.
289     *
290     * @see #keyList()
291     * @return the fully modifiable collection view over the keys
292     */
293    @Override
294    public Set<K> keySet() {
295        return new KeySetView<K>(this);
296    }
297
298    /**
299     * Gets a view over the keys in the map as a List.
300     * <p>
301     * The List will be ordered by object insertion into the map.
302     * The List is unmodifiable.
303     *
304     * @see #keySet()
305     * @return the unmodifiable list view over the keys
306     * @since 3.2
307     */
308    public List<K> keyList() {
309        return UnmodifiableList.unmodifiableList(insertOrder);
310    }
311
312    /**
313     * Gets a view over the values in the map.
314     * <p>
315     * The Collection will be ordered by object insertion into the map.
316     * <p>
317     * From Commons Collections 3.2, this Collection can be cast
318     * to a list, see {@link #valueList()}
319     *
320     * @see #valueList()
321     * @return the fully modifiable collection view over the values
322     */
323    @Override
324    public Collection<V> values() {
325        return new ValuesView<V>(this);
326    }
327
328    /**
329     * Gets a view over the values in the map as a List.
330     * <p>
331     * The List will be ordered by object insertion into the map.
332     * The List supports remove and set, but does not support add.
333     *
334     * @see #values()
335     * @return the partially modifiable list view over the values
336     * @since 3.2
337     */
338    public List<V> valueList() {
339        return new ValuesView<V>(this);
340    }
341
342    /**
343     * Gets a view over the entries in the map.
344     * <p>
345     * The Set will be ordered by object insertion into the map.
346     *
347     * @return the fully modifiable set view over the entries
348     */
349    @Override
350    public Set<Map.Entry<K, V>> entrySet() {
351        return new EntrySetView<K, V>(this, this.insertOrder);
352    }
353
354    //-----------------------------------------------------------------------
355    /**
356     * Returns the Map as a string.
357     *
358     * @return the Map as a String
359     */
360    @Override
361    public String toString() {
362        if (isEmpty()) {
363            return "{}";
364        }
365        final StringBuilder buf = new StringBuilder();
366        buf.append('{');
367        boolean first = true;
368        for (final Map.Entry<K, V> entry : entrySet()) {
369            final K key = entry.getKey();
370            final V value = entry.getValue();
371            if (first) {
372                first = false;
373            } else {
374                buf.append(", ");
375            }
376            buf.append(key == this ? "(this Map)" : key);
377            buf.append('=');
378            buf.append(value == this ? "(this Map)" : value);
379        }
380        buf.append('}');
381        return buf.toString();
382    }
383
384    //-----------------------------------------------------------------------
385    /**
386     * Gets the key at the specified index.
387     *
388     * @param index  the index to retrieve
389     * @return the key at the specified index
390     * @throws IndexOutOfBoundsException if the index is invalid
391     */
392    public K get(final int index) {
393        return insertOrder.get(index);
394    }
395
396    /**
397     * Gets the value at the specified index.
398     *
399     * @param index  the index to retrieve
400     * @return the key at the specified index
401     * @throws IndexOutOfBoundsException if the index is invalid
402     */
403    public V getValue(final int index) {
404        return get(insertOrder.get(index));
405    }
406
407    /**
408     * Gets the index of the specified key.
409     *
410     * @param key  the key to find the index of
411     * @return the index, or -1 if not found
412     */
413    public int indexOf(final Object key) {
414        return insertOrder.indexOf(key);
415    }
416
417    /**
418     * Sets the value at the specified index.
419     *
420     * @param index  the index of the value to set
421     * @param value  the new value to set
422     * @return the previous value at that index
423     * @throws IndexOutOfBoundsException if the index is invalid
424     * @since 3.2
425     */
426    public V setValue(final int index, final V value) {
427        final K key = insertOrder.get(index);
428        return put(key, value);
429    }
430
431    /**
432     * Puts a key-value mapping into the map at the specified index.
433     * <p>
434     * If the map already contains the key, then the original mapping
435     * is removed and the new mapping added at the specified index.
436     * The remove may change the effect of the index. The index is
437     * always calculated relative to the original state of the map.
438     * <p>
439     * Thus the steps are: (1) remove the existing key-value mapping,
440     * then (2) insert the new key-value mapping at the position it
441     * would have been inserted had the remove not occurred.
442     *
443     * @param index  the index at which the mapping should be inserted
444     * @param key  the key
445     * @param value  the value
446     * @return the value previously mapped to the key
447     * @throws IndexOutOfBoundsException if the index is out of range [0, size]
448     * @since 3.2
449     */
450    public V put(int index, final K key, final V value) {
451        if (index < 0 || index > insertOrder.size()) {
452            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size());
453        }
454
455        final Map<K, V> m = decorated();
456        if (m.containsKey(key)) {
457            final V result = m.remove(key);
458            final int pos = insertOrder.indexOf(key);
459            insertOrder.remove(pos);
460            if (pos < index) {
461                index--;
462            }
463            insertOrder.add(index, key);
464            m.put(key, value);
465            return result;
466        }
467        insertOrder.add(index, key);
468        m.put(key, value);
469        return null;
470    }
471
472    /**
473     * Removes the element at the specified index.
474     *
475     * @param index  the index of the object to remove
476     * @return the removed value, or <code>null</code> if none existed
477     * @throws IndexOutOfBoundsException if the index is invalid
478     */
479    public V remove(final int index) {
480        return remove(get(index));
481    }
482
483    /**
484     * Gets an unmodifiable List view of the keys which changes as the map changes.
485     * <p>
486     * The returned list is unmodifiable because changes to the values of
487     * the list (using {@link java.util.ListIterator#set(Object)}) will
488     * effectively remove the value from the list and reinsert that value at
489     * the end of the list, which is an unexpected side effect of changing the
490     * value of a list.  This occurs because changing the key, changes when the
491     * mapping is added to the map and thus where it appears in the list.
492     * <p>
493     * An alternative to this method is to use the better named
494     * {@link #keyList()} or {@link #keySet()}.
495     *
496     * @see #keyList()
497     * @see #keySet()
498     * @return The ordered list of keys.
499     */
500    public List<K> asList() {
501        return keyList();
502    }
503
504    //-----------------------------------------------------------------------
505    static class ValuesView<V> extends AbstractList<V> {
506        private final ListOrderedMap<Object, V> parent;
507
508        @SuppressWarnings("unchecked")
509        ValuesView(final ListOrderedMap<?, V> parent) {
510            super();
511            this.parent = (ListOrderedMap<Object, V>) parent;
512        }
513
514        @Override
515        public int size() {
516            return this.parent.size();
517        }
518
519        @Override
520        public boolean contains(final Object value) {
521            return this.parent.containsValue(value);
522        }
523
524        @Override
525        public void clear() {
526            this.parent.clear();
527        }
528
529        @Override
530        public Iterator<V> iterator() {
531            return new AbstractUntypedIteratorDecorator<Map.Entry<Object, V>, V>(parent.entrySet().iterator()) {
532                @Override
533                public V next() {
534                    return getIterator().next().getValue();
535                }
536            };
537        }
538
539        @Override
540        public V get(final int index) {
541            return this.parent.getValue(index);
542        }
543
544        @Override
545        public V set(final int index, final V value) {
546            return this.parent.setValue(index, value);
547        }
548
549        @Override
550        public V remove(final int index) {
551            return this.parent.remove(index);
552        }
553    }
554
555    //-----------------------------------------------------------------------
556    static class KeySetView<K> extends AbstractSet<K> {
557        private final ListOrderedMap<K, Object> parent;
558
559        @SuppressWarnings("unchecked")
560        KeySetView(final ListOrderedMap<K, ?> parent) {
561            super();
562            this.parent = (ListOrderedMap<K, Object>) parent;
563        }
564
565        @Override
566        public int size() {
567            return this.parent.size();
568        }
569
570        @Override
571        public boolean contains(final Object value) {
572            return this.parent.containsKey(value);
573        }
574
575        @Override
576        public void clear() {
577            this.parent.clear();
578        }
579
580        @Override
581        public Iterator<K> iterator() {
582            return new AbstractUntypedIteratorDecorator<Map.Entry<K, Object>, K>(parent.entrySet().iterator()) {
583                @Override
584                public K next() {
585                    return getIterator().next().getKey();
586                }
587            };
588        }
589    }
590
591    //-----------------------------------------------------------------------
592    static class EntrySetView<K, V> extends AbstractSet<Map.Entry<K, V>> {
593        private final ListOrderedMap<K, V> parent;
594        private final List<K> insertOrder;
595        private Set<Map.Entry<K, V>> entrySet;
596
597        public EntrySetView(final ListOrderedMap<K, V> parent, final List<K> insertOrder) {
598            super();
599            this.parent = parent;
600            this.insertOrder = insertOrder;
601        }
602
603        private Set<Map.Entry<K, V>> getEntrySet() {
604            if (entrySet == null) {
605                entrySet = parent.decorated().entrySet();
606            }
607            return entrySet;
608        }
609
610        @Override
611        public int size() {
612            return this.parent.size();
613        }
614        @Override
615        public boolean isEmpty() {
616            return this.parent.isEmpty();
617        }
618
619        @Override
620        public boolean contains(final Object obj) {
621            return getEntrySet().contains(obj);
622        }
623
624        @Override
625        public boolean containsAll(final Collection<?> coll) {
626            return getEntrySet().containsAll(coll);
627        }
628
629        @Override
630        @SuppressWarnings("unchecked")
631        public boolean remove(final Object obj) {
632            if (obj instanceof Map.Entry == false) {
633                return false;
634            }
635            if (getEntrySet().contains(obj)) {
636                final Object key = ((Map.Entry<K, V>) obj).getKey();
637                parent.remove(key);
638                return true;
639            }
640            return false;
641        }
642
643        @Override
644        public void clear() {
645            this.parent.clear();
646        }
647
648        @Override
649        public boolean equals(final Object obj) {
650            if (obj == this) {
651                return true;
652            }
653            return getEntrySet().equals(obj);
654        }
655
656        @Override
657        public int hashCode() {
658            return getEntrySet().hashCode();
659        }
660
661        @Override
662        public String toString() {
663            return getEntrySet().toString();
664        }
665
666        @Override
667        public Iterator<Map.Entry<K, V>> iterator() {
668            return new ListOrderedIterator<K, V>(parent, insertOrder);
669        }
670    }
671
672    //-----------------------------------------------------------------------
673    static class ListOrderedIterator<K, V> extends AbstractUntypedIteratorDecorator<K, Map.Entry<K, V>> {
674        private final ListOrderedMap<K, V> parent;
675        private K last = null;
676
677        ListOrderedIterator(final ListOrderedMap<K, V> parent, final List<K> insertOrder) {
678            super(insertOrder.iterator());
679            this.parent = parent;
680        }
681
682        @Override
683        public Map.Entry<K, V> next() {
684            last = getIterator().next();
685            return new ListOrderedMapEntry<K, V>(parent, last);
686        }
687
688        @Override
689        public void remove() {
690            super.remove();
691            parent.decorated().remove(last);
692        }
693    }
694
695    //-----------------------------------------------------------------------
696    static class ListOrderedMapEntry<K, V> extends AbstractMapEntry<K, V> {
697        private final ListOrderedMap<K, V> parent;
698
699        ListOrderedMapEntry(final ListOrderedMap<K, V> parent, final K key) {
700            super(key, null);
701            this.parent = parent;
702        }
703
704        @Override
705        public V getValue() {
706            return parent.get(getKey());
707        }
708
709        @Override
710        public V setValue(final V value) {
711            return parent.decorated().put(getKey(), value);
712        }
713    }
714
715    //-----------------------------------------------------------------------
716    static class ListOrderedMapIterator<K, V> implements OrderedMapIterator<K, V>, ResettableIterator<K> {
717        private final ListOrderedMap<K, V> parent;
718        private ListIterator<K> iterator;
719        private K last = null;
720        private boolean readable = false;
721
722        ListOrderedMapIterator(final ListOrderedMap<K, V> parent) {
723            super();
724            this.parent = parent;
725            this.iterator = parent.insertOrder.listIterator();
726        }
727
728        @Override
729        public boolean hasNext() {
730            return iterator.hasNext();
731        }
732
733        @Override
734        public K next() {
735            last = iterator.next();
736            readable = true;
737            return last;
738        }
739
740        @Override
741        public boolean hasPrevious() {
742            return iterator.hasPrevious();
743        }
744
745        @Override
746        public K previous() {
747            last = iterator.previous();
748            readable = true;
749            return last;
750        }
751
752        @Override
753        public void remove() {
754            if (readable == false) {
755                throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
756            }
757            iterator.remove();
758            parent.map.remove(last);
759            readable = false;
760        }
761
762        @Override
763        public K getKey() {
764            if (readable == false) {
765                throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
766            }
767            return last;
768        }
769
770        @Override
771        public V getValue() {
772            if (readable == false) {
773                throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
774            }
775            return parent.get(last);
776        }
777
778        @Override
779        public V setValue(final V value) {
780            if (readable == false) {
781                throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
782            }
783            return parent.map.put(last, value);
784        }
785
786        @Override
787        public void reset() {
788            iterator = parent.insertOrder.listIterator();
789            last = null;
790            readable = false;
791        }
792
793        @Override
794        public String toString() {
795            if (readable == true) {
796                return "Iterator[" + getKey() + "=" + getValue() + "]";
797            }
798            return "Iterator[]";
799        }
800    }
801
802}