CSCI 0112: Programming and Algorithms II
Program 7: Train Schedule
Grading Weight: 5
(programs will have a weight between 1 - 5)
Overview:
Write a program that uses a binary tree to store the
schedule for a set of connected train trips.
Train trips will be represented by pairs of cities. For example,
<Chico, Sacramento> represents that there is a train scheduled
from Chico to Sacramento.
Your program must read commands from standard input to perform the
following operations:
insert a trip into the database
remove a city from the database
print a city and the cities to which it connects
measure the distance between two cities (i.e. how many trains it would
take to get between the cities).
Program Requirements:
All
input and output
must be done in main().
You must store the data in a binary tree of strings called class
Stree. This class is independent of the "train" domain. It
is simply a binary tree of strings. It must not contain any
"train" artifacts.
The input consists of commands (insert, remove, print, distance) and
city
names. City names will NOT contain any space (so you can read
them cin >> str). Each line
will contain a single command.
Here are some sample lines from the program's input (note that
different commands have different numbers of arguments):
insert Chico Chicago
remove Chico
print Chicago
distance Chico New_York
insert
Insert the given "train trip"
into the tree. The first city is the origination city, the second
city is the destination city. If the tree is empty, make the
origination city the root. If the tree is not empty, and the
origination city is not in the tree, print the could not insert error (see below
for exact error messages). If the origination city is in the tree
but already has two trains departing from it (i.e. it already has a
left and right child) print the could
not insert error. If the destination city is already in
the tree, print the could not insert
error.
If a city has no children, always
insert a new trip as the left child
(you must do this to match the output of my program).
remove
Remove the given city from the
tree (only one
city is specified with a remove command). Each node
in the tree is the root of a subtree (with height >= 1).
When a city is removed, the entire subtree should be removed.
Don't forget to delete the Node(s) (by calling delete), you will lose
points if you don't
delete the nodes.
If the given city is not in the tree, print the could not remove error message (see
below).
print
The print command prints a city
and the trains that depart from that city:
print <city_name>
The format of the output must be:
<origination_city>: <destination>,
<destination>
If a city does not have 2 destinations, print none.
For example,
insert Chico Sacramento
insert Chico San_Francisco
print Chico
Should print:
Chico: Sacramento, San_Francisco
The order is important. The first destination inserted
into a city (the left child) must be printed first.
If one of Chico's destination cities is then removed, print should
print "none"
remove Sacramento
print Chico
Should print:
Chico: none, San_Francisco
The order of the cities is important. If you always
insert on the left when both the left and right are empty, and you
always print the left before the right, you will get the order correct.
If the given city is not in the tree, print the not in tree error message (see
below).
Note: if you do the extra credit that allows any number of trains to
depart from a city, you must update the print function so that it
prints all the cities, not just the first two.
distance
The distance command will take
two arguments, an origination city and a destination city. If
there is a path in the tree from the origination city to the
destination city, print the following:
origination to destination is n trains
where n is the integer number of hops between the cities (the number of
trains you must take to get from the origination to the destination,
which is also the number of edges that must be traversed in the
tree). For example, if there is a train from Chico to Sacramento,
the output to "distance Chico Sacramento" would be:
Chico to Sacramento is 1 train
If there was also a train from Sacramento to Los_Angeles, the output to
"distance Chico Los_Angeles" would be:
Chico to Los_Angeles is 2 trains
Note that "train" is printed if there is only 1 train, and "trains" is
printed if it is more than one train.
If the origination and/or the destination are not in the tree, or if
there is no path from the origination to the destination, print the no
path error (see below).
Note: when calculating the distance only follow children pointers
(left_child, right_child) do not follow parent pointers. The
extra credit includes functionality that searches both children and the
parent.
Errors and Error Messages:
You must be able to handle all
functional errors. For example, if a city is not in the tree, you
cannot print it. Print the following error messages (with the
appropriate city names) to standard error when you encounter an error
(be sure your output includes the "<" and the ">"):
Error: could not insert
<Chico, Los_Angeles>
Error: could not remove <Poughkeepsie>
Error: no path between <Chico> and <Albuquerque>
Error: <Tucson> not in tree
The only input error you must be
able
to handle is a bad command. When you read a bad command, print
the following error message to standard error, and skip all other text
on that line and continue processing the input (use peek() and ignore()
to skip the rest of the line):
Error: <find> is not a valid
command
If the command is correct, you may
assume that the following arguments are legal arguments.
However, you still have to handle the functional errors described
above.
Extra Credit:
No extra credit points will be given to late assignments.
If
you do the extra credit, you will have to turn in the non-extra credit
version AND the extra credit version. Create a subdirectory of
your turn in directory called extra_credit, and put your extra credit
version in that directory.
Do not do the extra credit until you
have completed the rest of the assignment. I won't help you with
the extra credit until you can show me a working version of the program
that performs the standard requirements. Save a working copy of
your program before you start working on the extra credit.
10 points extra credit: implement the tree as a general tree (each node
can have any number of children) instead of a binary tree.
To get these extra credit points you must use a standard template
library (STL) vector to store the children of a Node (instead of using
the two pointers m_left and m_right).
class Node
{
public:
Node(string str);
vector<Node *> children;
string m_string;
};
10 more points extra credit if you implement the path
command which prints out all the cities in the path. This
can be implemented by passing a reference to an STL
vector<string> to the Stree::path() function:
bool Stree::path(Node *root, string str, vector<string> &cities);
The output of path should be of the form:
origination to city1 to city2 to destination
10 more points extra credit if you implement
bi-directional train trips. In other words, if there is a trip
from Chico to Sacramento, then this extra credit would also model a
train from Sacramento to Chico.
This can be implemented by including parent pointers in the
Nodes. It will make the path and distance functions considerably
more complex. This is hard, you should talk to me before you
start implementing this last extra credit.
Hints:
Make
sure your tree insert, remove, and print functions are working properly
before doing anything else. This means you have to write some
code to test your tree. Test all the cases you can think of.
If there is a subtle bug in your
insert and/or remove functions that you don't find during testing, you
probably will not be able to get the program to work.
Use lots of assert statements.
When I program, I put assert statements everywhere. They save me
lots of time. A logic error that would take hours to find using a
debugger or cout statements, is
often found right away by an assert statement.
I've been writing tree programs for 20
years. Every time I write one I draw a picture. Draw a
picture of what you think the data structure should look like and then
step through your insert/remove functions and modify the picture as you
go. This will save you lots of time.
You need to search the tree to find
where to insert train trips. Searching in a tree is much easier
to do using a recursive function.
The path and distance functions are much easier to implement
recursively. You don't have to implement them recursively, but
the recursive solutions are 10 times shorter.
General Requirements:
I will deduct 10
percent
if your program does not compile using my Makefile
on a Linux machine. Thus you must make sure to use the filenames
listed below
(do not capitalize your filenames), and if you are working on windows,
you
should compile and test your program on a Linux machine before turning it in.
We will grade your program using another program, so if your program
does
not work exactly as specified below you will lose points.
The first lines of all your files (.h and .cpp) must
contain:
// last name, first name
// ecst_username@ecst.csuchico.edu
// 112 Program 7: Train Schedule
Testing
Your Program:
For this assignment I have provided a bash script (a program that
the bash shell can execute) to automatically test your program. Read
the automatic testing instructions and download the .tar file in the tests/p7 directory.
I will test your program with additional tests not posted in the
test directory. It is a very good idea to design and implement your
own set of tests.
How to
turn in code:
You must turn in the following file:
stree.h
stree.cpp
train.cpp