#include <iostream>
#include <iomanip>
#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 queue<valT> has
      queue(int initial_capacity);
      bool empty() const
      void add(const valT &);
      valT take()

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

template <typename T1, typename T2> struct couple
{ T1 a;
  T2 b;

  couple(const T1 & a0, const T2 & b0)
  { a = a0;
    b = b0; }

  T1 first() const
  { return a; }

  T2 second() const
  { return b; } };


int explore_path(place * here, place * target)
{ int best_so_far = 0x7FFFFFFF;
  set <place *> closed;
  queue <couple<place *, int> *> Q;
  Q.add(new couple(here, 0));

  while (! Q.empty())
  { couple<place *, int> * p = Q.take();
    place * here = p->first();
    int distance = p->second();
    cout << "from queue " << here->get_name() << ", distance so far " << distance << "\n";

    for (int i = 0; i < here->num_exits(); i += 1)
    { road * r = here->get_exit(i);
      int length = r->get_length();
      place * there = r->get_other_end(here);
      cout << "  checking " << r->get_name() << " to " << there->get_name() << "\n";

      if (there == target)
      { int total = distance + length;
        cout << "    found solution " << total << " miles\n";
        if (total < best_so_far)
          best_so_far = total; }

      else if (closed.contains(there))
      { cout << "    ignoring because in closed set\n";
        continue; }

      else
      { closed.add(there);
        couple<place *, int> * p = new couple(there, distance + r->get_length());
        cout << "    adding " << there->get_name() << " to queue with " << distance + r->get_length() << "\n";
        Q.add(p); } } }

  cout << "queue is empty, stopping\n";
  return best_so_far; }

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

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