    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.util.AbstractCollection;
    023import java.util.AbstractSet;
    024import java.util.Collection;
    025import java.util.Iterator;
    026import java.util.Objects;
    027import java.util.Set;
    028
    029import org.apache.commons.collections4.IteratorUtils;
    030import org.apache.commons.collections4.MultiSet;
    031import org.apache.commons.collections4.Transformer;
    032
    033/**
    034 * Abstract implementation of the {@link MultiSet} interface to simplify the
    035 * creation of subclass implementations.
    036 *
    037 * @param <E> the type held in the multiset
    038 * @since 4.1
    039 */
    040public abstract class AbstractMultiSet<E> extends AbstractCollection<E> implements MultiSet<E> {
    041
    042    /**
    043     * Inner class AbstractEntry.
    044     *
    045     * @param <E> the element type.
    046     */
    047    protected abstract static class AbstractEntry<E> implements Entry<E> {
    048
    049        @Override
    050        public boolean equals(final Object object) {
    051            if (object instanceof Entry) {
    052                final Entry<?> other = (Entry<?>) object;
    053                final E element = getElement();
    054                final Object otherElement = other.getElement();
    055
    056                return this.getCount() == other.getCount() &&
    057                       Objects.equals(element, otherElement);
    058            }
    059            return false;
    060        }
    061
    062        @Override
    063        public int hashCode() {
    064            final E element = getElement();
    065            return (element == null ? 0 : element.hashCode()) ^ getCount();
    066        }
    067
    068        @Override
    069        public String toString() {
    070            return String.format("%s:%d", getElement(), getCount());
    071        }
    072    }
    073
    074    /**
    075     * Inner class EntrySet.
    076     *
    077     * @param <E> the element type.
    078     */
    079    protected static class EntrySet<E> extends AbstractSet<Entry<E>> {
    080
    081        private final AbstractMultiSet<E> parent;
    082
    083        /**
    084         * Constructs a new view of the MultiSet.
    085         *
    086         * @param parent  the parent MultiSet
    087         */
    088        protected EntrySet(final AbstractMultiSet<E> parent) {
    089            this.parent = parent;
    090        }
    091
    092        @Override
    093        public boolean contains(final Object obj) {
    094            if (!(obj instanceof Entry<?>)) {
    095                return false;
    096            }
    097            final Entry<?> entry = (Entry<?>) obj;
    098            final Object element = entry.getElement();
    099            return parent.getCount(element) == entry.getCount();
    100        }
    101
    102        @Override
    103        public Iterator<Entry<E>> iterator() {
    104            return parent.createEntrySetIterator();
    105        }
    106
    107        @Override
    108        public boolean remove(final Object obj) {
    109            if (!(obj instanceof Entry<?>)) {
    110                return false;
    111            }
    112            final Entry<?> entry = (Entry<?>) obj;
    113            final Object element = entry.getElement();
    114            if (parent.contains(element)) {
    115                final int count = parent.getCount(element);
    116                if (entry.getCount() == count) {
    117                    parent.remove(element, count);
    118                    return true;
    119                }
    120            }
    121            return false;
    122        }
    123
    124        @Override
    125        public int size() {
    126            return parent.uniqueElements();
    127        }
    128    }
    129
    130    /**
    131     * Inner class iterator for the MultiSet.
    132     */
    133    private static final class MultiSetIterator<E> implements Iterator<E> {
    134        private final AbstractMultiSet<E> parent;
    135        private final Iterator<Entry<E>> entryIterator;
    136        private Entry<E> current;
    137        private int itemCount;
    138        private boolean canRemove;
    139
    140        /**
    141         * Constructs a new instance.
    142         *
    143         * @param parent the parent multiset
    144         */
    145        MultiSetIterator(final AbstractMultiSet<E> parent) {
    146            this.parent = parent;
    147            this.entryIterator = parent.entrySet().iterator();
    148            this.current = null;
    149            this.canRemove = false;
    150        }
    151
    152        /** {@inheritDoc} */
    153        @Override
    154        public boolean hasNext() {
    155            return itemCount > 0 || entryIterator.hasNext();
    156        }
    157
    158        /** {@inheritDoc} */
    159        @Override
    160        public E next() {
    161            if (itemCount == 0) {
    162                current = entryIterator.next();
    163                itemCount = current.getCount();
    164            }
    165            canRemove = true;
    166            itemCount--;
    167            return current.getElement();
    168        }
    169
    170        /** {@inheritDoc} */
    171        @Override
    172        public void remove() {
    173            if (!canRemove) {
    174                throw new IllegalStateException();
    175            }
    176            final int count = current.getCount();
    177            if (count > 1) {
    178                parent.remove(current.getElement());
    179            } else {
    180                entryIterator.remove();
    181            }
    182            canRemove = false;
    183        }
    184    }
    185
    186    /**
    187     * Inner class UniqueSet.
    188     *
    189     * @param <E> the element type.
    190     */
    191    protected static class UniqueSet<E> extends AbstractSet<E> {
    192
    193        /** The parent multiset */
    194        protected final AbstractMultiSet<E> parent;
    195
    196        /**
    197         * Constructs a new unique element view of the MultiSet.
    198         *
    199         * @param parent  the parent MultiSet
    200         */
    201        protected UniqueSet(final AbstractMultiSet<E> parent) {
    202            this.parent = parent;
    203        }
    204
    205        @Override
    206        public void clear() {
    207            parent.clear();
    208        }
    209
    210        @Override
    211        public boolean contains(final Object key) {
    212            return parent.contains(key);
    213        }
    214
    215        @Override
    216        public boolean containsAll(final Collection<?> coll) {
    217            return parent.containsAll(coll);
    218        }
    219
    220        @Override
    221        public Iterator<E> iterator() {
    222            return parent.createUniqueSetIterator();
    223        }
    224
    225        @Override
    226        public boolean remove(final Object key) {
    227            return parent.remove(key, parent.getCount(key)) != 0;
    228        }
    229
    230        @Override
    231        public int size() {
    232            return parent.uniqueElements();
    233        }
    234    }
    235
    236    /** View of the elements */
    237    private transient Set<E> uniqueSet;
    238
    239    /** View of the entries */
    240    private transient Set<Entry<E>> entrySet;
    241
    242    /**
    243     * Constructor needed for subclass serialisation.
    244     */
    245    protected AbstractMultiSet() {
    246    }
    247
    248    @Override
    249    public boolean add(final E object) {
    250        add(object, 1);
    251        return true;
    252    }
    253
    254    @Override
    255    public int add(final E object, final int occurrences) {
    256        throw new UnsupportedOperationException();
    257    }
    258
    259    /**
    260     * Clears the multiset removing all elements from the entrySet.
    261     */
    262    @Override
    263    public void clear() {
    264        final Iterator<Entry<E>> it = entrySet().iterator();
    265        while (it.hasNext()) {
    266            it.next();
    267            it.remove();
    268        }
    269    }
    270
    271    /**
    272     * Determines if the multiset contains the given element.
    273     *
    274     * @param object the object to search for
    275     * @return true if the multiset contains the given element
    276     */
    277    @Override
    278    public boolean contains(final Object object) {
    279        return getCount(object) > 0;
    280    }
    281
    282    /**
    283     * Create a new view for the set of entries in this multiset.
    284     *
    285     * @return a view of the set of entries
    286     */
    287    protected Set<Entry<E>> createEntrySet() {
    288        return new EntrySet<>(this);
    289    }
    290
    291    /**
    292     * Creates an entry set iterator.
    293     * Subclasses can override this to return iterators with different properties.
    294     *
    295     * @return the entrySet iterator
    296     */
    297    protected abstract Iterator<Entry<E>> createEntrySetIterator();
    298
    299    /**
    300     * Create a new view for the set of unique elements in this multiset.
    301     *
    302     * @return a view of the set of unique elements
    303     */
    304    protected Set<E> createUniqueSet() {
    305        return new UniqueSet<>(this);
    306    }
    307
    308    /**
    309     * Creates a unique set iterator.
    310     * Subclasses can override this to return iterators with different properties.
    311     *
    312     * @return the uniqueSet iterator
    313     */
    314    protected Iterator<E> createUniqueSetIterator() {
    315        final Transformer<Entry<E>, E> transformer = Entry::getElement;
    316        return IteratorUtils.transformedIterator(entrySet().iterator(), transformer);
    317    }
    318
    319    /**
    320     * Read the multiset in using a custom routine.
    321     * @param in the input stream
    322     * @throws IOException any of the usual I/O related exceptions
    323     * @throws ClassNotFoundException if the stream contains an object which class cannot be loaded
    324     * @throws ClassCastException if the stream does not contain the correct objects
    325     */
    326    protected void doReadObject(final ObjectInputStream in)
    327            throws IOException, ClassNotFoundException {
    328        final int entrySize = in.readInt();
    329        for (int i = 0; i < entrySize; i++) {
    330            @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
    331            final E obj = (E) in.readObject();
    332            final int count = in.readInt();
    333            setCount(obj, count);
    334        }
    335    }
    336
    337    /**
    338     * Write the multiset out using a custom routine.
    339     * @param out the output stream
    340     * @throws IOException any of the usual I/O related exceptions
    341     */
    342    protected void doWriteObject(final ObjectOutputStream out) throws IOException {
    343        out.writeInt(entrySet().size());
    344        for (final Entry<E> entry : entrySet()) {
    345            out.writeObject(entry.getElement());
    346            out.writeInt(entry.getCount());
    347        }
    348    }
    349
    350    /**
    351     * Returns an unmodifiable view of the entries of this multiset.
    352     *
    353     * @return the set of entries in this multiset
    354     */
    355    @Override
    356    public Set<Entry<E>> entrySet() {
    357        if (entrySet == null) {
    358            entrySet = createEntrySet();
    359        }
    360        return entrySet;
    361    }
    362
    363    @Override
    364    public boolean equals(final Object object) {
    365        if (object == this) {
    366            return true;
    367        }
    368        if (!(object instanceof MultiSet)) {
    369            return false;
    370        }
    371        final MultiSet<?> other = (MultiSet<?>) object;
    372        if (other.size() != size()) {
    373            return false;
    374        }
    375        for (final Entry<E> entry : entrySet()) {
    376            if (other.getCount(entry.getElement()) != getCount(entry.getElement())) {
    377                return false;
    378            }
    379        }
    380        return true;
    381    }
    382
    383    /**
    384     * Returns the number of occurrence of the given element in this multiset by
    385     * iterating over its entrySet.
    386     *
    387     * @param object the object to search for
    388     * @return the number of occurrences of the object, zero if not found
    389     */
    390    @Override
    391    public int getCount(final Object object) {
    392        for (final Entry<E> entry : entrySet()) {
    393            final E element = entry.getElement();
    394            if (Objects.equals(element, object)) {
    395                return entry.getCount();
    396            }
    397        }
    398        return 0;
    399    }
    400
    401    @Override
    402    public int hashCode() {
    403        return entrySet().hashCode();
    404    }
    405
    406    /**
    407     * Gets an iterator over the multiset elements. Elements present in the
    408     * MultiSet more than once will be returned repeatedly.
    409     *
    410     * @return the iterator
    411     */
    412    @Override
    413    public Iterator<E> iterator() {
    414        return new MultiSetIterator<>(this);
    415    }
    416
    417    @Override
    418    public boolean remove(final Object object) {
    419        return remove(object, 1) != 0;
    420    }
    421
    422    @Override
    423    public int remove(final Object object, final int occurrences) {
    424        throw new UnsupportedOperationException();
    425    }
    426
    427    @Override
    428    public boolean removeAll(final Collection<?> coll) {
    429        boolean result = false;
    430        for (final Object obj : coll) {
    431            final boolean changed = remove(obj, getCount(obj)) != 0;
    432            result = result || changed;
    433        }
    434        return result;
    435    }
    436
    437    @Override
    438    public int setCount(final E object, final int count) {
    439        if (count < 0) {
    440            throw new IllegalArgumentException("Count must not be negative.");
    441        }
    442
    443        final int oldCount = getCount(object);
    444        if (oldCount < count) {
    445            add(object, count - oldCount);
    446        } else {
    447            remove(object, oldCount - count);
    448        }
    449        return oldCount;
    450    }
    451
    452    /**
    453     * Returns the number of elements in this multiset.
    454     *
    455     * @return current size of the multiset
    456     */
    457    @Override
    458    public int size() {
    459        int totalSize = 0;
    460        for (final Entry<E> entry : entrySet()) {
    461            totalSize += entry.getCount();
    462        }
    463        return totalSize;
    464    }
    465
    466    /**
    467     * Implement a toString() method suitable for debugging.
    468     *
    469     * @return a debugging toString
    470     */
    471    @Override
    472    public String toString() {
    473        return entrySet().toString();
    474    }
    475
    476    /**
    477     * Returns the number of unique elements in this multiset.
    478     *
    479     * @return the number of unique elements
    480     */
    481    protected abstract int uniqueElements();
    482
    483    /**
    484     * Returns a view of the unique elements of this multiset.
    485     *
    486     * @return the set of unique elements in this multiset
    487     */
    488    @Override
    489    public Set<E> uniqueSet() {
    490        if (uniqueSet == null) {
    491            uniqueSet = createUniqueSet();
    492        }
    493        return uniqueSet;
    494    }
    495
    496}