mathCollection
Class BitMathIntSet

java.lang.Object
  mathCollection.BitMathIntSet

All Implemented Interfaces:

java.lang.Cloneable, java.io.Serializable

public class BitMathIntSet

extends java.lang.Object

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

This class represents mathematical sets with integer elements and is backed by an instance of BitSet. It offers destructive as well as non-destructive mathematical set manipulation methods and features several performance tweaks like cached hash code values and cardinality values.

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.

See Also:

BitSet, Serialized Form

Nested Class Summary

private class

BitMathIntSet.BitMathIntSetIterator An iterator class that returns every int element of this set as an Integer object.

Field Summary

private boolean	isConcurrentlyModified Used to check, whether this mathematical set was modified by an destructive method while iterating over it.
private java.util.BitSet	myBitSet The backing instance of BitSet 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	storedMinimum Acts as a cache for the smallest element of this set out of performance considerations.
private int	storedSize Acts as a cache for the cardinality value of this set out of performance considerations.

Constructor Summary

BitMathIntSet()
Constructs a new, empty mathematical set; the backing BitSet's initial size is large enough to explicitly store integers in the range 0 through 63.

BitMathIntSet(int nBits)
Constructs a new, empty mathematical set; the backing BitSet's initial size is large enough to explicitly store ints in the range 0 through nBits - 1.

BitMathIntSet(int[] intArray)
Constructs a new mathematical set containing the integer values from the specified array.

Method Summary

boolean	add(int bitIndex) Adds the specified element to this set if not already present.
boolean	addAll(BitMathIntSet set) Adds all of the integers in the specified BitMathIntSet to this mathematical set.
void	clear() Removes all elements from this set.
java.lang.Object	clone() Returns a complete copy of this BitMathIntSet instance.
boolean	contains(int bitIndex) Returns true if this set contains the specified integer.
BitMathIntSet	difference(BitMathIntSet set) Returns the asymmetric difference between this mathematical set and the specified set.
boolean	equals(java.lang.Object o) Compares the specified object with this set for equality.
int	getMaximum() Returns the highest integer value in this set (its maximum).
int	getMinimum() Returns the smallest integer value in this set (its minimum).If this set is empty then -1 is returned.
int	getNext(int bitIndex) Returns the smallest integer value in this set which is equal or greater than the specified integer (the next integer value).
int	hashCode() Returns the hash code value for this mathematical set.
BitMathIntSet	intersection(BitMathIntSet set) Returns the intersection with the specified set.
boolean	isDisjoint(BitMathIntSet set) Returns true if this mathematical set has no common elements with the specified set.
boolean	isEmpty() Returns true if this set contains no integers.
boolean	isSubset(BitMathIntSet set) Returns true if this mathematical set is a subset of the specified set.
boolean	isSuperset(BitMathIntSet set) Returns true if this mathematical set is a superset of the specified set.
java.util.Iterator	iterator() Returns an iterator over the integers in this mathematical set.
boolean	remove(int bitIndex) Removes the specified integer from this set if present.
boolean	removeAll(BitMathIntSet set) Removes from this mathematical set all of its integers that are contained in the specified BitMathIntSet.
boolean	retainAll(BitMathIntSet set) Retains only the integers in this mathematical set that are contained in the specified BitMathIntSet.
int	size() Returns the number of integers in this set (its cardinality).
BitMathIntSet	symmetricDifference(BitMathIntSet set) Returns the symmetric difference between this mathematical set and the specified set.
int[]	toArray() Returns an array with the elements of this set, sorted in ascending order.
java.lang.String	toString() Returns a string representation of this mathematical set.
BitMathIntSet	union(BitMathIntSet set) Returns the union with the specified set.

Methods inherited from class java.lang.Object

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

Field Detail

myBitSet

private java.util.BitSet myBitSet

The backing instance of BitSet 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 cardinality value of this set out of performance considerations. Whenever this set is changed, storedSize is set to -1 and gets updated as soon as the size() method is called.

storedMinimum

private int storedMinimum

Acts as a cache for the smallest element of this set out of performance considerations. Whenever a destructive method is called and the new value for storedMinimum cannot be determined in constant time, storedMinimum is set to -1 and gets updated as soon as the getMinimum() method is called.

isConcurrentlyModified

private boolean isConcurrentlyModified

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

Constructor Detail

BitMathIntSet

public BitMathIntSet()

Constructs a new, empty mathematical set; the backing BitSet's initial size is large enough to explicitly store integers in the range 0 through 63.

BitMathIntSet

public BitMathIntSet(int nBits)

Constructs a new, empty mathematical set; the backing BitSet's initial size is large enough to explicitly store ints in the range 0 through nBits - 1.

Parameters:

nBits - the initial size of the backing BitSet.

Throws:

java.lang.NegativeArraySizeException - if the specified initial size of the backing BitSet is negative.

BitMathIntSet

public BitMathIntSet(int[] intArray)

Constructs a new mathematical set containing the integer values from the specified array.

Parameters:

intArray - the array containing the integer values.

Throws:

java.lang.IndexOutOfBoundsException - if an integer in the specified array is negative.

Method Detail

iterator

public java.util.Iterator iterator()

Returns an iterator over the integers in this mathematical set. The values are returned as Integer objects in ascending order.

Returns:

an Iterator over the integers in this mathematical set.

See Also:

ConcurrentModificationException

hashCode

public int hashCode()

Returns the hash code value for this mathematical set. This ensures that s1.equals(s2) implies that s1.hashCode()==s2.hashCode() for any two mathematical 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 backing BitSet.

Returns:

the hash code value for this mathematical set.

size

public int size()

Returns the number of integers in this set (its cardinality).

This implementation first checks whether a cached cardinality value is available. If not (i.e. storedSize is -1), the cardinality gets calculated using size() of the backing BitSet.

Returns:

the number of integers in this set (its cardinality).

getMinimum

public int getMinimum()

Returns the smallest integer value in this set (its minimum).If this set is empty then -1 is returned.

This implementation first checks whether a cached minimum value is available. If not (i.e. storedMinimum is -1), the minimum gets calculated using nextSetBit(0) of the backing BitSet.

Returns:

the smallest integer value of this set (its minimum).

getMaximum

public int getMaximum()

Returns the highest integer value in this set (its maximum). If this set is empty then -1 is returned.

Returns:

the highest integer value in this set (its maximum).

getNext

public int getNext(int bitIndex)

Returns the smallest integer value in this set which is equal or greater than the specified integer (the next integer value). If no such integer value exists then -1 is returned.

Parameters:

bitIndex - the index to start checking from (inclusive).

Returns:

the next integer value up from bitIndex.

Throws:

java.lang.IndexOutOfBoundsException - if the specified index is negative.

isEmpty

public boolean isEmpty()

Returns true if this set contains no integers.

Returns:

true if this set contains no integers, false otherwise.

clone

public java.lang.Object clone()

Returns a complete copy of this BitMathIntSet instance.

Returns:

a copy of this mathematical set.

toArray

public int[] toArray()

Returns an array with the elements of this set, sorted in ascending order.

Returns:

an sorted array with the elements of this set.

toString

public java.lang.String toString()

Returns a string representation of this mathematical set. The string representation consists of a list of the set's integers in the order they are returned by its iterator, enclosed in curly brackets ("{}"). Adjacent elements are separated by the characters ", " (comma and space).

Returns:

a string representation of this mathematical set.

clear

public void clear()

Removes all elements from this set.

contains

public boolean contains(int bitIndex)

Returns true if this set contains the specified integer.

Parameters:

bitIndex - integer whose presence in this set is to be tested.

Returns:

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

Throws:

java.lang.IndexOutOfBoundsException - if the specified index is negative.

add

public boolean add(int bitIndex)

Adds the specified element to this set if not already present.

Parameters:

bitIndex - integer to be added to this set.

Returns:

true if the set did not already contain the specified integer, false otherwise.

Throws:

java.lang.IndexOutOfBoundsException - if the specified index is negative.

remove

public boolean remove(int bitIndex)

Removes the specified integer from this set if present.

Parameters:

bitIndex - integer to be removed from this set, if present.

Returns:

true if the set contained the specified integer, false otherwise.

Throws:

java.lang.IndexOutOfBoundsException - if the specified index is negative.

addAll

public boolean addAll(BitMathIntSet set)

Adds all of the integers in the specified BitMathIntSet to this mathematical set.

This implementation adds all of the integers by calling or() of the backing BitSet.

Parameters:

set - mathematical set whose integers are to be added to this set.

Returns:

true if this mathematical set changed as a result of the call, false otherwise.

retainAll

public boolean retainAll(BitMathIntSet set)

Retains only the integers in this mathematical set that are contained in the specified BitMathIntSet. In other words, removes from this mathematical set all of its elements that are not contained in the specified BitMathIntSet.

This implementation retains all of the integers by calling and() of the backing BitSet.

Parameters:

set - integers to be retained in this mathematical set.

Returns:

true if this mathematical set changed as a result of the call, false otherwise.

removeAll

public boolean removeAll(BitMathIntSet set)

Removes from this mathematical set all of its integers that are contained in the specified BitMathIntSet.

This implementation removes all of the integers by calling andNot() of the backing BitSet.

Parameters:

set - integers to be removed from this mathematical set.

Returns:

true if this mathematical set changed as a result of the call, false otherwise.

equals

public boolean equals(java.lang.Object o)

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

Parameters:

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

Returns:

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

isSubset

public boolean isSubset(BitMathIntSet set)

Returns true if this mathematical set is a subset of the specified set. That is, if all elements of this mathematical set are also present in the specified set.

Parameters:

set - set to be checked for being a superset.

Returns:

true if this mathematical set is a subset of the specifed set, false otherwise.

isSuperset

public boolean isSuperset(BitMathIntSet set)

Returns true if this mathematical set is a superset of the specified set. That is, if all elements of the specified set are also present in this mathematical set.

Parameters:

set - set to be checked for being a subset.

Returns:

true if this mathematical set is a superset of the specifed set, false otherwise.

isDisjoint

public boolean isDisjoint(BitMathIntSet set)

Returns true if this mathematical set has no common elements with the specified set.

This implementation calls intersects() of the backing BitSet.

Parameters:

set - set to be checked for common integers.

Returns:

true if this mathematical set has no common elements with the specifed set, false otherwise.

union

public BitMathIntSet union(BitMathIntSet set)

Returns the union with the specified set. This is a new BitMathIntSet containing all integers that are present in this mathematical set or in the specified set.

Parameters:

set - set to be united with this one.

Returns:

the union with the specified set.

intersection

public BitMathIntSet intersection(BitMathIntSet set)

Returns the intersection with the specified set. This is a new BitMathIntSet containing all integers that are present in this mathematical set as well as in the specified set.

Parameters:

set - set to be intersected with this one.

Returns:

the intersection with the specified set.

difference

public BitMathIntSet difference(BitMathIntSet set)

Returns the asymmetric difference between this mathematical set and the specified set. This is a new BitMathIntSet containing all integers that are present in this mathematical set but not in the specified set.

Parameters:

set - set which gets subtracted from this mathematical set.

Returns:

the difference with the specified set.

symmetricDifference

public BitMathIntSet symmetricDifference(BitMathIntSet set)

Returns the symmetric difference between this mathematical set and the specified set. This is a new BitMathIntSet containing all integers that are present either in this mathematical set or in the specified set but not in both.

Parameters:

set - set from which the symmetric difference is calculated.

Returns:

the symmetric difference with the specified set.