package io.papermc.paper.plugin.entrypoint.strategy;

import com.google.common.graph.Graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TopographicGraphSorter {

    // Topographically sort dependencies
    public static <N> List<N> sortGraph(Graph<N> graph) throws PluginGraphCycleException {
        List<N> sorted = new ArrayList<>();
        Deque<N> roots = new ArrayDeque<>();
        Map<N, Integer> nonRoots = new HashMap<>();

        for (N node : graph.nodes()) {
            // Is a node being referred to by any other nodes?
            int degree = graph.inDegree(node);
            if (degree == 0) {
                // Is a root
                roots.add(node);
            } else {
                // Isn't a root, the number represents how many nodes connect to it.
                nonRoots.put(node, degree);
            }
        }

        // Pick from nodes that aren't referred to anywhere else
        while (!roots.isEmpty()) {
            N next = roots.remove();

            for (N successor : graph.successors(next)) {
                // Traverse through, moving down a degree
                int newInDegree = nonRoots.get(successor) - 1;

                if (newInDegree == 0) {
                    nonRoots.remove(successor);
                    roots.add(successor);
                } else {
                    nonRoots.put(successor, newInDegree);
                }

            }
            sorted.add(next);
        }

        if (!nonRoots.isEmpty()) {
            throw new GraphCycleException();
        }

        return sorted;
    }

    public static class GraphCycleException extends RuntimeException {

    }
}
