/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* https://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.collections4.multiset;
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.lang.reflect.Array;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import org.apache.commons.collections4.MultiSet;
import org.apache.commons.collections4.iterators.AbstractIteratorDecorator;
/**
* Abstract implementation of the {@link MultiSet} interface to simplify the
* creation of subclass implementations.
* <p>
* Subclasses specify a Map implementation to use as the internal storage. The
* map will be used to map multiset elements to a number; the number represents the
* number of occurrences of that element in the multiset.
* </p>
*
* @param <E> The type held in the multiset.
* @since 4.1
*/
public abstract class AbstractMapMultiSet<E> extends AbstractMultiSet<E> {
/**
* Inner class EntrySetIterator.
*
* @param <E> The element type.
*/
protected static class EntrySetIterator<E> implements Iterator<Entry<E>> {
/** The parent map */
protected final AbstractMapMultiSet<E> parent;
/**
* The source Iterator.
*/
protected final Iterator<Map.Entry<E, MutableInteger>> decorated;
/** The last returned entry. */
protected Entry<E> last;
/** Whether remove is allowed at present. */
protected boolean canRemove;
/**
* Constructs a new instance.
*
* @param decorated The iterator to decorate.
* @param parent The parent multiset.
*/
protected EntrySetIterator(final Iterator<Map.Entry<E, MutableInteger>> decorated,
final AbstractMapMultiSet<E> parent) { this.decorated = decorated; this.parent = parent; }
@Override
public boolean hasNext() {
return decorated.hasNext();
}
@Override
public Entry<E> next() {
last = new MultiSetEntry<>(decorated.next()); canRemove = true; return last;
}
@Override
public void remove() {
if (!canRemove) { throw new IllegalStateException("Iterator remove() can only be called once after next()");
}
final int count = last.getCount(); decorated.remove(); parent.size -= count; parent.modCount++; last = null; canRemove = false; }
}
/**
* Inner class iterator for the MultiSet.
*/
private static final class MapBasedMultiSetIterator<E> implements Iterator<E> {
private final AbstractMapMultiSet<E> parent;
private final Iterator<Map.Entry<E, MutableInteger>> entryIterator;
private Map.Entry<E, MutableInteger> current;
private int itemCount;
private final int mods;
private boolean canRemove;
/**
* Constructs a new instance.
*
* @param parent The parent multiset.
*/
MapBasedMultiSetIterator(final AbstractMapMultiSet<E> parent) { this.parent = parent; this.entryIterator = parent.map.entrySet().iterator(); this.current = null; this.mods = parent.modCount; this.canRemove = false; }
/** {@inheritDoc} */
@Override
public boolean hasNext() {
return itemCount > 0 || entryIterator.hasNext();
}
/** {@inheritDoc} */
@Override
public E next() {
if (parent.modCount != mods) { throw new ConcurrentModificationException();
}
if (itemCount == 0) { current = entryIterator.next(); itemCount = current.getValue().value;
}
canRemove = true; itemCount--; return current.getKey();
}
/** {@inheritDoc} */
@Override
public void remove() {
if (parent.modCount != mods) { throw new ConcurrentModificationException();
}
if (!canRemove) { throw new IllegalStateException();
}
final MutableInteger mut = current.getValue(); if (mut.value > 1) { mut.value--;
} else {
entryIterator.remove();
}
parent.size--; canRemove = false; }
}
/**
* Inner class MultiSetEntry.
*
* @param <E> The key type.
*/
protected static class MultiSetEntry<E> extends AbstractEntry<E> {
/**
* The parent entry.
*/
protected final Map.Entry<E, MutableInteger> parentEntry;
/**
* Constructs a new instance.
*
* @param parentEntry The entry to decorate.
*/
protected MultiSetEntry(final Map.Entry<E, MutableInteger> parentEntry) { this.parentEntry = parentEntry; }
@Override
public int getCount() {
return parentEntry.getValue().value;
}
@Override
public E getElement() {
return parentEntry.getKey();
}
}
/**
* Mutable integer class for storing the data.
*/
protected static class MutableInteger {
/** The value of this mutable. */
protected int value;
/**
* Constructs a new instance.
*
* @param value The initial value.
*/
MutableInteger(final int value) { this.value = value; }
@Override
public boolean equals(final Object obj) {
if (!(obj instanceof MutableInteger)) { return false;
}
return ((MutableInteger) obj).value == value;
}
@Override
public int hashCode() {
return value;
}
}
/**
* Inner class UniqueSetIterator.
*
* @param <E> The element type.
*/
protected static class UniqueSetIterator<E> extends AbstractIteratorDecorator<E> {
/** The parent multiset. */
protected final AbstractMapMultiSet<E> parent;
/** The last returned element. */
protected E lastElement;
/** Whether remove is allowed at present. */
protected boolean canRemove;
/**
* Constructs a new instance.
*
* @param iterator The iterator to decorate.
* @param parent The parent multiset.
*/
protected UniqueSetIterator(final Iterator<E> iterator, final AbstractMapMultiSet<E> parent) {
super(iterator); this.parent = parent; }
@Override
public E next() {
lastElement = super.next(); canRemove = true; return lastElement;
}
@Override
public void remove() {
if (!canRemove) { throw new IllegalStateException("Iterator remove() can only be called once after next()");
}
final int count = parent.getCount(lastElement); super.remove(); parent.size -= count; parent.modCount++; lastElement = null; canRemove = false; }
}
/** The map to use to store the data. */
private transient Map<E, MutableInteger> map;
/** The current total size of the multiset; kept exact past {@link Integer#MAX_VALUE}, {@link #size()} saturates */
private transient long size;
/** The modification count for fail fast iterators. */
private transient int modCount;
/**
* Constructor needed for subclass serialization.
*/
protected AbstractMapMultiSet() { }
/**
* Constructor that assigns the specified Map as the backing store. The map
* must be empty and non-null.
*
* @param map The map to assign.
*/
protected AbstractMapMultiSet(final Map<E, MutableInteger> map) { this.map = map; }
/**
* Constructs a new instance that assigns the specified Map as the backing store. The map
* must be empty and non-null. The multiset is filled from the iterable elements.
*
* @param map The map to assign.
* @param iterable The iterable of elements to add.
* @since 4.6.0
*/
protected AbstractMapMultiSet(final Map<E, MutableInteger> map, final Iterable<? extends E> iterable) {
this(map); iterable.forEach(this::add); }
@Override
public int add(final E object, final int occurrences) {
if (occurrences < 0) { throw new IllegalArgumentException("Occurrences must not be negative.");
}
final MutableInteger mut = map.get(object); final int oldCount = mut != null ? mut.value : 0; if (occurrences > 0) { modCount++; if (mut == null) { map.put(object, new MutableInteger(occurrences)); size += occurrences;
} else {
final int applied = Math.min(occurrences, Integer.MAX_VALUE - mut.value); mut.value += applied; size += applied;
}
}
return oldCount;
}
/**
* Clears the multiset by clearing the underlying map.
*/
@Override
public void clear() {
modCount++; map.clear(); size = 0; }
/**
* Determines if the multiset contains the given element by checking if the
* underlying map contains the element as a key.
*
* @param object The object to search for.
* @return true if the multiset contains the given element.
*/
@Override
public boolean contains(final Object object) {
return map.containsKey(object);
}
@Override
protected Iterator<Entry<E>> createEntrySetIterator() {
return new EntrySetIterator<>(map.entrySet().iterator(), this);
}
@Override
protected Iterator<E> createUniqueSetIterator() {
return new UniqueSetIterator<>(getMap().keySet().iterator(), this);
}
/**
* Reads the multiset in using a custom routine.
*
* @param in The input stream.
* @throws IOException any of the usual I/O related exceptions.
* @throws ClassNotFoundException if the stream contains an object which class cannot be loaded.
* @throws ClassCastException if the stream does not contain the correct objects.
*/
@Override
protected void doReadObject(final ObjectInputStream in)
throws IOException, ClassNotFoundException {
final int entrySize = in.readInt(); for (int i = 0; i < entrySize; i++) {
@SuppressWarnings("unchecked") // This will fail at runtime if the stream is incorrect
final E obj = (E) in.readObject(); final int count = in.readInt(); if (count < 1) { throw new InvalidObjectException("Invalid count for entry: " + count);
}
map.put(obj, new MutableInteger(count)); size += count;
}
}
/**
* Writes the multiset out using a custom routine.
*
* @param out The output stream.
* @throws IOException any of the usual I/O related exceptions.
*/
@Override
protected void doWriteObject(final ObjectOutputStream out) throws IOException {
out.writeInt(map.size()); for (final Map.Entry<E, MutableInteger> entry : map.entrySet()) { out.writeObject(entry.getKey()); out.writeInt(entry.getValue().value); } }
@Override
public boolean equals(final Object object) {
if (object == this) { return true;
}
if (!(object instanceof MultiSet)) { return false;
}
final MultiSet<?> other = (MultiSet<?>) object; if (other.size() != size()) { return false;
}
for (final E element : map.keySet()) { if (other.getCount(element) != getCount(element)) { return false;
}
} return true;
}
/**
* Gets the number of occurrence of the given element in this multiset by
* looking up its count in the underlying map.
*
* @param object The object to search for.
* @return The number of occurrences of the object, zero if not found.
*/
@Override
public int getCount(final Object object) {
final MutableInteger count = map.get(object); if (count != null) { return count.value;
}
return 0;
}
/**
* Gets the map that backs this multiset.
* Not intended for interactive use outside of subclasses.
*
* @return The map being used by the MultiSet.
*/
protected Map<E, MutableInteger> getMap() {
return map;
}
@Override
public int hashCode() {
int total = 0; for (final Map.Entry<E, MutableInteger> entry : map.entrySet()) { final E element = entry.getKey(); final MutableInteger count = entry.getValue(); total += (element == null ? 0 : element.hashCode()) ^ count.value; } return total;
}
/**
* Returns true if the underlying map is empty.
*
* @return true if multiset is empty.
*/
@Override
public boolean isEmpty() {
return map.isEmpty();
}
/**
* Gets an iterator over the multiset elements. Elements present in the
* MultiSet more than once will be returned repeatedly.
*
* @return The iterator.
*/
@Override
public Iterator<E> iterator() {
return new MapBasedMultiSetIterator<>(this);
}
@Override
public int remove(final Object object, final int occurrences) {
if (occurrences < 0) { throw new IllegalArgumentException("Occurrences must not be negative.");
}
final MutableInteger mut = map.get(object); if (mut == null) { return 0;
}
final int oldCount = mut.value; if (occurrences > 0) { modCount++; if (occurrences < mut.value) { mut.value -= occurrences; size -= occurrences;
} else {
map.remove(object); size -= mut.value; mut.value = 0;
}
}
return oldCount;
}
/**
* Sets the map being wrapped.
* <p>
* <strong>Note:</strong> this method should only be used during deserialization
* </p>
*
* @param map The map to wrap.
*/
protected void setMap(final Map<E, MutableInteger> map) {
this.map = map; }
/**
* Returns the number of elements in this multiset, or {@code Integer.MAX_VALUE}
* if the multiset contains more than {@code Integer.MAX_VALUE} elements.
*
* @return current size of the multiset.
*/
@Override
public int size() {
return (int) Math.min(size, Integer.MAX_VALUE);
}
/**
* Returns an array of all of this multiset's elements.
*
* @return An array of all of this multiset's elements.
*/
@Override
public Object[] toArray() {
final Object[] result = new Object[size()]; int i = 0; for (final Map.Entry<E, MutableInteger> entry : map.entrySet()) { final E current = entry.getKey(); final MutableInteger count = entry.getValue(); for (int index = count.value; index > 0; index--) { result[i++] = current;
}
} return result;
}
/**
* Returns an array of all of this multiset's elements. If the input array has more elements than are in the multiset, trailing elements will be set to
* null.
*
* @param <T> The type of the array elements.
* @param array The array to populate.
* @return An array of all of this multiset's elements.
* @throws ArrayStoreException if the runtime type of the specified array is not a supertype of the runtime type of the elements in this list.
* @throws NullPointerException if the specified array is null.
*/
@Override
public <T> T[] toArray(T[] array) {
final int size = size(); if (array.length < size) {
@SuppressWarnings("unchecked") // safe as both are of type T
final T[] unchecked = (T[]) Array.newInstance(array.getClass().getComponentType(), size); array = unchecked;
}
int i = 0; for (final Map.Entry<E, MutableInteger> entry : map.entrySet()) { final E current = entry.getKey(); final MutableInteger count = entry.getValue(); for (int index = count.value; index > 0; index--) {
// unsafe, will throw ArrayStoreException if types are not compatible, see Javadoc
@SuppressWarnings("unchecked")
final T unchecked = (T) current; array[i++] = unchecked;
}
} while (i < array.length) { array[i++] = null;
}
return array;
}
@Override
protected int uniqueElements() {
return map.size();
}
}