1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84 public class ListOrderedMap<K, V>
85 extends AbstractMapDecorator<K, V>
86 implements OrderedMap<K, V>, Serializable {
87
88 static class EntrySetView<K, V> extends AbstractSet<Map.Entry<K, V>> {
89 private final ListOrderedMap<K, V> parent;
90 private final List<K> insertOrder;
91 private Set<Map.Entry<K, V>> entrySet;
92
93 EntrySetView(final ListOrderedMap<K, V> parent, final List<K> insertOrder) {
94 this.parent = parent;
95 this.insertOrder = insertOrder;
96 }
97
98 @Override
99 public void clear() {
100 this.parent.clear();
101 }
102
103 @Override
104 public boolean contains(final Object obj) {
105 return getEntrySet().contains(obj);
106 }
107 @Override
108 public boolean containsAll(final Collection<?> coll) {
109 return getEntrySet().containsAll(coll);
110 }
111
112 @Override
113 public boolean equals(final Object obj) {
114 if (obj == this) {
115 return true;
116 }
117 return getEntrySet().equals(obj);
118 }
119
120 private Set<Map.Entry<K, V>> getEntrySet() {
121 if (entrySet == null) {
122 entrySet = parent.decorated().entrySet();
123 }
124 return entrySet;
125 }
126
127 @Override
128 public int hashCode() {
129 return getEntrySet().hashCode();
130 }
131
132 @Override
133 public boolean isEmpty() {
134 return this.parent.isEmpty();
135 }
136
137 @Override
138 public Iterator<Map.Entry<K, V>> iterator() {
139 return new ListOrderedIterator<>(parent, insertOrder);
140 }
141
142 @Override
143 @SuppressWarnings("unchecked")
144 public boolean remove(final Object obj) {
145 if (!(obj instanceof Map.Entry)) {
146 return false;
147 }
148 if (getEntrySet().contains(obj)) {
149 final Object key = ((Map.Entry<K, V>) obj).getKey();
150 parent.remove(key);
151 return true;
152 }
153 return false;
154 }
155
156 @Override
157 public int size() {
158 return this.parent.size();
159 }
160
161 @Override
162 public String toString() {
163 return getEntrySet().toString();
164 }
165 }
166
167 static class KeySetView<K> extends AbstractSet<K> {
168 private final ListOrderedMap<K, Object> parent;
169
170 @SuppressWarnings("unchecked")
171 KeySetView(final ListOrderedMap<K, ?> parent) {
172 this.parent = (ListOrderedMap<K, Object>) parent;
173 }
174
175 @Override
176 public void clear() {
177 this.parent.clear();
178 }
179
180 @Override
181 public boolean contains(final Object value) {
182 return this.parent.containsKey(value);
183 }
184
185 @Override
186 public Iterator<K> iterator() {
187 return new AbstractUntypedIteratorDecorator<Map.Entry<K, Object>, K>(parent.entrySet().iterator()) {
188 @Override
189 public K next() {
190 return getIterator().next().getKey();
191 }
192 };
193 }
194
195 @Override
196 public int size() {
197 return this.parent.size();
198 }
199 }
200
201 static class ListOrderedIterator<K, V> extends AbstractUntypedIteratorDecorator<K, Map.Entry<K, V>> {
202 private final ListOrderedMap<K, V> parent;
203 private K last;
204
205 ListOrderedIterator(final ListOrderedMap<K, V> parent, final List<K> insertOrder) {
206 super(insertOrder.iterator());
207 this.parent = parent;
208 }
209
210 @Override
211 public Map.Entry<K, V> next() {
212 last = getIterator().next();
213 return new ListOrderedMapEntry<>(parent, last);
214 }
215
216 @Override
217 public void remove() {
218 super.remove();
219 parent.decorated().remove(last);
220 }
221 }
222
223 static class ListOrderedMapEntry<K, V> extends AbstractMapEntry<K, V> {
224 private final ListOrderedMap<K, V> parent;
225
226 ListOrderedMapEntry(final ListOrderedMap<K, V> parent, final K key) {
227 super(key, null);
228 this.parent = parent;
229 }
230
231 @Override
232 public V getValue() {
233 return parent.get(getKey());
234 }
235
236 @Override
237 public V setValue(final V value) {
238 return parent.decorated().put(getKey(), value);
239 }
240 }
241
242 static class ListOrderedMapIterator<K, V> implements OrderedMapIterator<K, V>, ResettableIterator<K> {
243 private final ListOrderedMap<K, V> parent;
244 private ListIterator<K> iterator;
245 private K last;
246 private boolean readable;
247
248 ListOrderedMapIterator(final ListOrderedMap<K, V> parent) {
249 this.parent = parent;
250 this.iterator = parent.insertOrder.listIterator();
251 }
252
253 @Override
254 public K getKey() {
255 if (!readable) {
256 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
257 }
258 return last;
259 }
260
261 @Override
262 public V getValue() {
263 if (!readable) {
264 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
265 }
266 return parent.get(last);
267 }
268
269 @Override
270 public boolean hasNext() {
271 return iterator.hasNext();
272 }
273
274 @Override
275 public boolean hasPrevious() {
276 return iterator.hasPrevious();
277 }
278
279 @Override
280 public K next() {
281 last = iterator.next();
282 readable = true;
283 return last;
284 }
285
286 @Override
287 public K previous() {
288 last = iterator.previous();
289 readable = true;
290 return last;
291 }
292
293 @Override
294 public void remove() {
295 if (!readable) {
296 throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
297 }
298 iterator.remove();
299 parent.map.remove(last);
300 readable = false;
301 }
302
303 @Override
304 public void reset() {
305 iterator = parent.insertOrder.listIterator();
306 last = null;
307 readable = false;
308 }
309
310 @Override
311 public V setValue(final V value) {
312 if (!readable) {
313 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
314 }
315 return parent.map.put(last, value);
316 }
317
318 @Override
319 public String toString() {
320 if (readable) {
321 return "Iterator[" + getKey() + "=" + getValue() + "]";
322 }
323 return "Iterator[]";
324 }
325 }
326
327 static class ValuesView<V> extends AbstractList<V> {
328 private final ListOrderedMap<Object, V> parent;
329
330 @SuppressWarnings("unchecked")
331 ValuesView(final ListOrderedMap<?, V> parent) {
332 this.parent = (ListOrderedMap<Object, V>) parent;
333 }
334
335 @Override
336 public void clear() {
337 this.parent.clear();
338 }
339
340 @Override
341 public boolean contains(final Object value) {
342 return this.parent.containsValue(value);
343 }
344
345 @Override
346 public V get(final int index) {
347 return this.parent.getValue(index);
348 }
349
350 @Override
351 public Iterator<V> iterator() {
352 return new AbstractUntypedIteratorDecorator<Map.Entry<Object, V>, V>(parent.entrySet().iterator()) {
353 @Override
354 public V next() {
355 return getIterator().next().getValue();
356 }
357 };
358 }
359
360 @Override
361 public V remove(final int index) {
362 return this.parent.remove(index);
363 }
364
365 @Override
366 public V set(final int index, final V value) {
367 return this.parent.setValue(index, value);
368 }
369
370 @Override
371 public int size() {
372 return this.parent.size();
373 }
374 }
375
376
377 private static final long serialVersionUID = 2728177751851003750L;
378
379
380
381
382
383
384
385
386
387
388
389
390
391 public static <K, V> ListOrderedMap<K, V> listOrderedMap(final Map<K, V> map) {
392 return new ListOrderedMap<>(map);
393 }
394
395
396 private final List<K> insertOrder = new ArrayList<>();
397
398
399
400
401
402
403
404 public ListOrderedMap() {
405 this(new HashMap<>());
406 }
407
408
409
410
411
412
413
414 protected ListOrderedMap(final Map<K, V> map) {
415 super(map);
416 insertOrder.addAll(decorated().keySet());
417 }
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436 public List<K> asList() {
437 return keyList();
438 }
439
440 @Override
441 public void clear() {
442 decorated().clear();
443 insertOrder.clear();
444 }
445
446
447
448
449
450
451
452
453 @Override
454 public Set<Map.Entry<K, V>> entrySet() {
455 return new EntrySetView<>(this, this.insertOrder);
456 }
457
458
459
460
461
462
463
464 @Override
465 public K firstKey() {
466 if (isEmpty()) {
467 throw new NoSuchElementException("Map is empty");
468 }
469 return insertOrder.get(0);
470 }
471
472
473
474
475
476
477
478
479 public K get(final int index) {
480 return insertOrder.get(index);
481 }
482
483
484
485
486
487
488
489
490 public V getValue(final int index) {
491 return get(insertOrder.get(index));
492 }
493
494
495
496
497
498
499
500 public int indexOf(final Object key) {
501 return insertOrder.indexOf(key);
502 }
503
504
505
506
507
508
509
510
511
512
513
514 public List<K> keyList() {
515 return UnmodifiableList.unmodifiableList(insertOrder);
516 }
517
518
519
520
521
522
523
524
525
526 @Override
527 public Set<K> keySet() {
528 return new KeySetView<>(this);
529 }
530
531
532
533
534
535
536
537 @Override
538 public K lastKey() {
539 if (isEmpty()) {
540 throw new NoSuchElementException("Map is empty");
541 }
542 return insertOrder.get(size() - 1);
543 }
544
545
546 @Override
547 public OrderedMapIterator<K, V> mapIterator() {
548 return new ListOrderedMapIterator<>(this);
549 }
550
551
552
553
554
555
556
557
558 @Override
559 public K nextKey(final Object key) {
560 final int index = insertOrder.indexOf(key);
561 if (index >= 0 && index < size() - 1) {
562 return insertOrder.get(index + 1);
563 }
564 return null;
565 }
566
567
568
569
570
571
572
573
574 @Override
575 public K previousKey(final Object key) {
576 final int index = insertOrder.indexOf(key);
577 if (index > 0) {
578 return insertOrder.get(index - 1);
579 }
580 return null;
581 }
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602 public V put(int index, final K key, final V value) {
603 if (index < 0 || index > insertOrder.size()) {
604 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size());
605 }
606
607 final Map<K, V> m = decorated();
608 if (m.containsKey(key)) {
609 final V result = m.remove(key);
610 final int pos = insertOrder.indexOf(key);
611 insertOrder.remove(pos);
612 if (pos < index) {
613 index--;
614 }
615 insertOrder.add(index, key);
616 m.put(key, value);
617 return result;
618 }
619 insertOrder.add(index, key);
620 m.put(key, value);
621 return null;
622 }
623
624 @Override
625 public V put(final K key, final V value) {
626 if (decorated().containsKey(key)) {
627
628 return decorated().put(key, value);
629 }
630
631 final V result = decorated().put(key, value);
632 insertOrder.add(key);
633 return result;
634 }
635
636
637
638
639
640
641
642
643
644 public void putAll(int index, final Map<? extends K, ? extends V> map) {
645 if (index < 0 || index > insertOrder.size()) {
646 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size());
647 }
648 for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
649 final K key = entry.getKey();
650 final boolean contains = containsKey(key);
651
652
653 put(index, entry.getKey(), entry.getValue());
654 if (!contains) {
655
656 index++;
657 } else {
658
659 index = indexOf(entry.getKey()) + 1;
660 }
661 }
662 }
663
664 @Override
665 public void putAll(final Map<? extends K, ? extends V> map) {
666 for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
667 put(entry.getKey(), entry.getValue());
668 }
669 }
670
671
672
673
674
675
676
677
678
679 @SuppressWarnings("unchecked")
680 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
681 in.defaultReadObject();
682 map = (Map<K, V>) in.readObject();
683 }
684
685
686
687
688
689
690
691
692 public V remove(final int index) {
693 return remove(get(index));
694 }
695
696 @Override
697 public V remove(final Object key) {
698 V result = null;
699 if (decorated().containsKey(key)) {
700 result = decorated().remove(key);
701 insertOrder.remove(key);
702 }
703 return result;
704 }
705
706
707
708
709
710
711
712
713
714
715 public V setValue(final int index, final V value) {
716 final K key = insertOrder.get(index);
717 return put(key, value);
718 }
719
720
721
722
723
724
725 @Override
726 public String toString() {
727 if (isEmpty()) {
728 return "{}";
729 }
730 final StringBuilder buf = new StringBuilder();
731 buf.append('{');
732 boolean first = true;
733 for (final Map.Entry<K, V> entry : entrySet()) {
734 final K key = entry.getKey();
735 final V value = entry.getValue();
736 if (first) {
737 first = false;
738 } else {
739 buf.append(", ");
740 }
741 buf.append(key == this ? "(this Map)" : key);
742 buf.append('=');
743 buf.append(value == this ? "(this Map)" : value);
744 }
745 buf.append('}');
746 return buf.toString();
747 }
748
749
750
751
752
753
754
755
756
757
758
759 public List<V> valueList() {
760 return new ValuesView<>(this);
761 }
762
763
764
765
766
767
768
769
770
771
772
773
774 @Override
775 public Collection<V> values() {
776 return new ValuesView<>(this);
777 }
778
779
780
781
782
783
784
785
786 private void writeObject(final ObjectOutputStream out) throws IOException {
787 out.defaultWriteObject();
788 out.writeObject(map);
789 }
790
791 }