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;
018
019 import java.util.ArrayList;
020 import java.util.Collection;
021 import java.util.ConcurrentModificationException;
022 import java.util.Iterator;
023 import java.util.List;
024 import java.util.Map;
025 import java.util.Set;
026
027 import org.apache.commons.collections.set.UnmodifiableSet;
028
029 /**
030 * A skeletal implementation of the {@link Bag}
031 * interface to minimize the effort required for target implementations.
032 * Subclasses need only to call <code>setMap(Map)</code> in their constructor
033 * (or invoke the Map constructor) specifying a map instance that will be used
034 * to store the contents of the bag.
035 * <p>
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 * @deprecated Moved to bag subpackage as AbstractMapBag. Due to be removed in v4.0.
040 * @since Commons Collections 2.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 */
048 public abstract class DefaultMapBag implements Bag {
049 private Map _map = null;
050 private int _total = 0;
051 private int _mods = 0;
052
053 /**
054 * No-argument constructor.
055 * Subclasses should invoke <code>setMap(Map)</code> in
056 * their constructors.
057 */
058 public DefaultMapBag() {
059 }
060
061 /**
062 * Constructor that assigns the specified Map as the backing store.
063 * The map must be empty.
064 *
065 * @param map the map to assign
066 */
067 protected DefaultMapBag(Map map) {
068 setMap(map);
069 }
070
071 /**
072 * Adds a new element to the bag by incrementing its count in the
073 * underlying map.
074 *
075 * @param object the object to add
076 * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
077 */
078 public boolean add(Object object) {
079 return add(object, 1);
080 }
081
082 /**
083 * Adds a new element to the bag by incrementing its count in the map.
084 *
085 * @param object the object to search for
086 * @param nCopies the number of copies to add
087 * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
088 */
089 public boolean add(Object object, int nCopies) {
090 _mods++;
091 if (nCopies > 0) {
092 int count = (nCopies + getCount(object));
093 _map.put(object, new Integer(count));
094 _total += nCopies;
095 return (count == nCopies);
096 } else {
097 return false;
098 }
099 }
100
101 /**
102 * Invokes {@link #add(Object)} for each element in the given collection.
103 *
104 * @param coll the collection to add
105 * @return <code>true</code> if this call changed the bag
106 */
107 public boolean addAll(Collection coll) {
108 boolean changed = false;
109 Iterator i = coll.iterator();
110 while (i.hasNext()) {
111 boolean added = add(i.next());
112 changed = changed || added;
113 }
114 return changed;
115 }
116
117 /**
118 * Clears the bag by clearing the underlying map.
119 */
120 public void clear() {
121 _mods++;
122 _map.clear();
123 _total = 0;
124 }
125
126 /**
127 * Determines if the bag contains the given element by checking if the
128 * underlying map contains the element as a key.
129 *
130 * @param object the object to search for
131 * @return true if the bag contains the given element
132 */
133 public boolean contains(Object object) {
134 return _map.containsKey(object);
135 }
136
137 /**
138 * Determines if the bag contains the given elements.
139 *
140 * @param coll the collection to check against
141 * @return <code>true</code> if the Bag contains all the collection
142 */
143 public boolean containsAll(Collection coll) {
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 public boolean containsAll(Bag other) {
155 boolean result = true;
156 Iterator i = other.uniqueSet().iterator();
157 while (i.hasNext()) {
158 Object current = i.next();
159 boolean contains = getCount(current) >= other.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("The map must be non-null and empty");
395 }
396 _map = map;
397 }
398
399 /**
400 * Utility method for implementations to access the map that backs
401 * this bag. Not intended for interactive use outside of
402 * subclasses.
403 */
404 protected Map getMap() {
405 return _map;
406 }
407
408 /**
409 * Create a list for use in iteration, etc.
410 */
411 private List extractList() {
412 List result = new ArrayList();
413 Iterator i = uniqueSet().iterator();
414 while (i.hasNext()) {
415 Object current = i.next();
416 for (int index = getCount(current); index > 0; index--) {
417 result.add(current);
418 }
419 }
420 return result;
421 }
422
423 /**
424 * Return number of modifications for iterator.
425 *
426 * @return the modification count
427 */
428 private int modCount() {
429 return _mods;
430 }
431
432 /**
433 * Implement a toString() method suitable for debugging.
434 *
435 * @return a debugging toString
436 */
437 public String toString() {
438 StringBuffer buf = new StringBuffer();
439 buf.append("[");
440 Iterator i = uniqueSet().iterator();
441 while (i.hasNext()) {
442 Object current = i.next();
443 int count = getCount(current);
444 buf.append(count);
445 buf.append(":");
446 buf.append(current);
447 if (i.hasNext()) {
448 buf.append(",");
449 }
450 }
451 buf.append("]");
452 return buf.toString();
453 }
454
455 }