// graph_read1.cc    graph_read1 < dijkstra1.dat > dijkstra1.chk
//                   work around for g++ on UMBC9 (IRIX 6.5.3)
//                   <fstream> segmentation fault on my_io >> vert1 problem

#include <iostream>                    // console I/O
#include <string>                      // for input data
#include <algorithm>
#include <list>
#include <vector>
using namespace std;                   // bring standard names into scope

class my_vertex;  // just declaring my_vertex as a type

class my_edge     // the type of objects in the adjacency lists
{
  public:
    my_edge(string Aedge, int Aweight){edge=Aedge; weight=Aweight;}
    inline string get_edge(){ return edge;}
    inline my_vertex * get_vertex_ptr(){return vertex;}
    inline void set_vertex_ptr(my_vertex * ptr){vertex=ptr;}
    inline int get_weight(){ return weight;}
  private:         // these data items are for the adjacency list
    string edge;   // name of vertex (edge is from parent vertex to here)
    my_vertex * vertex; // pointer to this vertex in the vector
    int weight;    // weight of this edge
};
typedef list<my_edge> Adj;  // the type of each adjacency list
  
class my_vertex   // the type of objects in the vector of vertices
{
  public:
    my_vertex(string Avertex, int d)
              {vertex=Avertex; distance=d;}
    my_vertex(string Avertex, int d, my_edge Aedge)
              {vertex=Avertex; distance=d; edge_list.push_back(Aedge);}
    inline int get_distance(){return distance;}
    inline string get_vertex(){return vertex;}
    inline Adj get_edges(){return edge_list;}
    inline Adj * get_Adj_ptr(){return &edge_list;}
    inline void add_edge(string vert2, int weight)
                         {edge_list.push_back(my_edge(vert2, weight));}
    inline void set_distance(int d){distance=d;}
    inline bool exist(string s){return vertex==s;}
    inline bool is_done(){return done;}
    inline void set_done(bool state){done=state;}
  private:          // these data items are for each vertex
    string vertex;  // name of this vertex
    int distance;   // distance of this vertex from source vertex
    bool done;      // finished with this vertex
                    // other variables could go here for more applications
    Adj edge_list;  // the head of the edge list for this vertex
};
typedef vector<my_vertex> graph_type; // type of the graph object

typedef graph_type::iterator graph_iterator; // type of iterator for vector

// probably best if the above was in a header file and #include here

int main(int argc, char *argv[])       // standard main program definition
{

  string vert1;           // just a place for inputting
  string vert2;           // "
  int    weight;          // "
  
  graph_type G;           // The graph is stored in the object G
  graph_iterator vert;    // need an iterator through G
  graph_iterator vert_p2; // another iterator through G
  Adj temp;               // need a temporary Adj list
  Adj::iterator p;        // need a temporary iterator through temp
  bool found;             // temporary
  
  cout << "graph_read1 running" << endl; //trace execution 
  

  while(!cin.eof()) // loop until end of file
  {
    cin >> vert1;
    if(vert1==string("#") || vert1==string("") ) // ignore comments and empty
    {
      cin.ignore(100, '\n');
      continue;
    }
    cin >> vert2 >> weight; // read the other two fields on the line
    cout << vert1 << "  " << vert2 << "  " << weight << endl; //print what read
    // if vert1 not a vertex, construct it
    if(G.empty()) // special 
    {
      G.push_back(my_vertex(vert1, 0, my_edge(vert2, weight)));
      G.push_back(my_vertex(vert2, 10000));  // no Adj yet
    }
    else
    {
      // find and push_back if vert==G.end() for vert2 and vert1
      found = false; // look for vert2 in vector of vertices
      for(vert=G.begin(); vert!=G.end(); vert++)
      {
        if(vert->exist(vert2))
    	{
    	  found = true;
    	  break;
    	}
      }
      if(!found)  
      {
        // if vert2 not a vertex, construct it
	G.push_back(my_vertex(vert2, 10000)); // no Adj
      }
      found = false; // look for vert1 in vector of vertices
      for(vert=G.begin(); vert!=G.end(); vert++)
      {
	if(vert->exist(vert1))
	{
          vert->add_edge(vert2, weight);
	  found = true;
	  break;
	}
      }
      if(!found)  
      {
        // if vert1 not a vertex, construct it
	G.push_back(my_vertex(vert1, 10000,
		    my_edge(vert2, weight)));
      }
    } // end if for 'else'
  } // end of while not eof
  
  // OK, G vector will not be reallocated again,
  // fill in Adj to vector pointers
  for(vert=G.begin(); vert!=G.end(); vert++)
  {
    for(p=vert->get_Adj_ptr()->begin();
       p!=vert->get_Adj_ptr()->end(); p++)
    {
      vert2 = p->get_edge();
      for(vert_p2=G.begin(); vert_p2!=G.end(); vert_p2++)
      {
        if(vert_p2->exist(vert2))
	{
	  p->set_vertex_ptr(vert_p2);
          break;
	}
      }
    }
  }
  
  cout << "print out data structure G" << endl;
  cout << "G.begin(), G.end() " << G.begin() << ' '
       << G.end() << endl;
  for(vert=G.begin(); vert!=G.end(); vert++)
  {
    cout << vert->get_vertex() << " " << vert->get_distance()
	 << "  " << vert << endl;
    temp = vert->get_edges();
    cout << "        ";  // use begin()  end() to be safe 
      for(p=temp.begin(); p!=temp.end(); p++)
      cout << '(' << p->get_edge() << ','
	   << p->get_vertex_ptr() 
	   << ',' << p->get_weight() << ") ";
      cout << endl;  
  }

  // PUT PROJECT CODE HERE

  cout << "graph_read1 finished" << endl;
  return 0;
}