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