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.bag;
018    
019    import java.io.IOException;
020    import java.io.ObjectInputStream;
021    import java.io.ObjectOutputStream;
022    import java.lang.reflect.Array;
023    import java.util.Collection;
024    import java.util.ConcurrentModificationException;
025    import java.util.Iterator;
026    import java.util.Map;
027    import java.util.Set;
028    
029    import org.apache.commons.collections.Bag;
030    import org.apache.commons.collections.set.UnmodifiableSet;
031    
032    /**
033     * Abstract implementation of the {@link Bag} interface to simplify the creation
034     * of subclass implementations.
035     * <p>
036     * Subclasses specify a Map implementation to use as the internal storage.
037     * The map will be used to map bag elements to a number; the number represents
038     * the number of occurrences of that element in the bag.
039     *
040     * @since Commons Collections 3.0 (previously DefaultMapBag v2.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     * @author Steve Clark
048     */
049    public abstract class AbstractMapBag implements Bag {
050        
051        /** The map to use to store the data */
052        private transient Map map;
053        /** The current total size of the bag */
054        private int size;
055        /** The modification count for fail fast iterators */
056        private transient int modCount;
057        /** The modification count for fail fast iterators */
058        private transient Set uniqueSet;
059    
060        /**
061         * Constructor needed for subclass serialisation.
062         * 
063         */
064        protected AbstractMapBag() {
065            super();
066        }
067    
068        /**
069         * Constructor that assigns the specified Map as the backing store.
070         * The map must be empty and non-null.
071         * 
072         * @param map  the map to assign
073         */
074        protected AbstractMapBag(Map map) {
075            super();
076            this.map = map;
077        }
078    
079        /**
080         * Utility method for implementations to access the map that backs
081         * this bag. Not intended for interactive use outside of subclasses.
082         * 
083         * @return the map being used by the Bag
084         */
085        protected Map getMap() {
086            return map;
087        }
088    
089        //-----------------------------------------------------------------------
090        /**
091         * Returns the number of elements in this bag.
092         *
093         * @return current size of the bag
094         */
095        public int size() {
096            return size;
097        }
098    
099        /**
100         * Returns true if the underlying map is empty.
101         *
102         * @return true if bag is empty
103         */
104        public boolean isEmpty() {
105            return map.isEmpty();
106        }
107    
108        /**
109         * Returns the number of occurrence of the given element in this bag
110         * by looking up its count in the underlying map.
111         *
112         * @param object  the object to search for
113         * @return the number of occurrences of the object, zero if not found
114         */
115        public int getCount(Object object) {
116            MutableInteger count = (MutableInteger) map.get(object);
117            if (count != null) {
118                return count.value;
119            }
120            return 0;
121        }
122    
123        //-----------------------------------------------------------------------
124        /**
125         * Determines if the bag contains the given element by checking if the
126         * underlying map contains the element as a key.
127         *
128         * @param object  the object to search for
129         * @return true if the bag contains the given element
130         */
131        public boolean contains(Object object) {
132            return map.containsKey(object);
133        }
134    
135        /**
136         * Determines if the bag contains the given elements.
137         * 
138         * @param coll  the collection to check against
139         * @return <code>true</code> if the Bag contains all the collection
140         */
141        public boolean containsAll(Collection coll) {
142            if (coll instanceof Bag) {
143                return containsAll((Bag) coll);
144            }
145            return containsAll(new HashBag(coll));
146        }
147    
148        /**
149         * Returns <code>true</code> if the bag contains all elements in
150         * the given collection, respecting cardinality.
151         * 
152         * @param other  the bag to check against
153         * @return <code>true</code> if the Bag contains all the collection
154         */
155        boolean containsAll(Bag other) {
156            boolean result = true;
157            Iterator it = other.uniqueSet().iterator();
158            while (it.hasNext()) {
159                Object current = it.next();
160                boolean contains = getCount(current) >= other.getCount(current);
161                result = result && contains;
162            }
163            return result;
164        }
165    
166        //-----------------------------------------------------------------------
167        /**
168         * Gets an iterator over the bag elements.
169         * Elements present in the Bag more than once will be returned repeatedly.
170         * 
171         * @return the iterator
172         */
173        public Iterator iterator() {
174            return new BagIterator(this);
175        }
176    
177        /**
178         * Inner class iterator for the Bag.
179         */
180        static class BagIterator implements Iterator {
181            private AbstractMapBag parent;
182            private Iterator entryIterator;
183            private Map.Entry current;
184            private int itemCount;
185            private final int mods;
186            private boolean canRemove;
187    
188            /**
189             * Constructor.
190             * 
191             * @param parent  the parent bag
192             */
193            public BagIterator(AbstractMapBag parent) {
194                this.parent = parent;
195                this.entryIterator = parent.map.entrySet().iterator();
196                this.current = null;
197                this.mods = parent.modCount;
198                this.canRemove = false;
199            }
200    
201            public boolean hasNext() {
202                return (itemCount > 0 || entryIterator.hasNext());
203            }
204    
205            public Object next() {
206                if (parent.modCount != mods) {
207                    throw new ConcurrentModificationException();
208                }
209                if (itemCount == 0) {
210                    current = (Map.Entry) entryIterator.next();
211                    itemCount = ((MutableInteger) current.getValue()).value;
212                }
213                canRemove = true;
214                itemCount--;
215                return current.getKey();
216            }
217    
218            public void remove() {
219                if (parent.modCount != mods) {
220                    throw new ConcurrentModificationException();
221                }
222                if (canRemove == false) {
223                    throw new IllegalStateException();
224                }
225                MutableInteger mut = (MutableInteger) current.getValue();
226                if (mut.value > 1) {
227                    mut.value--;
228                } else {
229                    entryIterator.remove();
230                }
231                parent.size--;
232                canRemove = false;
233            }
234        }
235    
236        //-----------------------------------------------------------------------
237        /**
238         * Adds a new element to the bag, incrementing its count in the underlying map.
239         *
240         * @param object  the object to add
241         * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
242         */
243        public boolean add(Object object) {
244            return add(object, 1);
245        }
246    
247        /**
248         * Adds a new element to the bag, incrementing its count in the map.
249         *
250         * @param object  the object to search for
251         * @param nCopies  the number of copies to add
252         * @return <code>true</code> if the object was not already in the <code>uniqueSet</code>
253         */
254        public boolean add(Object object, int nCopies) {
255            modCount++;
256            if (nCopies > 0) {
257                MutableInteger mut = (MutableInteger) map.get(object);
258                size += nCopies;
259                if (mut == null) {
260                    map.put(object, new MutableInteger(nCopies));
261                    return true;
262                } else {
263                    mut.value += nCopies;
264                    return false;
265                }
266            } else {
267                return false;
268            }
269        }
270    
271        /**
272         * Invokes {@link #add(Object)} for each element in the given collection.
273         *
274         * @param coll  the collection to add
275         * @return <code>true</code> if this call changed the bag
276         */
277        public boolean addAll(Collection coll) {
278            boolean changed = false;
279            Iterator i = coll.iterator();
280            while (i.hasNext()) {
281                boolean added = add(i.next());
282                changed = changed || added;
283            }
284            return changed;
285        }
286    
287        //-----------------------------------------------------------------------
288        /**
289         * Clears the bag by clearing the underlying map.
290         */
291        public void clear() {
292            modCount++;
293            map.clear();
294            size = 0;
295        }
296    
297        /**
298         * Removes all copies of the specified object from the bag.
299         * 
300         * @param object  the object to remove
301         * @return true if the bag changed
302         */
303        public boolean remove(Object object) {
304            MutableInteger mut = (MutableInteger) map.get(object);
305            if (mut == null) {
306                return false;
307            }
308            modCount++;
309            map.remove(object);
310            size -= mut.value;
311            return true;
312        }
313    
314        /**
315         * Removes a specified number of copies of an object from the bag.
316         * 
317         * @param object  the object to remove
318         * @param nCopies  the number of copies to remove
319         * @return true if the bag changed
320         */
321        public boolean remove(Object object, int nCopies) {
322            MutableInteger mut = (MutableInteger) map.get(object);
323            if (mut == null) {
324                return false;
325            }
326            if (nCopies <= 0) {
327                return false;
328            }
329            modCount++;
330            if (nCopies < mut.value) {
331                mut.value -= nCopies;
332                size -= nCopies;
333            } else {
334                map.remove(object);
335                size -= mut.value;
336            }
337            return true;
338        }
339    
340        /**
341         * Removes objects from the bag according to their count in the specified collection.
342         * 
343         * @param coll  the collection to use
344         * @return true if the bag changed
345         */
346        public boolean removeAll(Collection coll) {
347            boolean result = false;
348            if (coll != null) {
349                Iterator i = coll.iterator();
350                while (i.hasNext()) {
351                    boolean changed = remove(i.next(), 1);
352                    result = result || changed;
353                }
354            }
355            return result;
356        }
357    
358        /**
359         * Remove any members of the bag that are not in the given
360         * bag, respecting cardinality.
361         *
362         * @param coll  the collection to retain
363         * @return true if this call changed the collection
364         */
365        public boolean retainAll(Collection coll) {
366            if (coll instanceof Bag) {
367                return retainAll((Bag) coll);
368            }
369            return retainAll(new HashBag(coll));
370        }
371    
372        /**
373         * Remove any members of the bag that are not in the given
374         * bag, respecting cardinality.
375         * @see #retainAll(Collection)
376         * 
377         * @param other  the bag to retain
378         * @return <code>true</code> if this call changed the collection
379         */
380        boolean retainAll(Bag other) {
381            boolean result = false;
382            Bag excess = new HashBag();
383            Iterator i = uniqueSet().iterator();
384            while (i.hasNext()) {
385                Object current = i.next();
386                int myCount = getCount(current);
387                int otherCount = other.getCount(current);
388                if (1 <= otherCount && otherCount <= myCount) {
389                    excess.add(current, myCount - otherCount);
390                } else {
391                    excess.add(current, myCount);
392                }
393            }
394            if (!excess.isEmpty()) {
395                result = removeAll(excess);
396            }
397            return result;
398        }
399    
400        //-----------------------------------------------------------------------
401        /**
402         * Mutable integer class for storing the data.
403         */
404        protected static class MutableInteger {
405            /** The value of this mutable. */
406            protected int value;
407            
408            /**
409             * Constructor.
410             * @param value  the initial value
411             */
412            MutableInteger(int value) {
413                this.value = value;
414            }
415            
416            public boolean equals(Object obj) {
417                if (obj instanceof MutableInteger == false) {
418                    return false;
419                }
420                return ((MutableInteger) obj).value == value;
421            }
422    
423            public int hashCode() {
424                return value;
425            }
426        }
427        
428        //-----------------------------------------------------------------------
429        /**
430         * Returns an array of all of this bag's elements.
431         *
432         * @return an array of all of this bag's elements
433         */
434        public Object[] toArray() {
435            Object[] result = new Object[size()];
436            int i = 0;
437            Iterator it = map.keySet().iterator();
438            while (it.hasNext()) {
439                Object current = it.next();
440                for (int index = getCount(current); index > 0; index--) {
441                    result[i++] = current;
442                }
443            }
444            return result;
445        }
446    
447        /**
448         * Returns an array of all of this bag's elements.
449         *
450         * @param array  the array to populate
451         * @return an array of all of this bag's elements
452         */
453        public Object[] toArray(Object[] array) {
454            int size = size();
455            if (array.length < size) {
456                array = (Object[]) Array.newInstance(array.getClass().getComponentType(), size);
457            }
458    
459            int i = 0;
460            Iterator it = map.keySet().iterator();
461            while (it.hasNext()) {
462                Object current = it.next();
463                for (int index = getCount(current); index > 0; index--) {
464                    array[i++] = current;
465                }
466            }
467            if (array.length > size) {
468                array[size] = null;
469            }
470            return array;
471        }
472    
473        /**
474         * Returns an unmodifiable view of the underlying map's key set.
475         *
476         * @return the set of unique elements in this bag
477         */
478        public Set uniqueSet() {
479            if (uniqueSet == null) {
480                uniqueSet = UnmodifiableSet.decorate(map.keySet());
481            }
482            return uniqueSet;
483        }
484    
485        //-----------------------------------------------------------------------
486        /**
487         * Write the map out using a custom routine.
488         * @param out  the output stream
489         * @throws IOException
490         */
491        protected void doWriteObject(ObjectOutputStream out) throws IOException {
492            out.writeInt(map.size());
493            for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
494                Map.Entry entry = (Map.Entry) it.next();
495                out.writeObject(entry.getKey());
496                out.writeInt(((MutableInteger) entry.getValue()).value);
497            }
498        }
499    
500        /**
501         * Read the map in using a custom routine.
502         * @param map  the map to use
503         * @param in  the input stream
504         * @throws IOException
505         * @throws ClassNotFoundException
506         */
507        protected void doReadObject(Map map, ObjectInputStream in) throws IOException, ClassNotFoundException {
508            this.map = map;
509            int entrySize = in.readInt();
510            for (int i = 0; i < entrySize; i++) {
511                Object obj = in.readObject();
512                int count = in.readInt();
513                map.put(obj, new MutableInteger(count));
514                size += count;
515            }
516        }
517        
518        //-----------------------------------------------------------------------
519        /**
520         * Compares this Bag to another.
521         * This Bag equals another Bag if it contains the same number of occurrences of
522         * the same elements.
523         * 
524         * @param object  the Bag to compare to
525         * @return true if equal
526         */
527        public boolean equals(Object object) {
528            if (object == this) {
529                return true;
530            }
531            if (object instanceof Bag == false) {
532                return false;
533            }
534            Bag other = (Bag) object;
535            if (other.size() != size()) {
536                return false;
537            }
538            for (Iterator it = map.keySet().iterator(); it.hasNext();) {
539                Object element = it.next();
540                if (other.getCount(element) != getCount(element)) {
541                    return false;
542                }
543            }
544            return true;
545        }
546    
547        /**
548         * Gets a hash code for the Bag compatible with the definition of equals.
549         * The hash code is defined as the sum total of a hash code for each element.
550         * The per element hash code is defined as
551         * <code>(e==null ? 0 : e.hashCode()) ^ noOccurances)</code>.
552         * This hash code is compatible with the Set interface.
553         * 
554         * @return the hash code of the Bag
555         */
556        public int hashCode() {
557            int total = 0;
558            for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
559                Map.Entry entry = (Map.Entry) it.next();
560                Object element = entry.getKey();
561                MutableInteger count = (MutableInteger) entry.getValue();
562                total += (element == null ? 0 : element.hashCode()) ^ count.value;
563            }
564            return total;
565        }
566    
567        /**
568         * Implement a toString() method suitable for debugging.
569         * 
570         * @return a debugging toString
571         */
572        public String toString() {
573            if (size() == 0) {
574                return "[]";
575            }
576            StringBuffer buf = new StringBuffer();
577            buf.append('[');
578            Iterator it = uniqueSet().iterator();
579            while (it.hasNext()) {
580                Object current = it.next();
581                int count = getCount(current);
582                buf.append(count);
583                buf.append(':');
584                buf.append(current);
585                if (it.hasNext()) {
586                    buf.append(',');
587                }
588            }
589            buf.append(']');
590            return buf.toString();
591        }
592        
593    }