BAC Flights

0. Introduction. The Ballarat Airline Company (BAC) wants a simple program to process customer requests to fly from some origin city to some destination city: For each customer request, the program has to indicate whether a sequence of BAC flights exists from the origin city to the destination city, and, if such a sequence exists, the program prints it.

The following figure represents the routs that BAC flies (for simplicity cities on the figure are denoted by C1, C2, …, C9): See image.

Notice that not all BAC flights have return flights, for example there is a BAC flight from C1 to C2, but not a BAC flight from C2 to C1.

The algorithm for processing customer requests is described in the following section and uses stacks. You must “translate” the algorithm into C++, and create auxiliary C++ classes as specified below.

1. The Main Algorithm. Let us assume that we have a request to find a sequence of flights from X to Y. The request must be processed in the following way:

• We create an empty stack;
• All cities are marked as “unvisited”;
• We mark city X as “visited” and push it onto the stack;
• While the stack is not empty and top city in the stack is not the destination city Y:
  • If there is some “unvisited” city adjacent to the top city, we mark it as “visited” and push it onto the stack
  • Else we pop the stack

(i) Return the stack. If the stack is not empty it contains the sequence of flights from X to Y. If the stack is empty, such sequence does not exist.

2. classes Stack< T > and List< T > [4 marks each]. Create class templates Stack< T > and List< T >. You may need to make appropriate changes to the classes Stack and List discussed in the lectures. Class Stack< T > should contain a function with the following prototype

friend ostream& operator<<(ostream& stream, Stack< T* > &c);

that prints contents of the stack.

3. Class City [4 marks]. Create a class City, which has the following private instance variables:

• 1* string name; // name of the city
• 2* List< City* > *nextCities; // A pointer to a List of the cities to which there is a flight from the city.
• 3* bool visited; // the variable that shows whether the city has already been visited during the request processing algorithm.

The class also should contain constructor(s) and get and set functions for the instance variables.

There also should be a public function City* getNextUnvisitedCity() that returns a pointer to some “unvisited” city from the nextCities list, if there is any, otherwise returns NULL.

4. A function with the header

function Stack< City >* isPath(City * originCity, City * destinationCity)

that implements the Main Algorithm described in section 1.

5. main function, in which you create 9 cities according to the information given in the flight map (figure in section 0) and then process customer requests for three different pairs of cities (you can choose the pairs yourself). [