#include "Graph.h"
#include "Edge.h"
#include "Vertex.h"

#include <string>
#include <iostream>

/**
* @return The number of vertices in the Graph
*/
template <class V, class E>
unsigned int Graph<V,E>::numVertices() const {
  // TODO: Part 2

  return vertexMap.size();
}


/**
* The degree of the vertex. For directed: Sum of in-degree and out-degree
* @return Returns the degree of a given vertex.
* @param v Given vertex to return degree.
*/
template <class V, class E>
unsigned int Graph<V,E>::degree(const V & v) const {
  // TODO: Part 2
  std::string v_key = v.key();
  auto search = adjList.find(v_key);

  if(search != adjList.end()){
    return search->second.size();
  }
  return 0;
}


/**
* Inserts a Vertex into the Graph.
* @param key The key of the Vertex to insert
* @return The inserted Vertex
*/
template <class V, class E>
V & Graph<V,E>::insertVertex(std::string key) {
  // TODO: Part 2
  V & v = *(new V(key));
  vertexMap.insert(std::pair<std::string, V_byRef>(key, v));
  std::list<edgeListIter> v_list;
  adjList.insert(std::pair<std::string, std::list<edgeListIter>>(key, v_list));
  return v;
}


/**
* Removes a given Vertex
* @param v The Vertex to remove
*/
template <class V, class E>
void Graph<V,E>::removeVertex(const std::string & key) {
  // TODO: Part 2
  auto vertex_search = vertexMap.find(key);
  if(vertex_search != vertexMap.end()){
    vertexMap.erase(vertex_search);
    auto list_search = adjList.find(key);
    // for(auto it = list_search->second.begin(); it != list_search->second.end(); it++){
    //   //figure this part out
    //   if()
    // }
    adjList.erase(list_search);
  }
}


/**
* Inserts an Edge into the Graph.
* @param v1 The source Vertex
* @param v2 The destination Vertex
* @return The inserted Edge
*/
template <class V, class E>
E & Graph<V,E>::insertEdge(const V & v1, const V & v2) {
  // TODO: Part 2
  E & e = *(new E(v1, v2));
  //adding to edge list
  edgeList.push_back(e);
  //adding to adjacency list
  auto v1_search = adjList.find(v1.key());
  if(v1_search == adjList.end()){
    std::list<edgeListIter> edgeList;
    edgeList.push_back(e);
    adjList.insert(std::pair<std::string, std::list<edgeListIter>>(v1.key(), edgeList));
  }else{
    v1_search->second.push_back(v2);
  }

  auto v2_search = adjList(v2.key());
  if(v2_search == adjList.end()){
    std::list<edgeListIter> edgeList;
    edgeList.push_back(e);
    adjList.insert(std::pair<std::string, std::list<edgeListIter>>(v2.key(), edgeList));
  }else{
    v2_search->second.push_back(v1);
  }

  return e;
}


/**
* Removes an Edge from the Graph. Consider both the undirected and directed cases.
* min(degree(key1), degree(key2))
* @param key1 The key of the source Vertex
* @param key2 The key of the destination Vertex
*/
template <class V, class E>
void Graph<V,E>::removeEdge(const std::string key1, const std::string key2) {
  // TODO: Part 2
}


/**
* Removes an Edge from the Graph given by the location of the given iterator into the edge list.
* @param it An iterator at the location of the Edge that
* you would like to remove
*/
template <class V, class E>
void Graph<V,E>::removeEdge(const edgeListIter & it) {
  // TODO: Part 2
}


/**
* Return the list of incident edges from a given vertex.
* For the directed case, consider all edges that has the vertex as either a source or destination.
* @param key The key of the given vertex
* @return The list edges (by reference) that are adjacent to the given vertex
*/
template <class V, class E>
const std::list<std::reference_wrapper<E>> Graph<V,E>::incidentEdges(const std::string key) const {
  // TODO: Part 2
  std::list<std::reference_wrapper<E>> edges;
  return edges;
}


/**
* Return whether the two vertices are adjacent to one another. Consider both the undirected and directed cases.
* When the graph is directed, v1 and v2 are only adjacent if there is an edge from v1 to v2.
* @param key1 The key of the source Vertex
* @param key2 The key of the destination Vertex
* @return True if v1 is adjacent to v2, False otherwise
*/
template <class V, class E>
bool Graph<V,E>::isAdjacent(const std::string key1, const std::string key2) const {
  // TODO: Part 2
  return false;
}