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    }