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

struct ant_record
{ place * road_start, * road_end;
  int length, progress, total;
  
  ant_record(place * s, place * e, int l, int t, int p = 0)
  { road_start = s;
    road_end = e;
    length = l;
    progress = p;
    total = t; } };

struct ant_link
{ ant_record * data;
  ant_link * prev, * next;

  ant_link(ant_record * a, ant_link * p = NULL, ant_link * n = NULL)
  { data = a;
    prev = p;
    next = n; } };

class ant_list
{ protected:
    ant_link * first, * last, * scan_curr, * scan_prev, * scan_last;

  public:
    ant_list()
    { first = NULL;
      last = NULL;
      scan_last = NULL;
      scan_curr = NULL;
      scan_prev = NULL; }

    void add(ant_record * a)
    { ant_link * ne = new ant_link(a, last, NULL);
      if (first == NULL)
      { first = ne;
        last = ne; }
      else
      { last->next = ne;
        last = ne; } }

    bool start_scan()
    { scan_curr = first;
      scan_prev = NULL;
      scan_last = last;
      return scan_curr != NULL; }

    ant_record * get_next()
    { if (scan_curr == NULL)
        return NULL;
      ant_record * a = scan_curr->data;
      scan_prev = scan_curr;
      if (scan_curr == scan_last)
        scan_curr = NULL;
      else
        scan_curr = scan_curr->next;
      return a; }

    void remove_last()
    { if (scan_prev == NULL)
      { cerr << "remove_last called before start_scan and get_next\n";
        exit(1); }
      ant_link * prevprev = scan_prev->prev;
      if (scan_prev == last)
      { last = prevprev;
        if (last == NULL)
          first = NULL;
        else
          last->next = NULL; }
      else
      { scan_prev->next->prev = prevprev;
        if (prevprev == NULL)
          first = scan_prev->next;
        else
          prevprev->next = scan_prev->next; } }

    void delete_last()
    { delete scan_prev->data;
      delete scan_prev;
      scan_prev = NULL; } };

string pls(place * p)
{ if (p == NULL)
    return "nowhere";
  return p->get_name(); }

int explore_path(place * here, place * target)
{ set <place *> beento;
  ant_list AL;
  AL.add(new ant_record(NULL, here, 0, 0, -1));

  for (int time = 0; true; time += 1)
  { bool ok = AL.start_scan();
    if (! ok)
      break;
    while (true)
    { ant_record * ants = AL.get_next();
      if (ants == NULL)
        break;
      ants->progress += 1;
      if (ants->progress == ants->length)
      { AL.remove_last();
        place * arrived = ants->road_end;
        beento.add(arrived);
        int travelled = ants->total + ants->length;
        cout << "Arrived at " << arrived->get_name() << " after " << travelled << " miles\n";
        if (arrived == target)
        { cout << "********* Reached destination *********\n";
          return travelled; }
        int n = arrived->num_exits();
        for (int ex = 0; ex < n; ex += 1)
        { road * rd = arrived->get_exit(ex);
          place * there = rd->get_other_end(arrived);
          if (beento.contains(there))
            continue;
          AL.add(new ant_record(arrived, there, rd->get_length(), travelled)); }
        AL.delete_last(); } } }
  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); } }

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