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