

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object edu.neu.ccs.util.SmallSet
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.
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 1bit
in position i and a 0bit 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 0bit
in position i and a 1bit 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 (size1) . 
private static int[] 
HIBITS
The integer HIBITS[i] has a 1bit
in the positions from i to
31 and a 0bit 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 1bit
in the positions from 0 to
i and a 0bit 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 1bits 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 1bit in position i. 
static int 
getCoBitMask(int i)
Returns the integer with exactly one 0bit in position i. 
static int 
getHiBitMask(int i)
Returns the integer with 1bits in precisely the positions from i to 31. 
static int 
getLoBitMask(int i)
Returns the integer with 1bits 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 1bits 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 spaceseparated 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 
public static final int MIN
public static final int MAX
public static final int MAXSIZE
public static final int MASK
private static int[] BITS
The integer BITS[i]
has a 1bit
in position i
and a 0bit elsewhere.
private static int[] COBITS
The integer BITS[i]
has a 0bit
in position i
and a 1bit elsewhere.
private static int[] LOBITS
The integer LOBITS[i]
has a 1bit
in the positions from 0
to
i
and a 0bit elsewhere.
private static int[] HIBITS
The integer HIBITS[i]
has a 1bit
in the positions from i
to
31
and a 0bit elsewhere.
private int hash
private int size
private boolean bitsValid
The boolean that records whether or not the bit arrays associated with this set have been constructed and are valid.
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 (size1)
.
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 elementmaximum
 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 elementmaximum
 the maximum elementdata
 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 elementmax
 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 elementmax
 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 elementmax
 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
nonempty 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 1bits 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 spaceseparated 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 ab
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 1bit 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 0bit 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 1bits 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 1bits in precisely
the positions from i to 31.
Returns 0 if i is not between 0 and 31.
 Parameters:
i
 the bit position
Overview
Package
Class
Use
Tree
Deprecated
Index
PREV CLASS
NEXT CLASS
FRAMES
NO FRAMES
SUMMARY: NESTED  FIELD  CONSTR  METHOD
DETAIL: FIELD  CONSTR  METHOD