Programming Assignment 1 C++ Programming Review

Task 1: Selection

Write a program to determine (select) the k-th largest value in a list of N values.

Requirements

Files

selection.cpp


selection.h


selection_tests.cpp



Function

int select(size_t k, const int* list, size_t N);


Input



k := the rank of the desired value, 0 < k <= N


list := the collection of values from which to select


N := the number of values in the list, N > 0


Output









The value which is the k-th largest in the list.


Exceptions



Throws std::invalid_argument if the arguments are


invalid, e.g. k is out of bounds.



Approved Includes

cstddef, iostream, stdexcept, selection.h



Tests

You must submit a test suite that, when run, covers


at least 90% of your code.


See How To Measure Coverage with Gcov








Examples

Consider the list A = [8, 6, 7, 5, 3, 0, 9].

select(2, A, 7)
returns
8
select(4, A, 7)
returns
6
select(3, A, 7)
returns
7
select(5, A, 7)
returns
5
select(6, A, 7)
returns
3
select(7, A, 7)
returns
0
select(1, A, 7)
returns
9
select(0, A, 7)
throws
std::invavlid_argument
select(8, A, 7)
throws
std::invavlid_argument
Task 2: Collection<T>

Write a class template, Collection, that stores an unordered collection of Objects1..

Requirements


Files

collection.h


collection_tests.cpp



Class

template <typename Object>


class Collection;



Member Functions

Collection();


The default constructor makes an empty Collection.


----------------------


Collection(const Collection&);


~Collection();


Collection& operator=(const Collection&);


The Rule of Three copies and destroys Collections.


----------------------


size_t size() const;


Input








None.


Output







The number of elements in the collection.


Exceptions


None.



----------------------


bool is_empty() const;









    • Object is a generic type which is assumed to have a zero-parameter (default) constructor, an operator=, and a copy constructor (and, therefore, also a destructor).

Input

None.

Output

Boolean true if and only if the collection is empty.

Exceptions

None.

----------------------

void make_empty();

Input

None.

Output

None.

Side effect: the collection is now empty.

Exceptions

None.

----------------------

void insert(const Object& obj);

Input

obj := the value to insert

Output

None.

Side effect: the collection now contains the value of obj.

Exceptions

None.

----------------------





void remove(const Object& obj);




Input










obj := the value to remove


Output


None.



Side effect: at most one element which has the same


value as obj is removed.


Exceptions


None.



----------------------



bool contains(const Object& obj) const;


Input









obj := the value to look for


Output








Boolean true if and only if an Object that is equal


to obj is present in the collection.


Exceptions


None.




Approved Includes

cstddef, iostream, stdexcept, collection.h



Tests

You must submit a test suite that, when run, covers


at least 90% of your code.


See How To Measure Coverage with Gcov








Examples

Consider the following sequence of operations with post conditions:

    1. Make a new collection of ints : Collection<int> the_collection;

        a. A variable of type Collection<int> exists.

        b. The collection is empty.

2.    Insert 8, 6, 7, 5, 3, 0, 9 : the_collection.insert(8); …

        a. The collection has 7 elements: {8,6,7,5,3,0, 9}2

        b. The elements are the digits of Jenny’s phone number

    3. Remove 8 : the_collection.remove(8);

        a. The collection has 6 elements: {6, 7, 5, 3, 0, 9}2

        b. The collection is not empty

    4. Make empty : the_collection.make_empty();

        a. The collection is empty











































    • The order of the elements in the collection does not matter.
How To Measure Coverage with Gcov


Compile with coverage

g++ -std=c++17 -g --coverage <source files>


Run

./a.out


Generate coverage report

gcov -mr <source file>


View coverage report

cat <source file>.gcov

‘-’ means the line is not executable (does not count for coverage) ‘#####’ means the line is executable but was executed 0 times ‘126’ means the line was executed 126 times

Identify lines which are not covered

grep “#####” <source file>.gcov


Clean up before next measurement

rm -f *.gcov *.gcno *.gcda
Example

$ rm -f *.gcov *.gcno *.gcda

$ g++ -std=c++17 -g --coverage selection.cpp selection_tests.cpp

    • ./a.out passed 56 / 56
ALL TESTS PASSING

    • gcov -mr selection.cpp File 'selection.cpp' Lines executed:97.83% of 46 Creating 'selection.cpp.gcov'

$ grep “#####” selection.cpp.gcov

#####:    42:    throw "whoop"; // this line is not covered

$ cat selection.cpp.gcov

-:    0:Source:selection.cpp

-:    0:Graph:selection.gcno

-:    0:Data:selection.gcda

-:    0:Runs:1

... [snip] ...

    126: 41: if (k == 2007) {

#####:    42:    throw "whoop"; // this line is not covered

-:    43: }

... [snip] ...