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