CS 311 Spring 2008
Assignment 7
Assignment 7 is due at 5 p.m. Thursday, April 24.
It is worth 20 points.
Procedures
E-mail
answers to the exercises below to
ffggc@uaf.edu,
using the subject
“DA7”.
- Your answers should consist of one file:
treesort.h, from Exercise A.
The file (or an archive file containing it)
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 (20 pts total)
Exercise A — Treesort
Purpose
In this exercise, you will implement the Treesort algorithm.
This will require at least a partial implementation of a Binary Search Tree,
including insertion and inorder traversal.
Instructions
Write a C++ function template that sorts a given range using
the Treesort algorithm.
Be sure to follow the
coding standards.
All standards now apply!
- Call your function template “treesort”, and prototype it as shown.
template <typename FDIter>
void treesort(FDIter first, FDIter last);
- Implement your function template in file treesort.h.
Since this is a template, there should be no associated source file.
Your file may include any other functions and classes you want.
- What the function should do.
- Function treesort takes two forward iterators (see Notes on Iterators, below).
These specify a range to be sorted, in the usual manner: first points to the first item in the
list, and last points to just past the last item.
If first and last are equal, then the list is empty.
- Function treesort sorts the given range, in a stable manner,
using operator<.
The sorted data are stored in the same space as the original data.
- The function must use the Treesort algorithm (see pages 568–569 in the text).
- The Binary Search Tree.
- Your file must include at least a partial implementation of a Binary Search Tree,
including the insert and inorder-traversal operations.
- Other than the coding standards, there are no restrictions on how you implement
the Binary Search Tree. You may use separately allocated nodes, referenced by pointers,
or you may store your nodes in an array, and reference them with array indices.
The tree does not need to be a separate class.
You may decide other implementation issues however you want, within the constraints of the coding standards,
and the rest of these requirements.
- You may use the following from the C++ Standard Library:
- std::size_t, from <cstdlib>
- std::ptrdiff_t, from <cstdlib>
- std::swap, from <algorithm>
- std::iter_swap, from <algorithm>
- std::advance, from <algorithm>
- std::distance, from <algorithm>
- std::iterator_traits, from <iterator> (see Notes on Iterators, below)
You may not use any other C++ Standard Library classes or functions.
- Function treesort should have the highest reasonable levels of efficiency and exception safety.
- Function treesort must be exception-neutral; that is, exceptions thrown by value-type operations must propagate unchanged to the caller.
- You may not forbid any member function of the value type from throwing, except for the destructor.
Test Program & Grading
I have written a test program:
treesort_test.cpp.
If you compile and run your package with this program (unmodified!), then it will test
whether your code works properly.
Do not turn in treesort_test.cpp.
Note: The test program does not check whether you actually use a Binary Search Tree.
However, code that does not at least make an attempt at using a Binary Search Tree will not be graded.
Notes on Iterators
Forward Iterators
A forward iterator
is guaranteed to allow the following operations:
- Default constructor.
- Copy constructor.
- Copy assignment.
- Destructor.
- Dereference (operator*).
- Arrow (operator->)
- Equality test (operator==).
- Inequality test (operator!=).
- Increment (operator++, both kinds).
In particular, you can do this:
for (FDIter it = first; it != last; ++it)
{
doSomething(*it);
}
You may dereference a forward iterator any number of times
without changing the iterator.
You may not decrement a forward iterator.
You also may not add to a forward iterator
or subtract two forward iterators;
however, std::advance
and std::distance
may be used to perform these operations.
Finding the Value Type
It is likely that you will need to figure out what the value type is,
that is, what type the iterator points to.
To do this, use std::iterator_traits, as shown below.
typedef typename std::iterator_traits<FDIter>::value_type ValueType;
After this, ValueType is the item of the item referenced
by a FDIter.
Note: The “typename” above is a signal to the compiler
that what follows is a type;
many compilers require this keyword in the above situation.
In order to use std::iterator_traits, you will need to include the proper header:
#include <iterator>
You can find example code using std::iterator_traits
on the web page:
merge_sort.cpp.
(See the beginning of function stableMerge.)
Note: In some versions of Visual C++, std::iterator_traits
does not work properly when the iterator is a pointer.
Therefore, the test program will only test your function using iterators
to Standard Library containers (vector, deque, list), and possibly other types of iterators
that are guaranteed not to be pointers.