CS253 HW6: Templates!                

Changes                

• Added #include <cassert> to test.cc.
• Copy ctor & assignment are only defined from an Oval of the same type.
• Made Fold::operator() a const method.

Description                

For this assignment, you will implement a templated class called an Optimized Value List, or Oval (with a capital O). Like a list or vector, items in an Oval are in the order that you put them in, except … when you search for an item, that item gets moved forward, for quicker access later.                 

Your hw6.tar must contain Oval.h (with a capital O). All methods and functions will be in this header file. You will not create Oval.cc, a library, or a main() program (except for testing).                 

Template Parameters                

An Oval takes three template parameters:                 

• The type to be stored
• The amount to promote a value when find is called (default is 1). Behavior is undefined if this value is negative. Whenever you search for an element using find, it’s moved this much closer to the start of the list. The most popular items migrate to the front of the list for quick access.
• Equality comparison functor (defaults to equal_to).

Requirements for stored type                

The type stored by this templated class has the following requirements:

• Default constructor
• Copy constructor
• Assignment operator
• It is not required that ==, <, etc., be valid for the stored types. Your code must not use such operators—it must use the comparison functor, which should default to the std::equal_to functor.

Required public methods of Oval                

default constructor

Create an empty container.

copy constructor

Copy all information from the other container with the same template parameters.

constructor that takes a half-open range of two iterators

Add data items in the half-open iterator range are copied to this container, similar to most STL containers.

assignment operator

Copy all information from the other container with the same template parameters, replacing any existing data.

destructor

No memory leaks are allowed.

In the following method descriptions, value_type refers to the type stored, the first template parameter.                 

size_t size() const

Return the number of data items currently stored.

int find(const value_type &)

Look for the first instance of the given value from the start of the list to the end. Return the index of the item (the first item is 0) after that value was moved forward (toward the start of the container, toward the first item). If the item is already too far forward, move it as far as you can to the first location. Return −1 if not found.

size_t count(const value_type &) const

Return how many times the given value occurs in the container.

push_back

Works the same as vector’s push_back(). Duplicates are not treated specially.

size_t erase(const value_type &)

Erase all matching items, returns number of items erased.

void clear()

Make it have no values.

value_type & operator[](size_t)

const value_type & operator[](size_t) const

Subscripting. [0] returns a reference to the first element, [1] returns a reference to the second element, etc. Results are undefined if the subscript is out of range.

Const-correctness, for arguments, methods, and operators, is your job. For example, it must be possible to call .count() on a const object, or to copy a const object to a non-const object.                 

Don’t forget to use the comparison functor for .find(), .count(), and .erase(). Using simple == is not correct.                 

    export STACK_FRAME_LINK_OVERRIDE=ffff-ad921d60486366258809553a3db49a4a

Testing                

You will have to write a main() function to test your code. Put it in a separate file. Particularly, do not put main() in Oval.h. We will test your program by doing something like this:                 

    mkdir a-new-directory
    cd the-new-directory
    tar -x </some/where/else/hw6.tar
    cmake . && make
    cp /some/other/place/test-program.cc .
    g++ -Wall test-program.cc
    ./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 hw6.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.                 

Sample Run                

Here is a sample run, where % is my shell prompt:                 

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

# 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 executable from the source file test.cc:
add_executable(test test.cc)

# 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 "Oval.h"
#include "Oval.h"       // I meant to do that.
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>

using namespace std;

// Return a string with all the elements of this container.
template <typename T>
string cat(const T &container, string separator = "") {
    ostringstream oss;
    bool first = true;
    for (size_t i=0; i<container.size(); i++) {
        if (!first)
            oss << separator;
        first = false;
        oss << container[i];
    }
    return oss.str();
}

// case-independent comparison functor
class Fold {
  public:
    bool operator()(char a, char b) const {
        return tolower(a) == tolower(b);
    }
};

int main() {
    vector<short> initial_values = {123, 11, 22, 123, 33, 22, 123};
    Oval<int> o(initial_values.begin(), initial_values.end());
    cout << cat(o, ",") << '\n';
    auto count = o.erase(123);
    assert(count == 3);
    cout << "Erased " << count << " of 123: " << cat(o, ",") << '\n';
    count = o.erase(666);
    cout << "Erased " << count << " of 666: " << cat(o, ",") << '\n';
    assert(count == 0);
    auto n = o.find(22); cout << "find 22: " << cat(o, ",") << '\n';
    assert(n == 0);
    n = o.find(33); cout << "find 33: " << cat(o, ",") << '\n';
    assert(n == 1);
    n = o.find(99); cout << "find 99: " << cat(o, ",") << '\n';
    assert(n == -1);

    for (auto target : {11,22,66})
        cout << "count(" << target << ")=" << o.count(target) << '\n';

    string s = "BONEhea";
    Oval<char, 2, Fold> ov(s.begin(), s.end());
    ov.push_back('d');
    cout << cat(ov) << '\n';
    assert(ov.count('e') == 2);
    assert(ov.count('&') == 0);
    n = ov.find('e');
    assert(n == 1);
    assert(cat(ov) == "BEONhead");
    n = ov.find('%');
    assert(n == -1);
    assert(cat(ov) == "BEONhead");
    n = ov.find('D');
    cout << cat(ov) << '\n';
    assert(n == 5);
    assert(cat(ov) == "BEONhdea");
    n = ov.erase('e');
    assert(n == 2);
    assert(cat(ov) == "BONhda");

    cout << cat(ov) << '\n';
}
% ./test
123,11,22,123,33,22,123
Erased 3 of 123: 11,22,33,22
Erased 0 of 666: 11,22,33,22
find 22: 22,11,33,22
find 33: 22,33,11,22
find 99: 22,33,11,22
count(11)=1
count(22)=2
count(66)=0
BONEhead
BEONhdea
BONhda

Requirements                

• Your header file must have #include guards.
• Your header file must not have any using declarations.
• No memory leaks.
• You may add other methods and operators, as needed.
• You may implement the methods inside or outside of the class declaration.
• You may use the CMakeLists.txt shown, or create your own.
• You may not use any external programs. You many not use system(), fork(), popen(), execl(), execvp(), etc.
• You may not use C-style I/O, such as printf(), scanf(), fopen(), and getchar().
  • Instead, use C++ facilities such as cout, cerr, and ifstream.
• You may not use endl. Use flush if needed.
• You may not use dynamic memory via new, delete, malloc(), calloc(), realloc(), free(), strdup(), etc.
  • It’s ok to implicitly use dynamic memory via containers such as string or vector.
• You may not use the istream::eof() method.
• 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: hw6.tar
• It must contain:
  • Oval.h
  • CMakeLists.txt
• We will do this command. If you don’t have anything to build, it must successfully do nothing.

    cmake . && make

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

How to submit your work:                

In Canvas, check in the file hw6.tar to the assignment “HW6”. 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.