DefaultMapBag


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;
17  
18  import java.util.ArrayList  ;
19  import java.util.Collection  ;
20  import java.util.ConcurrentModificationException  ;
21  import java.util.Iterator  ;
22  import java.util.List  ;
23  import java.util.Map  ;
24  import java.util.Set  ;
25  
26  import org.apache.commons.collections.set.UnmodifiableSet;
27  
28  /**
29   * A skeletal implementation of the {@link Bag}
30   * interface to minimize the effort required for target implementations.
31   * Subclasses need only to call <code>setMap(Map)</code> in their constructor 
32   * (or invoke the Map constructor) specifying a map instance that will be used
33   * to store the contents of the bag.
34   * <p>
35   * The map will be used to map bag elements to a number; the number represents
36   * the number of occurrences of that element in the bag.
37   *
38   * @deprecated Moved to bag subpackage as AbstractMapBag. Due to be removed in v4.0.
39   * @since Commons Collections 2.0
40   * @version $Revision: 1.17 $ $Date: 2004/02/18 01:15:42 $
41   * 
42   * @author Chuck Burdick
43   * @author Michael A. Smith
44   * @author Stephen Colebourne
45   * @author Janek Bogucki
46   */
47  public abstract class DefaultMapBag implements Bag {
48      private Map   _map = null;
49      private int _total = 0;
50      private int _mods = 0;
51  
52      /**
53       * No-argument constructor.  
54       * Subclasses should invoke <code>setMap(Map)</code> in
55       * their constructors.
56       */
57      public DefaultMapBag() {
58      }
59  
60      /**
61       * Constructor that assigns the specified Map as the backing store.
62       * The map must be empty.
63       * 
64       * @param map  the map to assign
65       */
66      protected DefaultMapBag(Map   map) {
67          setMap(map);
68      }
69  
70      /**
71       * Adds a new element to the bag by incrementing its count in the 
72       * underlying map.
73       *
74       * @param object  the object to add
75       * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
76       */
77      public boolean add(Object   object) {
78          return add(object, 1);
79      }
80  
81      /**
82       * Adds a new element to the bag by incrementing its count in the map.
83       *
84       * @param object  the object to search for
85       * @param nCopies  the number of copies to add
86       * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
87       */
88      public boolean add(Object   object, int nCopies) {
89          _mods++;
90          if (nCopies > 0) {
91              int count = (nCopies + getCount(object));
92              _map.put(object, new Integer  (count));
93              _total += nCopies;
94              return (count == nCopies);
95          } else {
96              return false;
97          }
98      }
99  
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.getCount(current);
159             result = result && contains;
160         }
161         return result;
162     }
163 
164     /**
165      * Returns true if the given object is not null, has the precise type 
166      * of this bag, and contains the same number of occurrences of all the
167      * same elements.
168      *
169      * @param object  the object to test for equality
170      * @return true if that object equals this bag
171      */
172     public boolean equals(Object   object) {
173         if (object == this) {
174             return true;
175         }
176         if (object instanceof Bag == false) {
177             return false;
178         }
179         Bag other = (Bag) object;
180         if (other.size() != size()) {
181             return false;
182         }
183         for (Iterator   it = _map.keySet().iterator(); it.hasNext();) {
184             Object   element = (Object  ) it.next();
185             if (other.getCount(element) != getCount(element)) {
186                 return false;
187             }
188         }
189         return true;
190     }
191 
192     /**
193      * Returns the hash code of the underlying map.
194      *
195      * @return the hash code of the underlying map
196      */
197     public int hashCode() {
198         return _map.hashCode();
199     }
200 
201     /**
202      * Returns true if the underlying map is empty.
203      *
204      * @return true if there are no elements in this bag
205      */
206     public boolean isEmpty() {
207         return _map.isEmpty();
208     }
209 
210     public Iterator   iterator() {
211         return new BagIterator(this, extractList().iterator());
212     }
213 
214     static class BagIterator implements Iterator   {
215         private DefaultMapBag _parent = null;
216         private Iterator   _support = null;
217         private Object   _current = null;
218         private int _mods = 0;
219 
220         public BagIterator(DefaultMapBag parent, Iterator   support) {
221             _parent = parent;
222             _support = support;
223             _current = null;
224             _mods = parent.modCount();
225         }
226 
227         public boolean hasNext() {
228             return _support.hasNext();
229         }
230 
231         public Object   next() {
232             if (_parent.modCount() != _mods) {
233                 throw new ConcurrentModificationException  ();
234             }
235             _current = _support.next();
236             return _current;
237         }
238 
239         public void remove() {
240             if (_parent.modCount() != _mods) {
241                 throw new ConcurrentModificationException  ();
242             }
243             _support.remove();
244             _parent.remove(_current, 1);
245             _mods++;
246         }
247     }
248 
249     public boolean remove(Object   object) {
250         return remove(object, getCount(object));
251     }
252 
253     public boolean remove(Object   object, int nCopies) {
254         _mods++;
255         boolean result = false;
256         int count = getCount(object);
257         if (nCopies <= 0) {
258             result = false;
259         } else if (count > nCopies) {
260             _map.put(object, new Integer  (count - nCopies));
261             result = true;
262             _total -= nCopies;
263         } else { // count > 0 && count <= i  
264             // need to remove all
265             result = (_map.remove(object) != null);
266             _total -= count;
267         }
268         return result;
269     }
270 
271     public boolean removeAll(Collection   coll) {
272         boolean result = false;
273         if (coll != null) {
274             Iterator   i = coll.iterator();
275             while (i.hasNext()) {
276                 boolean changed = remove(i.next(), 1);
277                 result = result || changed;
278             }
279         }
280         return result;
281     }
282 
283     /**
284      * Remove any members of the bag that are not in the given
285      * bag, respecting cardinality.
286      *
287      * @param coll  the collection to retain
288      * @return true if this call changed the collection
289      */
290     public boolean retainAll(Collection   coll) {
291         return retainAll(new HashBag(coll));
292     }
293 
294     /**
295      * Remove any members of the bag that are not in the given
296      * bag, respecting cardinality.
297      * @see #retainAll(Collection)
298      * 
299      * @param other  the bag to retain
300      * @return <code>true</code> if this call changed the collection
301      */
302     public boolean retainAll(Bag other) {
303         boolean result = false;
304         Bag excess = new HashBag();
305         Iterator   i = uniqueSet().iterator();
306         while (i.hasNext()) {
307             Object   current = i.next();
308             int myCount = getCount(current);
309             int otherCount = other.getCount(current);
310             if (1 <= otherCount && otherCount <= myCount) {
311                 excess.add(current, myCount - otherCount);
312             } else {
313                 excess.add(current, myCount);
314             }
315         }
316         if (!excess.isEmpty()) {
317             result = removeAll(excess);
318         }
319         return result;
320     }
321 
322     /**
323      * Returns an array of all of this bag's elements.
324      *
325      * @return an array of all of this bag's elements
326      */
327     public Object  [] toArray() {
328         return extractList().toArray();
329     }
330 
331     /**
332      * Returns an array of all of this bag's elements.
333      *
334      * @param array  the array to populate
335      * @return an array of all of this bag's elements
336      */
337     public Object  [] toArray(Object  [] array) {
338         return extractList().toArray(array);
339     }
340 
341     /**
342      * Returns the number of occurrence of the given element in this bag
343      * by looking up its count in the underlying map.
344      *
345      * @param object  the object to search for
346      * @return the number of occurrences of the object, zero if not found
347      */
348     public int getCount(Object   object) {
349         int result = 0;
350         Integer   count = MapUtils.getInteger(_map, object);
351         if (count != null) {
352             result = count.intValue();
353         }
354         return result;
355     }
356 
357     /**
358      * Returns an unmodifiable view of the underlying map's key set.
359      *
360      * @return the set of unique elements in this bag
361      */
362     public Set   uniqueSet() {
363         return UnmodifiableSet.decorate(_map.keySet());
364     }
365 
366     /**
367      * Returns the number of elements in this bag.
368      *
369      * @return the number of elements in this bag
370      */
371     public int size() {
372         return _total;
373     }
374 
375     /**
376      * Actually walks the bag to make sure the count is correct and
377      * resets the running total
378      * 
379      * @return the current total size
380      */
381     protected int calcTotalSize() {
382         _total = extractList().size();
383         return _total;
384     }
385 
386     /**
387      * Utility method for implementations to set the map that backs
388      * this bag. Not intended for interactive use outside of
389      * subclasses.
390      */
391     protected void setMap(Map   map) {
392         if (map == null || map.isEmpty() == false) {
393             throw new IllegalArgumentException  ("The map must be non-null and empty");
394         }
395         _map = map;
396     }
397 
398     /**
399      * Utility method for implementations to access the map that backs
400      * this bag. Not intended for interactive use outside of
401      * subclasses.
402      */
403     protected Map   getMap() {
404         return _map;
405     }
406 
407     /**
408      * Create a list for use in iteration, etc.
409      */
410     private List   extractList() {
411         List   result = new ArrayList  ();
412         Iterator   i = uniqueSet().iterator();
413         while (i.hasNext()) {
414             Object   current = i.next();
415             for (int index = getCount(current); index > 0; index--) {
416                 result.add(current);
417             }
418         }
419         return result;
420     }
421 
422     /**
423      * Return number of modifications for iterator.
424      * 
425      * @return the modification count
426      */
427     private int modCount() {
428         return _mods;
429     }
430 
431     /**
432      * Implement a toString() method suitable for debugging.
433      * 
434      * @return a debugging toString
435      */
436     public String   toString() {
437         StringBuffer   buf = new StringBuffer  ();
438         buf.append("[");
439         Iterator   i = uniqueSet().iterator();
440         while (i.hasNext()) {
441             Object   current = i.next();
442             int count = getCount(current);
443             buf.append(count);
444             buf.append(":");
445             buf.append(current);
446             if (i.hasNext()) {
447                 buf.append(",");
448             }
449         }
450         buf.append("]");
451         return buf.toString();
452     }
453     
454 }
455
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags