edu.neu.ccs
Class SmallSet

java.lang.Object
  edu.neu.ccs.SmallSet

All Implemented Interfaces:

Comparable, Stringable

public class SmallSet

extends Object

implements Comparable, Stringable

Class SmallSet is a class that represents a set of int values between 0 and 31 as the bits in a single int state. This implements as a class the traditional bit representation of a small set.

The internal int state representation of the set as bits is returned by the getState method and also by the hashCode method.

Using the appropriate constructor, one can restrict the set to contain elements between given minimum and maximum elements rather than cover the full range from 0 to 31.

The method makeNextSubset provides an efficient mechanism for iterating through the subsets of a set.

Since:

2.6.0

Version:

2.6.0

Field Summary

private int[]	bits If bitsValid is true, then this array will contain the bit masks BITS[i] that correspond to the elements i in this set.
private static int[]	BITS The integer BITS[i] has a 1-bit in position i and a 0-bit elsewhere.
private boolean	bitsValid The boolean that records whether or not the bit arrays associated with this set have been constructed and are valid.
private static int[]	COBITS The integer BITS[i] has a 0-bit in position i and a 1-bit elsewhere.
private int	hash The representation of the set as an integer which equals its hash code.
private int[]	hibits If bitsValid is true, then this array will contain in position i the sum of the bit masks bits[j] for j from i to (size-1).
private static int[]	HIBITS The integer HIBITS[i] has a 1-bit in the positions from i to 31 and a 0-bit elsewhere.
private int[]	lobits If bitsValid is true, then this array will contain in position i the sum of the bit masks bits[j] for j from 0 to i.
private static int[]	LOBITS The integer LOBITS[i] has a 1-bit in the positions from 0 to i and a 0-bit elsewhere.
private int	mask The bit mask representing all possible elements permitted in this set.
static int	MASK The bit MASK with all 1's bits.
private int	masksize The number of 1 bits in mask.
static int	MAX The maximum set value in any set.
private int	maximum The maximum element permitted in this set.
static int	MAXSIZE The maximum number of elements in a set.
static int	MIN The minimum set value in any set.
private int	minimum The minimum element permitted in this set.
private int	size The number of elements in this set, that is, the count of 1-bits in the representation.

Constructor Summary

SmallSet()
The default constructor that creates an empty set with minimum element 0 and maximum element 31.

SmallSet(int minimum, int maximum)
The default constructor that creates an empty set with the given minimum and maximum elements.

SmallSet(int minimum, int maximum, String data)
The constructor that makes a set with the given minimum and maximum whose elements are initialized by the data in the given String.

SmallSet(SmallSet set)
The constructor that makes a clone of the given set.

SmallSet(String data)
The constructor that makes a set with minimum 0 and maximum 31 whose elements are initialized by the data in the given String.

Method Summary

boolean	addElement(int element) Adds the given element to this set provided that the element is in the range from minimum to maximum.
boolean	addElements(int[] elements) Adds the elements from the given array of elements to this set.
boolean	addRange(int min, int max) Adds the elements from min to max inclusive to this set but omits any elements that fall outside the set bounds minimum and maximum.
int	compareTo(Object object) If the given object is a SmallSet, then returns -1, 0, +1 depending on whether this set precedes the given set, is equal to the given set, or follows the given set.
void	complement() Replaces the set by its complement relative to the range from minimum to maximum.
boolean	contains(SmallSet set) Returns true if this set contains the given set as a subset.
boolean	equals(Object object) Returns true if the given Object is an instance of SmallSet and if both sets have the same elements.
protected void	fillBits() Fills the first size slots in the arrays bits, lobits, and hibits, as described in the comments for these member data variables.
void	fromStringData(String data) Initializes this set from the data in the given String.
static int	getBitMask(int i) Returns the integer with exactly one 1-bit in position i.
static int	getCoBitMask(int i) Returns the integer with exactly one 0-bit in position i.
static int	getHiBitMask(int i) Returns the integer with 1-bits in precisely the positions from i to 31.
static int	getLoBitMask(int i) Returns the integer with 1-bits in precisely the positions from 0 to i.
int	getMaximum() Returns the maximum permitted element in this set.
int	getMinimum() Returns the minimum permitted element in this set.
int	getState() Returns the integer state of this set.
boolean	hasElement(int element) Returns true if this set has the given element as one of its elements.
int	hashCode() Returns the integer state of this set.
boolean	intersectSet(SmallSet set) Replaces this set with the intersection of this set and the given set.
boolean	isEmpty() Returns true if this set is empty.
boolean	isFull() Returns true if this set is full, that is, if it contains all values between minimum and maximum.
boolean	isSubset(SmallSet set) Returns true if this set is a subset of the given set.
void	makeEmpty() Make this set empty.
void	makeFull() Make this set full.
boolean	makeNextSubset(SmallSet subset) Takes the given subset of this set and changes its state so that it is the next subset of this set relative to the compareTo comparison operation.
boolean	pruneElement(int element) Prunes the given element from this set provided that the element is in the range from minimum to maximum.
boolean	pruneElements(int[] elements) Prunes the elements from the given array of elements from this set.
boolean	pruneRange(int min, int max) Prunes the elements from min to max inclusive from this set.
boolean	pruneSet(SmallSet set) Prunes this set by removing the elements in common with the given set, that is, replaces this set by its set difference with the given set.
protected void	resetCount() Resets the internal size variable to equal the number of 1-bits in the integer set representation.
boolean	setState(int state) Sets the integer state of this set.
boolean	setToElement(int element) Sets this set to have the given element as its only element provided that the element is in the range from minimum to maximum.
boolean	setToElements(int[] elements) Sets the elements of this set to the elements from the given array of elements.
boolean	setToRange(int min, int max) Sets the elements of this set to the elements from min to max inclusive.
int	size() Returns the size of this set.
int[]	toArray() Returns an array with the integers in this set sorted in increasing order.
boolean	toggleElement(int element) If the given element is in the set then prune it, otherwise add it.
String	toString() Returns a space-separated list of the elements in the set.
String	toStringData() Identical to toString.
boolean	unionSet(SmallSet set) Adds the given set to this set but omits any elements in the given set that fall outside the bounds of this set.

Methods inherited from class java.lang.Object

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

Field Detail

MIN

public static final int MIN

The minimum set value in any set.

See Also:

Constant Field Values

MAX

public static final int MAX

The maximum set value in any set.

See Also:

Constant Field Values

MAXSIZE

public static final int MAXSIZE

The maximum number of elements in a set.

See Also:

Constant Field Values

MASK

public static final int MASK

The bit MASK with all 1's bits.

See Also:

Constant Field Values

BITS

private static int[] BITS

The integer BITS[i] has a 1-bit in position i and a 0-bit elsewhere.

COBITS

private static int[] COBITS

The integer BITS[i] has a 0-bit in position i and a 1-bit elsewhere.

LOBITS

private static int[] LOBITS

The integer LOBITS[i] has a 1-bit in the positions from 0 to i and a 0-bit elsewhere.

HIBITS

private static int[] HIBITS

The integer HIBITS[i] has a 1-bit in the positions from i to 31 and a 0-bit elsewhere.

hash

private int hash

The representation of the set as an integer which equals its hash code.

size

private int size

The number of elements in this set, that is, the count of 1-bits in the representation.

bitsValid

private boolean bitsValid

The boolean that records whether or not the bit arrays associated with this set have been constructed and are valid.

bits

private int[] bits

If bitsValid is true, then this array will contain the bit masks BITS[i] that correspond to the elements i in this set.

The bit masks will be in increasing order and will be in the first size slots.

All methods that change the state of this set will make the boolean bitsValid false.

This array will be constructed only if needed for use in the method makeNextSubset. If constructed, it will be reused.

lobits

private int[] lobits

If bitsValid is true, then this array will contain in position i the sum of the bit masks bits[j] for j from 0 to i.

The bit masks will be in the first size slots.

All methods that change the state of this set will make the boolean bitsValid false.

This array will be constructed only if needed for use in the method makeNextSubset. If constructed, it will be reused.

hibits

private int[] hibits

If bitsValid is true, then this array will contain in position i the sum of the bit masks bits[j] for j from i to (size-1).

The bit masks will be in the first size slots.

All methods that change the state of this set will make the boolean bitsValid false.

This array will be constructed only if needed for use in the method makeNextSubset. If constructed, it will be reused.

minimum

private int minimum

The minimum element permitted in this set.

maximum

private int maximum

The maximum element permitted in this set.

mask

private int mask

The bit mask representing all possible elements permitted in this set.

masksize

private int masksize

The number of 1 bits in mask.

Constructor Detail

SmallSet

public SmallSet()

The default constructor that creates an empty set with minimum element 0 and maximum element 31.

SmallSet

public SmallSet(String data)

The constructor that makes a set with minimum 0 and maximum 31 whose elements are initialized by the data in the given String.

See fromStringData for a discussion of how the String data is read.

Parameters:

data - the data to initialize the set

SmallSet

public SmallSet(int minimum,
                int maximum)

The default constructor that creates an empty set with the given minimum and maximum elements.

Suitable error checking will be done to force minimum and maximum to fall between 0 and 31 and to be in order.

Parameters:

minimum - the minimum element

maximum - the maximum element

SmallSet

public SmallSet(int minimum,
                int maximum,
                String data)

The constructor that makes a set with the given minimum and maximum whose elements are initialized by the data in the given String.

Suitable error checking will be done to force minimum and maximum to fall between 0 and 31 and to be in order.

See fromStringData for a discussion of how the String data is read.

Parameters:

minimum - the minimum element

maximum - the maximum element

data - the data to initialize the set

SmallSet

public SmallSet(SmallSet set)

The constructor that makes a clone of the given set.

Parameters:

set - to clone

Method Detail

size

public final int size()

Returns the size of this set.

getMinimum

public final int getMinimum()

Returns the minimum permitted element in this set.

getMaximum

public final int getMaximum()

Returns the maximum permitted element in this set.

isEmpty

public final boolean isEmpty()

Returns true if this set is empty.

isFull

public final boolean isFull()

Returns true if this set is full, that is, if it contains all values between minimum and maximum.

makeEmpty

public final void makeEmpty()

Make this set empty.

makeFull

public final void makeFull()

Make this set full.

setState

public final boolean setState(int state)

Sets the integer state of this set.

The state set restricts the elements to be between the minimum and the maximum.

Returns true if the internal state has changed.

Parameters:

state - the state for the set

getState

public final int getState()

Returns the integer state of this set.

Identical to hashCode.

hasElement

public final boolean hasElement(int element)

Returns true if this set has the given element as one of its elements.

Parameters:

element - the element to check

addElement

public final boolean addElement(int element)

Adds the given element to this set provided that the element is in the range from minimum to maximum.

Returns true if the internal state has changed.

Parameters:

element - the element to add

pruneElement

public final boolean pruneElement(int element)

Prunes the given element from this set provided that the element is in the range from minimum to maximum.

Returns true if the internal state has changed.

Parameters:

element - the element to prune

toggleElement

public final boolean toggleElement(int element)

If the given element is in the set then prune it, otherwise add it.

Normally, returns true. However, returns false if element is not in the range from minimum to maximum.

Parameters:

element - the element to toggle

setToElement

public final boolean setToElement(int element)

Sets this set to have the given element as its only element provided that the element is in the range from minimum to maximum.

Returns true if the internal state has changed.

Parameters:

element - the element to set

addElements

public final boolean addElements(int[] elements)

Adds the elements from the given array of elements to this set. Omits any elements that fall outside the set bounds minimum and maximum.

Returns true if the internal state has changed.

Parameters:

elements - the elements to place in this set

pruneElements

public final boolean pruneElements(int[] elements)

Prunes the elements from the given array of elements from this set.

Returns true if the internal state has changed.

Parameters:

elements - the elements to place in this set

setToElements

public final boolean setToElements(int[] elements)

Sets the elements of this set to the elements from the given array of elements. Omits any elements that fall outside the set bounds minimum and maximum.

Returns true if the internal state has changed.

Parameters:

elements - the elements to place in this set

addRange

public final boolean addRange(int min,
                              int max)

Adds the elements from min to max inclusive to this set but omits any elements that fall outside the set bounds minimum and maximum.

Returns true if the internal state has changed.

Parameters:

min - the minimum element

max - the maximum element

pruneRange

public final boolean pruneRange(int min,
                                int max)

Prunes the elements from min to max inclusive from this set.

Returns true if the internal state has changed.

Parameters:

min - the minimum element

max - the maximum element

setToRange

public final boolean setToRange(int min,
                                int max)

Sets the elements of this set to the elements from min to max inclusive. Omits any elements that fall outside the set bounds minimum and maximum.

Returns true if the internal state has changed.

Parameters:

min - the minimum element

max - the maximum element

unionSet

public final boolean unionSet(SmallSet set)

Adds the given set to this set but omits any elements in the given set that fall outside the bounds of this set.

Returns true if the internal state has changed.

Parameters:

set - the set to add to this set

intersectSet

public final boolean intersectSet(SmallSet set)

Replaces this set with the intersection of this set and the given set.

Returns true if the internal state has changed.

Parameters:

set - the set to intersect with this set

pruneSet

public final boolean pruneSet(SmallSet set)

Prunes this set by removing the elements in common with the given set, that is, replaces this set by its set difference with the given set.

Returns true if the internal state has changed.

Parameters:

set - the set to prune from this set

complement

public final void complement()

Replaces the set by its complement relative to the range from minimum to maximum.

The set is always changed by this operation.

contains

public final boolean contains(SmallSet set)

Returns true if this set contains the given set as a subset.

Does not test whether or not the two sets have the same bounds.

Parameters:

set - the set to test

isSubset

public final boolean isSubset(SmallSet set)

Returns true if this set is a subset of the given set.

Does not test whether or not the two sets have the same bounds.

Parameters:

set - the set to test

hashCode

public final int hashCode()

Returns the integer state of this set.

Identical to getState.

equals

public final boolean equals(Object object)

Returns true if the given Object is an instance of SmallSet and if both sets have the same elements.

Does not test whether or not the two sets have the same bounds.

compareTo

public final int compareTo(Object object)

If the given object is a SmallSet, then returns -1, 0, +1 depending on whether this set precedes the given set, is equal to the given set, or follows the given set.

Throws ClassCastException if the given object is not a SmallSet.

The details of the computation are as follows. Let set represent the given object cast to SmallSet.

If this set equals set, return 0.

Next, order sets by size:

If this set has more elements than set, return +1.

If this set has less elements than set, return -1.

Otherwise, order sets of the same size as follows. Consider the largest bit index i such that this set and set disagree at that index. Then if i is an element of this set return +1 and if i is an element of set return -1.

An equivalent way to think about set ordering is that sets of the same size are ordered according to their ordering as unsigned integers. In Java this is a bit more complicated to compute than need be because unsigned integer is not a supported type in Java.

Does not test whether or not the two sets have the same bounds.

Specified by:

compareTo in interface Comparable

makeNextSubset

public final boolean makeNextSubset(SmallSet subset)

Takes the given subset of this set and changes its state so that it is the next subset of this set relative to the compareTo comparison operation.

Returns true if and only if the state of the subset has indeed changed.

Returns false and does nothing if:

• The given subset is null.
• The given subset equals this set.
• The given subset is not actually a subset of this set.
• The given subset does not have the same bounds as this set.

The following code illustrates how to iterate over the non-empty subsets of a set named s.

     int min = s.getMinimum();
     int max = s.getMaximum();
 
     SmallSet subset = new SmallSet(min, max);    // start empty
 
     while (s.makeNextSubset(subset)) {
         // do some task with the next subset
     }

Parameters:

subset - the subset to change to the next subset

resetCount

protected final void resetCount()

Resets the internal size variable to equal the number of 1-bits in the integer set representation.

fillBits

protected final void fillBits()

Fills the first size slots in the arrays bits, lobits, and hibits, as described in the comments for these member data variables.

Does nothing if bitsValid is already true.

toArray

public final int[] toArray()

Returns an array with the integers in this set sorted in increasing order. The array length is equal to the size of this set.

toString

public final String toString()

Returns a space-separated list of the elements in the set. The list is enclosed in braces: {}.

toStringData

public final String toStringData()

Identical to toString.

Specified by:

toStringData in interface Stringable

See Also:

Stringable.fromStringData(String)

fromStringData

public final void fromStringData(String data)

Initializes this set from the data in the given String.

Expects a list consisting of individual numbers a between minimum and maximum or number pairs a-b representing a range between minimum and maximum.

The list should be separated by spaces and/or commas.

The list may optionally be enclosed in braces: {}.

For robustness, this method will ignore numbers outside the range minimum and maximum as well as any parse exceptions.

Specified by:

fromStringData in interface Stringable

Parameters:

data - the string data to define the set

See Also:

Stringable.toStringData()

getBitMask

public static int getBitMask(int i)

Returns the integer with exactly one 1-bit in position i.

Returns 0 if i is not between 0 and 31.

Parameters:

i - the bit position

getCoBitMask

public static int getCoBitMask(int i)

Returns the integer with exactly one 0-bit in position i.

Returns 0 if i is not between 0 and 31.

Parameters:

i - the bit position

getLoBitMask

public static int getLoBitMask(int i)

Returns the integer with 1-bits in precisely the positions from 0 to i.

Returns 0 if i is not between 0 and 31.

Parameters:

i - the bit position

getHiBitMask

public static int getHiBitMask(int i)

Returns the integer with 1-bits in precisely the positions from i to 31.

Returns 0 if i is not between 0 and 31.

Parameters:

i - the bit position