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