COMP15 Fall 20XX

**Due: Thursday, February 3, 11:00PM**

Many data structures have their basis in formal mathematics. In this assignment, you will build and test an abstract data type -- a C++ class -- to represent and manipulate small, finite sets of positive integers where the integers range from 0 to 127.

A set is represented using the "bit vector" technique where the set elements are encoded into the bits of one or more unsigned integers. Each bit stands for (represents) a single positive integer, starting from zero. If the bit is one, the corresponding positive integer is an element (member) of the set. In this case, individual bits in the vector are numbered from zero to 127. Thus, 127 is the largest positive integer that can be a member of a set and zero is the smallest.

Since only 32 bits can be represented in a single integer (an Intel IA-32 machine word), four integers are required to represent a set. These four integers are stored in a one-dimensional array. Bits within an integer are numbered sequentially from zero to 31, where bit zero is the least significant bit (LSB) and 31 is the most significant bit (MSB.) This is also the correspondence from bit to positive integer. The figure below illustrates the bit numbering and mapping for an 8-bit (8 element) set.

7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |

Bit zero at the far right is the LSB and bit seven at the far left hand side is the MSB.

The objectives for this project are:

- To learn the form of a C++ program and to extend an existing class with new functionality.
- To learn about the internal representation of integers and bit twiddling in C++.
- To become familiar and functional with the laboratory environment and its tools (the Emacs editor, the g++ compiler and so forth.)
- To begin to think systematically about program testing.

Three files are provided:

`bitset.h`, which is the declaration of the`BitSet`class and its interface,`bitset.cpp`, which is the definition of the`BitSet`class and the function`main`, and the`makefile`to build the program.

The existing implementation is incomplete. You will need to add new method functions to fully implement the interface. Here are requirements to be satisfied:

- The
`print`method displays the elements of a set. Elements must be displayed on a single line, must be surrounded by curly braces and must be separated by a space. If integers 6, 5 and 0 are elements of the set, then`print`should display "`{ 6 5 0 }`" on a single line. You must adhere to this format as your output will be checked automatically. - Study the behavior of the
`unionOf`function. It takes two sets as arguments and puts the union of the two sets into the current set (`this`object) which is the recipient of the call to`unionOf`. This approach makes the union operation look somewhat symmetric in its use. Follow this approach for the implementation of`intersectionOf`. - Add code to the function
`main`to test the`intersectionOf`function. Read and follow the pattern used to test the`unionOf`function. - Proofread and correct any existing code, if necessary.

The `makefile` will help you to build your program. To build
your program, which is called "`bitset`", change the working
directory to where your project files are stored and just type
`make` on the command line.
The `make` utility will read the `makefile`
in the current working directory and will build `bitset`. We will
discuss `make` and makefiles in more detail when preparing for
the second project.

Once you have completed the basic assignment, here are some extra things to try.

- Add a new set operation:
`isSubset`. - Extend the
`BitSet`implementation to accommodate finite sets of arbitrarily large size.

Accounts have been created for pre-registered students. To enable your account, go to the URL http://www.eecs.tufts.edu/~accounts. You will need to supply your Tufts e-mail login name and password to activate your account. If you do not have a Tufts e-mail login name or if you have a problem with account activation, please see a member of the system staff in Halligan Hall Room 231C.

We will be using the CS Department's `provide` system to submit
finished programs. The `provide` command syntax is:

provide comp15 <assignment> <files>Projects (assignments) are labelled "

provide comp15 p1 bitset.h bitset.cppBe sure you are completely satisfied with your work before submitting!

This semester we will be using the `gradebk` web service to keep
track of evaluations and scores. The URL for `gradebk` is
https://www.eecs.tufts.edu/gradebk. Please check your evaluations
within the two week period after your work has been reviewed and the
evaluation has been posted. Issues will not be considered after the two
week period has expired.

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 and initializes it to the empty state Parameters: None Returns: Nothing Side-effects: Changes the elements array Error conditions: None Function: bool isElement(int i) ; Purpose: Determines if the positive integer i is an element (member) of the mathematical set represented by the object Parameters: i: Positive integer value to be tested; The value provided by the caller could be out of the allowed range of integer values that can be represented in the bit set Returns: Returns true if i is an element of the set; returns false if i is not an element of the set Side-effects: None Error conditions: To be determined (TBD) by you! Function: void addElement(int i) ; Purpose: Adds the positive integer i to the mathematical set, that is, the positive integer i will become an element of the set Parameters: i: Positive integer value to be added to the set. The value provided by the caller could be out of the allowed range of integer values that can be represented in the bit set Returns: Nothing Side-effects: Changes the elements array Error conditions: To be determined (TBD) by you! Function: void removeElement(int i) ; Purpose: Removes the positive integer i from the mathematical set, that is, the positive integer i will no longer be an element of the set Parameters: i: Positive integer value to be removed from the set. The value provided by the caller could be out of the allowed range of integer values that can be represented in the bit set Returns: Nothing Side-effects: Changes the elements array Error conditions: To be determined (TBD) by you! Function: void print() ; Purpose: Displays the current elements of the set in a readable form using standard set notation, e.g., { 0 3 4 7 8 }. Please follow this format exactly. Parameters: None Returns: Nothing Side-effects: None Error conditions: None Function: void clear() ; Purpose: Clears the set and makes it empty Parameters: None Returns: Nothing Side-effects: Changes the elements array Error conditions: None Function: bool isEmpty() ; Purpose: Tests the current set to see if it's empty Parameters: None Returns: True if the set is empty; false if the set is not empty Side-effects: None Error conditions: None Function: bool isEqualTo(const BitSet &a) ; Purpose: Tests the current set to see if it is equal to the set given as a parameter; Equality means "has exactly the same elements." Parameters: a: Set operand (a reference parameter) Returns: True if the set a is equal to the current set; false if the set a is not equal to the current set Side-effects: None Error conditions: None Function: void unionOf(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 elements (members) of the current BitSet object will contain the union of the two sets Parameters: a: First set operand to the union operation (a reference parameter) b: Second set operand to the union operation (a reference parameter) Returns: Nothing Side-effects: Changes the elements array Error conditions: To be determined (TBD) by you! Function: void intersectionOf(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 elements (members) of the current BitSet object will contain the intersection of the two sets Parameters: a: First set operand to the intersection operation (a reference parameter) b: Second set operand to the intersection operation (a reference parameter) Returns: Nothing Side-effects: Changes the elements array Error conditions: To be determined (TBD) by you!Copyright © 2004-2013 Paul J. Drongowski