CS253 HW7: Looping!                

Changes                

Updates to the assignment will be noted here. None yet!                 

Description                

For this final assignment, you will improve on your HW5 work. You will turn it into a class named CountSort (not CountingSort). This class supports subscripting and iteration, much like standard STL containers. Even though the implementation is an array of counts, the interface that the class presents is much more similar to that of a sorted vector that contains the original data.                 

CountSort cs(10,35);
cs = {11,22,33,11,22,11};
for (auto v : cs)
    cout << v << '\n';
for (int i=0; i<cs.size(); i++)
    cout << cs[i] << '\n';

This implies the existence of the type CountSort::iterator, and the methods CountSort::begin(), CountSort::end(), CountSort::size(), and CountSort::operator[]().                 

Methods and operations                

CountSort must have these public methods & operators, where cs is a CountSort object:                 

CountSort cs(int,int);

Create a CountSort object that counts values within the given closed/inclusive range. Throw an invalid_argument object, mentioning the values, if the range is out of order.

cs = {int, …};

Replace all existing content in CountSort object with the given integers as if .insert() were called on each one.

cs.insert(int)

Insert the given integer into the object. Throw an out_of_range object, mentioning the given value and the acceptable range, if the integer is out of range for this object.

cs(int n)

Those are (round parentheses). Retrieve the n th raw count from the array of counts. For example, given CountSort cs(5,7); cs = {5,7,5,7,5};, cs(0)==3, which is how many fives have been counted. cs(1)==0, and cs(2)==2. Throw an out_of_range object, mentioning the given index and the valid range, if the index is out of range.

cs[int n]

Those are [square brackets]. Retrieve the n th int from the object, in sorted order. This is not a count; it’s the original int that was given to .insert(). [0] returns the smallest int, and [1] returns next smallest int (which may be the same value as [0], if the same value was inserted twice), and so on. For example, given CountSort cs(5,7); cs = {5,7,5,7,5};, cs[0]==5, cs[1]==5, cs[2]==5, cs[3]==7, and cs[4]==7. Throw an out_of_range object, mentioning the given index and the .size() of the object, if the index is out of range for this object.

cs.min(), cs.max()

Return the lowest and highest int values that this object can hold. These do not change over the lifetime of the object.

cs.width()

Return how many different possible int values this object can hold. This does not change over the lifetime of the object.

cs.size()

Return how many int values are currently stored in this container.

cs.empty()

Return true iff there are no values in this container.

cs.clear()

Make this container contain nothing.

cs.begin()

Return an object of type CountSort::iterator that corresponds to the smallest int currently stored in this object.

cs.end()

Return an object of type CountSort::iterator that corresponds one past the largest int currently stored in this object. Past, I say! It does not correspond to the last item, since .begin() & .end() form a half-open interval.

These operators must work, where csit is of type CountSort::iterator.                 

++csit

csit++

Increment the iterator, going to the next int (not the next count). Preincrement returns the new iterator value, and postincrement returns the previous value, in the same manner as ++ works on integers.

*csit

Yields, by value, the same kind of int that CountSort::operator[] returns. It does not return a count.

csit == csit

csit != csit

Compares two iterators for equality or inequality.

copy, assignment

Iterators are copy-constructable, and assignable.

The types and names in the descriptions, above, do not determine the C++ declarations of those methods. They only serve to informally describe what sort of arguments a method might take. For example, .empty() should return a bool, even though it wasn’t explicitly stated.                 

Const-correctness, for methods, arguments, and operators, is your job. For example, it must be possible call .size() or .begin() on const CountSort objects.                 

You may define other methods or data, public or private, as you see fit. You may define other classes, as you see fit. However, to use the CountSort class, the user need only #include "CountSort.h", not any other header files.                 

Iterator Invalidation                

A CountSort::iterator can be invalidated by:

• The corresponding CountSort object being destroyed.
• Assigning to, inserting into, or clearing the corresponding CountSort object.

    export STACK_FRAME_LINK_OVERRIDE=ffff-ad921d60486366258809553a3db49a4a

Sample Run                

% cat CMakeLists.txt
cmake_minimum_required(VERSION 3.11)
project(hw7)

# Are we in the wrong directory?
if (CMAKE_SOURCE_DIR MATCHES "[Hh][Ww]([0-9])$"
   AND NOT PROJECT_NAME MATCHES "${CMAKE_MATCH_1}$")
    message(FATAL_ERROR "Building ${PROJECT_NAME} in ${CMAKE_SOURCE_DIR}")
endif()

# Using -Wall is required:
add_compile_options(-Wall)

# These compile flags are highly recommended, but not required:
add_compile_options(-Wextra -Wpedantic)

# Optional super-strict mode:
add_compile_options(-fmessage-length=80 -fno-diagnostics-show-option
    -fstack-protector-all -g -O3 -std=c++17 -Walloc-zero -Walloca
    -Wctor-dtor-privacy -Wduplicated-cond -Wduplicated-branches
    -Werror -Wextra-semi -Wfatal-errors -Winit-self -Wlogical-op
    -Wold-style-cast -Wshadow -Wunused-const-variable=1
    -Wzero-as-null-pointer-constant)

# add_compile_options must be BEFORE add_executable.

# Create the library from CountSort.cc:
add_library(${PROJECT_NAME} CountSort.cc)

# Create the executable from the source file test.cc:
add_executable(test test.cc)
target_link_libraries(test ${PROJECT_NAME})

# Create a tar file every time:
add_custom_target(${PROJECT_NAME}.tar ALL COMMAND
    tar -cf ${PROJECT_NAME}.tar *.cc *.h CMakeLists.txt)
% cmake . && make
… cmake output appears here …
… make output appears here …
% cat test.cc
#include "CountSort.h"
#include "CountSort.h"  // I meant to do that.
#include <iostream>     // cout, cerr
#include <cassert>      // assert()
#include <cstdlib>      // malloc()

using namespace std;

// Ensure that the student is not just storing the items in a vector,
// by forbidding large allocations.

void *operator new(size_t size) {
    assert(size < 10'000);          // should never need this much
    return malloc(size);
}

void operator delete(void *p, size_t /* size */) {
    free(p);
}

void operator delete(void *p) {
    free(p);
}

int main() {
    CountSort cs(10,19);
    assert(cs.size()==0);
    assert(cs.empty());
    assert(cs.begin() == cs.end());
    cs.insert(11);
    assert(cs.size()==1);
    assert(!cs.empty());
    assert(cs.begin() != cs.end());
    cs = {11, 17, 13, 19, 19, 17, 19, 13, 17};
    assert(cs.size() == 9);
    cs.insert(19);
    // Now contains 11×1, 13×2, 17×3, 19×4.

    cout << "size: " << cs.size() << '\n';
    for (auto n : cs)
        cout << n << ' ';
    cout << '\n';
    for (int i=0; i<cs.size(); i++)
        cout << cs[i] << ' ';
    cout << '\n';
    for (int i=0; i<=cs.max()-cs.min(); i++)
        cout << cs.min()+i << 'x' << cs(i) << " ";
    cout << '\n';

    // Make sure they’re not storing all the numbers, just counts.
    for (int i=0; i<10'000; i++)
        cs.insert(15);
    // Now contains 11×1, 13×2, 15×10⁴ 17×3, 19×4.
    assert(cs.size() == 10'010);

    CountSort::iterator it = cs.begin();
    assert(*it == 11);
    assert(*it == 11);
    assert(*it == 11);
    assert(it == cs.begin());
    assert(it != cs.end());
    it++;               // now points at first 13
    assert(it != cs.begin());
    ++it;               // now points at second 13
    assert(*it == 13);
    assert(*it == 13);
    ++it;               // now points at first 15
    assert(*it == 15);
    for (int i=0; i<9'999; i++)
        it++;
    // it now points at the last 15
    assert(*it++ == 15);
    // it now points at the first 17
    assert(*it == 17);
    assert(*it == 17);
    assert(*it == 17);
    assert(*it == 17);
    assert(*it == 17);
    assert(*it == 17);

    return 0;
}
% ./test
size: 10
11 13 13 17 17 17 19 19 19 19 
11 13 13 17 17 17 19 19 19 19 
10x0 11x1 12x0 13x2 14x0 15x0 16x0 17x3 18x0 19x4 

Hints                

• CountSort—capital C, capital S. It’s a shame that these two letters don’t change shape between upper and lower case. Life is a series of trials.
• It is not the responsibility of the CountSort code to catch exceptions. The CountSort code throws the exception. It’s up to the calling code to catch the exception. If the exception is not caught, well, then, the program terminates horribly.
• Remember the separate purposes of ++ and * on an iterator. ++ goes to the next item. * returns the current item. * doesn’t move to the next item.
• Don’t confuse operator() and operator[]. They have different argument ranges, and different results.
• My test program is inadequate for your testing.

Libraries                

libhw7.a is a library file. It contains a number of *.o (object) files. It must contain CountSort.o, but it may also contain whatever other *.o files you need. The CMakeLists.txt shown creates libhw7.a. It does not contain main().                 

Testing                

You will have to write a main() function to test your code. Put it in a separate file, and do not make it part of libhw7.a. Particularly, do not put main() in CountSort.h or CountSort.cc. You will also have to create CountSort.h, and put it into hw7.tar. We will test your program by doing something like this:                 

    mkdir new-directory
    cd new-directory
    tar -x </some/where/else/hw7.tar
    cmake . && make
    cp /some/other/place/test-program.cc .
    g++ -Wall test-program.cc libhw7.a
    ./a.out

We will supply a main program to do the testing that we want. You should do something similar. It’s your choice whether to include your test program in your hw7.tar file. However, cmake . && make must work. If it fails because you didn’t package test.cc, but your CMakeLists.txt requires test.cc, then your build failed, and you get no points. Test your tar file, not just your code.                 

Requirements                

• Allocate a dynamic array of ints with new[] to hold the counts, and release it with delete[]. The array allocated must be exactly the right size needed. Other than that, no dynamic memory is allowed. No memory leaks are allowed.
• No function should call exit(), or produce any output.
• You may use the CMakeLists.txt shown, or create your own.
• Do not put using namespace std; in any header file.
• You may not use any external programs. You many not use system(), fork(), popen(), execl(), execvp(), etc.
• No global variables.
• For readability, don’t use ASCII int constants (65) instead of char constants ('A') for printable characters.
• We will compile your code like this: cmake . && make
  • If that generates warnings, you will lose a point.
  • If that generates errors, you will lose all points.
• There is no automated testing/pre-grading/re-grading.
  • Test your code yourself. It’s your job.
  • Even if you only change it a little bit.
  • Even if all you do is add a comment.
  • Test with the CSU compilers, not just your laptop’s compiler.

If you have any questions about the requirements, ask. In the real world, your programming tasks will almost always be vague and incompletely specified. Same here.                 

Tar file                

• The tar file for this assignment must be called: hw7.tar
• It must contain:
  • source files (*.cc), including CountSort.cc
  • header files (*.h), including CountSort.h
  • CMakeLists.txt, which will create the library file libhw7.a.
• These commands must produce the library libhw7.a:

    cmake . && make

• Your CMakeLists.txt must use at least -Wall when compiling.

How to submit your work:                

In Canvas, check in the file hw7.tar to the assignment “HW7”. It’s due 10:00:00ᴘᴍ MT Saturday, with a 24-hour late period for a 25% penalty.                 

How to receive negative points:                

Turn in someone else’s work.