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;
017:
018: import java.util.ArrayList;
019: import java.util.Collection;
020: import java.util.ConcurrentModificationException;
021: import java.util.Iterator;
022: import java.util.List;
023: import java.util.Map;
024: import java.util.Set;
025:
026: import org.apache.commons.collections.set.UnmodifiableSet;
027:
028: /**
029: * A skeletal implementation of the {@link Bag}
030: * interface to minimize the effort required for target implementations.
031: * Subclasses need only to call <code>setMap(Map)</code> in their constructor
032: * (or invoke the Map constructor) specifying a map instance that will be used
033: * to store the contents of the bag.
034: * <p>
035: * The map will be used to map bag elements to a number; the number represents
036: * the number of occurrences of that element in the bag.
037: *
038: * @deprecated Moved to bag subpackage as AbstractMapBag. Due to be removed in v4.0.
039: * @since Commons Collections 2.0
040: * @version $Revision: 357494 $ $Date: 2005-12-18 19:05:31 +0000 (Sun, 18 Dec 2005) $
041: *
042: * @author Chuck Burdick
043: * @author Michael A. Smith
044: * @author Stephen Colebourne
045: * @author Janek Bogucki
046: */
047: public abstract class DefaultMapBag implements Bag {
048: private Map _map = null;
049: private int _total = 0;
050: private int _mods = 0;
051:
052: /**
053: * No-argument constructor.
054: * Subclasses should invoke <code>setMap(Map)</code> in
055: * their constructors.
056: */
057: public DefaultMapBag() {
058: }
059:
060: /**
061: * Constructor that assigns the specified Map as the backing store.
062: * The map must be empty.
063: *
064: * @param map the map to assign
065: */
066: protected DefaultMapBag(Map map) {
067: setMap(map);
068: }
069:
070: /**
071: * Adds a new element to the bag by incrementing its count in the
072: * underlying map.
073: *
074: * @param object the object to add
075: * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
076: */
077: public boolean add(Object object) {
078: return add(object, 1);
079: }
080:
081: /**
082: * Adds a new element to the bag by incrementing its count in the map.
083: *
084: * @param object the object to search for
085: * @param nCopies the number of copies to add
086: * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
087: */
088: public boolean add(Object object, int nCopies) {
089: _mods++;
090: if (nCopies > 0) {
091: int count = (nCopies + getCount(object));
092: _map.put(object, new Integer(count));
093: _total += nCopies;
094: return (count == nCopies);
095: } else {
096: return false;
097: }
098: }
099:
100: /**
101: * Invokes {@link #add(Object)} for each element in the given collection.
102: *
103: * @param coll the collection to add
104: * @return <code>true</code> if this call changed the bag
105: */
106: public boolean addAll(Collection coll) {
107: boolean changed = false;
108: Iterator i = coll.iterator();
109: while (i.hasNext()) {
110: boolean added = add(i.next());
111: changed = changed || added;
112: }
113: return changed;
114: }
115:
116: /**
117: * Clears the bag by clearing the underlying map.
118: */
119: public void clear() {
120: _mods++;
121: _map.clear();
122: _total = 0;
123: }
124:
125: /**
126: * Determines if the bag contains the given element by checking if the
127: * underlying map contains the element as a key.
128: *
129: * @param object the object to search for
130: * @return true if the bag contains the given element
131: */
132: public boolean contains(Object object) {
133: return _map.containsKey(object);
134: }
135:
136: /**
137: * Determines if the bag contains the given elements.
138: *
139: * @param coll the collection to check against
140: * @return <code>true</code> if the Bag contains all the collection
141: */
142: public boolean containsAll(Collection coll) {
143: return containsAll(new HashBag(coll));
144: }
145:
146: /**
147: * Returns <code>true</code> if the bag contains all elements in
148: * the given collection, respecting cardinality.
149: *
150: * @param other the bag to check against
151: * @return <code>true</code> if the Bag contains all the collection
152: */
153: public boolean containsAll(Bag other) {
154: boolean result = true;
155: Iterator i = other.uniqueSet().iterator();
156: while (i.hasNext()) {
157: Object current = i.next();
158: boolean contains = getCount(current) >= other
159: .getCount(current);
160: result = result && contains;
161: }
162: return result;
163: }
164:
165: /**
166: * Returns true if the given object is not null, has the precise type
167: * of this bag, and contains the same number of occurrences of all the
168: * same elements.
169: *
170: * @param object the object to test for equality
171: * @return true if that object equals this bag
172: */
173: public boolean equals(Object object) {
174: if (object == this ) {
175: return true;
176: }
177: if (object instanceof Bag == false) {
178: return false;
179: }
180: Bag other = (Bag) object;
181: if (other.size() != size()) {
182: return false;
183: }
184: for (Iterator it = _map.keySet().iterator(); it.hasNext();) {
185: Object element = it.next();
186: if (other.getCount(element) != getCount(element)) {
187: return false;
188: }
189: }
190: return true;
191: }
192:
193: /**
194: * Returns the hash code of the underlying map.
195: *
196: * @return the hash code of the underlying map
197: */
198: public int hashCode() {
199: return _map.hashCode();
200: }
201:
202: /**
203: * Returns true if the underlying map is empty.
204: *
205: * @return true if there are no elements in this bag
206: */
207: public boolean isEmpty() {
208: return _map.isEmpty();
209: }
210:
211: public Iterator iterator() {
212: return new BagIterator(this , extractList().iterator());
213: }
214:
215: static class BagIterator implements Iterator {
216: private DefaultMapBag _parent = null;
217: private Iterator _support = null;
218: private Object _current = null;
219: private int _mods = 0;
220:
221: public BagIterator(DefaultMapBag parent, Iterator support) {
222: _parent = parent;
223: _support = support;
224: _current = null;
225: _mods = parent.modCount();
226: }
227:
228: public boolean hasNext() {
229: return _support.hasNext();
230: }
231:
232: public Object next() {
233: if (_parent.modCount() != _mods) {
234: throw new ConcurrentModificationException();
235: }
236: _current = _support.next();
237: return _current;
238: }
239:
240: public void remove() {
241: if (_parent.modCount() != _mods) {
242: throw new ConcurrentModificationException();
243: }
244: _support.remove();
245: _parent.remove(_current, 1);
246: _mods++;
247: }
248: }
249:
250: public boolean remove(Object object) {
251: return remove(object, getCount(object));
252: }
253:
254: public boolean remove(Object object, int nCopies) {
255: _mods++;
256: boolean result = false;
257: int count = getCount(object);
258: if (nCopies <= 0) {
259: result = false;
260: } else if (count > nCopies) {
261: _map.put(object, new Integer(count - nCopies));
262: result = true;
263: _total -= nCopies;
264: } else { // count > 0 && count <= i
265: // need to remove all
266: result = (_map.remove(object) != null);
267: _total -= count;
268: }
269: return result;
270: }
271:
272: public boolean removeAll(Collection coll) {
273: boolean result = false;
274: if (coll != null) {
275: Iterator i = coll.iterator();
276: while (i.hasNext()) {
277: boolean changed = remove(i.next(), 1);
278: result = result || changed;
279: }
280: }
281: return result;
282: }
283:
284: /**
285: * Remove any members of the bag that are not in the given
286: * bag, respecting cardinality.
287: *
288: * @param coll the collection to retain
289: * @return true if this call changed the collection
290: */
291: public boolean retainAll(Collection coll) {
292: return retainAll(new HashBag(coll));
293: }
294:
295: /**
296: * Remove any members of the bag that are not in the given
297: * bag, respecting cardinality.
298: * @see #retainAll(Collection)
299: *
300: * @param other the bag to retain
301: * @return <code>true</code> if this call changed the collection
302: */
303: public boolean retainAll(Bag other) {
304: boolean result = false;
305: Bag excess = new HashBag();
306: Iterator i = uniqueSet().iterator();
307: while (i.hasNext()) {
308: Object current = i.next();
309: int myCount = getCount(current);
310: int otherCount = other.getCount(current);
311: if (1 <= otherCount && otherCount <= myCount) {
312: excess.add(current, myCount - otherCount);
313: } else {
314: excess.add(current, myCount);
315: }
316: }
317: if (!excess.isEmpty()) {
318: result = removeAll(excess);
319: }
320: return result;
321: }
322:
323: /**
324: * Returns an array of all of this bag's elements.
325: *
326: * @return an array of all of this bag's elements
327: */
328: public Object[] toArray() {
329: return extractList().toArray();
330: }
331:
332: /**
333: * Returns an array of all of this bag's elements.
334: *
335: * @param array the array to populate
336: * @return an array of all of this bag's elements
337: */
338: public Object[] toArray(Object[] array) {
339: return extractList().toArray(array);
340: }
341:
342: /**
343: * Returns the number of occurrence of the given element in this bag
344: * by looking up its count in the underlying map.
345: *
346: * @param object the object to search for
347: * @return the number of occurrences of the object, zero if not found
348: */
349: public int getCount(Object object) {
350: int result = 0;
351: Integer count = MapUtils.getInteger(_map, object);
352: if (count != null) {
353: result = count.intValue();
354: }
355: return result;
356: }
357:
358: /**
359: * Returns an unmodifiable view of the underlying map's key set.
360: *
361: * @return the set of unique elements in this bag
362: */
363: public Set uniqueSet() {
364: return UnmodifiableSet.decorate(_map.keySet());
365: }
366:
367: /**
368: * Returns the number of elements in this bag.
369: *
370: * @return the number of elements in this bag
371: */
372: public int size() {
373: return _total;
374: }
375:
376: /**
377: * Actually walks the bag to make sure the count is correct and
378: * resets the running total
379: *
380: * @return the current total size
381: */
382: protected int calcTotalSize() {
383: _total = extractList().size();
384: return _total;
385: }
386:
387: /**
388: * Utility method for implementations to set the map that backs
389: * this bag. Not intended for interactive use outside of
390: * subclasses.
391: */
392: protected void setMap(Map map) {
393: if (map == null || map.isEmpty() == false) {
394: throw new IllegalArgumentException(
395: "The map must be non-null and empty");
396: }
397: _map = map;
398: }
399:
400: /**
401: * Utility method for implementations to access the map that backs
402: * this bag. Not intended for interactive use outside of
403: * subclasses.
404: */
405: protected Map getMap() {
406: return _map;
407: }
408:
409: /**
410: * Create a list for use in iteration, etc.
411: */
412: private List extractList() {
413: List result = new ArrayList();
414: Iterator i = uniqueSet().iterator();
415: while (i.hasNext()) {
416: Object current = i.next();
417: for (int index = getCount(current); index > 0; index--) {
418: result.add(current);
419: }
420: }
421: return result;
422: }
423:
424: /**
425: * Return number of modifications for iterator.
426: *
427: * @return the modification count
428: */
429: private int modCount() {
430: return _mods;
431: }
432:
433: /**
434: * Implement a toString() method suitable for debugging.
435: *
436: * @return a debugging toString
437: */
438: public String toString() {
439: StringBuffer buf = new StringBuffer();
440: buf.append("[");
441: Iterator i = uniqueSet().iterator();
442: while (i.hasNext()) {
443: Object current = i.next();
444: int count = getCount(current);
445: buf.append(count);
446: buf.append(":");
447: buf.append(current);
448: if (i.hasNext()) {
449: buf.append(",");
450: }
451: }
452: buf.append("]");
453: return buf.toString();
454: }
455:
456: }
|