    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 serialisation.
    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     * Read the map in using a custom routine.
    287     * @param map the map to use
    288     * @param in the input stream
    289     * @throws IOException any of the usual I/O related exceptions
    290     * @throws ClassNotFoundException if the stream contains an object which class cannot be loaded
    291     * @throws ClassCastException if the stream does not contain the correct objects
    292     */
    293    protected void doReadObject(final Map<E, MutableInteger> map, final ObjectInputStream in)
    294            throws IOException, ClassNotFoundException {
    295        this.map = map;
    296        final int entrySize = in.readInt();
    297        for (int i = 0; i < entrySize; i++) {
    298            @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
    299            final E obj = (E) in.readObject();
    300            final int count = in.readInt();
    301            map.put(obj, new MutableInteger(count));
    302            size += count;
    303        }
    304    }
    305
    306    /**
    307     * Write the map out using a custom routine.
    308     * @param out the output stream
    309     * @throws IOException any of the usual I/O related exceptions
    310     */
    311    protected void doWriteObject(final ObjectOutputStream out) throws IOException {
    312        out.writeInt(map.size());
    313        for (final Entry<E, MutableInteger> entry : map.entrySet()) {
    314            out.writeObject(entry.getKey());
    315            out.writeInt(entry.getValue().value);
    316        }
    317    }
    318
    319    /**
    320     * Compares this Bag to another. This Bag equals another Bag if it contains
    321     * the same number of occurrences of the same elements.
    322     *
    323     * @param object the Bag to compare to
    324     * @return true if equal
    325     */
    326    @Override
    327    public boolean equals(final Object object) {
    328        if (object == this) {
    329            return true;
    330        }
    331        if (!(object instanceof Bag)) {
    332            return false;
    333        }
    334        final Bag<?> other = (Bag<?>) object;
    335        if (other.size() != size()) {
    336            return false;
    337        }
    338        for (final E element : map.keySet()) {
    339            if (other.getCount(element) != getCount(element)) {
    340                return false;
    341            }
    342        }
    343        return true;
    344    }
    345
    346    /**
    347     * Returns the number of occurrence of the given element in this bag by
    348     * looking up its count in the underlying map.
    349     *
    350     * @param object the object to search for
    351     * @return the number of occurrences of the object, zero if not found
    352     */
    353    @Override
    354    public int getCount(final Object object) {
    355        final MutableInteger count = map.get(object);
    356        if (count != null) {
    357            return count.value;
    358        }
    359        return 0;
    360    }
    361
    362    /**
    363     * Utility method for implementations to access the map that backs this bag.
    364     * Not intended for interactive use outside of subclasses.
    365     *
    366     * @return the map being used by the Bag
    367     */
    368    protected Map<E, MutableInteger> getMap() {
    369        return map;
    370    }
    371
    372    /**
    373     * Gets a hash code for the Bag compatible with the definition of equals.
    374     * The hash code is defined as the sum total of a hash code for each
    375     * element. The per element hash code is defined as
    376     * {@code (e==null ? 0 : e.hashCode()) ^ noOccurrences)}. This hash code
    377     * is compatible with the Set interface.
    378     *
    379     * @return the hash code of the Bag
    380     */
    381    @Override
    382    public int hashCode() {
    383        int total = 0;
    384        for (final Entry<E, MutableInteger> entry : map.entrySet()) {
    385            final E element = entry.getKey();
    386            final MutableInteger count = entry.getValue();
    387            total += (element == null ? 0 : element.hashCode()) ^ count.value;
    388        }
    389        return total;
    390    }
    391
    392    /**
    393     * Returns true if the underlying map is empty.
    394     *
    395     * @return true if bag is empty
    396     */
    397    @Override
    398    public boolean isEmpty() {
    399        return map.isEmpty();
    400    }
    401
    402    /**
    403     * Gets an iterator over the bag elements. Elements present in the Bag more
    404     * than once will be returned repeatedly.
    405     *
    406     * @return the iterator
    407     */
    408    @Override
    409    public Iterator<E> iterator() {
    410        return new BagIterator<>(this);
    411    }
    412
    413    /**
    414     * Removes all copies of the specified object from the bag.
    415     *
    416     * @param object the object to remove
    417     * @return true if the bag changed
    418     */
    419    @Override
    420    public boolean remove(final Object object) {
    421        final MutableInteger mut = map.get(object);
    422        if (mut == null) {
    423            return false;
    424        }
    425        modCount++;
    426        map.remove(object);
    427        size -= mut.value;
    428        return true;
    429    }
    430
    431    /**
    432     * Removes a specified number of copies of an object from the bag.
    433     *
    434     * @param object the object to remove
    435     * @param nCopies the number of copies to remove
    436     * @return true if the bag changed
    437     */
    438    @Override
    439    public boolean remove(final Object object, final int nCopies) {
    440        final MutableInteger mut = map.get(object);
    441        if (mut == null) {
    442            return false;
    443        }
    444        if (nCopies <= 0) {
    445            return false;
    446        }
    447        modCount++;
    448        if (nCopies < mut.value) {
    449            mut.value -= nCopies;
    450            size -= nCopies;
    451        } else {
    452            map.remove(object);
    453            size -= mut.value;
    454        }
    455        return true;
    456    }
    457
    458    /**
    459     * Removes objects from the bag according to their count in the specified
    460     * collection.
    461     *
    462     * @param coll the collection to use
    463     * @return true if the bag changed
    464     */
    465    @Override
    466    public boolean removeAll(final Collection<?> coll) {
    467        boolean result = false;
    468        if (coll != null) {
    469            for (final Object current : coll) {
    470                final boolean changed = remove(current, 1);
    471                result = result || changed;
    472            }
    473        }
    474        return result;
    475    }
    476
    477    /**
    478     * Remove any members of the bag that are not in the given bag, respecting
    479     * cardinality.
    480     * @see #retainAll(Collection)
    481     * @param other the bag to retain
    482     * @return {@code true} if this call changed the collection
    483     */
    484    boolean retainAll(final Bag<?> other) {
    485        boolean result = false;
    486        final Bag<E> excess = new HashBag<>();
    487        for (final E current : uniqueSet()) {
    488            final int myCount = getCount(current);
    489            final int otherCount = other.getCount(current);
    490            if (1 <= otherCount && otherCount <= myCount) {
    491                excess.add(current, myCount - otherCount);
    492            } else {
    493                excess.add(current, myCount);
    494            }
    495        }
    496        if (!excess.isEmpty()) {
    497            result = removeAll(excess);
    498        }
    499        return result;
    500    }
    501
    502    /**
    503     * Remove any members of the bag that are not in the given bag, respecting
    504     * cardinality.
    505     *
    506     * @param coll the collection to retain
    507     * @return true if this call changed the collection
    508     */
    509    @Override
    510    public boolean retainAll(final Collection<?> coll) {
    511        if (coll instanceof Bag) {
    512            return retainAll((Bag<?>) coll);
    513        }
    514        return retainAll(new HashBag<>(coll));
    515    }
    516
    517    /**
    518     * Returns the number of elements in this bag.
    519     *
    520     * @return current size of the bag
    521     */
    522    @Override
    523    public int size() {
    524        return size;
    525    }
    526
    527    /**
    528     * Returns an array of all of this bag's elements.
    529     *
    530     * @return an array of all of this bag's elements
    531     */
    532    @Override
    533    public Object[] toArray() {
    534        final Object[] result = new Object[size()];
    535        int i = 0;
    536        for (final E current : map.keySet()) {
    537            for (int index = getCount(current); index > 0; index--) {
    538                result[i++] = current;
    539            }
    540        }
    541        return result;
    542    }
    543
    544    /**
    545     * Returns an array of all of this bag's elements.
    546     * If the input array has more elements than are in the bag,
    547     * trailing elements will be set to null.
    548     *
    549     * @param <T> the type of the array elements
    550     * @param array the array to populate
    551     * @return an array of all of this bag's elements
    552     * @throws ArrayStoreException if the runtime type of the specified array is not
    553     *   a supertype of the runtime type of the elements in this list
    554     * @throws NullPointerException if the specified array is null
    555     */
    556    @Override
    557    public <T> T[] toArray(T[] array) {
    558        final int size = size();
    559        if (array.length < size) {
    560            @SuppressWarnings("unchecked") // safe as both are of type T
    561            final T[] unchecked = (T[]) Array.newInstance(array.getClass().getComponentType(), size);
    562            array = unchecked;
    563        }
    564
    565        int i = 0;
    566        for (final E current : map.keySet()) {
    567            for (int index = getCount(current); index > 0; index--) {
    568                // unsafe, will throw ArrayStoreException if types are not compatible, see Javadoc
    569                @SuppressWarnings("unchecked")
    570                final T unchecked = (T) current;
    571                array[i++] = unchecked;
    572            }
    573        }
    574        while (i < array.length) {
    575            array[i++] = null;
    576        }
    577        return array;
    578    }
    579
    580    /**
    581     * Implement a toString() method suitable for debugging.
    582     *
    583     * @return a debugging toString
    584     */
    585    @Override
    586    public String toString() {
    587        if (isEmpty()) {
    588            return "[]";
    589        }
    590        final StringBuilder buf = new StringBuilder();
    591        buf.append(CollectionUtils.DEFAULT_TOSTRING_PREFIX);
    592        final Iterator<E> it = uniqueSet().iterator();
    593        while (it.hasNext()) {
    594            final Object current = it.next();
    595            final int count = getCount(current);
    596            buf.append(count);
    597            buf.append(CollectionUtils.COLON);
    598            buf.append(current);
    599            if (it.hasNext()) {
    600                buf.append(CollectionUtils.COMMA);
    601            }
    602        }
    603        buf.append(CollectionUtils.DEFAULT_TOSTRING_SUFFIX);
    604        return buf.toString();
    605    }
    606
    607    /**
    608     * Returns an unmodifiable view of the underlying map's key set.
    609     *
    610     * @return the set of unique elements in this bag
    611     */
    612    @Override
    613    public Set<E> uniqueSet() {
    614        if (uniqueSet == null) {
    615            uniqueSet = UnmodifiableSet.<E>unmodifiableSet(map.keySet());
    616        }
    617        return uniqueSet;
    618    }
    619
    620}