com.sdmetrics.math

Class HashMultiSet<E>

java.lang.Object

java.util.AbstractCollection<E>

com.sdmetrics.math.HashMultiSet<E>

Type Parameters:

E - the type of elements maintained by this set

All Implemented Interfaces:

java.lang.Iterable<E>, java.util.Collection<E>

public class HashMultiSet<E>
extends java.util.AbstractCollection<E>

A hash set that can contain the same element multiple times. Such sets are known as multisets or bags.

The number of times an element is contained in the multi set is called the cardinality of the element.

This implementation uses a HashMap to store the elements as keys, and their cardinality as values. Like HashMap, it is not thread safe and supports null values. Unlike HashMap, the iterator does not support removal of elements.

Constructor Summary

Constructors

Constructor and Description
HashMultiSet(java.util.Collection<? extends E> contents) Creates a new set containing all elements in the specified collection.
HashMultiSet(int capacity) Creates an empty multiset with specified initial capacity.

Method Summary

Modifier and Type	Method and Description
boolean	add(E e) Adds the specified element to this set.
void	clear() Removes all occurrences of all elements from this set.
boolean	contains(java.lang.Object o) Returns true if this set contains the specified element at least once.
boolean	equals(java.lang.Object o) Compares the specified object with this set for equality.
int	flatSetSize() Gets the number of distinct elements in this set, ignoring the cardinality of the elements.
int	getElementCount(java.lang.Object o) Retrieves the cardinality of an element in this set.
java.util.Iterator<E>	getFlatIterator() Returns an iterator over the elements in the set, ignoring the cardinality.
int	hashCode() Returns the hash code value for this set.
java.util.Iterator<E>	iterator() Returns an iterator over the elements in the set.
boolean	remove(java.lang.Object o) Removes one occurrence of the specified element from this set.
boolean	removeAll(java.util.Collection<?> c) Removes elements in this set that are also contained in the specified collection.
int	removeAny(java.lang.Object o) Removes all occurrences of an element from this set.
boolean	retainAll(java.util.Collection<?> c) Retains only the elements in this collection that are also contained in the specified collection.
int	size() Returns the number of elements in the set, respecting cardinality of the elements.

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, isEmpty, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

parallelStream, removeIf, spliterator, stream

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

HashMultiSet

public HashMultiSet(int capacity)

Creates an empty multiset with specified initial capacity. For the initial capacity, you only need to consider the number of distinct elements the set eventually holds, regardless of their cardinality.

Parameters:

capacity - the initial capacity

HashMultiSet

public HashMultiSet(java.util.Collection<? extends E> contents)

Creates a new set containing all elements in the specified collection. If the collection can contain elements multiple times (such as lists or other multi sets), the new set will respect the cardinality of the elements.

Parameters:

contents - the collection whose elements are to be placed into this set

Method Detail

iterator

public java.util.Iterator<E> iterator()

Returns an iterator over the elements in the set. Elements are returned in no particular order, however, an element of cardinality N will be returned N times.

This iterator does not support Iterator.remove().

Specified by:

iterator in interface java.lang.Iterable<E>

Specified by:

iterator in interface java.util.Collection<E>

Specified by:

iterator in class java.util.AbstractCollection<E>

Returns:

an iterator over the elements contained in this set

getFlatIterator

public java.util.Iterator<E> getFlatIterator()

Returns an iterator over the elements in the set, ignoring the cardinality. Each element in the set is returned exactly once, regardless of its cardinality.

This iterator does not support Iterator.remove().

Returns:

an iterator over the distinct elements contained in this set

size

public int size()

Returns the number of elements in the set, respecting cardinality of the elements.

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in class java.util.AbstractCollection<E>

flatSetSize

public int flatSetSize()

Gets the number of distinct elements in this set, ignoring the cardinality of the elements.

Returns:

The number of distinct elements in this set,

contains

public boolean contains(java.lang.Object o)

Returns true if this set contains the specified element at least once.

Specified by:

contains in interface java.util.Collection<E>

Overrides:

contains in class java.util.AbstractCollection<E>

getElementCount

public int getElementCount(java.lang.Object o)

Retrieves the cardinality of an element in this set.

Parameters:

o - the element to look up

Returns:

The cardinality of the element in this set, 0 if the set does not contain the element

add

public boolean add(E e)

Adds the specified element to this set. If the element is already present, its cardinality increases by one.

Specified by:

add in interface java.util.Collection<E>

Overrides:

add in class java.util.AbstractCollection<E>

Parameters:

e - element to be added to this set

Returns:

true (as specified by Collection.add(E))

remove

public boolean remove(java.lang.Object o)

Removes one occurrence of the specified element from this set. If the element is present more than once, its cardinality is decreased by one. If it is present only once, it is removed entirely from the set.

Specified by:

remove in interface java.util.Collection<E>

Overrides:

remove in class java.util.AbstractCollection<E>

Parameters:

o - Element of which one occurrence is to be removed from this set.

Returns:

true if the element was present in the set

removeAll

public boolean removeAll(java.util.Collection<?> c)

Removes elements in this set that are also contained in the specified collection. For each occurrence of an element in the specified collection, the cardinality of that element is decreased by one in this set.

Let the cardinality of element e be n>0 in this set, and assume the element is returned m≥0 times by the iterator of the specified collection. After the operation,

• if m<n, the cardinality of element e in this set is n-m
• if m≥n, all occurrences of e have been removed from this set

Specified by:

removeAll in interface java.util.Collection<E>

Overrides:

removeAll in class java.util.AbstractCollection<E>

retainAll

public boolean retainAll(java.util.Collection<?> c)

Retains only the elements in this collection that are also contained in the specified collection.

Let the cardinality of element e be n>0 in this set, and assume the element is returned m≥0 times by the iterator of the specified collection. After the operation,

• if m<n, the cardinality of element e in this set is m
• if m≥n, the cardinality of element e in this set remains unchanged at n

Specified by:

retainAll in interface java.util.Collection<E>

Overrides:

retainAll in class java.util.AbstractCollection<E>

clear

public void clear()

Removes all occurrences of all elements from this set. The set will be empty after this call returns.

Specified by:

clear in interface java.util.Collection<E>

Overrides:

clear in class java.util.AbstractCollection<E>

removeAny

public int removeAny(java.lang.Object o)

Removes all occurrences of an element from this set.

Parameters:

o - The element to remove

Returns:

The cardinality of the element before the call, 0 if the set did not contain the element

equals

public boolean equals(java.lang.Object o)

Compares the specified object with this set for equality. Returns true if the given object is a collection of the same size (both flat and respecting cardinality), and each element in this set has the same number of occurrences in the specified collection.

Note: if the specified object is not itself a HashMultiSet, we may have this.equals(o) but this.hashCode()!=o.hashCode().

Specified by:

equals in interface java.util.Collection<E>

Overrides:

equals in class java.lang.Object

Parameters:

o - object to be compared for equality with this set

Returns:

true if the specified object is equal to this set

hashCode

public int hashCode()

Returns the hash code value for this set.

This implementation takes the sum of hashCode(e)^cardinality(e) over all elements in the set.

Specified by:

hashCode in interface java.util.Collection<E>

Overrides:

hashCode in class java.lang.Object