Input isn't all that difficult to handle; the main issue seems to be whether to read input in all at once and checked before doing anything else (which is like batch mode) or to read input a line at a time and handle each line as it's read.
There doesn't seem to be an overwhelming argument for one side of the issue or the other. Reading and processing all the input initially allows for early detection of errors and avoids otherwise unnecessary work, but requires maintaining the input in a data structure (adimittedly, not a big deal, but it's still work). Reading and processing a line at a time is about the same amount of work without the extra data structures, at a cost of potentially processing an illegal input.
With no compelling arguments, go for the simpler solution - read and process input a line at a time.
The design question for the turtle is should it be a class or a set of stand-alone functions? The amount of work required by the turtle in each case is the about same. Because there's only one turtle needed to solve this problem, classes aren't really necessary. However, a class is a nice fit for this problem, so a turtle will be implemented as a class.
The remaining design issues are relatively mild, and can be dealt with as they come up during implementation.
main() inputs the start and transformation strings, using them to create a
turtle. It then calls do_commands() to deal with the drawing commands.
<main.cc procedures>= (U->) [D->]
int
main() {
string start;
if (!read_next_nonblank_line(std::cin, start))
return EXIT_SUCCESS;
string pattern;
if (!read_next_nonblank_line(std::cin, pattern))
go_bang("Unexpected end-of-file while reading transformation spec");
const str_index end = pattern.find("->");
if (end == std::string::npos)
go_bang("No \"->\" in transformation spec", pattern);
string replacement(pattern, end + 2, pattern.length() - end + 2);
pattern = pattern.substr(0, end);
turtle t(start, pattern, replacement);
do_commands(std::cin, t);
}
Definesmain(links are to index).
do_command() reads drawing commands from the input stream ins and
applies them to the turtle t.
To make things easier to parse, do_command() deletes spaces from the
command string. To check that the command string doesn't have extra spaces (as
in le ft = 32. 03) it splits the command string at the spaces; there should
be at most three pieces after the split (because spaces aren't required, there
could be less than three pieces; also, the draw command can legally produce
at most two pieces).
<main.cc procedures>+= (U->) [<-D->]
static void
do_commands(std::istream & ins, turtle & t) {
string cmd;
while (read_next_nonblank_line(ins, cmd)) {
if (split(cmd).size() > 3)
go_bang("Too many pieces in drawing command", cmd);
const string c = delete_characters(cmd);
double val;
if (is_cmd("draw", c, val))
t.draw(static_cast<unsigned>(val));
else if (is_cmd("right=", c, val))
t.set_right(val);
else if (is_cmd("left=", c, val))
t.set_left(val);
else if (is_cmd("forward=", c, val))
t.set_forward(val);
else
go_bang("Unrecognized drawing command in program", cmd);
}
}
Definesdo_commands(links are to index).
is_cmd() returns true if and only if the string str begins with the
command cmd. If str does begin with cmd, is_cmd() also returns
the associated value in val; the contents of val is undefined if
str doesn't begin with cmd.
This code assumes all the space characters have been removed from str.
<main.cc procedures>+= (U->) [<-D->]
static bool
is_cmd(const char * cmd, const string & str, double & val) {
if (str.find(cmd) != 0) return false;
std::istringstream sin(str.substr(strlen(cmd)));
if (!(sin >> val))
go_bang("missing value in drawing command", str);
char c;
if (sin >> c)
go_bang("Extra stuff at end of drawing command", str);
return true;
}
Definesis_cmd(links are to index).
go_bang() prints the error message in emsg and dies. line, if
given, is included in the error message.
<main.cc procedures>+= (U->) [<-D]
void
go_bang(const string & emsg, const string & line) {
std::cerr << "Turtle program error";
if (line.size())
std::cerr << " in line \"" << line << "\"";
std::cerr << ":\n " << emsg << ".\n";
exit(EXIT_FAILURE);
}
Definesgo_bang(links are to index).
<main.cc>= #include <string> #include <vector> #include <iostream> #include <cstring> #include <sstream> #include <cstdlib> #include "str-utils.h" #include "ps.h" #include "turtle.h" #include "utils.h" using std::string; static void do_commands(std::istream &, turtle &); static bool is_cmd(const char *, const string &, double &); <main.ccprocedures>
Definesmain.cc(links are to index).
<turtle public interface declarations>= (U->) turtle(const std::string & , const std::string &, const std::string &); void draw(unsigned); void set_forward(double); void set_left(double); void set_right(double);
The private interface is a bit more complicated, including member variables for the start, pattern, and replacement strings, as well as the current parameter values and the location stack.
<turtle private interface declarations>= (U->) [D->]
const std::string start, pattern, replacement;
double forward; // units.
double left, right; // radians.
struct location {
double x, y; // units.
double heading; // radians.
};
std::vector<location> locations;
The turtle also needs routines to execute a turtle string, move forward, return the top of the location stack, create a turtle string, and reset the turtle location to its initial state.
<turtle private interface declarations>+= (U->) [<-D] void execute(const std::string &); void fwd(void); location & top(void); std::string generate(unsigned); void reset();
Creating a new turtle is simple. The start, pattern, and replacement strings are stored without spaces to simplify handling.
<turtle definitions>= (U->) [D->]
turtle::
turtle(const string & s, const string & p, const string & r) :
start(delete_characters(s)),
pattern(delete_characters(p)),
replacement(delete_characters(r)) {
forward = 1.0;
set_left(20);
set_right(20);
reset();
}
Definesturtle(links are to index).
Set the turtle forward, left, and right parameters, specified in units and degrees, respectively.
<turtle definitions>+= (U->) [<-D->]
void turtle::
set_forward(double f) {
forward = f;
}
void turtle::
set_left(double l) {
left = l/d2r;
}
void turtle::
set_right(double r) {
right = r/d2r;
}
Definesset_forward,set_left,set_right(links are to index).
To draw, create a turtle string of the given generation and execute it.
<turtle definitions>+= (U->) [<-D->]
void turtle::
draw(unsigned generation) {
ps::open(generation);
execute(generate(generation));
ps::close();
}
Definesdraw(links are to index).
Generating a turtle string involves aging the start string the given amount.
<turtle definitions>+= (U->) [<-D->]
string turtle::
generate(unsigned generation) {
string s(start);
while (generation > 0) {
s = age(s, pattern, replacement);
generation--;
}
return s;
}
Definesgenerate(links are to index).
Aging a string is the left-to-right, non-overlapping substitution of the pattern string with the replacement string.
<turtle definitions>+= (U->) [<-D->]
static string
age(const string & start, const string & pat, const string & repl) {
string s;
str_index last = 0;
while (last < start.length()) {
str_index begin = start.find(pat, last);
if (string::npos == begin) {
s += start.substr(last, start.length() - last);
break;
}
s += (start.substr(last, begin - last) + repl);
last = begin + pat.length();
}
return s;
}
Definesage(links are to index).
Executing a turtle string is straightforward, given all the helper routines available.
<turtle definitions>+= (U->) [<-D->]
void turtle::
execute(const string & pgm) {
reset();
for (str_index i = 0; i < pgm.size(); i++) {
switch (pgm[i]) {
case 'F': {
const double oldx = top().x;
const double oldy = top().y;
fwd();
ps::line(oldx, oldy, top().x, top().y);
break;
}
case 'f':
fwd();
break;
case '-':
top().heading += left;
break;
case '+':
top().heading -= right;
break;
case '[':
locations.push_back(locations.back());
break;
case ']':
if (locations.size() < 2)
go_bang("Trying to pop an empty location stack");
locations.pop_back();
break;
default:
go_bang(string("Unknown command '") + pgm[i] + "' in turtle string");
}
}
}
Definesexecute(links are to index).
Move the turtle the forward distance along the given heading. Ah, trigonometry.
<turtle definitions>+= (U->) [<-D->]
void turtle::
fwd(void) {
location & l = top();
l.x += forward*cos(l.heading);
l.y += forward*sin(l.heading);
}
Definesfwd(links are to index).
Reposition the turtle at its home location in preparation for executing a turtle string. Clear the location stack too.
<turtle definitions>+= (U->) [<-D->]
void turtle::
reset(void) {
location l;
l.x = l.y = 0;
l.heading = 90.0/d2r;
locations.clear();
locations.push_back(l);
}
Definesreset(links are to index).
<turtle.h>=
#ifndef _turtle_h_defined_
#define _turtle_h_defined_
#include <string>
#include <vector>
#include <fstream>
class turtle {
public:
<turtle public interface declarations>
private:
<turtle private interface declarations>
};
#endif
Definesturtle.h(links are to index).
Return a reference to the current turtle location, dying if there isn't one.
<turtle definitions>+= (U->) [<-D]
turtle::location & turtle::
top(void) {
assert(locations.size() > 0);
return locations.back();
}
Definestop(links are to index).
<turtle.cc>=
#include <cmath>
#include <iostream>
#include "turtle.h"
#include "ps.h"
#include "str-utils.h"
#include "utils.h"
using std::string;
const double d2r = 360.0/(2*3.1415);
static string age(const string &, const string &, const string &);
<turtle definitions>
Definesturtle.cc(links are to index).
<string utility declarations>= (U->) extern std::string delete_characters( const std::string &, const char * = space_characters);
which returns a string equal the given string with all the given characters deleted; the default is to delete all space characters from the string.
The struct char_match is an example of a functor, structs whoes
instances can be called like functions. Structs are turned into functors by
defining the call operator operator ().
This code needs a functor because std::remove_copy_if() accepts a unary
prediate, and the character test needs to pass in two arguments: the character
and the list of characters to check against. The char_match functor helps
to get around this problem by accepting the character list as a constructor
argument. The call operator can then be defined as a unary predicate that
accepts a single character and compares it against the character list stored as
an instance variable of the struct.
<string utility definitions>= (U->)
struct char_match {
const char * const chars;
char_match(const char * const cp) : chars(cp) { }
bool operator()(char c) {
return index(chars, c);
}
};
string
delete_characters(const string & s, const char * chars) {
string s2(s);
str_index s2s =
std::remove_copy_if(s.begin(), s.end(),
s2.begin(), char_match(chars)) - s2.begin();
s2.erase(s2s, s.length() - s2s);
return s2;
}
Definesdelete_characters(links are to index).
main.cc>: D1
main.cc procedures>: D1, D2, D3, D4, U5
str-utils.cc>: D1
str-utils.h>: D1
turtle.cc>: D1
turtle.h>: D1
This page last modified on 2 April 2002.