1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4.bag;
18
19 import java.io.IOException;
20 import java.io.InvalidObjectException;
21 import java.io.ObjectInputStream;
22 import java.io.ObjectOutputStream;
23 import java.lang.reflect.Array;
24 import java.util.Collection;
25 import java.util.ConcurrentModificationException;
26 import java.util.Iterator;
27 import java.util.Map;
28 import java.util.Map.Entry;
29 import java.util.Objects;
30 import java.util.Set;
31
32 import org.apache.commons.collections4.Bag;
33 import org.apache.commons.collections4.CollectionUtils;
34 import org.apache.commons.collections4.multiset.AbstractMapMultiSet;
35 import org.apache.commons.collections4.set.UnmodifiableSet;
36
37 /**
38 * Abstract implementation of the {@link Bag} interface to simplify the creation
39 * of subclass implementations.
40 * <p>
41 * Subclasses specify a Map implementation to use as the internal storage. The
42 * map will be used to map bag elements to a number; the number represents the
43 * number of occurrences of that element in the bag.
44 * </p>
45 *
46 * @param <E> The type of elements in this bag
47 * @since 3.0 (previously DefaultMapBag v2.0)
48 * @deprecated Since 4.6.0, use {@link AbstractMapMultiSet} instead.
49 */
50 @Deprecated
51 public abstract class AbstractMapBag<E> implements Bag<E> {
52
53 /**
54 * Inner class iterator for the Bag.
55 */
56 static class BagIterator<E> implements Iterator<E> {
57 private final AbstractMapBag<E> parent;
58 private final Iterator<Map.Entry<E, MutableInteger>> entryIterator;
59 private Map.Entry<E, MutableInteger> current;
60 private int itemCount;
61 private final int mods;
62 private boolean canRemove;
63
64 /**
65 * Constructs a new instance.
66 *
67 * @param parent The parent bag
68 */
69 BagIterator(final AbstractMapBag<E> parent) {
70 this.parent = parent;
71 this.entryIterator = parent.map.entrySet().iterator();
72 this.current = null;
73 this.mods = parent.modCount;
74 this.canRemove = false;
75 }
76
77 /** {@inheritDoc} */
78 @Override
79 public boolean hasNext() {
80 return itemCount > 0 || entryIterator.hasNext();
81 }
82
83 /** {@inheritDoc} */
84 @Override
85 public E next() {
86 if (parent.modCount != mods) {
87 throw new ConcurrentModificationException();
88 }
89 if (itemCount == 0) {
90 current = entryIterator.next();
91 itemCount = current.getValue().value;
92 }
93 canRemove = true;
94 itemCount--;
95 return current.getKey();
96 }
97
98 /** {@inheritDoc} */
99 @Override
100 public void remove() {
101 if (parent.modCount != mods) {
102 throw new ConcurrentModificationException();
103 }
104 if (!canRemove) {
105 throw new IllegalStateException();
106 }
107 final MutableInteger mut = current.getValue();
108 if (mut.value > 1) {
109 mut.value--;
110 } else {
111 entryIterator.remove();
112 }
113 parent.size--;
114 canRemove = false;
115 }
116 }
117
118 /**
119 * Mutable integer class for storing the data.
120 */
121 protected static class MutableInteger {
122
123 /** The value of this mutable. */
124 protected int value;
125
126 /**
127 * Constructs a new instance.
128 *
129 * @param value The initial value
130 */
131 MutableInteger(final int value) {
132 this.value = value;
133 }
134
135 @Override
136 public boolean equals(final Object obj) {
137 if (!(obj instanceof MutableInteger)) {
138 return false;
139 }
140 return ((MutableInteger) obj).value == value;
141 }
142
143 @Override
144 public int hashCode() {
145 return value;
146 }
147 }
148
149 /** The map to use to store the data */
150 private transient Map<E, MutableInteger> map;
151
152 /** The current total size of the bag; kept exact past {@link Integer#MAX_VALUE}, {@link #size()} saturates */
153 private long size;
154
155 /** The modification count for fail fast iterators */
156 private transient int modCount;
157
158 /** Unique view of the elements */
159 private transient Set<E> uniqueSet;
160
161 /**
162 * Constructor needed for subclass serialization.
163 */
164 protected AbstractMapBag() {
165 }
166
167 /**
168 * Constructor that assigns the specified Map as the backing store. The map
169 * must be empty and non-null.
170 *
171 * @param map The map to assign
172 */
173 protected AbstractMapBag(final Map<E, MutableInteger> map) {
174 this.map = Objects.requireNonNull(map, "map");
175 }
176
177 /**
178 * Constructs a new instance that assigns the specified Map as the backing store. The map
179 * must be empty and non-null. The bag is filled from the iterable elements.
180 *
181 * @param map The map to assign.
182 * @param iterable The bag is filled from these iterable elements.
183 */
184 protected AbstractMapBag(final Map<E, MutableInteger> map, final Iterable<? extends E> iterable) {
185 this(map);
186 iterable.forEach(this::add);
187 }
188
189 /**
190 * Adds a new element to the bag, incrementing its count in the underlying map.
191 *
192 * @param object The object to add
193 * @return {@code true} if the object was not already in the {@code uniqueSet}
194 */
195 @Override
196 public boolean add(final E object) {
197 return add(object, 1);
198 }
199
200 /**
201 * Adds a new element to the bag, incrementing its count in the map.
202 * The count of an element saturates at {@code Integer.MAX_VALUE}; copies
203 * that would take it past that limit are not added.
204 *
205 * @param object The object to search for
206 * @param nCopies The number of copies to add
207 * @return {@code true} if the object was not already in the {@code uniqueSet}
208 */
209 @Override
210 public boolean add(final E object, final int nCopies) {
211 modCount++;
212 if (nCopies > 0) {
213 final MutableInteger mut = map.get(object);
214 if (mut == null) {
215 map.put(object, new MutableInteger(nCopies));
216 size += nCopies;
217 return true;
218 }
219 final int applied = Math.min(nCopies, Integer.MAX_VALUE - mut.value);
220 mut.value += applied;
221 size += applied;
222 }
223 return false;
224 }
225
226 /**
227 * Invokes {@link #add(Object)} for each element in the given collection.
228 *
229 * @param coll The collection to add
230 * @return {@code true} if this call changed the bag
231 */
232 @Override
233 public boolean addAll(final Collection<? extends E> coll) {
234 boolean changed = false;
235 for (final E current : coll) {
236 final boolean added = add(current);
237 changed = changed || added;
238 }
239 return changed;
240 }
241
242 /**
243 * Clears the bag by clearing the underlying map.
244 */
245 @Override
246 public void clear() {
247 modCount++;
248 map.clear();
249 size = 0;
250 }
251
252 /**
253 * Determines if the bag contains the given element by checking if the
254 * underlying map contains the element as a key.
255 *
256 * @param object The object to search for
257 * @return true if the bag contains the given element
258 */
259 @Override
260 public boolean contains(final Object object) {
261 return map.containsKey(object);
262 }
263
264 /**
265 * Returns {@code true} if the bag contains all elements in the given
266 * collection, respecting cardinality.
267 *
268 * @param other The bag to check against
269 * @return {@code true} if the Bag contains all the collection
270 */
271 boolean containsAll(final Bag<?> other) {
272 for (final Object current : other.uniqueSet()) {
273 if (getCount(current) < other.getCount(current)) {
274 return false;
275 }
276 }
277 return true;
278 }
279
280 /**
281 * Determines if the bag contains the given elements.
282 *
283 * @param coll The collection to check against
284 * @return {@code true} if the Bag contains all the collection
285 */
286 @Override
287 public boolean containsAll(final Collection<?> coll) {
288 if (coll instanceof Bag) {
289 return containsAll((Bag<?>) coll);
290 }
291 return containsAll(new HashBag<>(coll));
292 }
293
294 /**
295 * Reads the map in using a custom routine.
296 *
297 * @param map The map to use
298 * @param in The input stream
299 * @throws IOException any of the usual I/O related exceptions
300 * @throws ClassNotFoundException if the stream contains an object which class cannot be loaded
301 * @throws ClassCastException if the stream does not contain the correct objects
302 */
303 protected void doReadObject(final Map<E, MutableInteger> map, final ObjectInputStream in)
304 throws IOException, ClassNotFoundException {
305 this.map = map;
306 final int entrySize = in.readInt();
307 for (int i = 0; i < entrySize; i++) {
308 @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
309 final E obj = (E) in.readObject();
310 final int count = in.readInt();
311 if (count < 1) {
312 throw new InvalidObjectException("Invalid count for entry (must be >= 1): " + count);
313 }
314 map.put(obj, new MutableInteger(count));
315 size += count;
316 }
317 }
318
319 /**
320 * Writes the map out using a custom routine.
321 *
322 * @param out The output stream
323 * @throws IOException any of the usual I/O related exceptions
324 */
325 protected void doWriteObject(final ObjectOutputStream out) throws IOException {
326 out.writeInt(map.size());
327 for (final Entry<E, MutableInteger> entry : map.entrySet()) {
328 out.writeObject(entry.getKey());
329 out.writeInt(entry.getValue().value);
330 }
331 }
332
333 /**
334 * Compares this Bag to another. This Bag equals another Bag if it contains
335 * the same number of occurrences of the same elements.
336 *
337 * @param object The Bag to compare to
338 * @return true if equal
339 */
340 @Override
341 public boolean equals(final Object object) {
342 if (object == this) {
343 return true;
344 }
345 if (!(object instanceof Bag)) {
346 return false;
347 }
348 final Bag<?> other = (Bag<?>) object;
349 if (other.size() != size()) {
350 return false;
351 }
352 for (final E element : map.keySet()) {
353 if (other.getCount(element) != getCount(element)) {
354 return false;
355 }
356 }
357 return true;
358 }
359
360 /**
361 * Gets the number of occurrence of the given element in this bag by
362 * looking up its count in the underlying map.
363 *
364 * @param object The object to search for
365 * @return The number of occurrences of the object, zero if not found
366 */
367 @Override
368 public int getCount(final Object object) {
369 final MutableInteger count = map.get(object);
370 if (count != null) {
371 return count.value;
372 }
373 return 0;
374 }
375
376 /**
377 * Utility method for implementations to access the map that backs this bag.
378 * Not intended for interactive use outside of subclasses.
379 *
380 * @return The map being used by the Bag
381 */
382 protected Map<E, MutableInteger> getMap() {
383 return map;
384 }
385
386 /**
387 * Gets a hash code for the Bag compatible with the definition of equals.
388 * The hash code is defined as the sum total of a hash code for each
389 * element. The per element hash code is defined as
390 * {@code (e==null ? 0 : e.hashCode()) ^ noOccurrences)}. This hash code
391 * is compatible with the Set interface.
392 *
393 * @return The hash code of the Bag
394 */
395 @Override
396 public int hashCode() {
397 int total = 0;
398 for (final Entry<E, MutableInteger> entry : map.entrySet()) {
399 final E element = entry.getKey();
400 final MutableInteger count = entry.getValue();
401 total += (element == null ? 0 : element.hashCode()) ^ count.value;
402 }
403 return total;
404 }
405
406 /**
407 * Returns true if the underlying map is empty.
408 *
409 * @return true if bag is empty
410 */
411 @Override
412 public boolean isEmpty() {
413 return map.isEmpty();
414 }
415
416 /**
417 * Gets an iterator over the bag elements. Elements present in the Bag more
418 * than once will be returned repeatedly.
419 *
420 * @return The iterator
421 */
422 @Override
423 public Iterator<E> iterator() {
424 return new BagIterator<>(this);
425 }
426
427 /**
428 * Removes all copies of the specified object from the bag.
429 *
430 * @param object The object to remove
431 * @return true if the bag changed
432 */
433 @Override
434 public boolean remove(final Object object) {
435 final MutableInteger mut = map.get(object);
436 if (mut == null) {
437 return false;
438 }
439 modCount++;
440 map.remove(object);
441 size -= mut.value;
442 return true;
443 }
444
445 /**
446 * Removes a specified number of copies of an object from the bag.
447 *
448 * @param object The object to remove
449 * @param nCopies The number of copies to remove
450 * @return true if the bag changed
451 */
452 @Override
453 public boolean remove(final Object object, final int nCopies) {
454 final MutableInteger mut = map.get(object);
455 if (mut == null) {
456 return false;
457 }
458 if (nCopies <= 0) {
459 return false;
460 }
461 modCount++;
462 if (nCopies < mut.value) {
463 mut.value -= nCopies;
464 size -= nCopies;
465 } else {
466 map.remove(object);
467 size -= mut.value;
468 }
469 return true;
470 }
471
472 /**
473 * Removes objects from the bag according to their count in the specified
474 * collection.
475 *
476 * @param coll The collection to use
477 * @return true if the bag changed
478 */
479 @Override
480 public boolean removeAll(final Collection<?> coll) {
481 boolean result = false;
482 if (coll != null) {
483 for (final Object current : coll) {
484 final boolean changed = remove(current, 1);
485 result = result || changed;
486 }
487 }
488 return result;
489 }
490
491 /**
492 * Remove any members of the bag that are not in the given bag, respecting
493 * cardinality.
494 *
495 * @see #retainAll(Collection)
496 * @param other The bag to retain
497 * @return {@code true} if this call changed the collection
498 */
499 boolean retainAll(final Bag<?> other) {
500 boolean result = false;
501 final Bag<E> excess = new HashBag<>();
502 for (final E current : uniqueSet()) {
503 final int myCount = getCount(current);
504 final int otherCount = other.getCount(current);
505 if (1 <= otherCount && otherCount <= myCount) {
506 excess.add(current, myCount - otherCount);
507 } else if (otherCount == 0) {
508 excess.add(current, myCount);
509 }
510 }
511 if (!excess.isEmpty()) {
512 result = removeAll(excess);
513 }
514 return result;
515 }
516
517 /**
518 * Remove any members of the bag that are not in the given bag, respecting
519 * cardinality.
520 *
521 * @param coll The collection to retain
522 * @return true if this call changed the collection
523 */
524 @Override
525 public boolean retainAll(final Collection<?> coll) {
526 if (coll instanceof Bag) {
527 return retainAll((Bag<?>) coll);
528 }
529 return retainAll(new HashBag<>(coll));
530 }
531
532 /**
533 * Returns the number of elements in this bag, or {@code Integer.MAX_VALUE}
534 * if the bag contains more than {@code Integer.MAX_VALUE} elements.
535 *
536 * @return current size of the bag
537 */
538 @Override
539 public int size() {
540 return (int) Math.min(size, Integer.MAX_VALUE);
541 }
542
543 /**
544 * Returns an array of all of this bag's elements.
545 *
546 * @return An array of all of this bag's elements
547 */
548 @Override
549 public Object[] toArray() {
550 final Object[] result = new Object[size()];
551 int i = 0;
552 for (final E current : map.keySet()) {
553 for (int index = getCount(current); index > 0; index--) {
554 result[i++] = current;
555 }
556 }
557 return result;
558 }
559
560 /**
561 * Returns an array of all of this bag's elements.
562 * If the input array has more elements than are in the bag,
563 * trailing elements will be set to null.
564 *
565 * @param <T> The type of the array elements
566 * @param array The array to populate
567 * @return An array of all of this bag's elements
568 * @throws ArrayStoreException if the runtime type of the specified array is not
569 * a supertype of the runtime type of the elements in this list
570 * @throws NullPointerException if the specified array is null
571 */
572 @Override
573 public <T> T[] toArray(T[] array) {
574 final int size = size();
575 if (array.length < size) {
576 @SuppressWarnings("unchecked") // safe as both are of type T
577 final T[] unchecked = (T[]) Array.newInstance(array.getClass().getComponentType(), size);
578 array = unchecked;
579 }
580
581 int i = 0;
582 for (final E current : map.keySet()) {
583 for (int index = getCount(current); index > 0; index--) {
584 // unsafe, will throw ArrayStoreException if types are not compatible, see Javadoc
585 @SuppressWarnings("unchecked")
586 final T unchecked = (T) current;
587 array[i++] = unchecked;
588 }
589 }
590 while (i < array.length) {
591 array[i++] = null;
592 }
593 return array;
594 }
595
596 /**
597 * Implement a toString() method suitable for debugging.
598 *
599 * @return A debugging toString
600 */
601 @Override
602 public String toString() {
603 if (isEmpty()) {
604 return "[]";
605 }
606 final StringBuilder buf = new StringBuilder();
607 buf.append(CollectionUtils.DEFAULT_TOSTRING_PREFIX);
608 final Iterator<E> it = uniqueSet().iterator();
609 while (it.hasNext()) {
610 final Object current = it.next();
611 final int count = getCount(current);
612 buf.append(count);
613 buf.append(CollectionUtils.COLON);
614 buf.append(current);
615 if (it.hasNext()) {
616 buf.append(CollectionUtils.COMMA);
617 }
618 }
619 buf.append(CollectionUtils.DEFAULT_TOSTRING_SUFFIX);
620 return buf.toString();
621 }
622
623 /**
624 * Returns an unmodifiable view of the underlying map's key set.
625 *
626 * @return The set of unique elements in this bag
627 */
628 @Override
629 public Set<E> uniqueSet() {
630 if (uniqueSet == null) {
631 uniqueSet = UnmodifiableSet.<E>unmodifiableSet(map.keySet());
632 }
633 return uniqueSet;
634 }
635
636 }