Assignment

This lab is about finding a path from some source city to a destination city. Cities are represented by the City enum in the provided jar file. CitySelector is a provided interface that determines a "next hop" city (the next city to go to). CityPathConnector is a provided interface that uses a CitySelector to determine a path from a given source city to a given destination city.

Starting from the source city, a CityPathConnector will get the next city to visit from its CitySelector. The CityPathConnector will repeatedly do this until the CitySelector presents the destination city, at which point the path is complete. The CityPathConnector needs to keep track of which intermediary cities were visited.

For example, a path from New York to Atlanta might be:

New York, Washington, Boston, Los Angeles, Atlanta

Note that the realistic practicality of the path is not a concern for this lab.

However, here's a caveat. The CitySelector may return null; this denotes that there are no paths from the current city. When this happens, the CityPathConnector needs to go back to the previously visited city.

For example, given a source of New York and destination of Atlanta, the first part of the path might be:

New York, Washington, Boston

If the next city to visit is null, then the path becomes

New York, Washington, Boston, Washington

And the CityPathConnector checks for a next city from Washington (a CitySelector will not present a city more than once).

From there, the path can be completed; for example:

New York, Washington, Boston, Washington, Charlotte, Atlanta

Or, it will be possible that the CitySelector will return a string of null values, denoting that there is no path to the destination; for example:

New York, Washington, Boston, Washington, New York (null value and done).

Values of null presented by the CitySelector denote dead-end cities. When this happens on a path, we will also want to know what the "direct" (for lack of a better term) path is. For example, if the full path is:

New York, Washington, Boston, Washington, Charlotte, Atlanta

Then the direct path is:

New York, Washington, Charlotte, Atlanta

And when there is no path to the destination, the direct path will be empty. For example (going from New York to Atlanta):

Full Path: New York, Washington, Boston, Washington, New York Direct Path: (empty)

Part 1

1. Create an implementation of the CityPathConnector interface.

a. Use the stack data structure (java.lang.Stack) in your implementation.

Part 2

There are three ways to test and validate your implementation, as follows.

1. Use the RandomCitySelector which will present cities or null values in random order. A null value has equal chance as any eligible city to be presented.

2. Use the ListCitySelector. This allows you to hard code a city order so you can test specific test cases.

3. Use CityPathConnectorTester. This will automatically run your CityPathConnector against a series of predefined test cases and will show you which test cases were failed, if any.