CS 311 Fall 2009
Assignment 3

Assignment 1 is due at 5 p.m. Thursday, October 1. It is worth 25 points.

Procedures

This assignment is to be done individually.

E-mail answers to the exercises below to ffggc@uaf.edu, using the subject “DA3”.

• Your answers should consist of two files: da3.h and da3.cpp, from Exercises A–E. The two files (or a single archive file containing them) should be attached to your e-mail message.
• Be sure to include your name in your e-mail.
• I may not read your homework e-mail immediately. If you wish to discuss the assignment (or anything else) with me, send me a separate message with a different subject line.

Exercises (25 pts total)

General

This assignment is to be done individually.

In each of the following five exercises, you are to write a function or function template. All five are to be in the files da3.h and da3.cpp. The templates should be implemented entirely in the header file. The non-templates should be prototyped in the header and implemented in the source, as usual.

Be sure to follow the coding standards. Standard 3A (“Requirements on template parameter types must be documented.”) and standard 3B (“If a function is not a template and not a member of a class template, then the exceptions it throws must be documented.”) now apply. You do not need to follow standards 3C or 3D.

In the files da3.h and da3.cpp, you may include any other functions or classes that you wish. These will not be tested; however, they must follow the coding standards. Also, generally, use of the C++ Standard Library is legal in this assignment; some exercises do have restrictions on how it may be used, however.

Skeleton Files

I have provided unfinished “skeleton” files da3.h and da3.cpp. You may use these as the basis for your own work, if you wish. This is not required; however, if you do not wish to use these files, you still need to copy the declaration of class LLNode from the provided da3.h.

Test Program

I have written a single test program for all five exercises: da3_test.cpp. If you compile and run your package with this program (unmodified!), then it will test whether your package works properly.

Note that your code will not compile with the test program unless at least dummy versions of all five functions are written. Therefore, you must write all five, or your work will not be graded.

Do not turn in da3_test.cpp.

Exercise A — Linked List Look-Up

Purpose

In this exercise you will write code to deal with a Linked List. The code will signal an error condition (if one occurs) by throwing an exception.

Instructions

Write a function template listItem, prototyped as

template <typename T>
T listItem(const LLNode<T> * head,
           int index);

Your file will need to include the definition of the struct template LLNode. This struct definition can be found in the unfinished file da3.h, on the web page.

Function listItem is given a pointer to a NULL-terminated Linked List (as discussed in class, and demonstrated in the file list_size.cpp) and an integer index. It functions similarly to an array bracket operator, returning the item corresponding to the index, where the first item is numbered 0, the second 1, and so on, up to size – 1, where size is the number of items in the list. The data item is to be returned by value.

If the index is out of range — negative or at least size — then listItem should throw an exception of type std::out_of_range.

Other requirements:

• The function should throw only when the index is out of range.
• If an exception is thrown, then its “what” member should return a string giving a brief description of the error.

Exercise B — Did It Throw?

Purpose

This exercise is all about calling code that may throw an exception, and catching the exception appropriately.

Instructions

Write a function template didItThrow, prototyped as

template <typename Func>
void didItThrow(Func f,
                bool & threw);

Function didItThrow is given either a function pointer, or an object that acts like a function (that is, which has operator() defined). It then calls this function with no parameters. If the function throws, then it sets parameter threw to true, and passes the exception on to the caller. If the function does not throw, then it sets paramete threw to false, and returns normally.

Example usage:

void myFunc()
{ throw std::exception("Oh no!"); }

bool result;
try {
    didItThrow(myFunc, result);
{
catch (std::exception & e) {
    if (result)
        std::cout << "SUCCESS" << std::endl;
    else
        std::cout << "FAILURE" << std::endl;
}

The above should print “SUCCESS”

Other requirements:

• Make no assumptions about the type of the exception that might be thrown by the given function.
• Make no assumptions about the return value of theFunc; it may return a value, or it may not.

Exercise C — Print Range

Purpose

In this exercise you are to write a function that takes iterators as parameters and processes a range of data.

Instructions

Write a function template printRange, prototyped as

template <typename FDIter>
void printRange(FDIter first,
                FDIter last,
                std::ostream & theStream);

Parameters first and last are two forward iterators specifying a range in the standard manner. Function printRange should print each item in the range to the give stream, using operator<< Each item should be followed by a newline.

Example usage:

std::vector<int> v;
v.push_back(47);
v.push_back(59);
v.push_back(105);
printRange(v.begin(), v.end(), std::cout);

The above should print

47
59
105

Exercise D — Check Equality of Ranges in One Line

Purpose

This exercise requires you to research and use an STL algorithm that you may be unfamiliar with.

Instructions

Write a function rangesEqual, prototyped as

template <typename FDIter>
bool rangesEqual(FDIter first1,
                 FDIter last1,
                 FDIter first2);

Parameters first1 and last1 are forward iterators that specify a range in the usual way. Parameter first2 is a forward iterator that points to the beginning of a second range, which is assumed to contain the same number of items as the first range.

Function rangesEqual should compare the two ranges, returning true if they have the same values in the same order, and false otherwise.

Furthermore, rangesEqual should do its work with a single function call to a function in the C++ Standard Library. The body of rangesEqual should consist of this function call and nothing else. I am not going to tell you what function to call; some research may be necessary.

Example usage:

bool result;

std::vector<int> v1;
v.push_back(1);
v.push_back(6);
v.push_back(2);
v.push_back(0);
v.push_back(6);
// Now v1 has size 5 and holds 1, 6, 2, 0, 6.

std::vector<int> v2 = v1;
// Now v2 holds a copy of v1

result = rangesEqual(v1.begin(), v1.end(), v2.begin();
// Above should return true

v2[3] = 37;
result = rangesEqual(v1.begin(), v1.end(), v2.begin();
// Above should return false

Other requirements & notes:

• You must correctly handle the case when the first range is empty.
• You do not need to check whether the ranges contain the same number of items.

Exercise E — Recursive Collatz Function

Purpose

In this exercise, you are to implement a simple recursive algorithm.

Instructions

Write a recursive function (NOT a template) collatz, prototyped as

int collatz(int n);

Function collatz computes the following function. Beginning with a positive integer n, repeatedly perform the following process:

• If n is even, then replace n by n/2.
• If n is odd, then replace n by 3n+1.

The value of the function is how many steps are required before n reaches 1.

Thus:

• collatz(1) should return 0, since 1 is already 1; no steps are required.
• collatz(4) should return 2. The values obtained are 4, 2, 1; 2 steps required.
• collatz(7) should return 16. The values obtained are 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1; 16 steps are required.

Other requirements & notes:

• You do not need to check for numeric overflow or nonpositive parameters. You do need to document the fact that parameters resulting in these situations are illegal.
• You do not need to worry about the situation when you are given a positive integer, and the above process never reaches 1. (Note: It is, in fact, unknown whether this ever happens. Interesting, no?)

CS 311 Fall 2009: Assignment 3 / Updated: 28 Sep 2009 / Glenn G. Chappell / ffggc@uaf.edu