mathCollection
Class HashSetOfSets

java.lang.Object
  java.util.AbstractCollection
      java.util.AbstractSet
          mathCollection.AbstractSetOfSets
              mathCollection.HashSetOfSets

All Implemented Interfaces:

java.lang.Cloneable, java.util.Collection, java.io.Serializable, java.util.Set, SetOfSets

public class HashSetOfSets

extends AbstractSetOfSets

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

This class implements the SetOfSets interface, backed by a hash table (specifically, a HashSet instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. An instance of HashMultiset is used for permanently maintaining a 'flat' version of the set of sets (a simple set containing all the elements from the elementary sets once).

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.synchronizedSetOfSets method. This is best done at creation time, to prevent accidental unsynchronized access to the HashSetOfSets instance:

    SetOfSets sos = MathCollections.synchronizedSetofSets(new HashSetofSets(...));
 

See Also:

Set, MathSet, AbstractSetOfSets, HashSet, HashMap, Serialized Form

Nested Class Summary

private static class	HashSetOfSets.Element
private class	HashSetOfSets.HashSetOfSetsIterator A 'wrapper' iterator class that uses HashSet.iterator() while accounting for the additional storedHashCode attribute.

Field Summary

private HashMultiset	flatVersion Acts as a cache for the 'flattened' multiset version of this set of sets out of performance considerations.
private java.util.HashSet	myHashSet The backing instance of HashSet 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.

Constructor Summary

HashSetOfSets()
Constructs a new, empty set of sets; the backing HashSet instance as well as the HashMap flatVersion have default initial capacity (16) and load factor (0.75).

HashSetOfSets(java.util.Collection c)
Constructs a new set of sets set containing the elements in the specified collection.

HashSetOfSets(int initialCapacity)
Constructs a new, empty set of sets; the backing HashSet instance has the specified initial capacity and default load factor, which is 0.75.

HashSetOfSets(int initialCapacity, float loadFactor)
Constructs a new, empty set of sets; the backing HashSet instance has the specified initial capacity and the specified load factor.

Method Summary

boolean	add(java.lang.Object o) Adds the specified element (Set) to this set of sets if it is not already present.
void	clear() Removes all elements from this set of sets.
java.lang.Object	clone() Returns a shallow copy of this HashSetOfSets instance: the elements themselves are not cloned.
SetOfSets	containingSets(java.lang.Object o) Returns a set containing the elementary sets from within this set of sets that contain the specified element.
boolean	contains(java.lang.Object o) Returns true if this set of sets contains the specified element (Set).
boolean	containsAtom(java.lang.Object o) Returns true if this set of sets contains a set in which the specified element is present.
boolean	equals(java.lang.Object o) Compares the specified object with this set of sets for equality.
int	hashCode() Returns the hash code value for this set of sets.
boolean	isEmpty() Returns true if this set of sets contains no elements.
java.util.Iterator	iterator() Returns an iterator over the elements in this set of sets.
boolean	remove(java.lang.Object o) Removes the specified element (Set) from this set of sets if it is present.
int	size() Returns the number of elements (contained sets) in this set of sets (its cardinality).
SetOfSets	sortedArraySupersets(java.util.Set s) Returns a new set containing the supersets of the specified set.
SetOfSets	subsets(java.util.Set s) Returns a new set containing the subsets of the specified set.
SetOfSets	supersets(java.util.Set s) Returns a new set containing the supersets of the specified set.
Multiset	toMultiset() Returns the 'flattened' multiset version of this set of sets, containing the same elements as in all sets of this set of sets.
java.util.Set	toSet() Returns the 'flattened' version of this set of sets, in which every element from the elementary sets is present once.

Methods inherited from class mathCollection.AbstractSetOfSets

toString

Methods inherited from class java.util.AbstractSet

removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Set

addAll, containsAll, removeAll, retainAll, toArray, toArray

Field Detail

myHashSet

private java.util.HashSet myHashSet

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

flatVersion

private HashMultiset flatVersion

Acts as a cache for the 'flattened' multiset version of this set of sets out of performance considerations. The contents of flatVersion are always up-to-date since they get updated by all destructive methods in this class.

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.

Constructor Detail

HashSetOfSets

public HashSetOfSets()

Constructs a new, empty set of sets; the backing HashSet instance as well as the HashMap flatVersion have default initial capacity (16) and load factor (0.75).

HashSetOfSets

public HashSetOfSets(java.util.Collection c)

Constructs a new set of sets set containing the elements in the specified collection. The HashSet 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 set.

Throws:

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

HashSetOfSets

public HashSetOfSets(int initialCapacity)

Constructs a new, empty set of sets; the backing HashSet instance has the specified initial capacity and default load factor, which is 0.75.

Parameters:

initialCapacity - the initial capacity of the hash set.

Throws:

java.lang.IllegalArgumentException - if the initial capacity is less than zero.

HashSetOfSets

public HashSetOfSets(int initialCapacity,
                     float loadFactor)

Constructs a new, empty set of sets; the backing HashSet instance has the specified initial capacity and the specified load factor.

Parameters:

initialCapacity - the initial capacity of the hash set.

loadFactor - the load factor of the hash set.

Throws:

java.lang.IllegalArgumentException - if the initial capacity is less than zero, or if the load factor is nonpositive.

Method Detail

iterator

public java.util.Iterator iterator()

Returns an iterator over the elements in this set of sets. The elements are returned in no particular order.

Specified by:

iterator in interface java.util.Set

Returns:

an iterator over the elements in this set of sets.

See Also:

ConcurrentModificationException

hashCode

public int hashCode()

Returns the hash code value for this set of sets. To get the hash code of this set of sets, new hash code values for every element of this set of sets 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 sets 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.Set

Overrides:

hashCode in class AbstractSetOfSets

Returns:

the hash code value for this set of sets.

clone

public java.lang.Object clone()

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

Returns:

a shallow copy of this set.

isEmpty

public boolean isEmpty()

Returns true if this set of sets contains no elements.

Specified by:

isEmpty in interface java.util.Set

Returns:

true if this set of sets contains no elements, false otherwise.

size

public int size()

Returns the number of elements (contained sets) in this set of sets (its cardinality).

Specified by:

size in interface java.util.Set

Returns:

the number of elements in this set of sets (its cardinality).

clear

public void clear()

Removes all elements from this set of sets.

Specified by:

clear in interface java.util.Set

add

public boolean add(java.lang.Object o)

Adds the specified element (Set) to this set of sets if it is not already present.

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 SetOfSets

Parameters:

o - element to be added to this set of sets.

Returns:

true if the set of sets did not already contain the specified element, false otherwise.

Throws:

java.lang.ClassCastException - if the type of the specified element is incompatible (!(o instanceof Set)).

remove

public boolean remove(java.lang.Object o)

Removes the specified element (Set) from this set of sets if it is present.

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 SetOfSets

Parameters:

o - object to be removed from this set of sets, if present.

Returns:

true if the set of sets contained the specified element, false otherwise.

Throws:

java.lang.ClassCastException - if the type of the specified element is incompatible (!(o instanceof Set)).

contains

public boolean contains(java.lang.Object o)

Returns true if this set of sets contains the specified element (Set).

Specified by:

contains in interface SetOfSets

Parameters:

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

Returns:

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

Throws:

java.lang.ClassCastException - if the type of the specified element is incompatible (!(o instanceof Set)).

equals

public boolean equals(java.lang.Object o)

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

This implementation first checks if the given object is a HashSetOfSets. If so, the hash code values of this set of sets and the specified HashSetOfSets 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 result of the super method equals() is returned.

Specified by:

equals in interface java.util.Set

Parameters:

o - object to be compared for equality with this set of sets.

Returns:

true if the specified object is equal to this set of sets, false otherwise.

containsAtom

public boolean containsAtom(java.lang.Object o)

Returns true if this set of sets contains a set in which the specified element is present.

Specified by:

containsAtom in interface SetOfSets

Overrides:

containsAtom in class AbstractSetOfSets

Parameters:

o - the element whose presence in any elementary set within this set of sets is tested for.

Returns:

true if any set within this set of sets contains the specified element, false otherwise.

toSet

public java.util.Set toSet()

Returns the 'flattened' version of this set of sets, in which every element from the elementary sets is present once.

Specified by:

toSet in interface SetOfSets

Returns:

the 'flattened' version (simple set) of this set of sets.

toMultiset

public Multiset toMultiset()

Returns the 'flattened' multiset version of this set of sets, containing the same elements as in all sets of this set of sets.

Specified by:

toMultiset in interface SetOfSets

Returns:

the 'flattened' multiset version of this set of sets.

containingSets

public SetOfSets containingSets(java.lang.Object o)

Returns a set containing the elementary sets from within this set of sets that contain the specified element. If there are no sets containing the specified element, an empty set is returned.

Specified by:

containingSets in interface SetOfSets

Parameters:

o - the element that the returned sets have to contain.

Returns:

the elementary sets from this set of sets that contain the specified element.

subsets

public SetOfSets subsets(java.util.Set s)

Returns a new set containing the subsets of the specified set. If the specified set is empty or no supersets exist in this set, an empty set of sets is returned.

Specified by:

subsets in interface SetOfSets

Parameters:

s - the set that the returned sets have to be subsets of.

Returns:

the elementary sets from this set of sets that occur in the specified set.

supersets

public SetOfSets supersets(java.util.Set s)

Returns a new set containing the supersets of the specified set. If the specified set is empty, a copy of this set of sets is returned. If no supersets exist in this set, an empty set of sets is returned.

Specified by:

supersets in interface SetOfSets

Parameters:

s - the set that the returned sets have to be supersets of.

Returns:

the elementary sets from this set of sets that contain the specified set.

sortedArraySupersets

public SetOfSets sortedArraySupersets(java.util.Set s)

Returns a new set containing the supersets of the specified set. If the specified set is empty, a copy of this set of sets is returned. If no supersets exist in this set, an empty set of sets is returned.

This implementation is faster for large numbers of large sets. An array containing the elements of the specified set, sorted by their frequency of occurrence in this set of sets, is used to make the superset relation checks faster.

Note that this implementation requires the elements of this set of sets to have an efficient contains() method (constant complexity) to achieve the improved performance.

Parameters:

s - the set that the returned sets have to be supersets of.

Returns:

the elementary sets from this set of sets that contain the specified set.