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
89 private static final long serialVersionUID = 2728177751851003750L;
90
91
92 private final List<K> insertOrder = new ArrayList<>();
93
94
95
96
97
98
99
100
101
102
103
104
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
113
114
115
116
117 public ListOrderedMap() {
118 this(new HashMap<K, V>());
119 }
120
121
122
123
124
125
126
127 protected ListOrderedMap(final Map<K, V> map) {
128 super(map);
129 insertOrder.addAll(decorated().keySet());
130 }
131
132
133
134
135
136
137
138
139
140 private void writeObject(final ObjectOutputStream out) throws IOException {
141 out.defaultWriteObject();
142 out.writeObject(map);
143 }
144
145
146
147
148
149
150
151
152
153 @SuppressWarnings("unchecked")
154 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
155 in.defaultReadObject();
156 map = (Map<K, V>) in.readObject();
157 }
158
159
160
161 @Override
162 public OrderedMapIterator<K, V> mapIterator() {
163 return new ListOrderedMapIterator<>(this);
164 }
165
166
167
168
169
170
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
182
183
184
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
196
197
198
199
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
212
213
214
215
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
231 return decorated().put(key, value);
232 }
233
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
248
249
250
251
252
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
262
263 put(index, entry.getKey(), entry.getValue());
264 if (!contains) {
265
266 index++;
267 } else {
268
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
293
294
295
296
297
298
299 @Override
300 public Set<K> keySet() {
301 return new KeySetView<>(this);
302 }
303
304
305
306
307
308
309
310
311
312
313
314 public List<K> keyList() {
315 return UnmodifiableList.unmodifiableList(insertOrder);
316 }
317
318
319
320
321
322
323
324
325
326
327
328
329 @Override
330 public Collection<V> values() {
331 return new ValuesView<>(this);
332 }
333
334
335
336
337
338
339
340
341
342
343
344 public List<V> valueList() {
345 return new ValuesView<>(this);
346 }
347
348
349
350
351
352
353
354
355 @Override
356 public Set<Map.Entry<K, V>> entrySet() {
357 return new EntrySetView<>(this, this.insertOrder);
358 }
359
360
361
362
363
364
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
393
394
395
396
397
398 public K get(final int index) {
399 return insertOrder.get(index);
400 }
401
402
403
404
405
406
407
408
409 public V getValue(final int index) {
410 return get(insertOrder.get(index));
411 }
412
413
414
415
416
417
418
419 public int indexOf(final Object key) {
420 return insertOrder.indexOf(key);
421 }
422
423
424
425
426
427
428
429
430
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
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
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
480
481
482
483
484
485 public V remove(final int index) {
486 return remove(get(index));
487 }
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
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 }