// A Graph object holds a list of pointers to City objects, the cities
// in the graph.  Each City object stores pointers to the City objects
// it is directly linked to.  The links are bidirectional, which means
// that if city A is linked to city B then city B should also be
// linked to city A.

#ifndef _graph_h_
#define _graph_h_

#include <iostream>
#include <list>
#include <vector>
#include <string>

#include "city.h"  
#include "person.h"

class Graph {

public:
  Graph();
  ~Graph();

  // Add a city with the given name.  Returns true if successful
  bool add_city(const std::string& city_name);
  // Remove the city with the given name from the graph.  Returns true
  // if successful
  bool remove_city(const std::string& city_name);
  // Add a link between the two cities.  Returns true if successful
  bool add_link(const std::string& city_name1, const std::string& city_name2);
  // Remove a link between the two cities.  Returns true if
  // successful
  bool remove_link(const std::string& city_name1, const std::string& city_name2);
  // Add a pursuer to the city. Returns true if successful
  bool place_pursuer(const std::string& person_name, const std::string& city_name);
  // Add an evader to the city. Returns true if successful
  bool place_evader(const std::string& person_name, const std::string& city_name);
  // Construct a sorted list of the names of the cities that the given
  // city is immediately linked-to in the graph.  Return false if the
  // city is not found.
  bool get_neighbors(const std::string& name, std::list<std::string>& neighbor_cities) const;
  // Move the pursuers & evaders.  Return false if the game is over (a
  // pursuer caught the evader).
  bool tick();

 private:  

  // Return a pointer to the City in the list having the given name.
  // Returns NULL if the City is not in the list.
  City* find_city(const std::string& name) const;
  // Return an iterator that refers to the entry in the m_cities list
  // whose name is the passed name.  Returns m_cities.end() if no
  // pointer in the list points to a City with the given name.
  std::list<City*>::iterator find_city_iterator(const std::string& name);

  // ==============
  // REPRESENTATION
  // The list of pointers to City objects.
  std::list<City*> m_cities;
  // The list of pursuers
  std::list<Person*> m_pursuers;
  // The evader
  Person* m_evader;
};

#endif