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