112 p7

CSCI 0112: Programming and Algorithms II
Spring 2006
Program 7: Train Schedule
Code due: Midnight Friday May 12 (copied to your ecst turn-in directory, see below)

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).

This program will have a weight of 5.

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:

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 the lab machines. 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 one of the department's suns 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

How to turn in code:

You must turn in the following files:

stree.h
stree.cpp
train.cpp

copy the above files into the directory:
/user/projects/csci112/p7/USERNAME
where USERNAME is your ecst username.

Note: You will not be able to access this directory once the deadline has passed.

If you do any of the extra credit in addition to turning in your program to p7/USERNAME, you must create a new directory p7/USERNAME/extra_credit and put the files from you extra credit version in it.

Late assignments:

If you do not finish by the deadline (see top for the deadline), you may turn your assignment in up to 24 hours late. You will lose 15% for turning your assignment in 1-24 hours late.

If you turn your assignment in late, copy your assignment into the following directory:
/user/projects/csci112/p7_late/USERNAME
Assignments will not be accepted if more than 24 hours late.

Extra credit will not be accepted late.