001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections.bag;
018
019 import java.io.IOException;
020 import java.io.ObjectInputStream;
021 import java.io.ObjectOutputStream;
022 import java.lang.reflect.Array;
023 import java.util.Collection;
024 import java.util.ConcurrentModificationException;
025 import java.util.Iterator;
026 import java.util.Map;
027 import java.util.Set;
028
029 import org.apache.commons.collections.Bag;
030 import org.apache.commons.collections.set.UnmodifiableSet;
031
032 /**
033 * Abstract implementation of the {@link Bag} interface to simplify the creation
034 * of subclass implementations.
035 * <p>
036 * Subclasses specify a Map implementation to use as the internal storage.
037 * The map will be used to map bag elements to a number; the number represents
038 * the number of occurrences of that element in the bag.
039 *
040 * @since Commons Collections 3.0 (previously DefaultMapBag v2.0)
041 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
042 *
043 * @author Chuck Burdick
044 * @author Michael A. Smith
045 * @author Stephen Colebourne
046 * @author Janek Bogucki
047 * @author Steve Clark
048 */
049 public abstract class AbstractMapBag implements Bag {
050
051 /** The map to use to store the data */
052 private transient Map map;
053 /** The current total size of the bag */
054 private int size;
055 /** The modification count for fail fast iterators */
056 private transient int modCount;
057 /** The modification count for fail fast iterators */
058 private transient Set uniqueSet;
059
060 /**
061 * Constructor needed for subclass serialisation.
062 *
063 */
064 protected AbstractMapBag() {
065 super();
066 }
067
068 /**
069 * Constructor that assigns the specified Map as the backing store.
070 * The map must be empty and non-null.
071 *
072 * @param map the map to assign
073 */
074 protected AbstractMapBag(Map map) {
075 super();
076 this.map = map;
077 }
078
079 /**
080 * Utility method for implementations to access the map that backs
081 * this bag. Not intended for interactive use outside of subclasses.
082 *
083 * @return the map being used by the Bag
084 */
085 protected Map getMap() {
086 return map;
087 }
088
089 //-----------------------------------------------------------------------
090 /**
091 * Returns the number of elements in this bag.
092 *
093 * @return current size of the bag
094 */
095 public int size() {
096 return size;
097 }
098
099 /**
100 * Returns true if the underlying map is empty.
101 *
102 * @return true if bag is empty
103 */
104 public boolean isEmpty() {
105 return map.isEmpty();
106 }
107
108 /**
109 * Returns the number of occurrence of the given element in this bag
110 * by looking up its count in the underlying map.
111 *
112 * @param object the object to search for
113 * @return the number of occurrences of the object, zero if not found
114 */
115 public int getCount(Object object) {
116 MutableInteger count = (MutableInteger) map.get(object);
117 if (count != null) {
118 return count.value;
119 }
120 return 0;
121 }
122
123 //-----------------------------------------------------------------------
124 /**
125 * Determines if the bag contains the given element by checking if the
126 * underlying map contains the element as a key.
127 *
128 * @param object the object to search for
129 * @return true if the bag contains the given element
130 */
131 public boolean contains(Object object) {
132 return map.containsKey(object);
133 }
134
135 /**
136 * Determines if the bag contains the given elements.
137 *
138 * @param coll the collection to check against
139 * @return <code>true</code> if the Bag contains all the collection
140 */
141 public boolean containsAll(Collection coll) {
142 if (coll instanceof Bag) {
143 return containsAll((Bag) coll);
144 }
145 return containsAll(new HashBag(coll));
146 }
147
148 /**
149 * Returns <code>true</code> if the bag contains all elements in
150 * the given collection, respecting cardinality.
151 *
152 * @param other the bag to check against
153 * @return <code>true</code> if the Bag contains all the collection
154 */
155 boolean containsAll(Bag other) {
156 boolean result = true;
157 Iterator it = other.uniqueSet().iterator();
158 while (it.hasNext()) {
159 Object current = it.next();
160 boolean contains = getCount(current) >= other.getCount(current);
161 result = result && contains;
162 }
163 return result;
164 }
165
166 //-----------------------------------------------------------------------
167 /**
168 * Gets an iterator over the bag elements.
169 * Elements present in the Bag more than once will be returned repeatedly.
170 *
171 * @return the iterator
172 */
173 public Iterator iterator() {
174 return new BagIterator(this);
175 }
176
177 /**
178 * Inner class iterator for the Bag.
179 */
180 static class BagIterator implements Iterator {
181 private AbstractMapBag parent;
182 private Iterator entryIterator;
183 private Map.Entry current;
184 private int itemCount;
185 private final int mods;
186 private boolean canRemove;
187
188 /**
189 * Constructor.
190 *
191 * @param parent the parent bag
192 */
193 public BagIterator(AbstractMapBag parent) {
194 this.parent = parent;
195 this.entryIterator = parent.map.entrySet().iterator();
196 this.current = null;
197 this.mods = parent.modCount;
198 this.canRemove = false;
199 }
200
201 public boolean hasNext() {
202 return (itemCount > 0 || entryIterator.hasNext());
203 }
204
205 public Object next() {
206 if (parent.modCount != mods) {
207 throw new ConcurrentModificationException();
208 }
209 if (itemCount == 0) {
210 current = (Map.Entry) entryIterator.next();
211 itemCount = ((MutableInteger) current.getValue()).value;
212 }
213 canRemove = true;
214 itemCount--;
215 return current.getKey();
216 }
217
218 public void remove() {
219 if (parent.modCount != mods) {
220 throw new ConcurrentModificationException();
221 }
222 if (canRemove == false) {
223 throw new IllegalStateException();
224 }
225 MutableInteger mut = (MutableInteger) current.getValue();
226 if (mut.value > 1) {
227 mut.value--;
228 } else {
229 entryIterator.remove();
230 }
231 parent.size--;
232 canRemove = false;
233 }
234 }
235
236 //-----------------------------------------------------------------------
237 /**
238 * Adds a new element to the bag, incrementing its count in the underlying map.
239 *
240 * @param object the object to add
241 * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
242 */
243 public boolean add(Object object) {
244 return add(object, 1);
245 }
246
247 /**
248 * Adds a new element to the bag, incrementing its count in the map.
249 *
250 * @param object the object to search for
251 * @param nCopies the number of copies to add
252 * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
253 */
254 public boolean add(Object object, int nCopies) {
255 modCount++;
256 if (nCopies > 0) {
257 MutableInteger mut = (MutableInteger) map.get(object);
258 size += nCopies;
259 if (mut == null) {
260 map.put(object, new MutableInteger(nCopies));
261 return true;
262 } else {
263 mut.value += nCopies;
264 return false;
265 }
266 } else {
267 return false;
268 }
269 }
270
271 /**
272 * Invokes {@link #add(Object)} for each element in the given collection.
273 *
274 * @param coll the collection to add
275 * @return <code>true</code> if this call changed the bag
276 */
277 public boolean addAll(Collection coll) {
278 boolean changed = false;
279 Iterator i = coll.iterator();
280 while (i.hasNext()) {
281 boolean added = add(i.next());
282 changed = changed || added;
283 }
284 return changed;
285 }
286
287 //-----------------------------------------------------------------------
288 /**
289 * Clears the bag by clearing the underlying map.
290 */
291 public void clear() {
292 modCount++;
293 map.clear();
294 size = 0;
295 }
296
297 /**
298 * Removes all copies of the specified object from the bag.
299 *
300 * @param object the object to remove
301 * @return true if the bag changed
302 */
303 public boolean remove(Object object) {
304 MutableInteger mut = (MutableInteger) map.get(object);
305 if (mut == null) {
306 return false;
307 }
308 modCount++;
309 map.remove(object);
310 size -= mut.value;
311 return true;
312 }
313
314 /**
315 * Removes a specified number of copies of an object from the bag.
316 *
317 * @param object the object to remove
318 * @param nCopies the number of copies to remove
319 * @return true if the bag changed
320 */
321 public boolean remove(Object object, int nCopies) {
322 MutableInteger mut = (MutableInteger) map.get(object);
323 if (mut == null) {
324 return false;
325 }
326 if (nCopies <= 0) {
327 return false;
328 }
329 modCount++;
330 if (nCopies < mut.value) {
331 mut.value -= nCopies;
332 size -= nCopies;
333 } else {
334 map.remove(object);
335 size -= mut.value;
336 }
337 return true;
338 }
339
340 /**
341 * Removes objects from the bag according to their count in the specified collection.
342 *
343 * @param coll the collection to use
344 * @return true if the bag changed
345 */
346 public boolean removeAll(Collection coll) {
347 boolean result = false;
348 if (coll != null) {
349 Iterator i = coll.iterator();
350 while (i.hasNext()) {
351 boolean changed = remove(i.next(), 1);
352 result = result || changed;
353 }
354 }
355 return result;
356 }
357
358 /**
359 * Remove any members of the bag that are not in the given
360 * bag, respecting cardinality.
361 *
362 * @param coll the collection to retain
363 * @return true if this call changed the collection
364 */
365 public boolean retainAll(Collection coll) {
366 if (coll instanceof Bag) {
367 return retainAll((Bag) coll);
368 }
369 return retainAll(new HashBag(coll));
370 }
371
372 /**
373 * Remove any members of the bag that are not in the given
374 * bag, respecting cardinality.
375 * @see #retainAll(Collection)
376 *
377 * @param other the bag to retain
378 * @return <code>true</code> if this call changed the collection
379 */
380 boolean retainAll(Bag other) {
381 boolean result = false;
382 Bag excess = new HashBag();
383 Iterator i = uniqueSet().iterator();
384 while (i.hasNext()) {
385 Object current = i.next();
386 int myCount = getCount(current);
387 int otherCount = other.getCount(current);
388 if (1 <= otherCount && otherCount <= myCount) {
389 excess.add(current, myCount - otherCount);
390 } else {
391 excess.add(current, myCount);
392 }
393 }
394 if (!excess.isEmpty()) {
395 result = removeAll(excess);
396 }
397 return result;
398 }
399
400 //-----------------------------------------------------------------------
401 /**
402 * Mutable integer class for storing the data.
403 */
404 protected static class MutableInteger {
405 /** The value of this mutable. */
406 protected int value;
407
408 /**
409 * Constructor.
410 * @param value the initial value
411 */
412 MutableInteger(int value) {
413 this.value = value;
414 }
415
416 public boolean equals(Object obj) {
417 if (obj instanceof MutableInteger == false) {
418 return false;
419 }
420 return ((MutableInteger) obj).value == value;
421 }
422
423 public int hashCode() {
424 return value;
425 }
426 }
427
428 //-----------------------------------------------------------------------
429 /**
430 * Returns an array of all of this bag's elements.
431 *
432 * @return an array of all of this bag's elements
433 */
434 public Object[] toArray() {
435 Object[] result = new Object[size()];
436 int i = 0;
437 Iterator it = map.keySet().iterator();
438 while (it.hasNext()) {
439 Object current = it.next();
440 for (int index = getCount(current); index > 0; index--) {
441 result[i++] = current;
442 }
443 }
444 return result;
445 }
446
447 /**
448 * Returns an array of all of this bag's elements.
449 *
450 * @param array the array to populate
451 * @return an array of all of this bag's elements
452 */
453 public Object[] toArray(Object[] array) {
454 int size = size();
455 if (array.length < size) {
456 array = (Object[]) Array.newInstance(array.getClass().getComponentType(), size);
457 }
458
459 int i = 0;
460 Iterator it = map.keySet().iterator();
461 while (it.hasNext()) {
462 Object current = it.next();
463 for (int index = getCount(current); index > 0; index--) {
464 array[i++] = current;
465 }
466 }
467 if (array.length > size) {
468 array[size] = null;
469 }
470 return array;
471 }
472
473 /**
474 * Returns an unmodifiable view of the underlying map's key set.
475 *
476 * @return the set of unique elements in this bag
477 */
478 public Set uniqueSet() {
479 if (uniqueSet == null) {
480 uniqueSet = UnmodifiableSet.decorate(map.keySet());
481 }
482 return uniqueSet;
483 }
484
485 //-----------------------------------------------------------------------
486 /**
487 * Write the map out using a custom routine.
488 * @param out the output stream
489 * @throws IOException
490 */
491 protected void doWriteObject(ObjectOutputStream out) throws IOException {
492 out.writeInt(map.size());
493 for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
494 Map.Entry entry = (Map.Entry) it.next();
495 out.writeObject(entry.getKey());
496 out.writeInt(((MutableInteger) entry.getValue()).value);
497 }
498 }
499
500 /**
501 * Read the map in using a custom routine.
502 * @param map the map to use
503 * @param in the input stream
504 * @throws IOException
505 * @throws ClassNotFoundException
506 */
507 protected void doReadObject(Map map, ObjectInputStream in) throws IOException, ClassNotFoundException {
508 this.map = map;
509 int entrySize = in.readInt();
510 for (int i = 0; i < entrySize; i++) {
511 Object obj = in.readObject();
512 int count = in.readInt();
513 map.put(obj, new MutableInteger(count));
514 size += count;
515 }
516 }
517
518 //-----------------------------------------------------------------------
519 /**
520 * Compares this Bag to another.
521 * This Bag equals another Bag if it contains the same number of occurrences of
522 * the same elements.
523 *
524 * @param object the Bag to compare to
525 * @return true if equal
526 */
527 public boolean equals(Object object) {
528 if (object == this) {
529 return true;
530 }
531 if (object instanceof Bag == false) {
532 return false;
533 }
534 Bag other = (Bag) object;
535 if (other.size() != size()) {
536 return false;
537 }
538 for (Iterator it = map.keySet().iterator(); it.hasNext();) {
539 Object element = it.next();
540 if (other.getCount(element) != getCount(element)) {
541 return false;
542 }
543 }
544 return true;
545 }
546
547 /**
548 * Gets a hash code for the Bag compatible with the definition of equals.
549 * The hash code is defined as the sum total of a hash code for each element.
550 * The per element hash code is defined as
551 * <code>(e==null ? 0 : e.hashCode()) ^ noOccurances)</code>.
552 * This hash code is compatible with the Set interface.
553 *
554 * @return the hash code of the Bag
555 */
556 public int hashCode() {
557 int total = 0;
558 for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
559 Map.Entry entry = (Map.Entry) it.next();
560 Object element = entry.getKey();
561 MutableInteger count = (MutableInteger) entry.getValue();
562 total += (element == null ? 0 : element.hashCode()) ^ count.value;
563 }
564 return total;
565 }
566
567 /**
568 * Implement a toString() method suitable for debugging.
569 *
570 * @return a debugging toString
571 */
572 public String toString() {
573 if (size() == 0) {
574 return "[]";
575 }
576 StringBuffer buf = new StringBuffer();
577 buf.append('[');
578 Iterator it = uniqueSet().iterator();
579 while (it.hasNext()) {
580 Object current = it.next();
581 int count = getCount(current);
582 buf.append(count);
583 buf.append(':');
584 buf.append(current);
585 if (it.hasNext()) {
586 buf.append(',');
587 }
588 }
589 buf.append(']');
590 return buf.toString();
591 }
592
593 }