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