#include "Graph.h"
#include <fstream>
#include <sstream>
#include <algorithm>
#include <climits>

Graph::Graph() : n(0), directed(false), weighted(false), form('C') {
    matrix.assign(1, std::vector<int>(1, 0));
}

Graph::Graph(int n_) : n(n_), directed(false), weighted(true), form('L') {
    adj.assign(n + 1, std::set<std::pair<int, int>>());
}

Graph::Graph(int n_, bool directed_, bool weighted_, char form_)
    : n(n_), directed(directed_), weighted(weighted_), form(form_) {
    if (form == 'C') matrix.assign(n + 1, std::vector<int>(n + 1, 0));
    else if (form == 'L') adj.assign(n + 1, std::set<std::pair<int, int>>());
}

void Graph::readGraph(std::string fileName) {
    std::ifstream in(fileName);
    if (!in.is_open()) return;

    char t;
    in >> t;
    form = t;

    int m = 0;
    if (form == 'E') in >> n >> m;
    else in >> n;

    int d, w;
    in >> d >> w;
    directed = (d == 1);
    weighted = (w == 1);

    matrix.clear();
    adj.clear();
    edges.clear();

    if (form == 'C') {
        matrix.assign(n + 1, std::vector<int>(n + 1, 0));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) in >> matrix[i][j];
        if (!directed) {
            for (int i = 1; i <= n; ++i)
                for (int j = i + 1; j <= n; ++j) {
                    if (matrix[i][j] == 0) matrix[i][j] = matrix[j][i];
                    if (matrix[j][i] == 0) matrix[j][i] = matrix[i][j];
                }
        }
    } else if (form == 'L') {
        adj.assign(n + 1, std::set<std::pair<int, int>>());
        std::string line;
        std::getline(in, line); // rest of the "D W" line
        for (int i = 1; i <= n; ++i) {
            std::getline(in, line);
            std::istringstream ss(line);
            if (weighted) {
                int v, wgt;
                while (ss >> v >> wgt) adj[i].insert({v, wgt});
            } else {
                int v;
                while (ss >> v) adj[i].insert({v, 1});
            }
        }
        if (!directed) {
            for (int u = 1; u <= n; ++u) {
                std::vector<std::pair<int, int>> snapshot(adj[u].begin(), adj[u].end());
                for (auto& pr : snapshot) adj[pr.first].insert({u, pr.second});
            }
        }
    } else { // 'E'
        edges.reserve(m);
        std::set<std::pair<int, int>> seen;
        for (int i = 0; i < m; ++i) {
            int a, b, wgt = 1;
            in >> a >> b;
            if (weighted) in >> wgt;
            if (!directed) {
                auto key = std::minmax(a, b);
                if (!seen.insert({key.first, key.second}).second) continue;
            }
            edges.push_back({a, b, wgt});
        }
    }
}

void Graph::writeGraph(std::string fileName) {
    std::ofstream out(fileName);
    if (!out.is_open()) return;

    if (form == 'E') out << "E " << n << ' ' << edges.size() << '\n';
    else out << form << ' ' << n << '\n';
    out << (directed ? 1 : 0) << ' ' << (weighted ? 1 : 0) << '\n';

    if (form == 'C') {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) out << matrix[i][j] << ' ';
            out << '\n';
        }
    } else if (form == 'L') {
        for (int i = 1; i <= n; ++i) {
            bool first = true;
            for (auto& e : adj[i]) {
                if (!first) out << ' ';
                first = false;
                out << e.first;
                if (weighted) out << ' ' << e.second;
            }
            out << '\n';
        }
    } else {
        for (auto& e : edges) {
            out << std::get<0>(e) << ' ' << std::get<1>(e);
            if (weighted) out << ' ' << std::get<2>(e);
            out << '\n';
        }
    }
    out << '\n';
}

bool Graph::hasEdge(int from, int to) const {
    if (from < 1 || from > n || to < 1 || to > n) return false;
    if (form == 'C') return matrix[from][to] != 0;
    if (form == 'L') {
        auto it = adj[from].lower_bound({to, INT_MIN});
        return it != adj[from].end() && it->first == to;
    }
    for (auto& e : edges)
        if ((std::get<0>(e) == from && std::get<1>(e) == to) ||
            (!directed && std::get<0>(e) == to && std::get<1>(e) == from))
            return true;
    return false;
}

int Graph::weightOf(int from, int to) const {
    if (from < 1 || from > n || to < 1 || to > n) return 0;
    if (form == 'C') return matrix[from][to];
    if (form == 'L') {
        auto it = adj[from].lower_bound({to, INT_MIN});
        if (it != adj[from].end() && it->first == to) return it->second;
        return 0;
    }
    for (auto& e : edges)
        if ((std::get<0>(e) == from && std::get<1>(e) == to) ||
            (!directed && std::get<0>(e) == to && std::get<1>(e) == from))
            return std::get<2>(e);
    return 0;
}

void Graph::addEdge(int from, int to, int weight) {
    if (!weighted) weight = 1;
    if (hasEdge(from, to)) return;
    if (form == 'C') {
        matrix[from][to] = weight;
        if (!directed) matrix[to][from] = weight;
    } else if (form == 'L') {
        adj[from].insert({to, weight});
        if (!directed) adj[to].insert({from, weight});
    } else {
        edges.push_back({from, to, weight});
    }
}

void Graph::removeEdge(int from, int to) {
    if (form == 'C') {
        if (matrix[from][to] == 0) return;
        matrix[from][to] = 0;
        if (!directed) matrix[to][from] = 0;
    } else if (form == 'L') {
        auto it = adj[from].lower_bound({to, INT_MIN});
        if (it != adj[from].end() && it->first == to) adj[from].erase(it);
        if (!directed) {
            auto jt = adj[to].lower_bound({from, INT_MIN});
            if (jt != adj[to].end() && jt->first == from) adj[to].erase(jt);
        }
    } else {
        for (auto it = edges.begin(); it != edges.end(); ++it) {
            bool match = (std::get<0>(*it) == from && std::get<1>(*it) == to) ||
                         (!directed && std::get<0>(*it) == to && std::get<1>(*it) == from);
            if (match) {
                edges.erase(it);
                break;
            }
        }
    }
}

int Graph::changeEdge(int from, int to, int newWeight) {
    if (!weighted) newWeight = 1;
    if (form == 'C') {
        int old = matrix[from][to];
        if (old == 0) return 0;
        matrix[from][to] = newWeight;
        if (!directed) matrix[to][from] = newWeight;
        return old;
    }
    if (form == 'L') {
        auto it = adj[from].lower_bound({to, INT_MIN});
        if (it == adj[from].end() || it->first != to) return 0;
        int old = it->second;
        adj[from].erase(it);
        adj[from].insert({to, newWeight});
        if (!directed) {
            auto jt = adj[to].lower_bound({from, INT_MIN});
            if (jt != adj[to].end() && jt->first == from) {
                adj[to].erase(jt);
                adj[to].insert({from, newWeight});
            }
        }
        return old;
    }
    for (auto& e : edges) {
        bool match = (std::get<0>(e) == from && std::get<1>(e) == to) ||
                     (!directed && std::get<0>(e) == to && std::get<1>(e) == from);
        if (match) {
            int old = std::get<2>(e);
            std::get<2>(e) = newWeight;
            return old;
        }
    }
    return 0;
}

std::vector<std::set<std::pair<int, int>>> Graph::toAdjList() const {
    if (form == 'L') return adj;

    std::vector<std::set<std::pair<int, int>>> g(n + 1);
    if (form == 'C') {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                if (i == j || matrix[i][j] == 0) continue;
                g[i].insert({j, matrix[i][j]});
                if (!directed) g[j].insert({i, matrix[i][j]});
            }
    } else {
        for (auto& e : edges) {
            int a = std::get<0>(e), b = std::get<1>(e), w = std::get<2>(e);
            g[a].insert({b, w});
            if (!directed) g[b].insert({a, w});
        }
    }
    return g;
}

std::vector<std::vector<int>> Graph::toMatrix() const {
    if (form == 'C') return matrix;

    std::vector<std::vector<int>> M(n + 1, std::vector<int>(n + 1, 0));
    if (form == 'L') {
        for (int u = 1; u <= n; ++u)
            for (auto& e : adj[u]) {
                M[u][e.first] = e.second;
                if (!directed) M[e.first][u] = e.second;
            }
    } else {
        for (auto& e : edges) {
            int a = std::get<0>(e), b = std::get<1>(e), w = std::get<2>(e);
            M[a][b] = w;
            if (!directed) M[b][a] = w;
        }
    }
    return M;
}

std::vector<std::tuple<int, int, int>> Graph::toEdgeList() const {
    if (form == 'E') return edges;

    std::vector<std::tuple<int, int, int>> el;
    if (form == 'L') {
        for (int u = 1; u <= n; ++u)
            for (auto& e : adj[u]) {
                if (!directed && e.first < u) continue;
                el.push_back({u, e.first, e.second});
            }
    } else {
        for (int i = 1; i <= n; ++i)
            for (int j = (directed ? 1 : i); j <= n; ++j) {
                if (matrix[i][j] == 0) continue;
                el.push_back({i, j, matrix[i][j]});
            }
    }
    return el;
}

std::vector<std::set<int>> Graph::toSimpleAdj() const {
    auto g = toAdjList();
    std::vector<std::set<int>> nb(n + 1);
    for (int u = 1; u <= n; ++u)
        for (auto& e : g[u]) {
            nb[u].insert(e.first);
            nb[e.first].insert(u);
        }
    return nb;
}

void Graph::transformToAdjList() {
    if (form == 'L') return;
    adj = toAdjList();
    matrix.clear();
    edges.clear();
    form = 'L';
}

void Graph::transformToAdjMatrix() {
    if (form == 'C') return;
    matrix = toMatrix();
    adj.clear();
    edges.clear();
    form = 'C';
}

void Graph::transformToListOfEdges() {
    if (form == 'E') return;
    edges = toEdgeList();
    matrix.clear();
    adj.clear();
    form = 'E';
}