#ifndef GRAPH_H
#define GRAPH_H

// You are not required to use the classes below HOWEVER it is
// strongly recommended that you do so or at least use the class(es)
// below as a starting point - you may create your own classes,
// modify the ones below, inherit from the ones below, templatize
// the ones below, or just use the ones below (probably with a few
// additions).

#include <vector>
#include <list>
#include <map>
#include <string>
#include <iostream>

typedef std::string Vertex;

class Edge {

      friend std::ostream & operator<< ( std::ostream &, const Edge & ) ;
      // Should output the edge without a newline or any blank
      // space before or after it.  For example, if the weight
      // is 15 and dest AAA output would be:
      //   AAA(15)           or in bnf terms [stop]([int])

   public:

      Edge ( Vertex, int ) ;
      // virtual ~Edge ( ) { }      <--- uncomment if needed

      int getWeight ( ) const ;
      void setWeight ( int weightIn ) ;
         // throw an exception if negative weight
      Vertex getDestVertex ( ) const ;
      bool operator< ( const Edge &right ) const ;

      // You may add other public functions here or you can
      // inherit from this class

   protected:

      void setDestVertex ( Vertex vertIn ) ;

   private: 

     Vertex dest;  // destination vertex
     int weight;   // weight in minutes
     // should add the bus "name" as a member here

};


class Graph {

   public:

      Graph ( ) ;

      int numVertices ( ) const ;
      int numEdges ( ) const ;

      bool addVertex ( Vertex v ) ;
      bool addEdge ( Vertex start, Vertex dest, int weight ) ;
      bool updateEdge ( Vertex start, Vertex dest, int weight ) ;
      bool delEdges ( Vertex start, Vertex dest ) ;
      bool hasEdge ( Vertex start, Vertex dest ) const ;

      void clear ( ) ; // removes all edges
      void reset ( ) ; // clears entire graph (vertices and edges)

      std::vector<Vertex> getVertices ( ) const ;
      std::list<Edge> getEdges ( Vertex v ) const ;

      int getIndex ( Vertex v ) const ;
           // returns index of v in vector below or -1 if not found
      Vertex getVertex ( int i ) const ;
           // returns vertex in vector below at index i or throws
           // exception if not found

      std::list<Edge> shortestPath_v1 ( Vertex start, Vertex end ) const ;
           // do not print anything out (unless for temporary debugging)
           // should return the path and another function can process
           // and display it as appropriate

   private:

      std::map<Vertex, std::list<Edge>> adjList; // Adjacency List
      std::vector<Vertex> vertices;

      // static const int INFINITY = ... fill in

};

std::ostream & operator<<( std::ostream &out, const Graph &g );

#endif