    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 serialisation.
    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     * Read the multiset in using a custom routine.
    349     * @param in the input stream
    350     * @throws IOException any of the usual I/O related exceptions
    351     * @throws ClassNotFoundException if the stream contains an object which class cannot be loaded
    352     * @throws ClassCastException if the stream does not contain the correct objects
    353     */
    354    @Override
    355    protected void doReadObject(final ObjectInputStream in)
    356            throws IOException, ClassNotFoundException {
    357        final int entrySize = in.readInt();
    358        for (int i = 0; i < entrySize; i++) {
    359            @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
    360            final E obj = (E) in.readObject();
    361            final int count = in.readInt();
    362            map.put(obj, new MutableInteger(count));
    363            size += count;
    364        }
    365    }
    366
    367    /**
    368     * Write the multiset out using a custom routine.
    369     * @param out the output stream
    370     * @throws IOException any of the usual I/O related exceptions
    371     */
    372    @Override
    373    protected void doWriteObject(final ObjectOutputStream out) throws IOException {
    374        out.writeInt(map.size());
    375        for (final Map.Entry<E, MutableInteger> entry : map.entrySet()) {
    376            out.writeObject(entry.getKey());
    377            out.writeInt(entry.getValue().value);
    378        }
    379    }
    380
    381    @Override
    382    public boolean equals(final Object object) {
    383        if (object == this) {
    384            return true;
    385        }
    386        if (!(object instanceof MultiSet)) {
    387            return false;
    388        }
    389        final MultiSet<?> other = (MultiSet<?>) object;
    390        if (other.size() != size()) {
    391            return false;
    392        }
    393        for (final E element : map.keySet()) {
    394            if (other.getCount(element) != getCount(element)) {
    395                return false;
    396            }
    397        }
    398        return true;
    399    }
    400
    401    /**
    402     * Returns the number of occurrence of the given element in this multiset by
    403     * looking up its count in the underlying map.
    404     *
    405     * @param object the object to search for
    406     * @return the number of occurrences of the object, zero if not found
    407     */
    408    @Override
    409    public int getCount(final Object object) {
    410        final MutableInteger count = map.get(object);
    411        if (count != null) {
    412            return count.value;
    413        }
    414        return 0;
    415    }
    416
    417    /**
    418     * Utility method for implementations to access the map that backs this multiset.
    419     * Not intended for interactive use outside of subclasses.
    420     *
    421     * @return the map being used by the MultiSet
    422     */
    423    protected Map<E, MutableInteger> getMap() {
    424        return map;
    425    }
    426
    427    @Override
    428    public int hashCode() {
    429        int total = 0;
    430        for (final Map.Entry<E, MutableInteger> entry : map.entrySet()) {
    431            final E element = entry.getKey();
    432            final MutableInteger count = entry.getValue();
    433            total += (element == null ? 0 : element.hashCode()) ^ count.value;
    434        }
    435        return total;
    436    }
    437
    438    /**
    439     * Returns true if the underlying map is empty.
    440     *
    441     * @return true if multiset is empty
    442     */
    443    @Override
    444    public boolean isEmpty() {
    445        return map.isEmpty();
    446    }
    447
    448    /**
    449     * Gets an iterator over the multiset elements. Elements present in the
    450     * MultiSet more than once will be returned repeatedly.
    451     *
    452     * @return the iterator
    453     */
    454    @Override
    455    public Iterator<E> iterator() {
    456        return new MapBasedMultiSetIterator<>(this);
    457    }
    458
    459    @Override
    460    public int remove(final Object object, final int occurrences) {
    461        if (occurrences < 0) {
    462            throw new IllegalArgumentException("Occurrences must not be negative.");
    463        }
    464
    465        final MutableInteger mut = map.get(object);
    466        if (mut == null) {
    467            return 0;
    468        }
    469        final int oldCount = mut.value;
    470        if (occurrences > 0) {
    471            modCount++;
    472            if (occurrences < mut.value) {
    473                mut.value -= occurrences;
    474                size -= occurrences;
    475            } else {
    476                map.remove(object);
    477                size -= mut.value;
    478                mut.value = 0;
    479            }
    480        }
    481        return oldCount;
    482    }
    483
    484    /**
    485     * Sets the map being wrapped.
    486     * <p>
    487     * <strong>Note:</strong> this method should only be used during deserialization
    488     * </p>
    489     *
    490     * @param map the map to wrap
    491     */
    492    protected void setMap(final Map<E, MutableInteger> map) {
    493        this.map = map;
    494    }
    495
    496    /**
    497     * Returns the number of elements in this multiset.
    498     *
    499     * @return current size of the multiset
    500     */
    501    @Override
    502    public int size() {
    503        return size;
    504    }
    505
    506    /**
    507     * Returns an array of all of this multiset's elements.
    508     *
    509     * @return an array of all of this multiset's elements
    510     */
    511    @Override
    512    public Object[] toArray() {
    513        final Object[] result = new Object[size()];
    514        int i = 0;
    515        for (final Map.Entry<E, MutableInteger> entry : map.entrySet()) {
    516            final E current = entry.getKey();
    517            final MutableInteger count = entry.getValue();
    518            for (int index = count.value; index > 0; index--) {
    519                result[i++] = current;
    520            }
    521        }
    522        return result;
    523    }
    524
    525    /**
    526     * Returns an array of all of this multiset's elements.
    527     * If the input array has more elements than are in the multiset,
    528     * trailing elements will be set to null.
    529     *
    530     * @param <T> the type of the array elements
    531     * @param array the array to populate
    532     * @return an array of all of this multiset's elements
    533     * @throws ArrayStoreException if the runtime type of the specified array is not
    534     *   a supertype of the runtime type of the elements in this list
    535     * @throws NullPointerException if the specified array is null
    536     */
    537    @Override
    538    public <T> T[] toArray(T[] array) {
    539        final int size = size();
    540        if (array.length < size) {
    541            @SuppressWarnings("unchecked") // safe as both are of type T
    542            final T[] unchecked = (T[]) Array.newInstance(array.getClass().getComponentType(), size);
    543            array = unchecked;
    544        }
    545
    546        int i = 0;
    547        for (final Map.Entry<E, MutableInteger> entry : map.entrySet()) {
    548            final E current = entry.getKey();
    549            final MutableInteger count = entry.getValue();
    550            for (int index = count.value; index > 0; index--) {
    551                // unsafe, will throw ArrayStoreException if types are not compatible, see Javadoc
    552                @SuppressWarnings("unchecked")
    553                final T unchecked = (T) current;
    554                array[i++] = unchecked;
    555            }
    556        }
    557        while (i < array.length) {
    558            array[i++] = null;
    559        }
    560        return array;
    561    }
    562
    563    @Override
    564    protected int uniqueElements() {
    565        return map.size();
    566    }
    567}