Java > Open Source Codes > org > apache > commons > collections > bag > AbstractMapBag


1 /*
2  * Copyright 2002-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections.bag;
17
18 import java.io.IOException ;
19 import java.io.ObjectInputStream ;
20 import java.io.ObjectOutputStream ;
21 import java.lang.reflect.Array ;
22 import java.util.Collection ;
23 import java.util.ConcurrentModificationException ;
24 import java.util.Iterator ;
25 import java.util.Map ;
26 import java.util.Set ;
27
28 import org.apache.commons.collections.Bag;
29 import org.apache.commons.collections.set.UnmodifiableSet;
30
31 /**
32  * Abstract implementation of the {@link Bag} interface to simplify the creation
33  * of subclass implementations.
34  * <p>
35  * Subclasses specify a Map implementation to use as the internal storage.
36  * The map will be used to map bag elements to a number; the number represents
37  * the number of occurrences of that element in the bag.
38  *
39  * @since Commons Collections 3.0 (previously DefaultMapBag v2.0)
40  * @version $Revision: 1.15 $ $Date: 2004/05/15 12:27:04 $
41  *
42  * @author Chuck Burdick
43  * @author Michael A. Smith
44  * @author Stephen Colebourne
45  * @author Janek Bogucki
46  */
47 public abstract class AbstractMapBag implements Bag {
48     
49     /** The map to use to store the data */
50     private transient Map map;
51     /** The current total size of the bag */
52     private int size;
53     /** The modification count for fail fast iterators */
54     private transient int modCount;
55     /** The modification count for fail fast iterators */
56     private transient Set uniqueSet;
57
58     /**
59      * Constructor needed for subclass serialisation.
60      *
61      */
62     protected AbstractMapBag() {
63         super();
64     }
65
66     /**
67      * Constructor that assigns the specified Map as the backing store.
68      * The map must be empty and non-null.
69      *
70      * @param map the map to assign
71      */
72     protected AbstractMapBag(Map map) {
73         super();
74         this.map = map;
75     }
76
77     /**
78      * Utility method for implementations to access the map that backs
79      * this bag. Not intended for interactive use outside of subclasses.
80      *
81      * @return the map being used by the Bag
82      */
83     protected Map getMap() {
84         return map;
85     }
86
87     //-----------------------------------------------------------------------
88 /**
89      * Returns the number of elements in this bag.
90      *
91      * @return current size of the bag
92      */
93     public int size() {
94         return size;
95     }
96
97     /**
98      * Returns true if the underlying map is empty.
99      *
100      * @return true if bag is empty
101      */
102     public boolean isEmpty() {
103         return map.isEmpty();
104     }
105
106     /**
107      * Returns the number of occurrence of the given element in this bag
108      * by looking up its count in the underlying map.
109      *
110      * @param object the object to search for
111      * @return the number of occurrences of the object, zero if not found
112      */
113     public int getCount(Object object) {
114         MutableInteger count = (MutableInteger) map.get(object);
115         if (count != null) {
116             return count.value;
117         }
118         return 0;
119     }
120
121     //-----------------------------------------------------------------------
122 /**
123      * Determines if the bag contains the given element by checking if the
124      * underlying map contains the element as a key.
125      *
126      * @param object the object to search for
127      * @return true if the bag contains the given element
128      */
129     public boolean contains(Object object) {
130         return map.containsKey(object);
131     }
132
133     /**
134      * Determines if the bag contains the given elements.
135      *
136      * @param coll the collection to check against
137      * @return <code>true</code> if the Bag contains all the collection
138      */
139     public boolean containsAll(Collection coll) {
140         if (coll instanceof Bag) {
141             return containsAll((Bag) coll);
142         }
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     boolean containsAll(Bag other) {
154         boolean result = true;
155         Iterator it = other.uniqueSet().iterator();
156         while (it.hasNext()) {
157             Object current = it.next();
158             boolean contains = getCount(current) >= other.getCount(current);
159             result = result && contains;
160         }
161         return result;
162     }
163
164     //-----------------------------------------------------------------------
165 /**
166      * Gets an iterator over the bag elements.
167      * Elements present in the Bag more than once will be returned repeatedly.
168      *
169      * @return the iterator
170      */
171     public Iterator iterator() {
172         return new BagIterator(this);
173     }
174
175     /**
176      * Inner class iterator for the Bag.
177      */
178     static class BagIterator implements Iterator {
179         private AbstractMapBag parent;
180         private Iterator entryIterator;
181         private Map.Entry current;
182         private int itemCount;
183         private final int mods;
184         private boolean canRemove;
185
186         /**
187          * Constructor.
188          *
189          * @param parent the parent bag
190          */
191         public BagIterator(AbstractMapBag parent) {
192             this.parent = parent;
193             this.entryIterator = parent.map.entrySet().iterator();
194             this.current = null;
195             this.mods = parent.modCount;
196             this.canRemove = false;
197         }
198
199         public boolean hasNext() {
200             return (itemCount > 0 || entryIterator.hasNext());
201         }
202
203         public Object next() {
204             if (parent.modCount != mods) {
205                 throw new ConcurrentModificationException ();
206             }
207             if (itemCount == 0) {
208                 current = (Map.Entry ) entryIterator.next();
209                 itemCount = ((MutableInteger) current.getValue()).value;
210             }
211             canRemove = true;
212             itemCount--;
213             return current.getKey();
214         }
215
216         public void remove() {
217             if (parent.modCount != mods) {
218                 throw new ConcurrentModificationException ();
219             }
220             if (canRemove == false) {
221                 throw new IllegalStateException ();
222             }
223             MutableInteger mut = (MutableInteger) current.getValue();
224             if (mut.value > 0) {
225                 mut.value--;
226                 parent.size--;
227             } else {
228                 entryIterator.remove();
229             }
230             canRemove = false;
231         }
232     }
233
234     //-----------------------------------------------------------------------
235 /**
236      * Adds a new element to the bag, incrementing its count in the underlying map.
237      *
238      * @param object the object to add
239      * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
240      */
241     public boolean add(Object object) {
242         return add(object, 1);
243     }
244
245     /**
246      * Adds a new element to the bag, incrementing its count in the map.
247      *
248      * @param object the object to search for
249      * @param nCopies the number of copies to add
250      * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
251      */
252     public boolean add(Object object, int nCopies) {
253         modCount++;
254         if (nCopies > 0) {
255             MutableInteger mut = (MutableInteger) map.get(object);
256             size += nCopies;
257             if (mut == null) {
258                 map.put(object, new MutableInteger(nCopies));
259                 return true;
260             } else {
261                 mut.value += nCopies;
262                 return false;
263             }
264         } else {
265             return false;
266         }
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(Collection coll) {
276         boolean changed = false;
277         Iterator i = coll.iterator();
278         while (i.hasNext()) {
279             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(Object object) {
302         MutableInteger mut = (MutableInteger) 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(Object object, int nCopies) {
320         MutableInteger mut = (MutableInteger) 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 collection.
340      *
341      * @param coll the collection to use
342      * @return true if the bag changed
343      */
344     public boolean removeAll(Collection coll) {
345         boolean result = false;
346         if (coll != null) {
347             Iterator i = coll.iterator();
348             while (i.hasNext()) {
349                 boolean changed = remove(i.next(), 1);
350                 result = result || changed;
351             }
352         }
353         return result;
354     }
355
356     /**
357      * Remove any members of the bag that are not in the given
358      * bag, respecting cardinality.
359      *
360      * @param coll the collection to retain
361      * @return true if this call changed the collection
362      */
363     public boolean retainAll(Collection coll) {
364         if (coll instanceof Bag) {
365             return retainAll((Bag) coll);
366         }
367         return retainAll(new HashBag(coll));
368     }
369
370     /**
371      * Remove any members of the bag that are not in the given
372      * bag, respecting cardinality.
373      * @see #retainAll(Collection)
374      *
375      * @param other the bag to retain
376      * @return <code>true</code> if this call changed the collection
377      */
378     boolean retainAll(Bag other) {
379         boolean result = false;
380         Bag excess = new HashBag();
381         Iterator i = uniqueSet().iterator();
382         while (i.hasNext()) {
383             Object current = i.next();
384             int myCount = getCount(current);
385             int otherCount = other.getCount(current);
386             if (1 <= otherCount && otherCount <= myCount) {
387                 excess.add(current, myCount - otherCount);
388             } else {
389                 excess.add(current, myCount);
390             }
391         }
392         if (!excess.isEmpty()) {
393             result = removeAll(excess);
394         }
395         return result;
396     }
397
398     //-----------------------------------------------------------------------
399 /**
400      * Mutable integer class for storing the data.
401      */
402     protected static class MutableInteger {
403         /** The value of this mutable. */
404         protected int value;
405         
406         /**
407          * Constructor.
408          * @param value the initial value
409          */
410         MutableInteger(int value) {
411             this.value = value;
412         }
413         
414         public boolean equals(Object obj) {
415             if (obj instanceof MutableInteger == false) {
416                 return false;
417             }
418             return ((MutableInteger) obj).value == value;
419         }
420
421         public int hashCode() {
422             return value;
423         }
424     }
425     
426     //-----------------------------------------------------------------------
427 /**
428      * Returns an array of all of this bag's elements.
429      *
430      * @return an array of all of this bag's elements
431      */
432     public Object [] toArray() {
433         Object [] result = new Object [size()];
434         int i = 0;
435         Iterator it = map.keySet().iterator();
436         while (it.hasNext()) {
437             Object current = it.next();
438             for (int index = getCount(current); index > 0; index--) {
439                 result[i++] = current;
440             }
441         }
442         return result;
443     }
444
445     /**
446      * Returns an array of all of this bag's elements.
447      *
448      * @param array the array to populate
449      * @return an array of all of this bag's elements
450      */
451     public Object [] toArray(Object [] array) {
452         int size = size();
453         if (array.length < size) {
454             array = (Object []) Array.newInstance(array.getClass().getComponentType(), size);
455         }
456
457         int i = 0;
458         Iterator it = map.keySet().iterator();
459         while (it.hasNext()) {
460             Object current = it.next();
461             for (int index = getCount(current); index > 0; index--) {
462                 array[i++] = current;
463             }
464         }
465         if (array.length > size) {
466             array[size] = null;
467         }
468         return array;
469     }
470
471     /**
472      * Returns an unmodifiable view of the underlying map's key set.
473      *
474      * @return the set of unique elements in this bag
475      */
476     public Set uniqueSet() {
477         if (uniqueSet == null) {
478             uniqueSet = UnmodifiableSet.decorate(map.keySet());
479         }
480         return uniqueSet;
481     }
482
483     //-----------------------------------------------------------------------
484 /**
485      * Write the map out using a custom routine.
486      * @param out the output stream
487      * @throws IOException
488      */
489     protected void doWriteObject(ObjectOutputStream out) throws IOException {
490         out.writeInt(map.size());
491         for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
492             Map.Entry entry = (Map.Entry ) it.next();
493             out.writeObject(entry.getKey());
494             out.writeInt(((MutableInteger) entry.getValue()).value);
495         }
496     }
497
498     /**
499      * Read the map in using a custom routine.
500      * @param map the map to use
501      * @param in the input stream
502      * @throws IOException
503      * @throws ClassNotFoundException
504      */
505     protected void doReadObject(Map map, ObjectInputStream in) throws IOException , ClassNotFoundException {
506         this.map = map;
507         int entrySize = in.readInt();
508         for (int i = 0; i < entrySize; i++) {
509             Object obj = in.readObject();
510             int count = in.readInt();
511             map.put(obj, new MutableInteger(count));
512             size += count;
513         }
514     }
515     
516     //-----------------------------------------------------------------------
517 /**
518      * Compares this Bag to another.
519      * This Bag equals another Bag if it contains the same number of occurrences of
520      * the same elements.
521      *
522      * @param object the Bag to compare to
523      * @return true if equal
524      */
525     public boolean equals(Object object) {
526         if (object == this) {
527             return true;
528         }
529         if (object instanceof Bag == false) {
530             return false;
531         }
532         Bag other = (Bag) object;
533         if (other.size() != size()) {
534             return false;
535         }
536         for (Iterator it = map.keySet().iterator(); it.hasNext();) {
537             Object element = it.next();
538             if (other.getCount(element) != getCount(element)) {
539                 return false;
540             }
541         }
542         return true;
543     }
544
545     /**
546      * Gets a hash code for the Bag compatible with the definition of equals.
547      * The hash code is defined as the sum total of a hash code for each element.
548      * The per element hash code is defined as
549      * <code>(e==null ? 0 : e.hashCode()) ^ noOccurances)</code>.
550      * This hash code is compatible with the Set interface.
551      *
552      * @return the hash code of the Bag
553      */
554     public int hashCode() {
555         int total = 0;
556         for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
557             Map.Entry entry = (Map.Entry ) it.next();
558             Object element = entry.getKey();
559             MutableInteger count = (MutableInteger) entry.getValue();
560             total += (element == null ? 0 : element.hashCode()) ^ count.value;
561         }
562         return total;
563     }
564
565     /**
566      * Implement a toString() method suitable for debugging.
567      *
568      * @return a debugging toString
569      */
570     public String toString() {
571         if (size() == 0) {
572             return "[]";
573         }
574         StringBuffer buf = new StringBuffer ();
575         buf.append('[');
576         Iterator it = uniqueSet().iterator();
577         while (it.hasNext()) {
578             Object current = it.next();
579             int count = getCount(current);
580             buf.append(count);
581             buf.append(':');
582             buf.append(current);
583             if (it.hasNext()) {
584                 buf.append(',');
585             }
586         }
587         buf.append(']');
588         return buf.toString();
589     }
590     
591 }
592

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags