#include <iostream>
#include <fstream>
#include <string>
#include "mapstuff.h"

using namespace std;

/*
    class hashtable<keyT, valT> has
      hashtable(int initial_capacity);
      void add(const keyT &, const valT &);
      valT find(const keyT &) const;

    class set<keyT> has
      set(int initial_capacity);
      void add(const keyT &);
      bool contains(const keyT &) const;
      void remove(const keyT &);

    class place has
      place(const string & name);
      void add_exit(road *);
      string get_name() const;
      int num_exits() const;
      road * get_exit(int) const;

    class road has
      road(const string & name, int length, place *, place *);
      string get_name() const;
      int get_length() const;
      place * get_other_end(const place *) const;

    ordinary function
      void readmap(hashtable<keyT, valT> & HT, const string & fname);
*/

place * ask_for_place(const string & which, hashtable <string, place *> & HT)
{ while (true)
  { string s;
    cout << "Enter " << which << ": ";
    cin >> s;
    if (cin.fail())
    { cout << "\n";
      exit(0); }
    place * p = HT.find(s);
    if (p == NULL)
    { cout << "not found\n";
      continue; }
    return p; } }

int explore_path(place * here, place * target, set <place *> & closed)   // total distance or negative for failure
{ if (here == target)
    return 0;

  int n = here->num_exits();
  if (n == 0)
    return -1;

  if (closed.contains(here))
    return -1;
  closed.add(here);

  for (int i = 0; i < n; i += 1)
  { road * r = here->get_exit(i);
    place * there = r->get_other_end(here);
    cout << "Trying " << r->get_name() << " from " << here->get_name() << " to " <<
            there->get_name()<< ", " << r->get_length() << " more miles\n";
    int miles = explore_path(there, target, closed);
    if (miles >= 0)
      return miles + r->get_length();
    cout << "backtracked to " << here->get_name() << "\n"; }

  cout << "no more exits to try from " << here->get_name() << "\n";
  closed.remove(here);
  return -1; }

int main(int argc, char * argv[])
{ hashtable <string, place *> HT;
  readmap(HT, "nebraska.txt");

  place * start, * target;
  if (argc != 3)
  { start = ask_for_place("starting place", HT);
    target = ask_for_place("destination", HT); }
  else
  { start = HT.find(argv[1]);
    if (start == NULL)
    { cerr << argv[1] << " not found\n";
      exit(1); }
    target = HT.find(argv[2]);
    if (target == NULL)
    { cerr << argv[2] << " not found\n";
      exit(1); } }

  set <place *> closed;
  int dist = explore_path(start, target, closed);
  if (dist < 0)
    cout << "no path found\n";
  else
    cout << "path of length " << dist << " miles found\n"; }