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