///////////////////////////////////////////////////////
MOVED TO : https://github.com/claudemartin/multiset
///////////////////////////////////////////////////////
package ch.claude_martin;
import static java.util.Arrays.asList;
import static java.util.Objects.requireNonNull;
import java.io.Serializable;
import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.util.*;
import java.util.AbstractMap.SimpleImmutableEntry;
import java.util.Map.Entry;
import java.util.function.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
import javax.annotation.concurrent.NotThreadSafe;
/**
* Multiset in Java. It doesn't maintain sorting or insertion order. But it's not a regular set,
* because you can add an element more than once. If an element is already present that equals the
* element to be inserted then it's multiplicity (count) is incremented by one. <code>null</code> is
* allowed as an element.
*
* <p>
* An element with multiplicity zero is completely removed from the data structure and will not
* occur as a tuple of {@code (element, 0)}. This needs to be considered when using methods such as
* {@link #setMultiplicities(ToIntBiFunction)}, {@link #forEach(ObjIntConsumer)}, {@link #entries()}
* , and {@link #merge(Multiset, IntBinaryOperator)}.
*
* <p>
* <a href="https://humanoidreadable.wordpress.com/2015/02/20/multiset-in-java/">blog entry</a>
* <p>
* Copyright: You can use this for whatever you like! No restrictions.
*
* @author Claude Martin
*
* @param <T>
* The type of the elements
*/
@NotThreadSafe
public final class Multiset<T> extends AbstractCollection<T> implements Serializable {
private static final long serialVersionUID = -7083567870279959503L;
/** The backing map. */
final Map<T, Integer> map;
/** View as map. Lazy. This is the same as {@link #map} if and only if this is unmodifiable. */
private transient Map<T, Integer> view = null;
/**
* Total size of this multiset.
*
* @implNote Modification must always be performend on the {@link #map} first. This will fail if
* this multiset {@link #isUnmodifiable() is unmodifiable}.
*/
int size = 0;
public Multiset() {
this.map = new HashMap<>();
}
/** Creates an unmodifiable Multiset. */
private Multiset(final Multiset<T> multiset, final boolean unmodifiable) {
assert unmodifiable;
this.map = this.view = Collections.unmodifiableMap(multiset.map);
this.size = multiset.size;
this.checkSize();
return;
}
/** Creates an empty Multiset. */
private Multiset(final boolean empty) {
this.map = this.view = Collections.emptyMap();
this.size = 0;
}
/** Creates a new Multiset and adds all elements from the given collection. */
public Multiset(final Collection<? extends T> coll) {
requireNonNull(coll, "coll");
this.map = new HashMap<>(coll.size());
for (final T t : coll)
this.map.merge(t, 1, Integer::sum);
this.size = coll.size();
this.checkSize();
}
/** Creates a new Multiset and adds all elements from the given Multiset. */
public Multiset(final Multiset<? extends T> multiset) {
requireNonNull(multiset, "multiset");
multiset.checkSize();
this.map = new HashMap<>(multiset.map);
this.size = multiset.size;
this.checkSize();
}
/**
* Creates a new {@link Multiset} containing all given elements.
*
* @param elements
* The elements
* @return <code>new Multiset<>(asList(elements));</code>
*/
@SafeVarargs
public static <T> Multiset<T> of(final T... elements) {
requireNonNull(elements, "elements");
return new Multiset<>(asList(elements));
}
/**
* Creates a new {@link Multiset} containing all given elements, with the multiplicity defined by
* the given function.
*
* @param set
* The elements
* @param m
* The multiplicity
* @return new {@link Multiset} greated from the given data.
*/
public static <T> Multiset<T> of(final Set<? extends T> set, final ToIntFunction<? super T> m) {
requireNonNull(set, "set");
requireNonNull(m, "m");
final Multiset<T> result = new Multiset<>();
for (final T t : set)
result.setMultiplicity(t, m.applyAsInt(t));
return result;
}
/**
* Adds the object and returns true.
*
* @see #insert(Object)
*/
@Override
public boolean add(final T t) {
this.insert(t);
return true;
}
/**
* Sets the multiplicity of a certain key. The key is removed if m is 0 or added if it was 0.
* Therefore this may lead to a modification of the underlying data structure. The
* {@link #iterator() Iterator} supports @link {@link Iterator#remove() removal} of elements
* during iteration.
*
* @param element
* the element
* @param m
* new multiplicity
* @returns the old multiplicity.
*/
public int setMultiplicity(final T element, final int m) {
if (m < 0)
throw new IllegalArgumentException("m < 0");
final int i = this.map.getOrDefault(element, 0);
if (m == i)
return i;
if (m == 0)
this.map.remove(element);
else
this.map.put(element, m);
this.size = this.size - i + m;
this.checkSize();
return i;
}
/**
* Sets the multiplicity of a certain key, only if currently set to the specified value.
*
* @param element
* the element
* @param oldMultiplicity
* old multiplicity
* @param newMultiplicity
* new multiplicity
*
* @return {@code true} if the value was replaced
*
* @see Map#replace(Object, Object, Object)
*/
public boolean setMultiplicity(final T element, final int oldMultiplicity,
final int newMultiplicity) {
requireNonNull(element, "obj");
if (oldMultiplicity < 0 || newMultiplicity < 0)
throw new IllegalArgumentException("negative multiplicity");
if (this.getMultiplicity(element) == oldMultiplicity) {
this.setMultiplicity(element, newMultiplicity);
return true;
}
return false;
}
/**
* Adds the object and returns the new multiplicity.
*
* @see #add(Object)
*/
public int insert(final T t) {
final Integer result = this.map.merge(t, 1, Integer::sum);
this.size++;
this.checkSize();
return result;
}
/**
* Removes a single instance of the specified element from this multiset. This decrements the
* multiplicity by one. Does nothing if it wasn't in the set. To remove all equal objects you must
* call <code>{@link #setMultiplicity(Object, int) setMultiplicity(t, 0)}</code>.
*/
@Override
@SuppressWarnings("unchecked")
public boolean remove(final Object t) {
final int value = this.map.getOrDefault(t, 0);
switch (value) {
case 0:
return false;
case 1:
this.map.remove(t);
break;
default:
assert value > 1 : "invalid value";
this.map.put((T) t, value - 1);
break;
}
this.size--;
this.checkSize();
return true;
}
/**
* Reset the multiplicity for each element in this {@link Multiset}.
*
* <p>
* Note that elements with a multiplicity of zero will not be processed, as they are not contained
* in the multiset.
*
* @param m
* function for new multiplicities
* @return true, if any multiplicity of any element was altered.
*/
public boolean setMultiplicities(final ToIntBiFunction<? super T, Integer> m) {
requireNonNull(m, "m");
if (this.isEmpty())
return false;
boolean modified = false;
final Iterator<Entry<T, Integer>> itr = this.map.entrySet().iterator();
while (itr.hasNext()) {
final Entry<T, Integer> next = itr.next();
final T t = next.getKey();
final int oldm = next.getValue();
final int newM = m.applyAsInt(t, oldm);
if (oldm != newM) {
if (newM == 0)
itr.remove();
else
next.setValue(newM);
this.size += -oldm + newM;
modified = true;
}
}
this.checkSize();
return modified;
}
@SuppressWarnings({ "unchecked" })
@Override
public boolean removeAll(final Collection<?> c) {
requireNonNull(c, "c");
if (c instanceof Multiset)
return this.removeAll((Multiset<? extends T>) c);
return super.removeAll(c);
}
/**
* @see #removeAll(Collection)
*/
public boolean removeAll(final Multiset<?> set) {
requireNonNull(set, "set");
boolean result = false;
if (set.isEmpty())
return false;
final Iterator<Entry<T, Integer>> itr = this.map.entrySet().iterator();
while (itr.hasNext()) {
final Entry<T, Integer> next = itr.next();
if (set.map.containsKey(next.getKey())) {
itr.remove();
this.size -= next.getValue();
result = true;
}
}
this.checkSize();
return result;
}
@Override
public boolean retainAll(final Collection<?> c) {
requireNonNull(c, "c");
if (c instanceof Multiset)
return this.retainAll((Multiset<?>) c);
return this.asSet().retainAll(c);
}
/**
* @see #retainAll(Collection)
*/
public boolean retainAll(final Multiset<?> set) {
requireNonNull(set, "set");
if (set == this)
return false;
return this.asSet().retainAll(set.asSet());
}
/**
* Get the multiplicity or the given object. If the object is not in this multiset then the
* multiplicity is 0.
*
* @return the multiplicity.
*/
public int getMultiplicity(final Object t) {
return this.map.getOrDefault(t, 0);
}
Iterator<T> iterator(final Iterator<Entry<T, Integer>> entries) {
return new Iterator<T>() {
int c = 0;
T t = null;
@Override
public T next() {
if (!this.hasNext())
throw new NoSuchElementException();
if (this.c == 0) {
final Entry<T, Integer> e = entries.next();
this.t = e.getKey();
this.c = e.getValue();
}
this.c--;
return this.t;
}
@Override
public boolean hasNext() {
return this.c > 0 || entries.hasNext();
}
@Override
public void remove() {
final int multiplicity = Multiset.this.getMultiplicity(this.t);
if (multiplicity == 1) {
entries.remove();
Multiset.this.size--;
} else
Multiset.this.setMultiplicity(this.t, multiplicity - 1);
}
};
}
/**
* Iterator of all elements. Each element is iterated as many times as it is in this multiset. The
* {@link Iterator} supports the {@link Iterator#remove() remove} method.
*/
@Override
public Iterator<T> iterator() {
this.checkSize();
return this.iterator(this.map.entrySet().iterator());
}
@Override
public Spliterator<T> spliterator() {
return Spliterators.spliterator(this, 0);
}
/** The class invariant. */
void checkSize() {
assert this.map.values().stream().mapToInt(i -> i).sum() == this.size : this.getClass()
.getSimpleName() + ": wrong size";
}
/**
* {@inheritDoc}
* <p>
* This returns the total number of elements, including repeated memberships (cardinality). To get
* the amount of discinct elements use {@link #asMap()}.{@link Map#size() size()}.
* */
@Override
public int size() {
this.checkSize();
return this.size;
}
/**
* Returns a copy of the underlying set of elements. Changes to this set do not alter the
* Multiset.
*
* <p>
* If using the formal definition <code>(A, m)</code> of a multiset, the returned set is
* <code>A</code> and <code>multiset::getMultiplicity</code> is <code>m</code>.
*
* @see #asSet()
* @see #entries()
*/
public Set<T> toSet() {
return new HashSet<>(this.map.keySet());
}
/**
* Conventiance mehtod to create a string representation of this multiset.
* <p>
* Example: {@code ms.toString((t, i) -> t + " x " + i, ", ", "[ ", " ]")}
*
* @param f
* Mapping function for each entry (element and multiplicity)
* @param delimiter
* the delimiter to be used between each entry
* @param prefix
* the sequence of characters to be used at the beginning of the joined result
* @param suffix
* the sequence of characters to be used at the end of the joined result
* @return string representation of this multiset
*/
public String toString(final BiFunction<T, Integer, String> f, final CharSequence delimiter,
final CharSequence prefix, final CharSequence suffix) {
requireNonNull(f, "f");
requireNonNull(delimiter, "delimiter");
requireNonNull(prefix, "prefix");
requireNonNull(suffix, "suffix");
return this.map.entrySet().stream().map(e -> f.apply(e.getKey(), e.getValue()))
.collect(Collectors.joining(delimiter, prefix, suffix));
}
/**
* As a new, sorted List.
*
* <p>
* To sort by multiplicity, descending:<br>
* <code>multiset.toList((a, b) -> b.getValue() - a.getValue())</code>
*/
public List<T> toList(final Comparator<Map.Entry<T, Integer>> comparator) {
if (null == comparator)
return this.stream().collect(Collectors.toList());
return this.entries().sorted(comparator)
.flatMap(e -> IntStream.range(0, e.getValue()).<T> mapToObj(x -> e.getKey()))
.collect(Collectors.toList());
}
/**
* Streams each element and it's multiplicity. The returned entries are immutable. Mutable entries
* can be accessed using: {@code this.asMap().entrySet()}
*/
@SuppressWarnings("unchecked")
public Stream<Map.Entry<T, Integer>> entries() {
final Stream<Entry<T, Integer>> stream = this.map.entrySet().stream();
if (this.isUnmodifiable())
return stream;
return stream.map(SimpleImmutableEntry::new);
}
@Override
public boolean addAll(final Collection<? extends T> c) {
requireNonNull(c, "c");
if (c instanceof Multiset)
return this.addAll((Multiset<? extends T>) c);
return super.addAll(c);
}
/** @see #addAll(Collection) */
public boolean addAll(final Multiset<? extends T> ms) {
for (final Entry<? extends T, Integer> e : ms.map.entrySet()) {
final Integer val = e.getValue();
this.map.merge(e.getKey(), val, Integer::sum);
this.size += val;
}
this.checkSize();
return ms.size() != 0;
}
/**
* Two {@link Multiset}s are equal if both contain the same elements with the same multiplicities.
*/
@Override
public boolean equals(final Object obj) {
if (obj instanceof Multiset) {
final Multiset<?> other = (Multiset<?>) obj;
return this.size == other.size && this.map.equals(other.map);
}
return false;
}
@Override
public int hashCode() {
return this.size ^ this.map.hashCode();
}
@Override
public void clear() {
if (this.size == 0)
return;
this.map.clear();
this.size = 0;
this.checkSize();
}
/**
* Creates a clone. The cloned multiset is modifiable.
*/
@Override
protected Object clone() {
return new Multiset<>(this);
}
@Override
public boolean containsAll(final Collection<?> c) {
requireNonNull(c, "c");
if (c instanceof Multiset)
this.map.keySet().containsAll(((Multiset<?>) c).map.keySet());
return this.map.keySet().containsAll(c);
}
@Override
public boolean isEmpty() {
return this.size == 0;
}
/** Process each object only once, with the multiplicity given as a second parameter. */
public void forEach(final ObjIntConsumer<T> action) {
this.map.forEach(action::accept);
}
@Override
public boolean contains(final Object obj) {
return this.map.containsKey(obj);
}
/**
* The intersection of two multisets. This is equal to
* <code>this.{@link #merge(Multiset, IntBinaryOperator) merge}(set, {@link Math#min(int, int) Math::min})</code>
* . However, the type of the elements in the provided multiset does not matter.
*/
@SuppressWarnings("unchecked")
public Multiset<T> intersect(final Multiset<?> set) {
requireNonNull(set, "set");
return this.merge((Multiset<T>) set, Math::min);
}
/**
* The union of two multisets. This is equal to
* <code>this.{@link #merge(Multiset, IntBinaryOperator) merge}(set, {@link Integer#sum(int, int) Integer::sum})</code>
*
* <p>
* Note: A different definition of <i>union</i> would use {@link Math#max(int, int)} with
* {@link #merge(Multiset, IntBinaryOperator)}.
*
* @see #addAll(Collection)
*/
public Multiset<T> union(final Multiset<? extends T> set) {
requireNonNull(set, "set");
return this.merge(set, Integer::sum);
}
public <S> Multiset<S> union(final Multiset<? extends S> set, final Class<S> supertype) {
requireNonNull(set, "set");
requireNonNull(supertype, "supertype");
return this.merge(set, Integer::sum, supertype);
}
/**
* The relative complement of this and a given multiset.
*
* @see #removeAll(Collection)
*/
public Multiset<T> minus(final Multiset<? extends T> set) {
requireNonNull(set, "set");
final Multiset<T> result = new Multiset<>(this);
if (set.isEmpty())
return result;
result.removeAll(set);
return result;
}
/**
* Create new multiset from this and another multiset. The given operation will calculate the new
* multiplicity for all elements.
*
* <p>
* This pseudo-code illustrates how the operation is used to create a new multiset. In this case
* the result is equal to the result of {@link #union(Multiset)}. <code><pre>
* mset1 = [ a, a, a, b ];
* mset2 = [ b, c ];
* union = m1.merge(m2, Integer::sum);
* // m3 = [ a, a, a, b, b, c ]
* </pre></code>
*/
public Multiset<T> merge(final Multiset<? extends T> set, final IntBinaryOperator operation) {
requireNonNull(set, "set");
requireNonNull(operation, "operation");
final Multiset<T> result = new Multiset<>(this);
if (set.isEmpty() && this.isEmpty())
return result;
Stream.concat(this.map.keySet().stream(), set.map.keySet().stream()).distinct().forEach(t -> {
result.setMultiplicity(t, //
operation.applyAsInt(this.getMultiplicity(t), set.getMultiplicity(t)));
});
result.checkSize();
return result;
}
/**
* Create new multiset from this and another multiset. The given operation will calculate the new
* multiplicity for all elements.
*
* @implNote Only with assertions enabled there will be a check that all elements are assignable
* to the given supertype.
* @param set
* The other multiset
* @param operation
* the operation for the multiplicities
* @param supertype
* a supertype of both multisets
*/
@SuppressWarnings("unchecked")
public <S> Multiset<S> merge(final Multiset<? extends S> set, final IntBinaryOperator operation,
final Class<S> supertype) {
requireNonNull(set, "set");
requireNonNull(operation, "operation");
requireNonNull(supertype, "supertype");
assert this.asSet().stream().allMatch(e -> supertype.isAssignableFrom(e.getClass()));
assert set.asSet().stream().allMatch(e -> supertype.isAssignableFrom(e.getClass()));
return ((Multiset<S>) this).merge(set, operation);
}
private void readObject(final java.io.ObjectInputStream stream) throws Exception {
requireNonNull(stream, "stream").defaultReadObject();
this.checkSize();
}
/**
* Returnes an unmodifiable view of the specified {@link Multiset}.
*
* @param multiset
* the multiset for which an unmodifiable view is to be returned.
* @return an unmodifiable view of the specified map.
*/
public static <T> Multiset<T> unmodifiableMultiset(final Multiset<T> multiset) {
requireNonNull(multiset, "multiset");
if (multiset.isUnmodifiable())
return multiset;
if (multiset.isEmpty())
return emptyMultiset();
return new Multiset<>(multiset, true);
}
/**
* Checks whether this is backed by an unmodifiable map. An unmodifiable {@link Multiset} always
* has the same reference set for {@link #map} and {@link #view}.
*
* @see #unmodifiableMultiset(Multiset)
*/
public boolean isUnmodifiable() {
return this.map == this.view;
}
/**
* A map-view of this {@link Multiset}. Changes are reflected on the {@link Multiset}. However,
* when using streams or iterators it is not allowed to set the multiplicity to 0. Instead the
* entry needs to be {@link Iterator#remove() removed}.
* <p>
* Methods such as {@link Map#put}, {@link Map#clear}, and {@link Map#contains} delegated to the
* backing map of the {@link Multiset}.
*
* @see #asSet()
* @see #entries()
* */
public Map<T, Integer> asMap() {
if (this.view != null)
return this.view;
return this.view = new AbstractMap<T, Integer>() {
private Set<java.util.Map.Entry<T, Integer>> entrySet;
@Override
public Integer put(final T key, final Integer value) {
return Multiset.this.setMultiplicity(key, value);
}
@Override
public Set<java.util.Map.Entry<T, Integer>> entrySet() {
if (this.entrySet != null)
return this.entrySet;
return this.entrySet = new AbstractSet<Map.Entry<T, Integer>>() {
@Override
public Iterator<java.util.Map.Entry<T, Integer>> iterator() {
final Iterator<java.util.Map.Entry<T, Integer>> itr = Multiset.this.map.entrySet()
.iterator();
return new Iterator<Map.Entry<T, Integer>>() {
private Entry<T, Integer> last = null;
@Override
public boolean hasNext() {
return itr.hasNext();
}
@Override
public java.util.Map.Entry<T, Integer> next() {
return this.last = new Entry<T, Integer>() {
final Entry<T, Integer> next = itr.next();
final T t = this.next.getKey();
int v = this.next.getValue();
@Override
public T getKey() {
return this.t;
}
@Override
public Integer getValue() {
return this.v;
}
@Override
public Integer setValue(final Integer value) {
requireNonNull(value, "value");
final int val = value.intValue();
if (val < 0)
throw new IllegalArgumentException("value=" + val);
if (val == 0)
throw new IllegalArgumentException(
"Can't set multiplicity to 0. Use remove() instead!");
final int old = this.v;
Multiset.this.setMultiplicity(this.t, val);
this.v = val;
return old;
}
@Override
public final int hashCode() {
return Objects.hashCode(this.t) ^ this.v;
}
@Override
public final boolean equals(final Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
if (Objects.equals(this.t, e.getKey())
&& Objects.equals(this.v, e.getValue()))
return true;
}
return false;
}
@Override
public String toString() {
return this.t + "=" + this.v;
}
};
}
@Override
public void remove() {
if (this.last == null)
throw new NoSuchElementException();
itr.remove();
Multiset.this.size -= this.last.getValue();
Multiset.this.checkSize();
}
};
}
@Override
public int size() {
return Multiset.this.map.size();
}
@Override
public boolean isEmpty() {
return Multiset.this.map.isEmpty();
}
@Override
public boolean contains(final Object o) {
return Multiset.this.map.keySet().contains(o);
}
@Override
public boolean add(final java.util.Map.Entry<T, Integer> e) {
// NOT SUPPORTED!!!
return Multiset.this.map.entrySet().add(e);
}
@Override
public boolean remove(final Object o) {
return Multiset.this.map.entrySet().remove(o);
}
@Override
public boolean containsAll(final Collection<?> c) {
return Multiset.this.map.entrySet().containsAll(c);
}
@Override
public void clear() {
Multiset.this.map.clear();
}
};
}
};
}
/**
* Returns a set of all elements, without multiplicity. The set is backed by the multiset, so
* changes to the multiset are reflected in the set, and vice-versa. Removing one element from the
* set removes all equal elements from the multiset. It does not support the <code>add</code> or
* <code>addAll</code>.
*
* <p>
* If using the formal definition <code>(A, m)</code> of a multiset, the returned set is
* <code>A</code> and <code>multiset::getMultiplicity</code> is <code>m</code>.
*
* @see #toSet()
* @see #asMap()
* @see #entries()
* @return set-view of all elements
*/
public Set<T> asSet() {
return this.asMap().keySet();
}
/**
* Creates a synchronized (thread-safe) collection and a synchronized map, both backed by the
* specified multiset. The collection behaves just like the specified multiset, while the map
* corresponds to {@link #asMap()}. Both data structures are modifiable and use the created
* collection as the mutex for synchronization.
*
* @see Collections#synchronizedCollection(Collection)
*
* @param set
* the multiset
* @param consumer
* accepts the collection and the map.
* @throws RuntimeException
* if the security manager does not allow to create a SynchronizedMap by reflection.
*/
@SuppressWarnings("unchecked")
public static <T> void synchronizedMultiset(final Multiset<T> set,
final BiConsumer<Collection<T>, Map<T, Integer>> consumer) throws RuntimeException {
requireNonNull(set, "set");
requireNonNull(consumer, "consumer");
try {
final Collection<T> collection = Collections.synchronizedCollection(set);
final Class<? extends Map<T, Integer>> cls = (Class<? extends Map<T, Integer>>) Class
.forName("java.util.Collections$SynchronizedMap");
final Constructor<? extends Map<T, Integer>> ctor = //
cls.getDeclaredConstructor(Map.class, Object.class);
ctor.setAccessible(true);
final Map<T, Integer> map = ctor.newInstance(set.asMap(), collection);
consumer.accept(collection, map);
} catch (InstantiationException | IllegalAccessException | IllegalArgumentException
| InvocationTargetException | NoSuchMethodException | SecurityException
| ClassNotFoundException ex) {
throw new RuntimeException("Can't create synchronized Multiset.", ex);
}
}
static Multiset<?> emptyMultiset;
/** Returns an empty multiset (unmodifiable). */
@SuppressWarnings("unchecked")
public static <T> Multiset<T> emptyMultiset() {
if (null == emptyMultiset)
return (Multiset<T>) (emptyMultiset = new Multiset<T>(true));
return (Multiset<T>) emptyMultiset;
}
}
Comments
0 B
|👍
/👎