/*##############################################################################
## Author: Shaun Reed                                                         ##
## Legal: All Content (c) 2022 Shaun Reed, all rights reserved                ##
## About: Graph implementations to solve various problems in C++              ##
##                                                                            ##
## Contact: shaunrd0@gmail.com  | URL: www.shaunreed.com | GitHub: shaunrd0   ##
################################################################################
*/

#include <iostream>
#include <unordered_map>
#include <map>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstdint>

#ifndef GRAPHS_LIB_GRAPH_HPP
#define GRAPHS_LIB_GRAPH_HPP


namespace Simple {
  typedef int32_t Node;
  typedef std::vector<Node> Nodes;
  typedef std::vector<Nodes> Edges;

  class Graph {
  public:
    Graph() = default;
    explicit Graph(Edges e) : edges(std::move(e)) { }

    void Print()
    {
      for (size_t node = 0; node < edges.size(); node++) {
        for (const auto & to : edges[node]) {
          std::cout << "(" << node << ")-----(" << to << ")" << std::endl;
        }
      }
    }

    // Where graph[i] represents the connection between node i and graph[i]
    // {1, 1, 2, 2}
    void ReadEdges(const std::vector<int> & graph)
    {
      edges.clear();
      edges.assign(graph.size(), {});
      for (int i = 0; i < graph.size(); i++) {
        if (i == graph[i]) continue;
        edges[graph[i]].push_back(i);
        edges[i].push_back(graph[i]);
      }
    }

    // Where each graph[i] represents a single edge between two nodes
    // { {1, 2}, {2, 3}, {3, 1} }
    void ReadEdges(const std::vector<std::pair<int, int>> & graph)
    {
      edges.clear();
      for (const auto & edge : graph) {
        while (edges.size() <= edge.first || edges.size() <= edge.second) {
          edges.emplace_back();
        }
        edges[edge.first].push_back(edge.second);
        edges[edge.second].push_back(edge.first);
      }
    }

    // Where graph[node] holds all connected adjacent nodes
    // {{1}, {2, 3}, {2, 1, 0}}
    void ReadEdges(const std::vector<std::vector<int>> & graph)
    {
      edges.clear();
      edges.assign(graph.size(), {});
      for (size_t i = 0; i < graph.size(); i++) {
        for (const auto & adj : graph[i]) {
          if (adj == i) continue;
          edges[i].push_back(adj);
          edges[adj].push_back(int32_t(i));
        }
      }
    }

  private:
    Edges edges;
  };
}


namespace Object {
  struct Node {
    Node() : val(INT32_MIN), adj() { }
    explicit Node(int32_t v) : val(v), adj() { }
    Node(int32_t v, std::vector<int32_t> a) : val(v), adj(std::move(a)) { }

    int32_t val;
    std::vector<int32_t> adj;

    // Define operator== for std::find; And comparisons between nodes
    bool operator==(const Node & b) const { return this->val == b.val;}
    bool operator!=(const Node & b) const { return this->val != b.val;}
  };

  typedef std::vector<Node> Edges;

  class Graph {
  public:
    Graph() = default;
    explicit Graph(Edges e) : edges(std::move(e)) { }

    void Print()
    {
      for (int32_t node = 0; node < edges.size(); node++) {
        for (const auto & to : GetNode(node)->adj) {
          std::cout << "(" << node << ")-----(" << to << ")" << std::endl;
        }
      }
    }

    Node * GetNode(const int32_t & nodeVal)
    {
      auto foundNode = std::find(edges.begin(), edges.end(), Node(nodeVal));
//                       [nodeVal](const Node & a)->bool { return a.val == nodeVal;});
      if (foundNode == edges.end()) return nullptr; // Node does not exist
      return &*foundNode;
    }

    Node * CreateNode(const int32_t & nodeVal)
    {
      auto newNode = GetNode(nodeVal);
      if (newNode != nullptr) return newNode;
      // Create node if not found
      edges.emplace_back(nodeVal); // Calls Node(int32_t) ctor
      return &edges.back(); // Get ptr to our new node; Don't copy it
    }

    // Where graph[i] represents the connection between node i and graph[i]
    // {1, 1, 2, 2}
    void ReadEdges(const std::vector<int> & graph)
    {
      edges.clear();
      for (int i = 0; i < graph.size(); i++) {
        if (i == graph[i]) continue;
        // Check if nodes already exist; Create them if not found
        auto nodeFrom = CreateNode(graph[i]);
        auto nodeTo = CreateNode(i);
        // Push node ptr to adjacent list
        nodeFrom->adj.push_back(nodeTo->val);
        nodeTo->adj.push_back(nodeFrom->val);
      }
    }

    // Where each graph[i] represents a single edge between two nodes
    // { {1, 2}, {2, 3}, {3, 1} }
    void ReadEdges(const std::vector<std::pair<int, int>> & graph)
    {
      edges.clear();
      for (const auto & edge : graph) {
        auto nodeFrom = CreateNode(edge.first);
        auto nodeTo = CreateNode(edge.second);
        nodeFrom->adj.push_back(nodeTo->val);
        nodeTo->adj.push_back(nodeFrom->val);
      }
    }

    // Where graph[node] holds all connected adjacent nodes
    // {{1}, {2, 3}, {2, 1, 0}}
    void ReadEdges(const std::vector<std::vector<int>> & graph)
    {
      edges.clear();
      edges.assign(graph.size(), {});
      for (size_t i = 0; i < graph.size(); i++) {
        for (const auto & adj : graph[i]) {
          if (adj == i) continue;
          auto nodeFrom = CreateNode(int32_t(i));
          auto nodeTo = CreateNode(adj);
          nodeFrom->adj.push_back(nodeTo->val);
          nodeTo->adj.push_back(nodeFrom->val);
        }
      }
    }

  private:
    Edges edges;
  };
}

namespace Weighted {
  using Weight = int32_t;
  using Adjacent = std::multimap<Weight, int32_t>;
  struct Node {
    Node() : val(INT32_MIN), adj() { }
    explicit Node(int32_t v) : val(v), adj() { }
    Node(int32_t v, Adjacent a) : val(v), adj(std::move(a)) { }

    int32_t val;
    Adjacent adj;
  };
  using Edge = std::pair<int, int>;

  class Graph {
    Graph() = default;
    explicit Graph(Node n) : root(std::move(n)) { }
    void ReadGraph(std::vector<std::vector<int>> nodeList)
    {
      // Read a 2D vector of nodes into a
    }
  private:
    Node root;
  };
}


//namespace Object {
//struct Edge {
//    friend struct Node;
//    friend class Graph;
//    Edge() : from(INT32_MIN), to(INT32_MIN) { }
//    Edge(const int32_t & f, const int32_t & t) : from(f), to(t) { }
//
//  private:
//    int32_t from, to;
//  };
//  using Edges = std::vector<Edge>;
//
////  template <typename T, typename S>
////  struct Subscriptor {
////    T<int32_t, S> data;
////  };
//
//  struct Node {
//    using Adjacent = std::vector<Node *>;
//    using NodeMap = std::unordered_map<int32_t, Node *>;
//    friend class Graph; // Allow Graph to access protected / private members
//    friend struct GraphData;
//
//    // Struct is public by default
//    Node () : val(0), adj() { }
//    explicit Node(int32_t v) : val(v), adj() { }
//    Node(int32_t v, Adjacent a) : val(v), adj(std::move(a)) { }
//    inline void SetAdjacent(Adjacent a) { adj = std::move(a);}
//    inline void SetVal(int32_t v) { val = v;}
//    NodeMap GetNodeMap() {
//      NodeMap result;
//      BuildNodeMap(&result);
//      return result;
//    }
//    void BuildNodeMap(NodeMap & nodeMap, Node * startNode=nullptr) {
//      auto list = startNode == nullptr ? adj : startNode->adj;
//      for (const auto & node : list) {
//        if (!nodeMap.count(node->val)) {
//          nodeMap[node->val] = node;
//          BuildNodeMap(nodeMap, startNode);
//        }
//      }
//    }
//
//  protected:
//    int32_t val;
//    Adjacent adj;
//    Edges edges;
//  };
//
//  struct GraphData {
//    GraphData() = default;
//    explicit GraphData(const Node & n)
//    {
//      graphEdges n.edges;
//      for (const auto & edge : n.edges) {
//      }
//    }
//
//    // Implement subscript operators for unordered_multimap
//    struct GraphEdges {
//      Edges * operator[](int32_t nodeVal) {
//        auto found = graphEdges.find(nodeVal):
//        if (found != graphEdges.end()) {
//          return &*found->second;
//        }
//        else {
//          return nullptr;
//        }
//      }
//      std::unordered_multimap<int32_t, Edges *> graphEdges;
//    };
//
//    // Implement subscript operators for unordered_map
//    struct GraphNodes {
//      Node * operator[](int32_t nodeVal) {
//        auto found = graphNodes.find(nodeVal):
//        if (found != graphNodes.end()) {
//          return &*found->second;
//        }
//        else {
//          return nullptr;
//        }
//      }
//      std::unordered_map<int32_t, Node *> graphNodes;
//    };
//    // unordered_* provides O(1) access and search
//    GraphEdges graphEdges;
//    GraphNodes graphNodes;
//  };
//
//  class Graph {
//    // Class is private by default
//    Node root;
//    std::unordered_map<int32_t, Node *> graphNodes;
//    std::multimap<int32_t, Edges> graphEdges;
////    std::unordered_map<int32_t, Node *> graphNodes;
////    GraphData data; // Struct containing all graph edges / nodes
//
//  public:
//    Graph() = default;
//    explicit Graph(Node r) : root(std::move(r)) { }
//
//    inline const Node & GetRoot() const { return root;}
////    inline Node * GetNode(int32_t nodeVal) { return data.graphNodes[nodeVal];}
////    inline const Node * GetConstNode(int32_t nodeVal)
////    { return data.graphNodes[nodeVal];}
//
//    const Node * DFS(int32_t nodeVal, int32_t startNode=INT32_MIN)
//    {
//      // If startNode was not set, begin search from root node
//      startNode = startNode == INT32_MIN ? root.val : startNode;
//      if (startNode == nodeVal) {
//        return graphNodes[nodeVal];
//      }
//      for (const auto & edge : root.edges) {
//        return DFS(nodeVal, edge.to);
//      }
//    }
//  };
//}

#endif // GRAPHS_LIB_GRAPH_HPP