001: /*
002: * Copyright 2002-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.bag;
017:
018: import java.io.IOException;
019: import java.io.ObjectInputStream;
020: import java.io.ObjectOutputStream;
021: import java.lang.reflect.Array;
022: import java.util.Collection;
023: import java.util.ConcurrentModificationException;
024: import java.util.Iterator;
025: import java.util.Map;
026: import java.util.Set;
027:
028: import org.apache.commons.collections.Bag;
029: import org.apache.commons.collections.set.UnmodifiableSet;
030:
031: /**
032: * Abstract implementation of the {@link Bag} interface to simplify the creation
033: * of subclass implementations.
034: * <p>
035: * Subclasses specify a Map implementation to use as the internal storage.
036: * The map will be used to map bag elements to a number; the number represents
037: * the number of occurrences of that element in the bag.
038: *
039: * @since Commons Collections 3.0 (previously DefaultMapBag v2.0)
040: * @version $Revision: 219131 $ $Date: 2005-07-15 00:11:12 +0100 (Fri, 15 Jul 2005) $
041: *
042: * @author Chuck Burdick
043: * @author Michael A. Smith
044: * @author Stephen Colebourne
045: * @author Janek Bogucki
046: * @author Steve Clark
047: */
048: public abstract class AbstractMapBag implements Bag {
049:
050: /** The map to use to store the data */
051: private transient Map map;
052: /** The current total size of the bag */
053: private int size;
054: /** The modification count for fail fast iterators */
055: private transient int modCount;
056: /** The modification count for fail fast iterators */
057: private transient Set uniqueSet;
058:
059: /**
060: * Constructor needed for subclass serialisation.
061: *
062: */
063: protected AbstractMapBag() {
064: super ();
065: }
066:
067: /**
068: * Constructor that assigns the specified Map as the backing store.
069: * The map must be empty and non-null.
070: *
071: * @param map the map to assign
072: */
073: protected AbstractMapBag(Map map) {
074: super ();
075: this .map = map;
076: }
077:
078: /**
079: * Utility method for implementations to access the map that backs
080: * this bag. Not intended for interactive use outside of subclasses.
081: *
082: * @return the map being used by the Bag
083: */
084: protected Map getMap() {
085: return map;
086: }
087:
088: //-----------------------------------------------------------------------
089: /**
090: * Returns the number of elements in this bag.
091: *
092: * @return current size of the bag
093: */
094: public int size() {
095: return size;
096: }
097:
098: /**
099: * Returns true if the underlying map is empty.
100: *
101: * @return true if bag is empty
102: */
103: public boolean isEmpty() {
104: return map.isEmpty();
105: }
106:
107: /**
108: * Returns the number of occurrence of the given element in this bag
109: * by looking up its count in the underlying map.
110: *
111: * @param object the object to search for
112: * @return the number of occurrences of the object, zero if not found
113: */
114: public int getCount(Object object) {
115: MutableInteger count = (MutableInteger) map.get(object);
116: if (count != null) {
117: return count.value;
118: }
119: return 0;
120: }
121:
122: //-----------------------------------------------------------------------
123: /**
124: * Determines if the bag contains the given element by checking if the
125: * underlying map contains the element as a key.
126: *
127: * @param object the object to search for
128: * @return true if the bag contains the given element
129: */
130: public boolean contains(Object object) {
131: return map.containsKey(object);
132: }
133:
134: /**
135: * Determines if the bag contains the given elements.
136: *
137: * @param coll the collection to check against
138: * @return <code>true</code> if the Bag contains all the collection
139: */
140: public boolean containsAll(Collection coll) {
141: if (coll instanceof Bag) {
142: return containsAll((Bag) coll);
143: }
144: return containsAll(new HashBag(coll));
145: }
146:
147: /**
148: * Returns <code>true</code> if the bag contains all elements in
149: * the given collection, respecting cardinality.
150: *
151: * @param other the bag to check against
152: * @return <code>true</code> if the Bag contains all the collection
153: */
154: boolean containsAll(Bag other) {
155: boolean result = true;
156: Iterator it = other.uniqueSet().iterator();
157: while (it.hasNext()) {
158: Object current = it.next();
159: boolean contains = getCount(current) >= other
160: .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()
457: .getComponentType(), size);
458: }
459:
460: int i = 0;
461: Iterator it = map.keySet().iterator();
462: while (it.hasNext()) {
463: Object current = it.next();
464: for (int index = getCount(current); index > 0; index--) {
465: array[i++] = current;
466: }
467: }
468: if (array.length > size) {
469: array[size] = null;
470: }
471: return array;
472: }
473:
474: /**
475: * Returns an unmodifiable view of the underlying map's key set.
476: *
477: * @return the set of unique elements in this bag
478: */
479: public Set uniqueSet() {
480: if (uniqueSet == null) {
481: uniqueSet = UnmodifiableSet.decorate(map.keySet());
482: }
483: return uniqueSet;
484: }
485:
486: //-----------------------------------------------------------------------
487: /**
488: * Write the map out using a custom routine.
489: * @param out the output stream
490: * @throws IOException
491: */
492: protected void doWriteObject(ObjectOutputStream out)
493: throws IOException {
494: out.writeInt(map.size());
495: for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
496: Map.Entry entry = (Map.Entry) it.next();
497: out.writeObject(entry.getKey());
498: out.writeInt(((MutableInteger) entry.getValue()).value);
499: }
500: }
501:
502: /**
503: * Read the map in using a custom routine.
504: * @param map the map to use
505: * @param in the input stream
506: * @throws IOException
507: * @throws ClassNotFoundException
508: */
509: protected void doReadObject(Map map, ObjectInputStream in)
510: throws IOException, ClassNotFoundException {
511: this .map = map;
512: int entrySize = in.readInt();
513: for (int i = 0; i < entrySize; i++) {
514: Object obj = in.readObject();
515: int count = in.readInt();
516: map.put(obj, new MutableInteger(count));
517: size += count;
518: }
519: }
520:
521: //-----------------------------------------------------------------------
522: /**
523: * Compares this Bag to another.
524: * This Bag equals another Bag if it contains the same number of occurrences of
525: * the same elements.
526: *
527: * @param object the Bag to compare to
528: * @return true if equal
529: */
530: public boolean equals(Object object) {
531: if (object == this ) {
532: return true;
533: }
534: if (object instanceof Bag == false) {
535: return false;
536: }
537: Bag other = (Bag) object;
538: if (other.size() != size()) {
539: return false;
540: }
541: for (Iterator it = map.keySet().iterator(); it.hasNext();) {
542: Object element = it.next();
543: if (other.getCount(element) != getCount(element)) {
544: return false;
545: }
546: }
547: return true;
548: }
549:
550: /**
551: * Gets a hash code for the Bag compatible with the definition of equals.
552: * The hash code is defined as the sum total of a hash code for each element.
553: * The per element hash code is defined as
554: * <code>(e==null ? 0 : e.hashCode()) ^ noOccurances)</code>.
555: * This hash code is compatible with the Set interface.
556: *
557: * @return the hash code of the Bag
558: */
559: public int hashCode() {
560: int total = 0;
561: for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
562: Map.Entry entry = (Map.Entry) it.next();
563: Object element = entry.getKey();
564: MutableInteger count = (MutableInteger) entry.getValue();
565: total += (element == null ? 0 : element.hashCode())
566: ^ count.value;
567: }
568: return total;
569: }
570:
571: /**
572: * Implement a toString() method suitable for debugging.
573: *
574: * @return a debugging toString
575: */
576: public String toString() {
577: if (size() == 0) {
578: return "[]";
579: }
580: StringBuffer buf = new StringBuffer();
581: buf.append('[');
582: Iterator it = uniqueSet().iterator();
583: while (it.hasNext()) {
584: Object current = it.next();
585: int count = getCount(current);
586: buf.append(count);
587: buf.append(':');
588: buf.append(current);
589: if (it.hasNext()) {
590: buf.append(',');
591: }
592: }
593: buf.append(']');
594: return buf.toString();
595: }
596:
597: }
|