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