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