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