#include <queue>
#include <algorithm>
#include <string>
#include <list>

/**
 * Returns an std::list of vertex keys that creates some shortest path between `start` and `end`.
 *
 * This list MUST include the key of the `start` vertex as the first vertex in the list, the key of
 * the `end` vertex as the last element in the list, and an ordered list of all vertexMap that must
 * be traveled along the shortest path.
 *
 * For example, the path a -> c -> e returns a list with three elements: "a", "c", "e".
 *
 * @param start The key for the starting vertex.
 * @param end   The key for the ending vertex.
 */
template <class V, class E>
std::list<std::string> Graph<V,E>::shortestPath(const std::string start, const std::string end) {
  struct Vertex {
    std::string key;
    int length;

    Vertex() {
      key = "";
      length = 0;
    }

    Vertex(std::string theKey, int theLength) {
      key = theKey;
      length = theLength;
    }
  };


  std::list<std::string> path;
  std::queue<string> q;
  q.push(start);

  std::unordered_map<std::string, Vertex> vertexMap;
  vertexMap.insert(make_pair(start, Vertex()));

  while (!q.empty()) {
    std::string & key = q.front();
    q.pop();

    Vertex vertex = vertexMap.at(key);
    std::list<reference_wrapper<E>> edges = incidentEdges(key);

    for (typename std::list<reference_wrapper<E>>::iterator it = edges.begin(); it != edges.end(); it++) {
      Edge edge = (*it).get();
      std::string edgeKey;

      if (edge.dest().key() != key) {
        edgeKey = edge.dest().key();
      } else {
        edgeKey = edge.source().key();
      }

      bool shouldClear = false;

      if (vertexMap.find(edgeKey) == vertexMap.end()) {
        q.push(edgeKey);
        vertexMap.insert(make_pair(edgeKey, Vertex(key, 1 + vertex.length)));

        shouldClear = true;
      }

      if (shouldClear && end == edgeKey) {
        while (!q.empty()) {
          q.pop();
        }

        break;
      }
    }
  }

  std::string current = end;

  while (current.length() != 0) {
    path.push_front(current);
    current = vertexMap.at(current).key;
  }

  return path;
}