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