HashBag


1   // Copyright (c) 2003-2007, Jodd Team (jodd.sf.net). All Rights Reserved.
2   
3   package jodd.util.collection;
4   
5   import jodd.mutable.MutableInteger;
6   
7   import java.lang.reflect.Array  ;
8   import java.util.*;
9   
10  /**
11   * HashBag implementation of a {@link Bag}
12   */
13  public class HashBag implements Bag {
14  
15      protected transient Map map;                    // map for storing data
16      protected int size;                             // current bag size
17      private transient int modCount;                 // modification count for fail fast iterators
18  
19      public HashBag() {
20          super();
21          map = new HashMap();
22      }
23  
24      public HashBag(Collection coll) {
25          this();
26          addAll(coll);
27      }
28  
29      // ---------------------------------------------------------------- size
30      /**
31       * Returns the number of elements in the bag.
32       */
33      public int size() {
34          return size;
35      }
36  
37      /**
38       * Returns <code>true</code> if bag is empty.
39       */
40      public boolean isEmpty() {
41          return map.isEmpty();
42      }
43  
44      /**
45       * Returns the number of occurrence of the given element in bag.
46       */
47      public int getCount(Object   object) {
48          MutableInteger count = (MutableInteger) map.get(object);
49          if (count != null) {
50              return count.value;
51          }
52          return 0;
53      }
54  
55      // ---------------------------------------------------------------- contains
56  
57      /**
58       * Determines if the bag contains the given element.
59  
60       * @return <code>true</code> if the bag contains the given element
61       */
62      public boolean contains(Object   object) {
63          return map.containsKey(object);
64      }
65  
66      /**
67       * Determines if the bag contains all the collection elements..
68  
69       * @return <code>true</code> if the Bag contains all the collection elements
70       */
71      public boolean containsAll(Collection coll) {
72          if (coll instanceof Bag) {
73              return containsAll((Bag) coll);
74          }
75          return containsAll(new HashBag(coll));
76      }
77  
78      /**
79       * Returns <code>true</code> if the bag contains all elements in
80       * the given bag, respecting cardinality.
81  
82       * @return <code>true</code> if the Bag contains all the bag elements
83       */
84      boolean containsAll(Bag other) {
85          boolean result = true;
86          Iterator it = other.uniqueSet().iterator();
87          while (it.hasNext()) {
88              Object   current = it.next();
89              boolean contains = getCount(current) >= other.getCount(current);
90              result = result && contains;
91          }
92          return result;
93      }
94  
95      // ---------------------------------------------------------------- iterator
96  
97      /**
98       * Returns an iterator over the bag elements.
99       * Elements present in the Bag more than once will be returned repeatedly.
100      */
101     public Iterator iterator() {
102         return new BagIterator(this);
103     }
104 
105     /**
106      * Inner class iterator for the Bag.
107      */
108     static class BagIterator implements Iterator {
109         private HashBag parent;
110         private Iterator entryIterator;
111         private Map.Entry current;
112         private int itemCount;
113         private final int mods;
114         private boolean canRemove;
115 
116         BagIterator(HashBag parent) {
117             this.parent = parent;
118             this.entryIterator = parent.map.entrySet().iterator();
119             this.current = null;
120             this.mods = parent.modCount;
121             this.canRemove = false;
122         }
123 
124         public boolean hasNext() {
125             return (itemCount > 0 || entryIterator.hasNext());
126         }
127 
128         public Object   next() {
129             if (parent.modCount != mods) {
130                 throw new ConcurrentModificationException();
131             }
132             if (itemCount == 0) {
133                 current = (Map.Entry) entryIterator.next();
134                 itemCount = ((MutableInteger) current.getValue()).value;
135             }
136             canRemove = true;
137             itemCount--;
138             return current.getKey();
139         }
140 
141         public void remove() {
142             if (parent.modCount != mods) {
143                 throw new ConcurrentModificationException();
144             }
145             if (canRemove == false) {
146                 throw new IllegalStateException  ();
147             }
148             MutableInteger mut = (MutableInteger) current.getValue();
149             if (mut.value > 1) {
150                 mut.value--;
151             } else {
152                 entryIterator.remove();
153             }
154             parent.size--;
155             canRemove = false;
156         }
157     }
158 
159     // ---------------------------------------------------------------- add
160     /**
161      * Adds a new element to the bag, incrementing its count in the underlying map.
162 
163      * @return <code>true</code> if the object was not already in the bag
164      */
165     public boolean add(Object   object) {
166         return add(object, 1);
167     }
168 
169     /**
170      * Adds a new element to the bag, incrementing its count in the map.
171 
172      * @return <code>true</code> if the object was not already in the bag
173      */
174     public boolean add(Object   object, int copies) {
175         if (copies <= 0) {
176             throw new IllegalArgumentException  ("Invalid number of bag element copies (" + copies + ")");
177         }
178         modCount++;
179         MutableInteger mut = (MutableInteger) map.get(object);
180         size += copies;
181         if (mut == null) {
182             map.put(object, new MutableInteger(copies));
183             return true;
184         } else {
185             mut.value += copies;
186             return false;
187         }
188     }
189 
190     /**
191      * Invokes {@link #add(Object)} for each element in the given collection.
192      *
193      * @return <code>true</code> if this call changed the bag
194      */
195     public boolean addAll(Collection coll) {
196         boolean changed = false;
197         Iterator i = coll.iterator();
198         while (i.hasNext()) {
199             boolean added = add(i.next());
200             changed = changed || added;
201         }
202         return changed;
203     }
204 
205     // ---------------------------------------------------------------- remove
206 
207     /**
208      * Clears the bag by clearing the underlying map.
209      */
210     public void clear() {
211         if (size == 0) {
212             return;
213         }
214         modCount++;
215         map.clear();
216         size = 0;
217     }
218 
219     /**
220      * Removes all copies of the specified object from the bag.
221      *
222      * @return <code>true</code> if the bag changed
223      */
224     public boolean remove(Object   object) {
225         MutableInteger mut = (MutableInteger) map.get(object);
226         if (mut == null) {
227             return false;
228         }
229         modCount++;
230         map.remove(object);
231         size -= mut.value;
232         return true;
233     }
234 
235     /**
236      * Removes a specified number of copies of an object from the bag.
237      *
238      * @return <code>true</code> if the bag changed
239      */
240     public boolean remove(Object   object, int copies) {
241         if (copies <= 0) {
242             throw new IllegalArgumentException  ("Invalid number of bag element copies (" + copies + ")");
243         }
244         MutableInteger mut = (MutableInteger) map.get(object);
245         if (mut == null) {
246             return false;
247         }
248         modCount++;
249         if (copies < mut.value) {
250             mut.value -= copies;
251             size -= copies;
252         } else {
253             map.remove(object);
254             size -= mut.value;
255         }
256         return true;
257     }
258 
259     /**
260      * Removes objects from the bag according to their count in the specified collection.
261      * @return <code>true</code> if the bag changed
262      */
263     public boolean removeAll(Collection coll) {
264         boolean result = false;
265         if (coll != null) {
266             Iterator i = coll.iterator();
267             while (i.hasNext()) {
268                 boolean changed = remove(i.next(), 1);
269                 result = result || changed;
270             }
271         }
272         return result;
273     }
274 
275 
276     // ---------------------------------------------------------------- retain
277 
278     /**
279      * Remove any members of the bag that are not in the given
280      * bag, respecting cardinality.
281      *
282      * @return <code>true</code> if this call changed the collection
283      */
284     public boolean retainAll(Collection coll) {
285         if (coll instanceof Bag) {
286             return retainAll((Bag) coll);
287         }
288         return retainAll(new HashBag(coll));
289     }
290 
291     /**
292      * Remove any members of the bag that are not in the given
293      * bag, respecting cardinality.
294      *
295      * @return <code>true</code> if this call changed the collection
296      */
297     boolean retainAll(Bag other) {
298         boolean result = false;
299         Bag excess = new HashBag();
300         Iterator it = map.keySet().iterator();
301         while (it.hasNext()) {
302             Object   current = it.next();
303             int myCount = getCount(current);
304             int otherCount = other.getCount(current);
305             if (1 <= otherCount && otherCount <= myCount) {
306                 excess.add(current, myCount - otherCount);
307             } else {
308                 excess.add(current, myCount);
309             }
310         }
311         if (!excess.isEmpty()) {
312             result = removeAll(excess);
313         }
314         return result;
315     }
316 
317 
318 
319     // ---------------------------------------------------------------- convert
320 
321     public Set uniqueSet() {
322         return map.keySet();
323     }
324 
325     /**
326      * Returns an array of all of bag's elements.
327      */
328     public Object  [] toArray() {
329         Object  [] result = new Object  [size()];
330         int i = 0;
331         Iterator it = map.keySet().iterator();
332         while (it.hasNext()) {
333             Object   current = it.next();
334             for (int index = getCount(current); index > 0; index--) {
335                 result[i++] = current;
336             }
337         }
338         return result;
339     }
340 
341     /**
342      * Populates an array with all of this bag's elements.
343      */
344     public Object  [] toArray(Object  [] array) {
345         int size = size();
346         if (array.length < size) {
347             array = (Object  []) Array.newInstance(array.getClass().getComponentType(), size);
348         }
349 
350         int i = 0;
351         Iterator it = map.keySet().iterator();
352         while (it.hasNext()) {
353             Object   current = it.next();
354             for (int index = getCount(current); index > 0; index--) {
355                 array[i++] = current;
356             }
357         }
358         while (array.length > size) {
359             array[size] = null;
360             size++;
361         }
362         return array;
363     }
364 
365     //-----------------------------------------------------------------------
366 
367     /**
368      * Compares bag to another.
369      * This Bag equals another Bag if it contains the same number of occurrences of
370      * the same elements.
371 
372      * @return <code>true</code> if equal
373      */
374     public boolean equals(Object   object) {
375         if (object == this) {
376             return true;
377         }
378         if (object instanceof Bag == false) {
379             return false;
380         }
381         Bag other = (Bag) object;
382         if (other.size() != size()) {
383             return false;
384         }
385         Iterator it = map.keySet().iterator();
386         while (it.hasNext()) {
387             Object   element = it.next();
388             if (other.getCount(element) != getCount(element)) {
389                 return false;
390             }
391         }
392         return true;
393     }
394 
395     /**
396      * Gets a hash code for the Bag compatible with the definition of equals.
397      * The hash code is defined as the sum total of a hash code for each element.
398      * The per element hash code is defined as
399      * <code>(e==null ? 0 : e.hashCode()) ^ noOccurances)</code>.
400      * This hash code is compatible with the Set interface.
401      */
402     public int hashCode() {
403         int total = 0;
404         for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
405             Map.Entry entry = (Map.Entry) it.next();
406             Object   element = entry.getKey();
407             MutableInteger count = (MutableInteger) entry.getValue();
408             total += (element == null ? 0 : element.hashCode()) ^ count.value;
409         }
410         return total;
411     }
412 
413     /**
414      * Implement a toString() method suitable for debugging.
415      */
416     public String   toString() {
417         if (size() == 0) {
418             return "[]";
419         }
420         StringBuffer   buf = new StringBuffer  ();
421         buf.append('[');
422         Iterator it = uniqueSet().iterator();
423         while (it.hasNext()) {
424             Object   current = it.next();
425             int count = getCount(current);
426             buf.append(count);
427             buf.append(':');
428             buf.append(current);
429             if (it.hasNext()) {
430                 buf.append(',');
431             }
432         }
433         buf.append(']');
434         return buf.toString();
435     }
436 
437 }
438
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags