Program 0: A Bitset class

The goal of this assignment is to refresh your programming skills, recall material from ECE 1574, and get familiar with the course work-flow. If you struggle with this assignment you are woefully ill-prepared for this course. This means you should devote additional time to it and seek advice from the TAs and myself, or as a last resort drop.

Description

A bitset or bit array is a simple data structure representing a set of bits, each of which which may be 0 (false) or 1 (true). Bitsets have many uses in computing and appear in several algorithms. The C++ standard library has a bitset class where the number of bits or size must be known at compile time. Our class is similar but the size of the bitset can be specified at run-time. An individual bit in the set is addressed by an index in the range 0 to size-1.

The underlying implementation of a bitset is as a dynamic array of integer types, that is one of the fixed width types. The size of the underlying array should be large enough to hold size number of bits. For example suppose you used an array of type unint8_t and N = 12, then the size of the array would need to be two (2*8 = 16 > 12).

Define and implement a class Bitset that should support:

• default construction of a valid bitset of width 8, with all bits set to 0
• construction of a valid bitset of width N, where N is of type intmax_t, with all bits set to 0, the bitset is invalid if N <= 0
• construction of a valid bitset initialized with a string of the form 00010000. If the string contains any character other than 0 or 1, the bitset is invalid.
  
• a method to return the size of the bitset
• a method to determine if the bitset is valid
• a method to set the nth bit to 1, if n not in [0, size-1] then the bitset becomes invalid
• a method to reset the nth bit to 0, if n not in [0, size-1] then the bitset becomes invalid
• a method to toggle the nth bit (1 to 0 or 0 to 1), if n not in [0,size-1] then the bitset becomes invalid
• a method to test if the nth bit is set by returning a bool value of true if set and false if not, if n not in [0,size-1] then the bitset becomes invalid and false is returned
• a method to return the bitset as a std::string of 0 or 1 characters. This should be represented left-to-right with the most significant bit first.

Note: the class is not Copy-Constructible or Copy-Assignable, since you likely do not know how to write copy constructors and assignment operators yet (you will soon). This means you will not be able to copy or assign one bitset instance to another, and as a consequence, pass one or return one by value from a function.

The outline of the class is defined in the starter code inside the file bitset.hpp as:

class Bitset{
public:

  // TODO COMMENT
  Bitset();

  // TODO COMMENT
  Bitset(intmax_t size);

  // TODO COMMENT
  Bitset(const std::string & value);

  // TODO COMMENT
  ~Bitset();

  Bitset(const Bitset & ) = delete;
  Bitset & operator=(const Bitset &) = delete;

  // TODO COMMENT
  intmax_t size() const;

  // TODO COMMENT
  bool good() const;

  // TODO COMMENT
  void set(intmax_t index);

  // TODO COMMENT
  void reset(intmax_t index);

  // TODO COMMENT
  void toggle(intmax_t index);

  // TODO COMMENT
  bool test(intmax_t index);

  // TODO COMMENT
  std::string asString() const;

private:

  // TODO 
};

Do not modify the public portion of the class definition. To ensure you understand memory management as described in ECE 1574, it is required that you manually perform allocation and deallocation of memory as part of your implementation, that is do not use std::vector or any other container in your implementation. Your implementation should not leak memory or have invalid read/writes.

You will need to define the internal members and methods (marked TODO) and implement all methods in the bitset.cpp file. You should add appropriate comment blocks to each method as well (marked TODO COMMENT) in bitset.hpp. You will need to write tests in the file bitset_test.cpp using the Catch testing framework, as described in class meeting 3. The included CMakeLists.txt file sets up everything for you. Just generate your build directory for your development environment as described in the course work-flow tutorial.

Grader

We will be using an automatic grader to help you determine your assignment's completeness and correctness. A portion of each assignment grade will be determined by the number of passing tests as determined by the autograder, with our evaluation filling in the rest. This means you know before you turn in your submission that all is well. You can submit to the autograder as many times as you like, but it is rate limited (4 submissions every hour) to keep you from using it as your compiler. See this page for a summary of how to use the grader (Note is is not WebCAT, which many of you may be familiar with).

For this assignment you should upload a zip file containing only the files: bitset.hpp, bitset.cpp, and bitset_test.cpp. There is a build target called "submission" configured by default to create this file with the correct contents in your build directory.

Submission

Once you are satisfied with your code, upload a zip file containing (only) bitset.hpp, bitset.cpp, and bitset_test.cpp through Canvas at the assignment link. You should not submit the other files from the starter code, nor your build directory. There is a build target called "submission" configured by default to create this file with the correct contents in your build directory.

Grading

There are 100 points allocated to this assignment.

• Correctly submitting the required files: 10 points
• Your tests compile: 10 points
• Your tests pass: 25 points (proportional)
• Instructor tests compile with your code: 10 points
• Instructor tests pass: 25 points (proportional)
• No tests leak memory: 10 points
• Design requirements met: 10 points (only partially assessed by grader)