#ifndef GRAPH_H_
#define GRAPH_H_

#include <ostream>
#include <ranges>
#include <vector>
#include <unordered_map>
#include <unordered_set>

namespace graph {

// Forward declerations
template <typename T> class Graph;
template <typename T> std::ostream &operator<<(std::ostream &os, Graph<T> &G);

template <typename T> class Graph {
public:
  virtual ~Graph() = default;

  // Return true if there is a path from u to v
  virtual bool contains(const T &u, const T &v) = 0;

  // Add edge e(u,v)
  virtual void insert(const T &u, const T &v) = 0;

  // Remove edge e(u,v)
  virtual void remove(const T &u, const T &v) = 0;

  // Return graph vertices
  auto vertices() const;

  // Return num. of vertices
  std::uint16_t V();

  // Return num. of edges
  std::uint16_t E();

  // Adjacency matrix representation
  std::unordered_map<T, std::unordered_set<T>> adjList;
};

template <typename T>
auto Graph<T>::vertices() const {
    std::vector<T> keys;
    keys.reserve(adjList.size());
    for (const auto& pair : adjList) {
        keys.push_back(pair.first);
    }
    return keys;
}

template <typename T> std::uint16_t Graph<T>::V() {
  return static_cast<std::uint16_t>(adjList.size());
}

template <typename T> std::uint16_t Graph<T>::E() {
  std::uint16_t edges = 0;
  for (const auto &u : vertices()) {
    edges += static_cast<std::uint16_t>(adjList[u].size());
  }
  return edges;
}

} // namespace graph

#endif