    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.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    /**
    262     * Always throws {@link UnsupportedOperationException}.
    263     *
    264     * @param object Ignored.
    265     * @param occurrences Ignored.
    266     * @throws UnsupportedOperationException Always thrown.
    267     */
    268    @Override
    269    public int add(final E object, final int occurrences) {
    270        throw new UnsupportedOperationException();
    271    }
    272
    273    /**
    274     * Clears the multiset removing all elements from the entrySet.
    275     */
    276    @Override
    277    public void clear() {
    278        final Iterator<Entry<E>> it = entrySet().iterator();
    279        while (it.hasNext()) {
    280            it.next();
    281            it.remove();
    282        }
    283    }
    284
    285    /**
    286     * Determines if the multiset contains the given element.
    287     *
    288     * @param object The object to search for
    289     * @return true if the multiset contains the given element
    290     */
    291    @Override
    292    public boolean contains(final Object object) {
    293        return getCount(object) > 0;
    294    }
    295
    296    /**
    297     * Create a new view for the set of entries in this multiset.
    298     *
    299     * @return A view of the set of entries
    300     */
    301    protected Set<Entry<E>> createEntrySet() {
    302        return new EntrySet<>(this);
    303    }
    304
    305    /**
    306     * Creates an entry set iterator.
    307     * Subclasses can override this to return iterators with different properties.
    308     *
    309     * @return The entrySet iterator
    310     */
    311    protected abstract Iterator<Entry<E>> createEntrySetIterator();
    312
    313    /**
    314     * Create a new view for the set of unique elements in this multiset.
    315     *
    316     * @return A view of the set of unique elements
    317     */
    318    protected Set<E> createUniqueSet() {
    319        return new UniqueSet<>(this);
    320    }
    321
    322    /**
    323     * Creates a unique set iterator.
    324     * Subclasses can override this to return iterators with different properties.
    325     *
    326     * @return The uniqueSet iterator
    327     */
    328    protected Iterator<E> createUniqueSetIterator() {
    329        final Transformer<Entry<E>, E> transformer = Entry::getElement;
    330        return IteratorUtils.transformedIterator(entrySet().iterator(), transformer);
    331    }
    332
    333    /**
    334     * Reads the multiset in using a custom routine.
    335     *
    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 cannot be loaded
    339     * @throws ClassCastException if the stream does not contain the correct objects
    340     */
    341    protected void doReadObject(final ObjectInputStream in)
    342            throws IOException, ClassNotFoundException {
    343        final int entrySize = in.readInt();
    344        for (int i = 0; i < entrySize; i++) {
    345            @SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
    346            final E obj = (E) in.readObject();
    347            final int count = in.readInt();
    348            setCount(obj, count);
    349        }
    350    }
    351
    352    /**
    353     * Writes the multiset out using a custom routine.
    354     *
    355     * @param out The output stream
    356     * @throws IOException any of the usual I/O related exceptions
    357     */
    358    protected void doWriteObject(final ObjectOutputStream out) throws IOException {
    359        out.writeInt(entrySet().size());
    360        for (final Entry<E> entry : entrySet()) {
    361            out.writeObject(entry.getElement());
    362            out.writeInt(entry.getCount());
    363        }
    364    }
    365
    366    /**
    367     * Returns an unmodifiable view of the entries of this multiset.
    368     *
    369     * @return The set of entries in this multiset
    370     */
    371    @Override
    372    public Set<Entry<E>> entrySet() {
    373        if (entrySet == null) {
    374            entrySet = createEntrySet();
    375        }
    376        return entrySet;
    377    }
    378
    379    @Override
    380    public boolean equals(final Object object) {
    381        if (object == this) {
    382            return true;
    383        }
    384        if (!(object instanceof MultiSet)) {
    385            return false;
    386        }
    387        final MultiSet<?> other = (MultiSet<?>) object;
    388        if (other.size() != size()) {
    389            return false;
    390        }
    391        for (final Entry<E> entry : entrySet()) {
    392            if (other.getCount(entry.getElement()) != getCount(entry.getElement())) {
    393                return false;
    394            }
    395        }
    396        return true;
    397    }
    398
    399    /**
    400     * Gets the number of occurrence of the given element in this multiset by
    401     * iterating over its entrySet.
    402     *
    403     * @param object The object to search for
    404     * @return The number of occurrences of the object, zero if not found
    405     */
    406    @Override
    407    public int getCount(final Object object) {
    408        for (final Entry<E> entry : entrySet()) {
    409            final E element = entry.getElement();
    410            if (Objects.equals(element, object)) {
    411                return entry.getCount();
    412            }
    413        }
    414        return 0;
    415    }
    416
    417    @Override
    418    public int hashCode() {
    419        return entrySet().hashCode();
    420    }
    421
    422    /**
    423     * Gets an iterator over the multiset elements. Elements present in the
    424     * MultiSet more than once will be returned repeatedly.
    425     *
    426     * @return The iterator
    427     */
    428    @Override
    429    public Iterator<E> iterator() {
    430        return new MultiSetIterator<>(this);
    431    }
    432
    433    @Override
    434    public boolean remove(final Object object) {
    435        return remove(object, 1) != 0;
    436    }
    437
    438    /**
    439     * Always throws {@link UnsupportedOperationException}.
    440     *
    441     * @param object Ignored.
    442     * @param occurrences Ignored.
    443     * @throws UnsupportedOperationException Always thrown.
    444     */
    445    @Override
    446    public int remove(final Object object, final int occurrences) {
    447        throw new UnsupportedOperationException();
    448    }
    449
    450    @Override
    451    public boolean removeAll(final Collection<?> coll) {
    452        boolean result = false;
    453        for (final Object obj : coll) {
    454            final boolean changed = remove(obj, getCount(obj)) != 0;
    455            result = result || changed;
    456        }
    457        return result;
    458    }
    459
    460    @Override
    461    public int setCount(final E object, final int count) {
    462        if (count < 0) {
    463            throw new IllegalArgumentException("Count must not be negative.");
    464        }
    465
    466        final int oldCount = getCount(object);
    467        if (oldCount < count) {
    468            add(object, count - oldCount);
    469        } else {
    470            remove(object, oldCount - count);
    471        }
    472        return oldCount;
    473    }
    474
    475    /**
    476     * Returns the number of elements in this multiset.
    477     *
    478     * @return current size of the multiset, or {@code Integer.MAX_VALUE} if the total exceeds it.
    479     */
    480    @Override
    481    public int size() {
    482        // TODO reuse IterableUtils.sumToInt(Iterable, ToIntFunction)
    483        int size = 0;
    484        try {
    485            for (final Entry<E> entry : entrySet()) {
    486                size = Math.addExact(size, entry.getCount());
    487            }
    488        } catch (final ArithmeticException e) {
    489            size = Integer.MAX_VALUE;
    490        }
    491        return size;
    492    }
    493
    494    /**
    495     * Implement a toString() method suitable for debugging.
    496     *
    497     * @return A debugging toString
    498     */
    499    @Override
    500    public String toString() {
    501        return entrySet().toString();
    502    }
    503
    504    /**
    505     * Returns the number of unique elements in this multiset.
    506     *
    507     * @return The number of unique elements
    508     */
    509    protected abstract int uniqueElements();
    510
    511    /**
    512     * Returns a view of the unique elements of this multiset.
    513     *
    514     * @return The set of unique elements in this multiset
    515     */
    516    @Override
    517    public Set<E> uniqueSet() {
    518        if (uniqueSet == null) {
    519            uniqueSet = createUniqueSet();
    520        }
    521        return uniqueSet;
    522    }
    523
    524}