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