#pragma once
#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
#include <iostream>

class Edge {
  public:
    unsigned int u, v;

    bool operator==(const Edge &e) const { return u == e.u && v == e.v; }
};

class StoredEdge {
  public:
    Edge e;
    // indices into adjacency lists
    // adj[u][u2vindex] = v;
    // adj[v][v2uindex] = u;
    unsigned int u2vindex, v2uindex;
};

class DiDegree {
  public:
    unsigned int in;
    unsigned int out;
};

typedef std::vector<unsigned int> DegreeSequence;
typedef std::vector<DiDegree> DiDegreeSequence;

template< class RandomIt, class Compare >
void insertionSort( RandomIt first, RandomIt last, Compare comp ) {
    if (first == last)
        return;
    for (RandomIt next = first;;) {
        RandomIt a = next;
        next++;
        if (next == last)
            break;
        RandomIt b = next;
        auto newvalue = *next;
        //             next
        // 1 2 3 4 5 6  4
        //           a  b
        // 1 2 3 4 5 x  6
        //         a b
        // 1 2 3 4 x 5  6
        //       a b
        // 1 2 3 4 4 5  6
        while (b != first && comp(newvalue, *a)) { // if newvalue < *a
            *b = *a;
            b = a--;
        }
        *b = newvalue;
    }
}

class Graph {
  public:
    Graph() {}

    Graph(unsigned int n) { reset(n); }

    ~Graph() {}

    // Clears any previous edges and create
    // an empty graph on n vertices
    void reset(unsigned int n) {
        edges.clear();
        adj.resize(n);
        for (auto &v : adj)
            v.clear();
        badj.resize(n);
        for (auto &v : badj) {
            v.resize(n);
            v.assign(n, false);
        }
    }

    unsigned int edgeCount() const { return edges.size(); }

    const Edge &getEdge(unsigned int i) const { return edges[i].e; }

    const auto& getAdj() const { return adj; }

    const auto& getBooleanAdj() const { return badj; }

    // When the degree sequence is not graphics, the Graph can be
    // in any state, it is not neccesarily empty
    bool createFromDegreeSequence(const DegreeSequence &d, bool slowSort = false) {
        // Havel-Hakimi algorithm
        // Based on Erdos-Gallai theorem

        unsigned int n = d.size();

        // degree, vertex index
        std::vector<std::pair<unsigned int, unsigned int>> degrees(n);
        for (unsigned int i = 0; i < n; ++i) {
            degrees[i].first = d[i];
            degrees[i].second = i;
        }

        // Clear the graph
        reset(n);

        // First use general sorting algorithm
        std::sort(
            degrees.begin(), degrees.end(),
            [](const auto &p1, const auto &p2) { return p1.first < p2.first; });

        while (!degrees.empty()) {
            // Highest degree is at back of the vector
            // Take it out
            unsigned int degree = degrees.back().first;
            unsigned int u = degrees.back().second;
            degrees.pop_back();
            // In the end, all remaining degrees are zero
            if (degree == 0) {
                break;
            }
            if (degree > degrees.size()) {
                return false;
            }
            // Now loop over the last 'degree' entries of degrees
            auto rit = degrees.rbegin();
            for (unsigned int i = 0; i < degree; ++i) {
                if (rit->first == 0 || !addEdge({u, rit->second})) {
                    return false;
                }
                rit->first--;
                ++rit;
            }
            // To compare influence of sorting methods
            if (slowSort) {
                // Re-sort using general sort
                std::sort(degrees.begin(), degrees.end(),
                              [](const auto &p1, const auto &p2) {
                                  return p1.first < p2.first;
                              });
            } else {
                // Re-sort using insertion sort
                insertionSort(degrees.begin(), degrees.end(),
                              [](const auto &p1, const auto &p2) {
                                  return p1.first < p2.first;
                              });
            }
        }
        return true;
    }

    DegreeSequence getDegreeSequence() const {
        DegreeSequence d(adj.size());
        std::transform(adj.begin(), adj.end(), d.begin(),
                       [](const auto &u) { return u.size(); });
        return d;
    }

    // Assumes valid vertex indices
    bool hasEdge(const Edge& e_) const {
        return badj[e_.u][e_.v];
        //Edge e;
        //if (adj[e_.u].size() <= adj[e_.v].size()) {
        //    e = e_;
        //} else {
        //    e.u = e_.v;
        //    e.v = e_.u;
        //}
        //for (unsigned int v : adj[e.u]) {
        //    if (v == e.v)
        //        return true;
        //}
        //return false;
    }

    bool addEdge(const Edge &e) {
        if (e.u >= adj.size() || e.v >= adj.size())
            return false;
        if (hasEdge(e))
            return false;
        StoredEdge se;
        se.e = e;
        se.u2vindex = adj[e.u].size();
        se.v2uindex = adj[e.v].size();
        adj[e.u].push_back(e.v);
        adj[e.v].push_back(e.u);
        edges.push_back(se);
        badj[e.u][e.v] = 1;
        badj[e.v][e.u] = 1;
        return true;
    }

    // There are two possible edge exchanges
    // switchType indicates which one is desired
    // Returns false if the switch is not possible
    bool exchangeEdges(unsigned int e1index, unsigned int e2index,
                       bool switchType, bool trackTriangles = false) {
        StoredEdge &se1 = edges[e1index];
        StoredEdge &se2 = edges[e2index];
        const Edge &e1 = se1.e;
        const Edge &e2 = se2.e;

        // The new edges configuration is one of these two
        // A) e1.u - e2.u and e1.v - e2.v
        // B) e1.u - e2.v and e2.u - e1.v
        // Note that to do (B) instead of (A), simply swap e2.u <-> e2.v
        // Now we can just consider switch type (A)
        if (switchType) {
            std::swap(se2.e.u, se2.e.v);
            std::swap(se2.u2vindex, se2.v2uindex);
        }

        // First check if the move is possible
        if (hasEdge({e1.u, e2.u}) || hasEdge({e1.v, e2.v}))
            return false; // conflicting edges

        if (trackTriangles) {
            trackedTriangles -= countTriangles(e1);
            trackedTriangles -= countTriangles(e2);
        }

        // Clear old edges
        badj[e1.u][e1.v] = false;
        badj[e1.v][e1.u] = false;
        badj[e2.u][e2.v] = false;
        badj[e2.v][e2.u] = false;

        adj[e1.u][se1.u2vindex] = e2.u;
        adj[e1.v][se1.v2uindex] = e2.v;
        adj[e2.u][se2.u2vindex] = e1.u;
        adj[e2.v][se2.v2uindex] = e1.v;
        // Carefull: when updating se1,se2 also e1 and 2e change
        std::swap(se1.e.v, se2.e.u);
        std::swap(se1.v2uindex, se2.u2vindex);
        // e1 and e2 now contain the NEW edges!!
        badj[e1.u][e1.v] = true;
        badj[e1.v][e1.u] = true;
        badj[e2.u][e2.v] = true;
        badj[e2.v][e2.u] = true;

        if (trackTriangles) {
            trackedTriangles += countTriangles(e1);
            trackedTriangles += countTriangles(e2);
        }

        return true;
    }

    // Assumes edge exists
    // Used for computing triangle-delta's after switch move
    unsigned int countTriangles(Edge e) const {
        auto triangles = 0u;
        if (adj[e.u].size() > adj[e.v].size())
            std::swap(e.u, e.v);
        for (auto w : adj[e.u]) {
            if (hasEdge({w, e.v}))
                ++triangles;
        }
        return triangles;
    }

    unsigned int countTriangles() const {
        auto triangles = 0u;
        for (auto& v : adj) {
            for (unsigned int i = 0; i < v.size(); ++i) {
                for (unsigned int j = i + 1; j < v.size(); ++j) {
                    if (hasEdge({v[i], v[j]})) {
                        ++triangles;
                    }
                }
            }
        }
        assert(triangles % 3 == 0);
        return triangles / 3;
    }

    unsigned int& getTrackedTriangles() { return trackedTriangles; }

    // Should return zero
    int consistencyCheck() const {
        // Check if info in 'edges' is present
        // in adj and badj
        for (auto &se : edges) {
            if (se.e.u >= adj.size() || se.e.v >= adj.size())
                return 1;
            if (!badj[se.e.u][se.e.v])
                return 2;
            if (!badj[se.e.v][se.e.u])
                return 3;
            if (se.u2vindex >= adj[se.e.u].size())
                return 4;
            if (se.v2uindex >= adj[se.e.v].size())
                return 5;
            if (adj[se.e.u][se.u2vindex] != se.e.v)
                return 6;
            if (adj[se.e.v][se.v2uindex] != se.e.u)
                return 7;
        }
        // Check if info in 'adj' is present
        // in badj and edges
        for (unsigned int u = 0; u < adj.size(); ++u) {
            for (unsigned int v : adj[u]) {
                if (!badj[u][v])
                    return 8;
                if (!badj[v][u])
                    return 9;
                // Check if it appears in edges
                bool found = false;
                for (auto &se : edges) {
                    if ((se.e.u == u && se.e.v == v) ||
                        (se.e.u == v && se.e.v == u)) {
                        found = true;
                        break;
                    }
                }
                if (!found)
                    return 10;
            }
        }
        // Check if info in 'badj' is present
        // in adj and edges
        // TODO
        return 0;
    }

  private:
    // Graph is saved in three formats for speed
    // They should be kept consistent at all times
    std::vector<std::vector<unsigned int>> adj;
    std::vector<std::vector<bool>> badj; // symmetric binary matrix
    std::vector<StoredEdge> edges;
    unsigned int trackedTriangles;
};