edu.neu.ccs
Class SmallSet

java.lang.Object
  extended byedu.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