#ifndef GRAPH_HPP_
#define GRAPH_HPP_

#include <iostream>
#include <fstream>
#include <utility>
#include <functional>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <unordered_map>
#include <limits>
#include "index_pq.hpp"
#include "my_integer.hpp"

template <typename T>
class Graph {
 private:
  std::vector<std::unordered_map<int, T> > adjList {};
  int numVertices {};

 public:
  // empty graph with N vertices
  explicit Graph(int N);

  // construct graph from edge list in filename
  explicit Graph(const std::string& filename);

  // add an edge directed from vertex i to vertex j with given weight
  void addEdge(int i, int j, T weight);

  // removes edge from vertex i to vertex j
  void removeEdge(int i, int j);

  // is there an edge from vertex i to vertex j?
  bool isEdge(int i, int j) const;

  // return weight of edge from i to j
  // will throw an exception if there is no edge from i to j
  T getEdgeWeight(int i, int j) const;

  // returns number of vertices in the graph
  int size() const;

  // alias a const iterator to our adjacency list type to iterator
  using iterator = 
  typename std::vector<std::unordered_map<int, T> >::const_iterator;

  // cbegin returns const iterator pointing to first element of adjList
  iterator begin() const {
    return adjList.cbegin();
  }

  iterator end() const {
    return adjList.cend();
  }

  // return iterator to a particular vertex
  iterator neighbours(int a) const {
    return adjList.begin() + a;
  }
};

template <typename T>
Graph<T>::Graph(int N) : adjList(N), numVertices {N} {}

template <typename T>
Graph<T>::Graph(const std::string& inputFile) {
  std::ifstream infile {inputFile};
  if (!infile) {
    std::cerr << inputFile << " could not be opened\n";
    return;
  }
  // first line has number of vertices
  infile >> numVertices;
  adjList.resize(numVertices);
  int i {};
  int j {};
  double weight {};
  // assume each remaining line is of form
  // origin dest weight
  while (infile >> i >> j >> weight) {
    addEdge(i, j, static_cast<T>(weight));
  }
}

template <typename T>
int Graph<T>::size() const {
  return numVertices;
}

template <typename T>
void Graph<T>::addEdge(int i, int j, T weight) {
  if (i < 0 or i >= numVertices or j < 0 or j >= numVertices) {
    throw std::out_of_range("invalid vertex number");
  }
  adjList[i].insert({j, weight});
}

template <typename T>
void Graph<T>::removeEdge(int i, int j) {
  // check if i and j are valid
  if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {
    adjList[i].erase(j);
  }
}

template <typename T>
bool Graph<T>::isEdge(int i, int j) const {
  if (i >= 0 && i < numVertices && j >= 0 && j < numVertices) {
    return adjList.at(i).contains(j);
  }
  return false;
}

template <typename T>
T Graph<T>::getEdgeWeight(int i, int j) const {
  return adjList.at(i).at(j);
}

template <typename T>
std::ostream& operator<<(std::ostream& out, const Graph<T>& G) {
  for (int i = 0; i < G.size(); ++i) {
    out << i << ':';
    for (const auto& [neighbour, weight] : *(G.neighbours(i))) {
      out << " (" << i << ", " << neighbour << ")[" << weight << ']';
    }
    out << '\n';
  }
  return out;
}

// End of functions from Graph class











































template <typename T>
bool isSubgraph(const Graph<T>& H, const Graph<T>& G) {
  if (H.size() > G.size()) {
    return false;
  }
  for (int i = 0; i < H.size(); ++i) {
    for (int j = 0; j < H.size(); ++j) {
      if (H.isEdge(i,j)) {
        if (!G.isEdge(i,j) || (G.getEdgeWeight(i,j) != H.getEdgeWeight(i,j))) {
          return false;
        }
      }
    }
  }
  return true;
}










template <typename T>
bool isTreePlusIsolated(const Graph<T>& G, int root) {//Takes too long, try fixing when you can...
  std::vector<bool> visited(G.size(), false);
  std::queue<int> q {};
  int node {};
  q.push(root);
  while (!q.empty()) {
    node = q.front();
    q.pop();
    if (!visited[node]) {
      for (auto& v : *(G.neighbours(node))) {
        q.push(v.first);
      }
      visited[node] = true;
    } else {
      return false;
    }
  }
for (int v = 0; v < G.size(); ++v) {
    if (!visited[v]) {
      for (int u = 0; u < G.size(); ++u) {
        if (G.isEdge(u,v)) {
          return false;
        }
      }
    }
  }
  return true;
}


template <typename T>
std::vector<T> pathLengthsFromRoot(const Graph<T>& tree, int root) {//Make this quicker somehow... maybe try using their iterators?
  std::vector<T> bestDistanceTo(tree.size());
  std::queue<int> q {};
  int node {};
  q.push(root);
  //bestDistanceTo[root] = 0;
  while (!q.empty()) {
    node = q.front();
    q.pop();
    for (auto& v : *(tree.neighbours(node))) {
        bestDistanceTo[v.first] = bestDistanceTo[node] + v.second;
        q.push(v.first);
      }
    }
    return bestDistanceTo;
}























template <typename T>
bool allEdgesRelaxed(const std::vector<T>& bestDistanceTo, const Graph<T>& G, 
                      int source) {
  T null {};
  if (bestDistanceTo[source] != null) {
    return false;
  }
  std::vector<T> dist = bestDistanceTo;
  for (int v = 0; v < G.size(); ++v) {
    for (int u = 0; u < G.size(); ++u) {
      if (G.isEdge(u,v)) {
        if (dist.at(v) > dist.at(u) + G.getEdgeWeight(u, v)) {
          return false;
        }
      }
    }
  }
  return true;
}

// return a number of type T to stand in for "infinity"
template <typename T>
T infinity() {
  if (std::numeric_limits<T>::has_infinity) {
    return std::numeric_limits<T>::infinity();
  } else if constexpr (std::is_same_v<T, MyInteger>) {
    return MyInteger {std::numeric_limits<int>::max()};
  } else {
    return std::numeric_limits<T>::max();
  }
}

// lazy solution as in Tutorial Week 10
template <typename T>
std::vector<T> singleSourceLazyDistance(const Graph<T>& G, int source) {
  // alias the long name for a minimum priority queue holding
  // objects of type DistAndVertex
  using DistAndVertex = std::pair<T, int>;
  using minPQ = std::priority_queue<DistAndVertex,
                                  std::vector<DistAndVertex>,
                                  std::greater<DistAndVertex> >;
  minPQ queue {};
  queue.push({T {}, source});
  // record best distance to vertex found so far
  int N = G.size();
  std::vector<T> bestDistanceTo(N, infinity<T>());
  bestDistanceTo.at(source) = T {};
  // being in visited means we have already explored a vertex's neighbours
  // the bestDistanceTo for a vertex in visited is the true distance.
  std::vector<bool> visited(N);
  while (!queue.empty()) {
    auto [dist, current] = queue.top();
    queue.pop();
    // as we use a lazy version of Dijkstra a vertex can appear multiple
    // times in the queue.  If we have already visited the vertex we
    // take out of the queue we just go on to the next one
    if (visited.at(current)) {
      continue;
    }
    visited.at(current) = true;
    // relax all outgoing edges of current
    for (const auto& [neighbour, weight] : *(G.neighbours(current))) {
      T distanceViaCurrent = bestDistanceTo.at(current) + weight;
      if (bestDistanceTo.at(neighbour) > distanceViaCurrent) {
        bestDistanceTo.at(neighbour) = distanceViaCurrent;
        // lazy dijkstra: nextPoint could already be in the queue
        // we don't update it with better distance just found.
        queue.push({distanceViaCurrent, neighbour});
      }
    }
  }
  return bestDistanceTo;
}


























// Implement your solution using an index priority queue here
template <typename T>
Graph<T> singleSourceIndex(const Graph<T>& G, int source) {
  int n = G.size();//Save |V| for ease of access
  std::vector<int> path(n, -1);//Initialise path vector
  std::vector<T> bestDistanceTo(n, infinity<T>());//Initialise "Best distance to" vector
  bestDistanceTo.at(source) = T {}; //The source's shortest path is trivial
  IndexPriorityQueue<T> q(n);//Initialise queue
  for (int v = 0; v < n; ++v) {
    q.push(bestDistanceTo.at(v), v);//Populate queue with each vertex and its path; this holds the invariant that all unknwon shortest paths still live on the queue
  }
  while (!q.empty()) {
    auto [dist, current] = q.top();
    q.pop();
    for (const auto& [neighbour, weight] : *(G.neighbours(current))) {
      T distanceViaCurrent = bestDistanceTo.at(current) + weight;
      if (bestDistanceTo.at(neighbour) > distanceViaCurrent) {
        bestDistanceTo.at(neighbour) = distanceViaCurrent;
        path.at(neighbour) = current;
        q.changeKey(bestDistanceTo.at(neighbour), neighbour);
      }
    }
  }
  Graph<T> tree(n);
  for (int v = 0; v < n; ++v) {
    if (path.at(v) != -1) {
      tree.addEdge(path.at(v), v, G.getEdgeWeight(path.at(v),v));
    }
  }
  return tree;
}






// Implement your lazy solution using std::priority_queue here
template <typename T>
Graph<T> singleSourceLazy(const Graph<T>& G, int source) {
  //Credit to the Week 10 tutorial as a grand contributor to this code.
  using DistAndVertex = std::pair<T, int>;
  using minPQ = std::priority_queue<DistAndVertex,
                                  std::vector<DistAndVertex>,
                                  std::greater<DistAndVertex> >;
  minPQ queue {};//Initialise queue
  queue.push({T {}, source});//Initialise source vertex on queue
  int N = G.size();//Save |V| for ease of access
  std::vector<T> bestDistanceTo(N, infinity<T>());// Initialise "Best distance to" vector
  std::vector<int> path(N, -1);//Initialise path vector
  bestDistanceTo.at(source) = T {};
  // being in visited means we have already explored a vertex's neighbours
  // the bestDistanceTo for a vertex in visited is the true distance.
  std::vector<bool> visited(N);

  while (!queue.empty()) {
    auto [dist, current] = queue.top();//Extract priority vertex
    queue.pop();
    if (!visited.at(current)) {
      visited.at(current) = true;
      for (const auto& [neighbour, weight] : *(G.neighbours(current))) {//Populate queue with vertexes without known shortest path
        T distanceViaCurrent = bestDistanceTo.at(current) + weight;
        if (bestDistanceTo.at(neighbour) > distanceViaCurrent) {//This condition lets Lazy Dijkstra handle shorter paths to vertexes first, ignoring longer paths
          bestDistanceTo.at(neighbour) = distanceViaCurrent;
          path.at(neighbour) = current;
          queue.push({distanceViaCurrent, neighbour});//Lazy Dijksta; 
        }
      }
    }
  }
  Graph<T> tree(N);
  for (int v = 0; v < N; ++v) {
    if (path.at(v) != -1) {//Form the shortest path tree
      tree.addEdge(path.at(v), v, G.getEdgeWeight(path.at(v),v));
    }
  }
  return tree;
}





// Implement your solution using std::set here
template <typename T>
Graph<T> singleSourceSet(const Graph<T>& G, int source) {
  return Graph<T> {G.size()};
}




// put your "best" solution here
// this is the one we will use for performance testing
template <typename T>
Graph<T> singleSourceShortestPaths(const Graph<T>& G, int source) {
  return singleSourceIndex(G, source); 
}

#endif      // GRAPH_HPP_
