We want to name things (nan, zero) that will do something and then leave. These sound like procedures, and indeed that's how they're used in the examples.
The form to match is:
(throwing
(((<handler-name> <handler-argument> ...) <handler-body> ...) ...)
<expression> ...)
Ignoring the abort, we want this to become:
(let ((<handler-name> (lambda (<handler-argument> ...) <handler-body> ...)) ...)
<expression> ...)
To give the handlers the ability to abort, we wrap this in a call-with-current-continuation and call the continuation with the result of the handlers.
(call-with-current-continuation
(lambda (abort)
(let ((<handler-name>
(lambda (<handler-argument> ...)
(abort (begin <handler-body> ...)))) ...)
<expression> ...)))
Putting this together:
(define-syntax throwing
(syntax-rules ()
((throwing
(((<handler-name> <handler-argument> ...) <handler-body> ...) ...)
<expression> ...)
(call-with-current-continuation
(lambda (abort)
(let ((<handler-name>
(lambda (<handler-argument> ...)
(abort (begin <handler-body> ...)))) ...)
<expression> ...))))))
Let's do the minimum to get the starter code to compile. We see Special<int> objects used in the following ways (via the name Elt):
Elt()
Elt(e) // where e is an int
n.is_special() // called on an Elt n, returning a boolean
n.value() // called on an Elt n, returning something that can be output
// based on the specification, it's an int
Following the Rational example from lecture, we produce the preliminary code:
template <typename T>
class Special {
public:
Special() {}
Special(T v) {} // So Special<int> can be made with an int value
bool is_special() { return true; }
T value() { T v; return v; }
};
We compile Special alone, and it compiles. Next we declare chop, which is called as follows, with no return value:
chop(ints.begin(), ints.end(), 2, m) // list<Elt> ints
// from lecture, vector<T>'s begin() and end() are:
// typename vector<T>::const_iterator
// so we'll try:
// typename list<Elt>::const_iterator
// int 2
// window size, as mentioned in the specification,
// so always int
// map< list<Elt>, vector<Elt> > m
The specification says to make chop a templated function, and we see above that it depends on some type Elt that chop doesn't know. So we declare it as follows:
template<typename Elt>
void chop(typename list<Elt>::const_iterator b, typename list<Elt>::const_iterator e,
int w, map< list<Elt>, vector<Elt> > m) {}
We compile chop alone, and it compiles. We repeat the process (including compiling it!) with choose:
/*
choose called as: Elt n = choose(ints, m)
return type: Elt
arguments: list<Elt> ints, map< list<Elt>, vector<Elt> > m
*/
template<typename Elt>
Elt choose(list<Elt> ints, map< list<Elt>, vector<Elt> > m) { Elt e; return e; }
Now we add these to the starter code, and try to compile. If it doesn't compile, we comment out the calls to chop and choose, to see if Special works. The we uncomment the call to chop, to see if that works, finally we uncomment the calls to choose to see if they work. I found a typo in my chop declaration this way. If I hadn't spotted it just by looking, I would have removed arguments from the call and declaration of chop, until I found the one causing the problem.
Next we add meaning to Special. We want to store and return the value given to one constructor, and make a note that we're special if the other constructor is called. Again following the Rational example:
template <typename T>
class Special {
public:
Special() { special = true; }
Special(T value) { v = value; special = false; }
bool is_special() { return special; }
T value() { return v; }
private:
bool special;
T v;
};
The first time I did this I used instance variables with the same name as a method, and the compiler complained, so I changed them to be different. Once again, if I was unsure of the problem, I would have made incremental changes between the working version and the new version until I narrowed down the problem.
Now we add meaning to chop. It works by altering m, so we must change m to a non-const reference. We are making lists of size w, starting at s, to index into m. The only list methods we're given are begin, end, push_back and pop_front, so we try to use those. We use the iterators as shown in lecture.
template<typename Elt>
void chop(typename list<Elt>::const_iterator b, typename list<Elt>::const_iterator e,
int w, map< list<Elt>, vector<Elt> >& m) {
list<Elt> l;
// First window.
for (int i = 0; i < w; ++i) {
l.push_back(*b);
++b;
}
// Store first window with first element.
vector<Elt> v;
v.push_back(*b);
m[l] = v;
}
The compiler now complains. Removing lines, we see that it's the last line, something about
operator<. Looking at the specification, we see that we need to add such
an operator to Special. Following the Rational example:
template <typename T>
class Special {
public:
Special() { special = true; }
Special(T value) { v = value; special = false; }
bool is_special() { return special; }
T value() { return v; }
bool operator<(const Special<T>& s) {
return !special && (s.special || v < s.v);
}
private:
bool special;
T v;
};
We compile this alone again. Then we try it with chop and get a problem again. If we haven't gone to tutorial we read the announcements to see that we should try adding const to our operator. An alternative is to try declaring it outside the class. Or we can ask for help on the newsgroup or in email.
Now we make the rest of chop:
template<typename Elt>
void chop(typename list<Elt>::const_iterator b, typename list<Elt>::const_iterator e,
int w, map< list<Elt>, vector<Elt> >& m) {
list<Elt> l;
// First window.
for (int i = 0; i < w; ++i) {
l.push_back(*b);
++b;
}
// Store first window with first element.
vector<Elt> v;
v.push_back(*b);
m[l] = v;
Elt e = *b;
++b;
while (b != e) {
l.pop_front();
l.push_back(e);
// add *b to vector at m[l]
++b;
}
}
We seem to be stuck. How do we know if we need to make a new vector? We try a little experiment to see what we get back when there's no element stored (null? an exception? something else?):
#include <map>
#include <iostream>
using namespace std;
int main() {
map< int, int > m;
cout << m[3];
return 0;
}
We get 0. Let's try another:
#include <map>
#include <vector>
#include <iostream>
using namespace std;
int main() {
map< int, vector<int> > m;
cout << m[3];
return 0;
}
The compiler complains that it can't output a vector. So we try:
#include <map>
#include <vector>
#include <iostream>
using namespace std;
int main() {
map< int, vector<int> > m;
cout << m[3].size();
return 0;
}
That works, and seems to be creating a zero size vector automatically. So we proceed:
template<typename Elt>
void chop(typename list<Elt>::const_iterator b, typename list<Elt>::const_iterator e,
int w, map< list<Elt>, vector<Elt> >& m) {
list<Elt> l;
// First window.
for (int i = 0; i < w; ++i) {
l.push_back(*b);
++b;
}
// Store first window with first element.
vector<Elt> v;
v.push_back(*b);
m[l] = v;
Elt e = *b;
++b;
while (b != e) {
l.pop_front();
l.push_back(e);
m[l].push_back(*b);
++b;
}
}
We compile the above, then move on to choose. Looking at test(), choose must be updating ints, so we change it to a non-const reference. We also change m to a const reference, since we probably don't want to copy an entire map.
template<typename Elt>
Elt choose(list<Elt>& ints, const map< list<Elt>, vector<Elt> >& m) {
Elt e = m[ints][rand() % m[ints].size()];
ints.pop_front();
ints.push_back(e);
return e;
}
The compiler tells us (after we narrow it down in the usual way) that m[ints] is a problem. But it worked in chop. The two differences are in the declaration of the list and the map. Changing choose to be more like chop, we find that dropping the const on m lets it compile (exercise: think about why).
We put a call to test() in main, and it works. Finally, we copy and modify the body of test to make our main:
int main(int argc, char** argv) {
// Get first command line argument as window size.
int window_size;
if (argc < 2) {
cerr << "Usage: " << argv[0] << " window_size" << endl;
return 1;
} else {
window_size = atoi(argv[1]);
}
typedef Special<string> Elt;
list<Elt> words;
for (int i = 0; i != window_size; ++i) {
words.push_back(Elt());
}
// Read the starting sequence of words.
string word;
while (cin >> word) {
words.push_back(word);
}
words.push_back(Elt());
map< list<Elt>, vector<Elt> > m;
chop(words.begin(), words.end(), window_size, m);
// An elegant way not to treat first 2 random digits separately.
words.clear();
for (int i = 0; i != window_size; ++i) {
words.push_back(Elt());
}
Elt n = choose(words, m);
while (!n.is_special()) {
cout << n.value();
n = choose(words, m);
}
cout << endl;
return 0;
}