mathCollection
Class HashMultiset

java.lang.Object
  java.util.AbstractCollection
      mathCollection.AbstractMultiset
          mathCollection.HashMultiset

All Implemented Interfaces:

java.lang.Cloneable, java.util.Collection, Multiset, java.io.Serializable

public class HashMultiset

extends AbstractMultiset

implements Multiset, java.lang.Cloneable, java.io.Serializable

This class implements the Multiset interface, backed by a hash map (specifically, a HashMap instance).

Equal elements are returned in successive order, whereas different elements have no specific iteration order; in particular, it is not guaranteed that the element order will remain constant over time. Multiple copies of the same element only require as much memory as a single instance of it. This class permits the null element.

Note that this implementation is not synchronized. If multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set. If no such object exists, the set should be "wrapped" using the MathCollections.synchronizedMultiset method. This is best done at creation time, to prevent accidental unsynchronized access to the HashMultiset instance:

     Multiset mus = MathCollections.synchronizedMultiset(new HashMultiset(...));
 

See Also:

Collection, Multiset, AbstractMultiset, HashMap, Serialized Form

Nested Class Summary

private class

HashMultiset.HashMultisetIterator An iterator that, in spite of the specific element storage technique in a Multiset (equal elements get 'counted' instead of each being stored separately), iterates over individual Multiset elements.

Field Summary

private boolean	isConcurrentlyModified Used to check, whether this multiset was modified by an destructive method while iterating over it.
private java.util.HashMap	myHashMap The backing instance of HashMap where the elements of this set are stored.
private int	storedHashCode Acts as a cache for the hash code value of this set out of performance considerations.
private int	storedSize Acts as a cache for the size value of this set out of performance considerations.

Constructor Summary

HashMultiset()
Constructs a new, empty multiset; the backing HashMap instance has default initial capacity (16) and load factor (0.75).

HashMultiset(java.util.Collection c)
Constructs a new multiset containing the elements in the specified collection.

HashMultiset(int initialCapacity)
Constructs a new, empty multiset; the backing HashMap instance has specified initial capacity and default load factor (0.75).

HashMultiset(int initialCapacity, float loadFactor)
Constructs a new, empty multiset; the backing HashMap instance has specified initial capacity and load factor.

Method Summary

boolean	add(java.lang.Object o) Adds the specified element to this multiset.
boolean	add(java.lang.Object o, int quantity) Adds the specified element quantity of times to this multiset.
void	clear() Removes all elements from this set.
java.lang.Object	clone() Returns a shallow copy of this HashMultiset instance: the elements themselves are not cloned.
boolean	contains(java.lang.Object o) Returns true if this set contains the specified element.
Multiset	difference(java.util.Collection c) Returns the asymmetric difference between this multiset and the specified collection.
boolean	equals(java.lang.Object o) Compares the specified object with this multiset for equality.
int	getQuantity(java.lang.Object o) Returns the number of times the specified element is present in this multiset.
int	hashCode() Returns the hash code value for this multiset.
Multiset	intersection(java.util.Collection c) Returns the intersection with the specified collection.
boolean	isEmpty() Returns true if this multiset contains no elements.
boolean	isSuperset(java.util.Collection c) Returns true if this multiset is a superset of the specified collection.
java.util.Iterator	iterator() Returns an iterator over the elements in this multiset.
boolean	remove(java.lang.Object o) Removes the specified element from this multiset if it is present.
boolean	remove(java.lang.Object o, int quantity) Removes the specified element quantity of times from this multiset if possible.
boolean	setQuantity(java.lang.Object o, int quantity) Adjusts the number of times the specified element is present in this multiset to be the specified value (zero if the value is negative).
int	setSize() Returns the size of a 'flattened' version of this multiset in which every element of this multiset is present exactly once.
int	size() Returns the number of elements in this multiset (its cardinality).
Multiset	sum(java.util.Collection c) Returns the sum with the specified collection.
Multiset	symmetricDifference(java.util.Collection c) Returns the symmetric difference between this multiset and the specified collection.
java.util.Set	toSet() Returns a new Set containing the 'flattened' version of this multiset in which every element of this multiset is present exactly once.
Multiset	union(java.util.Collection c) Returns the union with the specified collection.

Methods inherited from class mathCollection.AbstractMultiset

isDisjoint, isSubset, toString

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, removeAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

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

Methods inherited from interface mathCollection.Multiset

isDisjoint, isSubset

Methods inherited from interface java.util.Collection

addAll, containsAll, removeAll, retainAll, toArray, toArray

Field Detail

myHashMap

private java.util.HashMap myHashMap

The backing instance of HashMap where the elements of this set are stored.

storedHashCode

private int storedHashCode

Acts as a cache for the hash code value of this set out of performance considerations. Whenever this set is changed, storedHashCode is set to 0 and gets updated as soon as the hashCode() method is called.

storedSize

private int storedSize

Acts as a cache for the size value of this set out of performance considerations. The value of storedSize is always up-to-date since it gets updated by all destructive methods in this class.

isConcurrentlyModified

private boolean isConcurrentlyModified

Used to check, whether this multiset was modified by an destructive method while iterating over it.

Constructor Detail

HashMultiset

public HashMultiset()

Constructs a new, empty multiset; the backing HashMap instance has default initial capacity (16) and load factor (0.75).

HashMultiset

public HashMultiset(java.util.Collection c)

Constructs a new multiset containing the elements in the specified collection. The backing HashMap instance is created with default load factor (0.75) and an initial capacity sufficient to contain the elements in the specified collection.

Parameters:

c - the collection whose elements are to be placed into this multiset.

Throws:

java.lang.NullPointerException - if the specified collection is null.

HashMultiset

public HashMultiset(int initialCapacity)

Constructs a new, empty multiset; the backing HashMap instance has specified initial capacity and default load factor (0.75). Note that the backing HashMap only stores single copies of equal elements.

Parameters:

initialCapacity - the initial capacity for distinct elements.

Throws:

java.lang.IllegalArgumentException - if the initial capacity is negative.

HashMultiset

public HashMultiset(int initialCapacity,
                    float loadFactor)

Constructs a new, empty multiset; the backing HashMap instance has specified initial capacity and load factor. Note that the backing HashMap only stores single copies of equal elements.

Parameters:

initialCapacity - the initial capacity for distinct elements.

loadFactor - the load factor.

Throws:

java.lang.IllegalArgumentException - if the initial capacity is negative or the load factor is nonpositive.

Method Detail

iterator

public java.util.Iterator iterator()

Returns an iterator over the elements in this multiset. Different elements are returned in no particular order, however, equal elements are always returned subsequently.

Specified by:

iterator in interface java.util.Collection

Returns:

an Iterator over the elements in this multiset.

See Also:

ConcurrentModificationException

hashCode

public int hashCode()

Returns the hash code value for this multiset. To get the hash code of this multiset, new hash code values for every element of this multiset are calculated from a polynomial of 3rd order and finally summed up. This ensures that s1.equals(s2) implies that s1.hashCode()==s2.hashCode() for any two multisets s1 and s2, as required by the general contract of Object.hashCode().

This implementation first checks whether a cached hash code value is available. If not (i.e. storedHashCode is zero), the hash code gets calculated using hashCode() of the super class.

Specified by:

hashCode in interface java.util.Collection

Overrides:

hashCode in class AbstractMultiset

Returns:

the hash code value for this multiset.

clone

public java.lang.Object clone()

Returns a shallow copy of this HashMultiset instance: the elements themselves are not cloned.

Returns:

a shallow copy of this multiset.

isEmpty

public boolean isEmpty()

Returns true if this multiset contains no elements.

Specified by:

isEmpty in interface java.util.Collection

Returns:

true if this multiset contains no elements, false otherwise.

size

public int size()

Returns the number of elements in this multiset (its cardinality).

Specified by:

size in interface java.util.Collection

Returns:

the number of elements in this multiset (its cardinality).

clear

public void clear()

Removes all elements from this set.

Specified by:

clear in interface java.util.Collection

contains

public boolean contains(java.lang.Object o)

Returns true if this set contains the specified element.

Specified by:

contains in interface java.util.Collection

Parameters:

o - element whose presence in this set is to be tested.

Returns:

true if this set contains the specified element, false otherwise.

add

public boolean add(java.lang.Object o)

Adds the specified element to this multiset.

This implementation sets storedHashCode to 0 (representing an unavailable hash code value), which forces hashCode() to recalculate the actual hash code value.

Specified by:

add in interface java.util.Collection

Parameters:

o - element to be added to this set.

Returns:

true, adding an element to a multiset will always be a success.

add

public boolean add(java.lang.Object o,
                   int quantity)

Adds the specified element quantity of times to this multiset. If quantity is negative or 0, the multiset remains unchanged and false is returned.

If the set gets altered, this implementation sets storedHashCode to 0 (representing an unavailable hash code value), which forces hashCode() to recalculate the actual hash code value.

Specified by:

add in interface Multiset

Parameters:

o - element to be added to this set.

quantity - quantity of elements to add.

Returns:

true if quantity is greater than 0, false otherwise

remove

public boolean remove(java.lang.Object o)

Removes the specified element from this multiset if it is present. If the element is present more than once, its quantity gets decreased by one.

If the set gets altered, this implementation sets storedHashCode to 0 (representing an unavailable hash code value), which forces hashCode() to recalculate the actual hash code value.

Specified by:

remove in interface java.util.Collection

Parameters:

o - object to be removed from this multiset, if present.

Returns:

true if the multiset contained the specified element, false otherwise.

remove

public boolean remove(java.lang.Object o,
                      int quantity)

Removes the specified element quantity of times from this multiset if possible. If quantity is negative or 0, the multiset remains unchanged and false is returned.

If the set gets altered, this implementation sets storedHashCode to 0 (representing an unavailable hash code value), which forces hashCode() to recalculate the actual hash code value.

Specified by:

remove in interface Multiset

Parameters:

o - object to be removed from this multiset, if present.

quantity - quantity of elements to remove.

Returns:

true if the multiset got altered, false otherwise.

equals

public boolean equals(java.lang.Object o)

Compares the specified object with this multiset for equality. Returns true if the specified object is also a multiset, the two sets have the same size, and every element of the specified set is contained in this set the same number of times.

This implementation first checks if the given object is a HashMultiset. If so, the hash code values of this multiset and the specified HashMultiset are compared. Since the hash code values are being cached, this represents a quick solution if the sets aren't equal. However, if the hash code values are equal, it cannot be assumed that the sets themselves are equal, since different sets can have the same hash code value. In this case, the sets are compared on a per-element basis using the super method equals.

Specified by:

equals in interface java.util.Collection

Overrides:

equals in class AbstractMultiset

Parameters:

o - object to be compared for equality with this multiset.

Returns:

true if the specified object is equal to this multiset, false otherwise.

getQuantity

public int getQuantity(java.lang.Object o)

Returns the number of times the specified element is present in this multiset.

Specified by:

getQuantity in interface Multiset

Parameters:

o - element whose quantity is returned.

Returns:

quantity of the specified element, 0 if it is not present.

See Also:

setQuantity(java.lang.Object, int)

setQuantity

public boolean setQuantity(java.lang.Object o,
                           int quantity)

Adjusts the number of times the specified element is present in this multiset to be the specified value (zero if the value is negative).

This implementation sets storedHashCode to 0 (representing an unavailable hash code value), which forces hashCode() to recalculate the actual hash code value.

Specified by:

setQuantity in interface Multiset

Parameters:

o - element whose quantity gets set.

quantity - quantity of the specified element to be set.

Returns:

true if this multiset has been modified, false otherwise.

See Also:

getQuantity(java.lang.Object)

toSet

public java.util.Set toSet()

Returns a new Set containing the 'flattened' version of this multiset in which every element of this multiset is present exactly once.

Specified by:

toSet in interface Multiset

Returns:

the 'flattened' version of this multiset.

setSize

public int setSize()

Returns the size of a 'flattened' version of this multiset in which every element of this multiset is present exactly once.

Specified by:

setSize in interface Multiset

Returns:

the size of the 'flattened' version of this multiset.

isSuperset

public boolean isSuperset(java.util.Collection c)

Returns true if this multiset is a superset of the specified collection. That is, if all elements of the specified collection are also present in this multiset at least the same number of times.

This implementation checks if the specified collection is an instance of Multiset or Set. If so, the result of the super method isSuperset is returned. Otherwise, it tries to create the intersection of this HashMultiset and the specified Collection c by iterating over c and adding common elements to a new multiset. If an element is found whose quantity in the current intersection multiset is greater or equal than in this HashMultiset, false is returned. If the intersection can be built up completely, this HashMultiset is a superset of c and true is returned.

Specified by:

isSuperset in interface Multiset

Overrides:

isSuperset in class AbstractMultiset

Parameters:

c - collection to be checked for being a subset.

Returns:

true if this multiset is a superset of the specifed collection, false otherwise.

See Also:

AbstractMultiset.isSubset(Collection)

sum

public Multiset sum(java.util.Collection c)

Returns the sum with the specified collection. This is a new Multiset containing all elements that are present in this multiset or in the specified collection. The quantities of equal elements get added up.

Specified by:

sum in interface Multiset

Parameters:

c - collection to be united with.

Returns:

the union with the specified collection.

union

public Multiset union(java.util.Collection c)

Returns the union with the specified collection. This is a new HashMultiset containing all elements that are present in this multiset or in the specified collection. For equal elements, the resulting quantity is the maximum of the two given quantities.

Specified by:

union in interface Multiset

Parameters:

c - collection to be united with.

Returns:

the union with the specified collection.

intersection

public Multiset intersection(java.util.Collection c)

Returns the intersection with the specified collection. This is a new HashMultiset containing all elements that are present in this multiset as well as in the specified collection. For equal elements, the resulting quantity is the minimum of the two given quantities.

Specified by:

intersection in interface Multiset

Parameters:

c - collection to be intersected with.

Returns:

the intersection with the specified collection.

difference

public Multiset difference(java.util.Collection c)

Returns the asymmetric difference between this multiset and the specified collection. This is a new HashMultiset containing all elements that are present in this multiset but not in the specified collection. The quantities of equal elements get subtracted.

Specified by:

difference in interface Multiset

Parameters:

c - collection from which the difference is calculated.

Returns:

the difference with the specified collection.

symmetricDifference

public Multiset symmetricDifference(java.util.Collection c)

Returns the symmetric difference between this multiset and the specified collection. This is a new HashMultiset containing all elements that are present either in this multiset or in the specified collection but not in both. The quantities of equal elements get subtracted from each other (maximum minus minimum).

Specified by:

symmetricDifference in interface Multiset

Parameters:

c - collection from which the symmetric difference is calculated

Returns:

the symmetric difference with the specified collection.