1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.multimap;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.ObjectOutputStream;
22 import java.util.AbstractCollection;
23 import java.util.AbstractMap;
24 import java.util.AbstractSet;
25 import java.util.ArrayList;
26 import java.util.Collection;
27 import java.util.Iterator;
28 import java.util.Map;
29 import java.util.Map.Entry;
30 import java.util.Set;
31
32 import org.apache.commons.collections4.CollectionUtils;
33 import org.apache.commons.collections4.IteratorUtils;
34 import org.apache.commons.collections4.MapIterator;
35 import org.apache.commons.collections4.MultiSet;
36 import org.apache.commons.collections4.MultiValuedMap;
37 import org.apache.commons.collections4.Transformer;
38 import org.apache.commons.collections4.iterators.AbstractIteratorDecorator;
39 import org.apache.commons.collections4.iterators.EmptyMapIterator;
40 import org.apache.commons.collections4.iterators.IteratorChain;
41 import org.apache.commons.collections4.iterators.LazyIteratorChain;
42 import org.apache.commons.collections4.iterators.TransformIterator;
43 import org.apache.commons.collections4.keyvalue.AbstractMapEntry;
44 import org.apache.commons.collections4.keyvalue.UnmodifiableMapEntry;
45 import org.apache.commons.collections4.multiset.AbstractMultiSet;
46 import org.apache.commons.collections4.multiset.UnmodifiableMultiSet;
47
48
49
50
51
52
53
54
55
56
57
58
59 public abstract class AbstractMultiValuedMap<K, V> implements MultiValuedMap<K, V> {
60
61
62 private transient Collection<V> valuesView;
63
64
65 private transient EntryValues entryValuesView;
66
67
68 private transient MultiSet<K> keysMultiSetView;
69
70
71 private transient AsMap asMapView;
72
73
74 private transient Map<K, Collection<V>> map;
75
76
77
78
79 protected AbstractMultiValuedMap() {
80 super();
81 }
82
83
84
85
86
87
88
89 @SuppressWarnings("unchecked")
90 protected AbstractMultiValuedMap(final Map<K, ? extends Collection<V>> map) {
91 if (map == null) {
92 throw new NullPointerException("Map must not be null.");
93 }
94 this.map = (Map<K, Collection<V>>) map;
95 }
96
97
98
99
100
101
102
103 protected Map<K, ? extends Collection<V>> getMap() {
104 return map;
105 }
106
107
108
109
110
111
112
113
114 @SuppressWarnings("unchecked")
115 protected void setMap(final Map<K, ? extends Collection<V>> map) {
116 this.map = (Map<K, Collection<V>>) map;
117 }
118
119 protected abstract Collection<V> createCollection();
120
121
122 @Override
123 public boolean containsKey(final Object key) {
124 return getMap().containsKey(key);
125 }
126
127 @Override
128 public boolean containsValue(final Object value) {
129 return values().contains(value);
130 }
131
132 @Override
133 public boolean containsMapping(final Object key, final Object value) {
134 final Collection<V> coll = getMap().get(key);
135 return coll != null && coll.contains(value);
136 }
137
138 @Override
139 public Collection<Entry<K, V>> entries() {
140 return entryValuesView != null ? entryValuesView : (entryValuesView = new EntryValues());
141 }
142
143
144
145
146
147
148
149
150 @Override
151 public Collection<V> get(final K key) {
152 return wrappedCollection(key);
153 }
154
155 Collection<V> wrappedCollection(final K key) {
156 return new WrappedCollection(key);
157 }
158
159
160
161
162
163
164
165
166
167
168 @Override
169 public Collection<V> remove(final Object key) {
170 return CollectionUtils.emptyIfNull(getMap().remove(key));
171 }
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186 @Override
187 public boolean removeMapping(final Object key, final Object value) {
188 final Collection<V> coll = getMap().get(key);
189 if (coll == null) {
190 return false;
191 }
192 final boolean changed = coll.remove(value);
193 if (coll.isEmpty()) {
194 getMap().remove(key);
195 }
196 return changed;
197 }
198
199 @Override
200 public boolean isEmpty() {
201 return getMap().isEmpty();
202 }
203
204 @Override
205 public Set<K> keySet() {
206 return getMap().keySet();
207 }
208
209
210
211
212
213
214
215
216 @Override
217 public int size() {
218
219
220
221
222 int size = 0;
223 for (final Collection<V> col : getMap().values()) {
224 size += col.size();
225 }
226 return size;
227 }
228
229
230
231
232
233
234
235
236 @Override
237 public Collection<V> values() {
238 final Collection<V> vs = valuesView;
239 return vs != null ? vs : (valuesView = new Values());
240 }
241
242 @Override
243 public void clear() {
244 getMap().clear();
245 }
246
247
248
249
250
251
252
253
254
255
256
257 @Override
258 public boolean put(final K key, final V value) {
259 Collection<V> coll = getMap().get(key);
260 if (coll == null) {
261 coll = createCollection();
262 if (coll.add(value)) {
263 map.put(key, coll);
264 return true;
265 }
266 return false;
267 }
268 return coll.add(value);
269 }
270
271
272
273
274
275
276
277
278
279
280
281
282
283 @Override
284 public boolean putAll(final Map<? extends K, ? extends V> map) {
285 if (map == null) {
286 throw new NullPointerException("Map must not be null.");
287 }
288 boolean changed = false;
289 for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
290 changed |= put(entry.getKey(), entry.getValue());
291 }
292 return changed;
293 }
294
295
296
297
298
299
300
301
302
303
304
305
306
307 @Override
308 public boolean putAll(final MultiValuedMap<? extends K, ? extends V> map) {
309 if (map == null) {
310 throw new NullPointerException("Map must not be null.");
311 }
312 boolean changed = false;
313 for (final Map.Entry<? extends K, ? extends V> entry : map.entries()) {
314 changed |= put(entry.getKey(), entry.getValue());
315 }
316 return changed;
317 }
318
319
320
321
322
323
324
325
326
327
328
329 @Override
330 public MultiSet<K> keys() {
331 if (keysMultiSetView == null) {
332 keysMultiSetView = UnmodifiableMultiSet.unmodifiableMultiSet(new KeysMultiSet());
333 }
334 return keysMultiSetView;
335 }
336
337 @Override
338 public Map<K, Collection<V>> asMap() {
339 return asMapView != null ? asMapView : (asMapView = new AsMap(map));
340 }
341
342
343
344
345
346
347
348
349
350 @Override
351 public boolean putAll(final K key, final Iterable<? extends V> values) {
352 if (values == null) {
353 throw new NullPointerException("Values must not be null.");
354 }
355
356 if (values instanceof Collection<?>) {
357 final Collection<? extends V> valueCollection = (Collection<? extends V>) values;
358 return !valueCollection.isEmpty() && get(key).addAll(valueCollection);
359 }
360 final Iterator<? extends V> it = values.iterator();
361 return it.hasNext() && CollectionUtils.addAll(get(key), it);
362 }
363
364 @Override
365 public MapIterator<K, V> mapIterator() {
366 if (size() == 0) {
367 return EmptyMapIterator.emptyMapIterator();
368 }
369 return new MultiValuedMapIterator();
370 }
371
372 @Override
373 public boolean equals(final Object obj) {
374 if (this == obj) {
375 return true;
376 }
377 if (obj instanceof MultiValuedMap) {
378 return asMap().equals(((MultiValuedMap<?, ?>) obj).asMap());
379 }
380 return false;
381 }
382
383 @Override
384 public int hashCode() {
385 return getMap().hashCode();
386 }
387
388 @Override
389 public String toString() {
390 return getMap().toString();
391 }
392
393
394
395
396
397
398
399
400
401
402
403
404
405 class WrappedCollection implements Collection<V> {
406
407 protected final K key;
408
409 public WrappedCollection(final K key) {
410 this.key = key;
411 }
412
413 protected Collection<V> getMapping() {
414 return getMap().get(key);
415 }
416
417 @Override
418 public boolean add(final V value) {
419 Collection<V> coll = getMapping();
420 if (coll == null) {
421 coll = createCollection();
422 AbstractMultiValuedMap.this.map.put(key, coll);
423 }
424 return coll.add(value);
425 }
426
427 @Override
428 public boolean addAll(final Collection<? extends V> other) {
429 Collection<V> coll = getMapping();
430 if (coll == null) {
431 coll = createCollection();
432 AbstractMultiValuedMap.this.map.put(key, coll);
433 }
434 return coll.addAll(other);
435 }
436
437 @Override
438 public void clear() {
439 final Collection<V> coll = getMapping();
440 if (coll != null) {
441 coll.clear();
442 AbstractMultiValuedMap.this.remove(key);
443 }
444 }
445
446 @Override
447 public Iterator<V> iterator() {
448 final Collection<V> coll = getMapping();
449 if (coll == null) {
450 return IteratorUtils.EMPTY_ITERATOR;
451 }
452 return new ValuesIterator(key);
453 }
454
455 @Override
456 public int size() {
457 final Collection<V> coll = getMapping();
458 return coll == null ? 0 : coll.size();
459 }
460
461 @Override
462 public boolean contains(final Object obj) {
463 final Collection<V> coll = getMapping();
464 return coll != null && coll.contains(obj);
465 }
466
467 @Override
468 public boolean containsAll(final Collection<?> other) {
469 final Collection<V> coll = getMapping();
470 return coll != null && coll.containsAll(other);
471 }
472
473 @Override
474 public boolean isEmpty() {
475 final Collection<V> coll = getMapping();
476 return coll == null || coll.isEmpty();
477 }
478
479 @Override
480 public boolean remove(final Object item) {
481 final Collection<V> coll = getMapping();
482 if (coll == null) {
483 return false;
484 }
485
486 final boolean result = coll.remove(item);
487 if (coll.isEmpty()) {
488 AbstractMultiValuedMap.this.remove(key);
489 }
490 return result;
491 }
492
493 @Override
494 public boolean removeAll(final Collection<?> c) {
495 final Collection<V> coll = getMapping();
496 if (coll == null) {
497 return false;
498 }
499
500 final boolean result = coll.removeAll(c);
501 if (coll.isEmpty()) {
502 AbstractMultiValuedMap.this.remove(key);
503 }
504 return result;
505 }
506
507 @Override
508 public boolean retainAll(final Collection<?> c) {
509 final Collection<V> coll = getMapping();
510 if (coll == null) {
511 return false;
512 }
513
514 final boolean result = coll.retainAll(c);
515 if (coll.isEmpty()) {
516 AbstractMultiValuedMap.this.remove(key);
517 }
518 return result;
519 }
520
521 @Override
522 public Object[] toArray() {
523 final Collection<V> coll = getMapping();
524 if (coll == null) {
525 return CollectionUtils.EMPTY_COLLECTION.toArray();
526 }
527 return coll.toArray();
528 }
529
530 @Override
531 @SuppressWarnings("unchecked")
532 public <T> T[] toArray(final T[] a) {
533 final Collection<V> coll = getMapping();
534 if (coll == null) {
535 return (T[]) CollectionUtils.EMPTY_COLLECTION.toArray(a);
536 }
537 return coll.toArray(a);
538 }
539
540 @Override
541 public String toString() {
542 final Collection<V> coll = getMapping();
543 if (coll == null) {
544 return CollectionUtils.EMPTY_COLLECTION.toString();
545 }
546 return coll.toString();
547 }
548
549 }
550
551
552
553
554 private class KeysMultiSet extends AbstractMultiSet<K> {
555
556 @Override
557 public boolean contains(final Object o) {
558 return getMap().containsKey(o);
559 }
560
561 @Override
562 public boolean isEmpty() {
563 return getMap().isEmpty();
564 }
565
566 @Override
567 public int size() {
568 return AbstractMultiValuedMap.this.size();
569 }
570
571 @Override
572 protected int uniqueElements() {
573 return getMap().size();
574 }
575
576 @Override
577 public int getCount(final Object object) {
578 int count = 0;
579 final Collection<V> col = AbstractMultiValuedMap.this.getMap().get(object);
580 if (col != null) {
581 count = col.size();
582 }
583 return count;
584 }
585
586 @Override
587 protected Iterator<MultiSet.Entry<K>> createEntrySetIterator() {
588 final MapEntryTransformer transformer = new MapEntryTransformer();
589 return IteratorUtils.transformedIterator(map.entrySet().iterator(), transformer);
590 }
591
592 private final class MapEntryTransformer
593 implements Transformer<Map.Entry<K, Collection<V>>, MultiSet.Entry<K>> {
594 @Override
595 public MultiSet.Entry<K> transform(final Map.Entry<K, Collection<V>> mapEntry) {
596 return new AbstractMultiSet.AbstractEntry<K>() {
597 @Override
598 public K getElement() {
599 return mapEntry.getKey();
600 }
601
602 @Override
603 public int getCount() {
604 return mapEntry.getValue().size();
605 }
606 };
607 }
608 }
609 }
610
611
612
613
614 private class EntryValues extends AbstractCollection<Entry<K, V>> {
615
616 @Override
617 public Iterator<Entry<K, V>> iterator() {
618 return new LazyIteratorChain<Entry<K, V>>() {
619
620 final Collection<K> keysCol = new ArrayList<>(getMap().keySet());
621 final Iterator<K> keyIterator = keysCol.iterator();
622
623 @Override
624 protected Iterator<? extends Entry<K, V>> nextIterator(final int count) {
625 if (!keyIterator.hasNext()) {
626 return null;
627 }
628 final K key = keyIterator.next();
629 final Transformer<V, Entry<K, V>> entryTransformer = new Transformer<V, Entry<K, V>>() {
630
631 @Override
632 public Entry<K, V> transform(final V input) {
633 return new MultiValuedMapEntry(key, input);
634 }
635
636 };
637 return new TransformIterator<>(new ValuesIterator(key), entryTransformer);
638 }
639 };
640 }
641
642 @Override
643 public int size() {
644 return AbstractMultiValuedMap.this.size();
645 }
646
647 }
648
649
650
651
652 private class MultiValuedMapEntry extends AbstractMapEntry<K, V> {
653
654 public MultiValuedMapEntry(final K key, final V value) {
655 super(key, value);
656 }
657
658 @Override
659 public V setValue(final V value) {
660 throw new UnsupportedOperationException();
661 }
662
663 }
664
665
666
667
668 private class MultiValuedMapIterator implements MapIterator<K, V> {
669
670 private final Iterator<Entry<K, V>> it;
671
672 private Entry<K, V> current = null;
673
674 public MultiValuedMapIterator() {
675 this.it = AbstractMultiValuedMap.this.entries().iterator();
676 }
677
678 @Override
679 public boolean hasNext() {
680 return it.hasNext();
681 }
682
683 @Override
684 public K next() {
685 current = it.next();
686 return current.getKey();
687 }
688
689 @Override
690 public K getKey() {
691 if (current == null) {
692 throw new IllegalStateException();
693 }
694 return current.getKey();
695 }
696
697 @Override
698 public V getValue() {
699 if (current == null) {
700 throw new IllegalStateException();
701 }
702 return current.getValue();
703 }
704
705 @Override
706 public void remove() {
707 it.remove();
708 }
709
710 @Override
711 public V setValue(final V value) {
712 if (current == null) {
713 throw new IllegalStateException();
714 }
715 return current.setValue(value);
716 }
717
718 }
719
720
721
722
723 private class Values extends AbstractCollection<V> {
724 @Override
725 public Iterator<V> iterator() {
726 final IteratorChain<V> chain = new IteratorChain<>();
727 for (final K k : keySet()) {
728 chain.addIterator(new ValuesIterator(k));
729 }
730 return chain;
731 }
732
733 @Override
734 public int size() {
735 return AbstractMultiValuedMap.this.size();
736 }
737
738 @Override
739 public void clear() {
740 AbstractMultiValuedMap.this.clear();
741 }
742 }
743
744
745
746
747 private class ValuesIterator implements Iterator<V> {
748 private final Object key;
749 private final Collection<V> values;
750 private final Iterator<V> iterator;
751
752 public ValuesIterator(final Object key) {
753 this.key = key;
754 this.values = getMap().get(key);
755 this.iterator = values.iterator();
756 }
757
758 @Override
759 public void remove() {
760 iterator.remove();
761 if (values.isEmpty()) {
762 AbstractMultiValuedMap.this.remove(key);
763 }
764 }
765
766 @Override
767 public boolean hasNext() {
768 return iterator.hasNext();
769 }
770
771 @Override
772 public V next() {
773 return iterator.next();
774 }
775 }
776
777
778
779
780 private class AsMap extends AbstractMap<K, Collection<V>> {
781 final transient Map<K, Collection<V>> decoratedMap;
782
783 AsMap(final Map<K, Collection<V>> map) {
784 this.decoratedMap = map;
785 }
786
787 @Override
788 public Set<Map.Entry<K, Collection<V>>> entrySet() {
789 return new AsMapEntrySet();
790 }
791
792 @Override
793 public boolean containsKey(final Object key) {
794 return decoratedMap.containsKey(key);
795 }
796
797 @Override
798 public Collection<V> get(final Object key) {
799 final Collection<V> collection = decoratedMap.get(key);
800 if (collection == null) {
801 return null;
802 }
803 @SuppressWarnings("unchecked")
804 final
805 K k = (K) key;
806 return wrappedCollection(k);
807 }
808
809 @Override
810 public Set<K> keySet() {
811 return AbstractMultiValuedMap.this.keySet();
812 }
813
814 @Override
815 public int size() {
816 return decoratedMap.size();
817 }
818
819 @Override
820 public Collection<V> remove(final Object key) {
821 final Collection<V> collection = decoratedMap.remove(key);
822 if (collection == null) {
823 return null;
824 }
825
826 final Collection<V> output = createCollection();
827 output.addAll(collection);
828 collection.clear();
829 return output;
830 }
831
832 @Override
833 public boolean equals(final Object object) {
834 return this == object || decoratedMap.equals(object);
835 }
836
837 @Override
838 public int hashCode() {
839 return decoratedMap.hashCode();
840 }
841
842 @Override
843 public String toString() {
844 return decoratedMap.toString();
845 }
846
847 @Override
848 public void clear() {
849 AbstractMultiValuedMap.this.clear();
850 }
851
852 class AsMapEntrySet extends AbstractSet<Map.Entry<K, Collection<V>>> {
853
854 @Override
855 public Iterator<Map.Entry<K, Collection<V>>> iterator() {
856 return new AsMapEntrySetIterator(decoratedMap.entrySet().iterator());
857 }
858
859 @Override
860 public int size() {
861 return AsMap.this.size();
862 }
863
864 @Override
865 public void clear() {
866 AsMap.this.clear();
867 }
868
869 @Override
870 public boolean contains(final Object o) {
871 return decoratedMap.entrySet().contains(o);
872 }
873
874 @Override
875 public boolean remove(final Object o) {
876 if (!contains(o)) {
877 return false;
878 }
879 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
880 AbstractMultiValuedMap.this.remove(entry.getKey());
881 return true;
882 }
883 }
884
885
886
887
888 class AsMapEntrySetIterator extends AbstractIteratorDecorator<Map.Entry<K, Collection<V>>> {
889
890 AsMapEntrySetIterator(final Iterator<Map.Entry<K, Collection<V>>> iterator) {
891 super(iterator);
892 }
893
894 @Override
895 public Map.Entry<K, Collection<V>> next() {
896 final Map.Entry<K, Collection<V>> entry = super.next();
897 final K key = entry.getKey();
898 return new UnmodifiableMapEntry<>(key, wrappedCollection(key));
899 }
900 }
901 }
902
903
904
905
906
907
908
909 protected void doWriteObject(final ObjectOutputStream out) throws IOException {
910 out.writeInt(map.size());
911 for (final Map.Entry<K, Collection<V>> entry : map.entrySet()) {
912 out.writeObject(entry.getKey());
913 out.writeInt(entry.getValue().size());
914 for (final V value : entry.getValue()) {
915 out.writeObject(value);
916 }
917 }
918 }
919
920
921
922
923
924
925
926
927 protected void doReadObject(final ObjectInputStream in)
928 throws IOException, ClassNotFoundException {
929 final int entrySize = in.readInt();
930 for (int i = 0; i < entrySize; i++) {
931 @SuppressWarnings("unchecked")
932 final K key = (K) in.readObject();
933 final Collection<V> values = get(key);
934 final int valueSize = in.readInt();
935 for (int j = 0; j < valueSize; j++) {
936 @SuppressWarnings("unchecked")
937 final
938 V value = (V) in.readObject();
939 values.add(value);
940 }
941 }
942 }
943
944 }