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 * http://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.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 * Abstract implementation of the {@link Bag} interface to simplify the creation
36 * of subclass implementations.
37 * <p>
38 * Subclasses specify a Map implementation to use as the internal storage. The
39 * map will be used to map bag elements to a number; the number represents the
40 * number of occurrences of that element in the bag.
41 * </p>
42 *
43 * @param <E> the type of elements in this bag
44 * @since 3.0 (previously DefaultMapBag v2.0)
45 */
46 public abstract class AbstractMapBag<E> implements Bag<E> {
47
48 /**
49 * Inner class iterator for the Bag.
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 * Constructs a new instance.
61 *
62 * @param parent the parent bag
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 /** {@inheritDoc} */
73 @Override
74 public boolean hasNext() {
75 return itemCount > 0 || entryIterator.hasNext();
76 }
77
78 /** {@inheritDoc} */
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 /** {@inheritDoc} */
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 * Mutable integer class for storing the data.
114 */
115 protected static class MutableInteger {
116 /** The value of this mutable. */
117 protected int value;
118
119 /**
120 * Constructs a new instance.
121 * @param value the initial value
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 /** The map to use to store the data */
141 private transient Map<E, MutableInteger> map;
142 /** The current total size of the bag */
143 private int size;
144
145 /** The modification count for fail fast iterators */
146 private transient int modCount;
147
148 /** Unique view of the elements */
149 private transient Set<E> uniqueSet;
150
151 /**
152 * Constructor needed for subclass serialisation.
153 */
154 protected AbstractMapBag() {
155 }
156
157 /**
158 * Constructor that assigns the specified Map as the backing store. The map
159 * must be empty and non-null.
160 *
161 * @param map the map to assign
162 */
163 protected AbstractMapBag(final Map<E, MutableInteger> map) {
164 this.map = map;
165 }
166
167 /**
168 * Adds a new element to the bag, incrementing its count in the underlying map.
169 *
170 * @param object the object to add
171 * @return {@code true} if the object was not already in the {@code uniqueSet}
172 */
173 @Override
174 public boolean add(final E object) {
175 return add(object, 1);
176 }
177
178 /**
179 * Adds a new element to the bag, incrementing its count in the map.
180 *
181 * @param object the object to search for
182 * @param nCopies the number of copies to add
183 * @return {@code true} if the object was not already in the {@code uniqueSet}
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 * Invokes {@link #add(Object)} for each element in the given collection.
202 *
203 * @param coll the collection to add
204 * @return {@code true} if this call changed the bag
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 * Clears the bag by clearing the underlying map.
218 */
219 @Override
220 public void clear() {
221 modCount++;
222 map.clear();
223 size = 0;
224 }
225
226 /**
227 * Determines if the bag contains the given element by checking if the
228 * underlying map contains the element as a key.
229 *
230 * @param object the object to search for
231 * @return true if the bag contains the given element
232 */
233 @Override
234 public boolean contains(final Object object) {
235 return map.containsKey(object);
236 }
237
238 /**
239 * Returns {@code true} if the bag contains all elements in the given
240 * collection, respecting cardinality.
241 *
242 * @param other the bag to check against
243 * @return {@code true} if the Bag contains all the collection
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 * Determines if the bag contains the given elements.
256 *
257 * @param coll the collection to check against
258 * @return {@code true} if the Bag contains all the collection
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 * Read the map in using a custom routine.
270 * @param map the map to use
271 * @param in the input stream
272 * @throws IOException any of the usual I/O related exceptions
273 * @throws ClassNotFoundException if the stream contains an object which class can not be loaded
274 * @throws ClassCastException if the stream does not contain the correct objects
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") // This will fail at runtime if the stream is incorrect
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 * Write the map out using a custom routine.
291 * @param out the output stream
292 * @throws IOException any of the usual I/O related exceptions
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 * Compares this Bag to another. This Bag equals another Bag if it contains
304 * the same number of occurrences of the same elements.
305 *
306 * @param object the Bag to compare to
307 * @return true if equal
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 * Returns the number of occurrence of the given element in this bag by
331 * looking up its count in the underlying map.
332 *
333 * @param object the object to search for
334 * @return the number of occurrences of the object, zero if not found
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 * Utility method for implementations to access the map that backs this bag.
347 * Not intended for interactive use outside of subclasses.
348 *
349 * @return the map being used by the Bag
350 */
351 protected Map<E, MutableInteger> getMap() {
352 return map;
353 }
354
355 /**
356 * Gets a hash code for the Bag compatible with the definition of equals.
357 * The hash code is defined as the sum total of a hash code for each
358 * element. The per element hash code is defined as
359 * {@code (e==null ? 0 : e.hashCode()) ^ noOccurrences)}. This hash code
360 * is compatible with the Set interface.
361 *
362 * @return the hash code of the Bag
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 * Returns true if the underlying map is empty.
377 *
378 * @return true if bag is empty
379 */
380 @Override
381 public boolean isEmpty() {
382 return map.isEmpty();
383 }
384
385 /**
386 * Gets an iterator over the bag elements. Elements present in the Bag more
387 * than once will be returned repeatedly.
388 *
389 * @return the iterator
390 */
391 @Override
392 public Iterator<E> iterator() {
393 return new BagIterator<>(this);
394 }
395
396 /**
397 * Removes all copies of the specified object from the bag.
398 *
399 * @param object the object to remove
400 * @return true if the bag changed
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 * Removes a specified number of copies of an object from the bag.
416 *
417 * @param object the object to remove
418 * @param nCopies the number of copies to remove
419 * @return true if the bag changed
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 * Removes objects from the bag according to their count in the specified
443 * collection.
444 *
445 * @param coll the collection to use
446 * @return true if the bag changed
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 * Remove any members of the bag that are not in the given bag, respecting
462 * cardinality.
463 * @see #retainAll(Collection)
464 *
465 * @param other the bag to retain
466 * @return {@code true} if this call changed the collection
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 * Remove any members of the bag that are not in the given bag, respecting
488 * cardinality.
489 *
490 * @param coll the collection to retain
491 * @return true if this call changed the collection
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 * Returns the number of elements in this bag.
503 *
504 * @return current size of the bag
505 */
506 @Override
507 public int size() {
508 return size;
509 }
510
511 /**
512 * Returns an array of all of this bag's elements.
513 *
514 * @return an array of all of this bag's elements
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 * Returns an array of all of this bag's elements.
530 * If the input array has more elements than are in the bag,
531 * trailing elements will be set to null.
532 *
533 * @param <T> the type of the array elements
534 * @param array the array to populate
535 * @return an array of all of this bag's elements
536 * @throws ArrayStoreException if the runtime type of the specified array is not
537 * a supertype of the runtime type of the elements in this list
538 * @throws NullPointerException if the specified array is null
539 */
540 @Override
541 public <T> T[] toArray(T[] array) {
542 final int size = size();
543 if (array.length < size) {
544 @SuppressWarnings("unchecked") // safe as both are of type T
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 // unsafe, will throw ArrayStoreException if types are not compatible, see Javadoc
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 * Implement a toString() method suitable for debugging.
566 *
567 * @return a debugging toString
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 * Returns an unmodifiable view of the underlying map's key set.
593 *
594 * @return the set of unique elements in this bag
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 }