Project 4
Spring 2009
Due: Wed, Apr 8 @ 10 PM
10 points
This project involves implementing a resizable bit set. Note that this is not a template class.
If you need a refresher on sets and set operations, check out Set (mathematics).
The class BitSet should let one store n elements from zero to n-1. Use a dynamically-allocated C-style array of unsigned ints to implement BitSet. Lists of private data members, methods, and overloaded operators appear below. Decide which methods should be public and private. Decide which methods should be const. Decide which exceptions the methods should throw. Use bad_alloc, length_error, and out_of_range from stdexcept. You can assume that methods performing operations on two BitSets do so only on BitSets of the same size. Don't worry about DOC comments. You've suffered enough.
This design is a little different—and hopefully simpler—than the one we discussed briefly in class, which included a count of the number of elements in the set. Keeping track of the number elements after various operations adds a little computational overhead, which seems unnecessary since any good class for a set should implement a method that returns the cardinality of the set (i.e., the number of elements).
As with p3, to grade your class, we will drop a main.cc file into your directory and compile it, so it is critically important that you implement the methods as directed.
| Data Member | Description |
| unsigned n | The capacity of the set |
| unsigned sz | The number of unsigned ints in the array |
| unsigned bps | Bits per segment |
| unsigned *bits | Pointer to the dynamically allocated C-style array of unsigned ints |
| Method Name | Description |
| BitSet | Default constructor |
| BitSet | Explicit constructor that creates a BitSet capable of storing n elements |
| BitSet | Copy constructor |
| resize | Resizes the BitSet to n elements |
| setAll | Sets all elements of the BitSet |
| unsetAll | Unsets all elements of the BitSet |
| empty | Returns true if the BitSet is empty |
| equal | Returns true if two BitSets are equal |
| memberOf | Returns true if the provided element is a member of the BitSet |
| cardinality | Returns the number of elements in the BitSet |
| add | Adds an element to the BitSet |
| remove | Removes an element from the BitSet |
| setunion | Performs the union of two BitSets |
| intersection | Performs the intersection of two BitSets |
| complement | Performs the absolute complement of the BitSet |
| complement | Performs the complement of the BitSet relative to another |
| difference | Performs the symmetric difference of two BitSets |
| toString | Returns a string representation of the BitSet in a set format |
| Prints the BitSet in a set format to an ostream | |
| printUnsigned | Prints the BitSet as unsigned ints |
| ~BitSet | Destructor |
| allocateBits | Allocates an array of unsigned ints sufficient for storing n elements (i.e., bits) |
| initialize | Sets all data members to zero or null |
| Operator | Description |
| operator~ | Performs the absolute complement of the BitSet |
| operator= | Performs assignment/memberwise copy |
| operator+= | Adds an element to the BitSet |
| operator-= | Removes an element from the BitSet |
| operator| | Performs the union of two BitSets and returns the result |
| operator|= | Performs the union of two BitSets |
| operator& | Performs the intersection of two BitSets and returns the result |
| operator&= | Performs the intersection of two BitSets |
| operator- | Performs the relative complement and returns the result |
| operator-= | Performs the relative complement |
| operator== | Returns true if two BitSets are equal |
| operator!= | Returns true if two BitSets at not equal |
| operator<< | stream insertion operator |
| operator>> | stream extraction operator |
Test your implementation of the BitSet class in main.cc. However, we will use our own main function to evaluate your classes. Consequently, you must not modify the class name or method names. This would also be an important consideration for any large-scale software project. Our main.cc will include only main.h, so put all necessary includes there. That is, for this project, you must have all pertinent includes for main.cc in main.h. In general, you should not need to declare any additional methods or data members.
/* * COSC 072 Project 4 * Name: <your name> * ID: <GoCard ID> * E-mail: <e-mail address> * Instructor: Maloof * TA: <TA's name> * * In accordance with the class policies and Georgetown's Honor Code, * I certify that, with the exceptions of the class resources and those * items noted below, I have neither given nor received any assistance * on this project. */
Instructions for Electronic Submission
If you need to include a message to your TA about your submission, then place the message in a file named README. Place the README file in the project's directory.
Assuming all of your code is in the subdirectory p4, directory, this directory and the submit program should be in the same directory:
seva% ls p4/ submit.jar
To reduce the size of the zip file, before submitting, remove all object and executable files:
seva% cd p4 seva% make clean
If you need to include a message to your TA or me about your submission, then place the message in a file named README. Place the README file in the project's directory.
To move from the p4 directory to the parent directory, type
seva% cd ..At this point, you should be above the p4 directory:
seva% ls p4/ submit.jar
(Additional useful Unix commands)
When you are ready to submit, change the name of the directory to your netid. For example, if your netid is maloofm, then rename the directory p4 by typing
seva% mv p4 maloofmCreate a zip file of the directory and its contents by typing
seva% zip -r p4.zip maloofm/*This command creates a zip file named p4.zip by recursively (-r) copying all of the files (*) from the directory maloofm/.
To submit the zip file type
seva% java -jar submit.jar -a p4 -f p4.zipp4 is the name of the assignment (-a) and p4.zip is the file (-f) to be submitted for that assignment.
If the program submits the file successfully, you will receive a receipt by e-mail at the address <netid>@georgetown.edu.
Submit your project only once.
Once you've submitted your project, it is important to keep an electronic copy on a university machine (e.g., seva) that preserves the modification date and time. If we lose your project or the submission system breaks, then we will need to look at the modification date and time of your project to ensure that you submitted it before it was due.
You can also change the directory's name back to the original name. For example,
seva% mv maloofm p4Note that changing the name of the directory does not change the dates of the files in the directory. You can also remove the zip file from your directory:
seva% rm p4.zip
The TA who will be grading your projects this semester is listed on the main page. You must submit your project before 5 PM on the due date.
Submit is pretty reliable, but it is software. If you're running submit correctly and you see an error message labeled as SEVERE, then it's time to execute Plan B by using mail to submit your project.
To accomplish this, assuming the file you want to submit p4.zip, type at the seva prompt
seva% uuencode p4.zip p4.zip | mail cosc072@cush.georgetown.eduBriefly, uuencode encodes the binary file p4.zip as an ASCII file that can be transmitted as mail. This form of the uuencode command pipes the ASCII-encoded file through standard input and into (|) the mail command.
When we receive you mail, we will save it to a file and use uudecode to translate the ASCII-encoded file back to the original binary file. Virtually all mail clients automatically encode binary files in this way.
Please don't use this account for communication. We don't check it regularly.
Copyright © 2019 Mark Maloof. All Rights Reserved. This material may not be published, broadcast, rewritten, or redistributed.