Most of you have, by now, gained some experience using the Standard Template Library (STL) for C++. The design of such libraries is a complex undertaking, with many tradeoffs to be considered—far more than can be covered in this course. The current assignment will give you a taste for some of the issues, and will help to familiarize you with generics (templates) and with the synergy between subtype and parametric polymorphism.
Your task is to implement variants on a set collection
type. These should look familiar given our discussion of the dictionary
(mapping) types used by switch (case) statements.
I am providing a file of (incomplete) starter code.
Its most basic definition is of the abstract class simple_set:
template<class T, class C = comp<T> >
class simple_set {
public:
virtual ~simple_set<T>() {}
virtual simple_set<T>& operator+=(T item) = 0;
// add item to set
virtual simple_set<T>& operator-=(T item) = 0;
// remove item from set, if it was present
virtual bool contains(T item) = 0;
// indicate whether item is in set
};
Class C is a “comparator”; it provides an
equals method that can be used to identify duplicate elements.
(It also provides a precedes method, but that isn’t needed
for simple_set.)
The default comparator comp employs
T’s
operator==, assuming it exists.
You might want a different comparator for, say char*s,
since the built-in == compares pointer values,
not lexicographic ordering of strings.
As an example, the starter code contains a concrete class
stl_simple_set that adapts the sets of the STL to the
simple_set interface. (STL sets are implemented as
balanced search trees.)
This set is for illustration purposes only; the code you write is not to
make use of any of the collections in the STL.
Building on simple_set, the provided code then defines a
more complex range_set:
template<class T, class C = comp<T> >
class range_set : public virtual simple_set<T> {
public:
virtual range_set<T>& operator+=(range<T, C> r) = 0;
virtual range_set<T>& operator-=(range<T, C> r) = 0;
};
where range is defined as follows
template<class T, class C = comp<T> >
class range {
T L; // represents all elements from L, inclusive
T H; // through H, _exclusive_
C cmp;
public:
range(T l, T h) : L(l), H(h) {} // constructor
T low() { return L; }
T high() { return H; }
bool contains(T item) { return cmp(item, H) && !cmp(item, L); }
};
Here
C’s precedes method is used to determine whether
a given element lies
within the range. The default comparator comp employs
T’s operator<,
assuming it exists.
Again, you might want a different comparator for certain types.
So what is a range_set good for? It allows you to insert
and remove contiguous ranges of elements from the set en masse
and, in some implementations, in amortized constant time, rather
than time linear (or worse) in the number of elements in the range.
The provided code defines an stl_range_set, again as an
example, but this implementation does not have good performance.
The problem is that the sets of the STL are defined to hold individual
elements only; they do not capture ranges.
You are to implement three versions each of simple_set
and range_set:
carray_simple_set<T> and
carray_range_set<T, C, I>
l and h of
type T, which must be coercible to int;
insert and remove routines throw an
out_of_bounds exception if passed an element outside
the half-open range [l, h).
Insertion, removal, and lookup of individual elements must all take
constant time.
For carray_range_set, T must support an
increment operation, and insertion and removal of ranges can take
time linear in the size of the range.
Must be space efficient: carray_simple_set(l, h)
must consume h − l + c bits, for some
small constant c.
hashed_simple_set<T, F> and
hashed_range_set<T, F, C, I>
int,
specifying the maximum number of elements that can belong to the set
at any one time. Insert routine throws an
overflow exception if there is no more room
in the table.
Optional template parameter F specifies a
function-object class
that can be used to convert a T object into an int.
Insertion, removal, and lookup of individual elements should take
expected constant time.
For hashed_range_set, T must support an
increment operation, and insertion and removal of ranges can take
time linear in the size of the range.
bin_search_simple_set<T> and
bin_search_range_set<T, C>
int,
specifying the maximum number of elements (or, for
bin_search_range_set, ranges) that can belong to the
set at any one time. Insert routine throws an
overflow exception if there is no more room.
Insertion and removal of individual elements or ranges may take time
linear in the number of elements or ranges currently in the set,
worst case, but must take amortized constant time if elements are
inserted in sorted order. Lookup must take logarithmic time.
For carray_range_set and hashed_range_set,
optional template parameter I specifies a function-object
class that can be used to increment a T object, to iterate
over the elements of a range.
carray_range_set should inherit from
range_set and carray_simple_set;
hashed_range_set and bin_search_range_set
should similarly inherit from both range_set and their
corresponding non-range version. See the stl_range_set for
an example of how to do this.
Because its internal data structure represents individual elements only,
the stl_range_set, like
carray_range_set
and
hashed_range_set,
can be instantiated only for types that
support an increment operation.
As noted above, this means that ranges can’t be inserted and removed
efficiently. It also means that the set cannot support ranges
containing an unbounded number of elements. Ideally, one would like to
be able to create a set of real numbers, and specify that it contains
not only 1.2, 4.67, and −0.235, but also all values from 123 up to (but
not including) 158.5. Your bin_search_range_set will allow
this. When instantiated for strings, it will also allow ranges like
["apple", "orange"), which includes an unbounded number of strings.
Warning: keep in mind that ranges have the potential to overlap, both with individual elements and with each other. If you insert a range that overlaps an existing range, you’ll need to merge them. If you remove a range from the middle of an existing range, you’ll need to split it. The worst case is probably removal of an individual element from the middle of a range. If the range isn’t finite, the upper half of the resulting split will need to be open on the left, something the current code doesn’t support.
As in previous assignments, you may work alone or in teams of two. If you choose to work in pairs, the obvious division of labor is to divide up the implementations. If you do this, take care to figure out what common assumptions you need to share with your partner.
Be sure to follow all the rules on the Grading page. As with all assignments,
use the turn-in script:
~cs254/bin/TURN_IN. Put your write-up in a
README.txt or README.pdf file in the directory in
which you run the script. Be sure to describe any
features
of your code that the TAs might not immediately notice.
operator=,
operator==,
operator!=,
operator| (union),
operator& (intersection),
and operator- (difference). Can you make these
work for sets with the same element type but different
implementations? (E.g., can you compare a
carray_simple_set<T>
and a hashed_simple_set<T>?)
Can you make them work for range_sets whose ranges
aren’t finite?
NB: One could design both the set abstraction and the concrete implementations in many different ways. The starter code I’ve given you may not suit your fancy. Feel free to explore other APIs for extra credit, but if you do, put them in separate files, and be sure to respect the given API for the main assignment; otherwise the TA won’t be able to test your code with his driver scripts and you won’t get the credit you want.
Before the beginning of class on Thursday, December 3, send
e-mail to to cs254 containing answers to the following
questions:
// your code here”
comments in the starter code to make it compile and run correctly?
gdb, where does it get stuck?
MAIN DUE DATE: noon, Monday December 14; no extensions.
