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