#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <vector>
#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; } }

struct explore_params
{ place * here, * target;
  set <place *> closed;
  vector <place *> placepath, bestplacepath;
  vector <road *> roadpath, bestroadpath;
  int bestsofar, travelled, depth; 

  explore_params(place * start, place * destination)
  { here = start;
    target = destination;
    bestsofar = 0x7FFFFFFF;
    travelled = 0;
    depth = 0;
    placepath.push_back(start); }

  void take_step(road * r, place * to)
  { roadpath.push_back(r);
    placepath.push_back(to);
    closed.add(to);
    here = to;
    travelled += r->get_length();
    depth += 1; }

  void come_back()
  { travelled -= roadpath.back()->get_length();
    roadpath.pop_back();
    closed.remove(placepath.back());
    placepath.pop_back();
    here = placepath.back();
    depth -= 1; } };

void explore_path(explore_params & p)
{ if (p.here == p.target)
  { cout << "found solution, " << p.travelled << " miles\n";
    if (p.travelled < p.bestsofar)
    { p.bestsofar = p.travelled;
      p.bestplacepath = p.placepath;
      p.bestroadpath = p.roadpath; }
    return; }

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

  for (int i = 0; i < n; i += 1)
  { road * r = p.here->get_exit(i);
    place * there = r->get_other_end(p.here);
    if (p.closed.contains(there))
      continue;
    int length = r->get_length();
    cout << setw(3 * p.depth) << "" << "Trying " << r->get_name() << " from " << p.here->get_name() <<
            " to " << there->get_name()<< ", " << length << " more miles\n";

    p.take_step(r, there);
    explore_path(p);
    p.come_back();
    cout << setw(3 * p.depth) << "" << "backtracked to " << p.here->get_name() << "\n"; }

  cout << setw(3 * p.depth) << "" << "no more exits to try from " << p.here->get_name() << "\n"; }


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); } }

  explore_params pars(start, target);
  explore_path(pars);

  if (pars.bestsofar == 0x7FFFFFFF)
    cout << "no path found\n";
  else
  { cout << "path of length " << pars.bestsofar << " miles found\n";
    for (int i = 0; i < pars.bestroadpath.size(); i += 1)
    { place * from = pars.bestplacepath[i], * to = pars.bestplacepath[i + 1];
      road * rd = pars.bestroadpath[i];
      cout << "from " << from->get_name() << " " << rd->get_name() << " " << rd->get_length()
           << " miles to " << to->get_name() << "\n"; } } }