1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.bag;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.ObjectOutputStream;
22 import java.lang.reflect.Array;
23 import java.util.Collection;
24 import java.util.ConcurrentModificationException;
25 import java.util.Iterator;
26 import java.util.Map;
27 import java.util.Map.Entry;
28 import java.util.Set;
29
30 import org.apache.commons.collections4.Bag;
31 import org.apache.commons.collections4.CollectionUtils;
32 import org.apache.commons.collections4.set.UnmodifiableSet;
33
34
35
36
37
38
39
40
41
42
43
44
45
46 public abstract class AbstractMapBag<E> implements Bag<E> {
47
48
49
50
51 static class BagIterator<E> implements Iterator<E> {
52 private final AbstractMapBag<E> parent;
53 private final Iterator<Map.Entry<E, MutableInteger>> entryIterator;
54 private Map.Entry<E, MutableInteger> current;
55 private int itemCount;
56 private final int mods;
57 private boolean canRemove;
58
59
60
61
62
63
64 BagIterator(final AbstractMapBag<E> parent) {
65 this.parent = parent;
66 this.entryIterator = parent.map.entrySet().iterator();
67 this.current = null;
68 this.mods = parent.modCount;
69 this.canRemove = false;
70 }
71
72
73 @Override
74 public boolean hasNext() {
75 return itemCount > 0 || entryIterator.hasNext();
76 }
77
78
79 @Override
80 public E next() {
81 if (parent.modCount != mods) {
82 throw new ConcurrentModificationException();
83 }
84 if (itemCount == 0) {
85 current = entryIterator.next();
86 itemCount = current.getValue().value;
87 }
88 canRemove = true;
89 itemCount--;
90 return current.getKey();
91 }
92
93
94 @Override
95 public void remove() {
96 if (parent.modCount != mods) {
97 throw new ConcurrentModificationException();
98 }
99 if (!canRemove) {
100 throw new IllegalStateException();
101 }
102 final MutableInteger mut = current.getValue();
103 if (mut.value > 1) {
104 mut.value--;
105 } else {
106 entryIterator.remove();
107 }
108 parent.size--;
109 canRemove = false;
110 }
111 }
112
113
114
115 protected static class MutableInteger {
116
117 protected int value;
118
119
120
121
122
123 MutableInteger(final int value) {
124 this.value = value;
125 }
126
127 @Override
128 public boolean equals(final Object obj) {
129 if (!(obj instanceof MutableInteger)) {
130 return false;
131 }
132 return ((MutableInteger) obj).value == value;
133 }
134
135 @Override
136 public int hashCode() {
137 return value;
138 }
139 }
140
141 private transient Map<E, MutableInteger> map;
142
143 private int size;
144
145
146 private transient int modCount;
147
148
149 private transient Set<E> uniqueSet;
150
151
152
153
154 protected AbstractMapBag() {
155 }
156
157
158
159
160
161
162
163 protected AbstractMapBag(final Map<E, MutableInteger> map) {
164 this.map = map;
165 }
166
167
168
169
170
171
172
173 @Override
174 public boolean add(final E object) {
175 return add(object, 1);
176 }
177
178
179
180
181
182
183
184
185 @Override
186 public boolean add(final E object, final int nCopies) {
187 modCount++;
188 if (nCopies > 0) {
189 final MutableInteger mut = map.get(object);
190 size += nCopies;
191 if (mut == null) {
192 map.put(object, new MutableInteger(nCopies));
193 return true;
194 }
195 mut.value += nCopies;
196 }
197 return false;
198 }
199
200
201
202
203
204
205
206 @Override
207 public boolean addAll(final Collection<? extends E> coll) {
208 boolean changed = false;
209 for (final E current : coll) {
210 final boolean added = add(current);
211 changed = changed || added;
212 }
213 return changed;
214 }
215
216
217
218
219 @Override
220 public void clear() {
221 modCount++;
222 map.clear();
223 size = 0;
224 }
225
226
227
228
229
230
231
232
233 @Override
234 public boolean contains(final Object object) {
235 return map.containsKey(object);
236 }
237
238
239
240
241
242
243
244
245 boolean containsAll(final Bag<?> other) {
246 for (final Object current : other.uniqueSet()) {
247 if (getCount(current) < other.getCount(current)) {
248 return false;
249 }
250 }
251 return true;
252 }
253
254
255
256
257
258
259
260 @Override
261 public boolean containsAll(final Collection<?> coll) {
262 if (coll instanceof Bag) {
263 return containsAll((Bag<?>) coll);
264 }
265 return containsAll(new HashBag<>(coll));
266 }
267
268
269
270
271
272
273
274
275
276 protected void doReadObject(final Map<E, MutableInteger> map, final ObjectInputStream in)
277 throws IOException, ClassNotFoundException {
278 this.map = map;
279 final int entrySize = in.readInt();
280 for (int i = 0; i < entrySize; i++) {
281 @SuppressWarnings("unchecked")
282 final E obj = (E) in.readObject();
283 final int count = in.readInt();
284 map.put(obj, new MutableInteger(count));
285 size += count;
286 }
287 }
288
289
290
291
292
293
294 protected void doWriteObject(final ObjectOutputStream out) throws IOException {
295 out.writeInt(map.size());
296 for (final Entry<E, MutableInteger> entry : map.entrySet()) {
297 out.writeObject(entry.getKey());
298 out.writeInt(entry.getValue().value);
299 }
300 }
301
302
303
304
305
306
307
308
309 @Override
310 public boolean equals(final Object object) {
311 if (object == this) {
312 return true;
313 }
314 if (!(object instanceof Bag)) {
315 return false;
316 }
317 final Bag<?> other = (Bag<?>) object;
318 if (other.size() != size()) {
319 return false;
320 }
321 for (final E element : map.keySet()) {
322 if (other.getCount(element) != getCount(element)) {
323 return false;
324 }
325 }
326 return true;
327 }
328
329
330
331
332
333
334
335
336 @Override
337 public int getCount(final Object object) {
338 final MutableInteger count = map.get(object);
339 if (count != null) {
340 return count.value;
341 }
342 return 0;
343 }
344
345
346
347
348
349
350
351 protected Map<E, MutableInteger> getMap() {
352 return map;
353 }
354
355
356
357
358
359
360
361
362
363
364 @Override
365 public int hashCode() {
366 int total = 0;
367 for (final Entry<E, MutableInteger> entry : map.entrySet()) {
368 final E element = entry.getKey();
369 final MutableInteger count = entry.getValue();
370 total += (element == null ? 0 : element.hashCode()) ^ count.value;
371 }
372 return total;
373 }
374
375
376
377
378
379
380 @Override
381 public boolean isEmpty() {
382 return map.isEmpty();
383 }
384
385
386
387
388
389
390
391 @Override
392 public Iterator<E> iterator() {
393 return new BagIterator<>(this);
394 }
395
396
397
398
399
400
401
402 @Override
403 public boolean remove(final Object object) {
404 final MutableInteger mut = map.get(object);
405 if (mut == null) {
406 return false;
407 }
408 modCount++;
409 map.remove(object);
410 size -= mut.value;
411 return true;
412 }
413
414
415
416
417
418
419
420
421 @Override
422 public boolean remove(final Object object, final int nCopies) {
423 final MutableInteger mut = map.get(object);
424 if (mut == null) {
425 return false;
426 }
427 if (nCopies <= 0) {
428 return false;
429 }
430 modCount++;
431 if (nCopies < mut.value) {
432 mut.value -= nCopies;
433 size -= nCopies;
434 } else {
435 map.remove(object);
436 size -= mut.value;
437 }
438 return true;
439 }
440
441
442
443
444
445
446
447
448 @Override
449 public boolean removeAll(final Collection<?> coll) {
450 boolean result = false;
451 if (coll != null) {
452 for (final Object current : coll) {
453 final boolean changed = remove(current, 1);
454 result = result || changed;
455 }
456 }
457 return result;
458 }
459
460
461
462
463
464
465
466
467
468 boolean retainAll(final Bag<?> other) {
469 boolean result = false;
470 final Bag<E> excess = new HashBag<>();
471 for (final E current : uniqueSet()) {
472 final int myCount = getCount(current);
473 final int otherCount = other.getCount(current);
474 if (1 <= otherCount && otherCount <= myCount) {
475 excess.add(current, myCount - otherCount);
476 } else {
477 excess.add(current, myCount);
478 }
479 }
480 if (!excess.isEmpty()) {
481 result = removeAll(excess);
482 }
483 return result;
484 }
485
486
487
488
489
490
491
492
493 @Override
494 public boolean retainAll(final Collection<?> coll) {
495 if (coll instanceof Bag) {
496 return retainAll((Bag<?>) coll);
497 }
498 return retainAll(new HashBag<>(coll));
499 }
500
501
502
503
504
505
506 @Override
507 public int size() {
508 return size;
509 }
510
511
512
513
514
515
516 @Override
517 public Object[] toArray() {
518 final Object[] result = new Object[size()];
519 int i = 0;
520 for (final E current : map.keySet()) {
521 for (int index = getCount(current); index > 0; index--) {
522 result[i++] = current;
523 }
524 }
525 return result;
526 }
527
528
529
530
531
532
533
534
535
536
537
538
539
540 @Override
541 public <T> T[] toArray(T[] array) {
542 final int size = size();
543 if (array.length < size) {
544 @SuppressWarnings("unchecked")
545 final T[] unchecked = (T[]) Array.newInstance(array.getClass().getComponentType(), size);
546 array = unchecked;
547 }
548
549 int i = 0;
550 for (final E current : map.keySet()) {
551 for (int index = getCount(current); index > 0; index--) {
552
553 @SuppressWarnings("unchecked")
554 final T unchecked = (T) current;
555 array[i++] = unchecked;
556 }
557 }
558 while (i < array.length) {
559 array[i++] = null;
560 }
561 return array;
562 }
563
564
565
566
567
568
569 @Override
570 public String toString() {
571 if (isEmpty()) {
572 return "[]";
573 }
574 final StringBuilder buf = new StringBuilder();
575 buf.append(CollectionUtils.DEFAULT_TOSTRING_PREFIX);
576 final Iterator<E> it = uniqueSet().iterator();
577 while (it.hasNext()) {
578 final Object current = it.next();
579 final int count = getCount(current);
580 buf.append(count);
581 buf.append(CollectionUtils.COLON);
582 buf.append(current);
583 if (it.hasNext()) {
584 buf.append(CollectionUtils.COMMA);
585 }
586 }
587 buf.append(CollectionUtils.DEFAULT_TOSTRING_SUFFIX);
588 return buf.toString();
589 }
590
591
592
593
594
595
596 @Override
597 public Set<E> uniqueSet() {
598 if (uniqueSet == null) {
599 uniqueSet = UnmodifiableSet.<E>unmodifiableSet(map.keySet());
600 }
601 return uniqueSet;
602 }
603
604 }