More information on the BitSet assignment
P.J. Drongowski
16 September 2004
You will need to use the C++ binary operators:
& Bit-wise AND
| Bit-wise OR
~ Bit-wise NOT
>> Right shift
<< Left shift
to implement the BitSet module (class.) The C++ binary operators
work just like the Java binary operators. However, you must pay
attention to the length of the integer that represents the set.
You really need to know how numbers are represented in a (machine)
integer and can apply that knowledge.
************************************************************************
Here are some examples to help you understand the representation
of a finite set using BitSet and the method functions that operate
on a BitSet object:
Remember, we are trying to represent finite sets of positive integers.
If the set we want to represent is { 0 1 4 7 } and the set size is 8,
then the internal representation is:
Bit index: 76543210
------------------------
currentMembers: 10010011 setSize: 8
Let's assume that this set is stored in the BitSet object s. Then,
s.isEmpty() ; // returns FALSE (0)
s.getSize() ; // returns 8
s.getMembers() ; // returns 0x93
s.isMember(6) ; // returns FALSE (0)
s.isMember(4) ; // returns TRUE (1)
s.printMembers() ; // displays "{ 0 1 4 7 }"
Next, let's apply the makeMember function to s:
s.makeMember(3) ; // adds a new member (3) to set s
s.printMembers() ; // displays "{ 0 1 3 4 7 }"
Now apply the makeMembers function to s:
s.makeMembers(0x00) ; // makes the set s empty
s.isEmpty() ; // returns TRUE (1)
s.printMembers() ; // displays "{ }" cuz the set is empty
************************************************************************
Here is an informal specification for the BitSet interface. You will
need to build and test to this specification.
Function: BitSet() ;
Purpose: Creates a new BitSet object; the size of the new
bit set is the maximum allowed size and the set is empty
(no set elements/members)
Parameters:
None
Returns:
Nothing
Side-effects:
Changes currentMembers and setSize
Error conditions:
None
Function: BitSet(int initialSize) ;
Purpose: Creates a new BitSet object; the size of the new
bit set is the specified size and the set is empty (no
set elements/members)
Parameters:
initialSize: Number of elements allowed in the new set
Returns:
Nothing
Side-effects:
Changes currentMembers and setSize
Error conditions:
Specified set size is greater than MAX_SET_SIZE
Function: BitSet(unsigned long int initialMembers, int initialSize) ;
Purpose: Creates a new BitSet object; the size of the new
bit set is the specified size and the set contains the initial
set elements as specified by the bits in initialMembers
Parameters:
initialMembers: Bits that specify the initial members of the new set
ititialSize: Number of elements allowed in the new set
Returns:
Nothing
Side-effects:
Changes currentMembers and setSize
Error conditions:
Specified set size is greater than MAX_SET_SIZE
Function: int getSize() ;
Purpose: Accessor function to return the size of the bit set
(i.e., the number of elements/members that can be represented in the
bit set, not the number of elements/members in the bit set)
Parameters:
None
Returns:
The allowed size of the bit set
Side-effects:
None
Error conditions:
None
Function: void makeMembers(unsigned long int newMembers) ;
Purpose: Mutator function that sets the current members of the set
to the specified new members; This function effectively assigns
new members to the set -- it does not perform a union between the
current members and new members; The new members replace the
current members
Parameters:
newMembers: Bits that specify the new elements/members of the set
Returns:
Nothing
Side-effects:
Changes currentMembers
Error conditions:
Parameter may specify members outside those allowed by the current
set size
Function: unsigned long int getMembers() ;
Purpose: Accessor function that returns the current members of the set
Parameters:
None
Returns:
The current members of the set (as encoded)
Side-effects:
None
Error conditions:
None
Function: void printMembers() ;
Purpose: Displays the current members of the set in a readable form
using standard set notation, e.g., { 0 3 4 7 8 }
Parameters:
None
Returns:
Nothing
Side-effects:
None
Error conditions:
None
Function: bool isMember(int i) ;
Purpose: Determines if the positive integer i is a member/element of
the set
Parameters:
i: Positive integer value to be tested; could be out of the allowed
range of integer values that can be represented in the bit set
Returns:
Returns true if i is a member/element of the set; returns false if
i is not a member of the set
Side-effects:
None
Error conditions:
To be determined (TBD) by you!
Function: void makeMember(int i) ;
Purpose: Adds the positive integer i to the current members of the set
Parameters:
i: Positive integer value to be added to the set; could be out of
the allowed range of integer values that can be represented in the
bit set
Returns:
Nothing
Side-effects:
Changes currentMembers
Error conditions:
To be determined (TBD) by you!
Function: void setUnion(const BitSet &a, const BitSet &b) ;
Purpose: Forms the union of the two argument sets and stores the result
in the current BitSet object, i.e., the members/elements of the current
BitSet object will contain the union of the two sets
Parameters:
a: The first operand to the union operation (a reference parameter)
b: The second operand to the union operation (a reference parameter)
Returns:
Nothing
Side-effects:
Changes currentMembers, may change setSize to account for argument
sets of different sizes
Error conditions:
To be determined (TBD) by you!
Function: void setIntersection(const BitSet &a, const BitSet &b) ;
Purpose: Forms the intersection of the two argument sets and stores the
result in the current BitSet object, i.e., the members/elements of the
current BitSet object will contain the intersection of the two sets
Parameters:
a: The first operand to the intersection operation (a reference parameter)
b: The second operand to the intersection operation (a reference parameter)
Returns:
Nothing
Side-effects:
Changes currentMembers, may change setSize to account for argument
sets of different sizes
Error conditions:
To be determined (TBD) by you!
Function: bool isEmpty() ;
Purpose: Determines if the current set is empty
Parameters:
None
Returns:
Returns true if the current set (this) is empty; returns false if
the current set is not empty
Side-effects:
None
Error conditions:
None