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