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