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