#ifndef GRAPH_H
#define GRAPH_H

#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <memory>


template<class Vertice>
class Graph
// My stl-based implementation of an undirected weighted graph.
// It operates only on vertice numbers and stores associated objects
// in vector<shared_ptr>. Each vertice caches its neighboring indeces as set<int>.
// Edges are tracked as map< pair<int,int>, int> - two vertice numbers to weight.
// All functions that take two vertice indeces are symmetric:
// calls some_function( index1, index2 ) and some_function( index2, index1) are equivalent.
{
public:
    typedef std::pair<int, int> EdgeKey;
    typedef std::shared_ptr<Vertice> SpVertice;

    Graph(int capacity) :
    // constructor reservers space for selected capacity
        verticeNeighbors(capacity, std::set<int>())
    {
        vertices.reserve(capacity);
    }

    int V() const
    //returns the number of vertices in the graph
    {
        return vertices.size();
    }

    int E() const
    //returns the number of edges in the graph
    {
        return edges.size();
    }

    Vertice* vertice(int index) const
    // pass out vertice associated with index
    {
        auto it = vertices.at(index);
        return it.get();
    }

    void addVertice(SpVertice sp)
    {
        vertices.push_back(sp);
    }

    int distance(int x, int y) const
    // returns non-negative value if there is an edge from node x to node y or -1 otherwise
    {
        vertices.at(x);
        vertices.at(y);
        // the code above should throw out_of_bounds if indeces are wrong
        auto iElement = vertices.find(makeEdgeKey(x, y));
        if (iElement == vertices.end())
            return -1;
        else
            return iElement->second;
    }

    void connect(int x, int y, int weight = 0)
    //adds to G the edge from x to y, or sets new weight to existing edge
    {
        vertices.at(x);
        vertices.at(y);
        // the code above should throw out_of_bounds if indeces are wrong
        edges.insert(std::make_pair(makeEdgeKey(x, y), weight));

        verticeNeighbors[x].insert(y);
        verticeNeighbors[y].insert(x);
    }

    void disconnect(int x, int y)
    //removes the edge from x to y, if it is there
    {
        vertices.at(x);
        vertices.at(y);
        // the code above should throw out_of_bounds if indeces are wrong
        edges.erase(makeEdgeKey(x, y));
        verticeNeighbors[x].erase(y);
        verticeNeighbors[y].erase(x);
    }


    std::set<int> neighbors(int index) const
    //lists all nodes y such that there is an edge from x to y.
    {
        return verticeNeighbors.at(index);;
    }


private:
    std::map<EdgeKey, int> edges;
    std::vector<SpVertice> vertices;
    std::vector<std::set<int>> verticeNeighbors;

    EdgeKey makeEdgeKey(int x, int y)
    // construct a two-value key where values are ordered
    {
        if(x > y)
            return std::make_pair(y, x);
        else
            return std::make_pair(x, y);
    }
};

template <class Vertice>
std::ostream& operator<< (std::ostream& stream, const Graph<Vertice>& G)
{
    int v = G.V();
    int e = G.E();

    std::cout << "Graph of " << v << " vertices and " << e << " edges:" << std::endl;

    for(int i = 0; i < v; i++)
    {
        std::cout << "V(" << *G.vertice(i) << ") : ";
        auto neighbors = G.neighbors(i);

        for(auto p : neighbors)
        {
            std::cout << p << " ";
        }
        std::cout << std::endl;
    }

    return stream;
}


#endif // GRAPH_H