package jnpf.elnService.formula;

import jnpf.elnEntity.formula.ElnTemplateFormulaBindingEntity;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

public class FormulaDependencyGraph {

    public Result validate(Collection<ElnTemplateFormulaBindingEntity> bindings) {
        Map<String, ElnTemplateFormulaBindingEntity> nodes = new LinkedHashMap<>();
        Map<String, String> resultOwners = new HashMap<>();
        for (ElnTemplateFormulaBindingEntity item : bindings == null
                ? Collections.<ElnTemplateFormulaBindingEntity>emptyList() : bindings) {
            if (item != null && "ACTIVE".equals(item.getBangdingZhuangtai())) {
                nodes.put(item.getId(), item);
                resultOwners.put(item.getJieguoBangdingId(), item.getId());
            }
        }
        Map<String, Set<String>> edges = new LinkedHashMap<>();
        Map<String, Integer> indegrees = new LinkedHashMap<>();
        for (String id : nodes.keySet()) {
            edges.put(id, new LinkedHashSet<>());
            indegrees.put(id, 0);
        }
        for (ElnTemplateFormulaBindingEntity consumer : nodes.values()) {
            for (String fieldBindingId : safeValues(consumer.getCanshuYingshe())) {
                String producer = resultOwners.get(fieldBindingId);
                if (producer != null && edges.get(producer).add(consumer.getId())) {
                    indegrees.put(consumer.getId(), indegrees.get(consumer.getId()) + 1);
                }
            }
        }
        PriorityQueue<String> ready = new PriorityQueue<>();
        indegrees.forEach((id, degree) -> { if (degree == 0) ready.add(id); });
        List<String> order = new ArrayList<>();
        while (!ready.isEmpty()) {
            String current = ready.poll();
            order.add(current);
            List<String> next = new ArrayList<>(edges.get(current));
            next.sort(Comparator.naturalOrder());
            for (String target : next) {
                int degree = indegrees.get(target) - 1;
                indegrees.put(target, degree);
                if (degree == 0) ready.add(target);
            }
        }
        if (order.size() == nodes.size()) return Result.valid(order);
        return Result.cycle(findCycle(edges));
    }

    private static Collection<String> safeValues(Map<String, String> values) {
        return values == null ? Collections.emptyList() : values.values();
    }

    private static List<String> findCycle(Map<String, Set<String>> edges) {
        Map<String, Integer> colors = new HashMap<>();
        List<String> stack = new ArrayList<>();
        List<String> ids = new ArrayList<>(edges.keySet());
        Collections.sort(ids);
        for (String id : ids) {
            List<String> cycle = dfs(id, edges, colors, stack);
            if (!cycle.isEmpty()) return cycle;
        }
        return Collections.emptyList();
    }

    private static List<String> dfs(String id, Map<String, Set<String>> edges,
            Map<String, Integer> colors, List<String> stack) {
        int color = colors.getOrDefault(id, 0);
        if (color == 2) return Collections.emptyList();
        if (color == 1) {
            int start = stack.indexOf(id);
            List<String> cycle = new ArrayList<>(stack.subList(start, stack.size()));
            cycle.add(id);
            return cycle;
        }
        colors.put(id, 1);
        stack.add(id);
        List<String> targets = new ArrayList<>(edges.getOrDefault(id, Collections.emptySet()));
        Collections.sort(targets);
        for (String target : targets) {
            List<String> cycle = dfs(target, edges, colors, stack);
            if (!cycle.isEmpty()) return cycle;
        }
        stack.remove(stack.size() - 1);
        colors.put(id, 2);
        return Collections.emptyList();
    }

    public static final class Result {
        private final List<String> topologicalOrder;
        private final List<String> cyclePath;
        private Result(List<String> order, List<String> cycle) {
            this.topologicalOrder = Collections.unmodifiableList(new ArrayList<>(order));
            this.cyclePath = Collections.unmodifiableList(new ArrayList<>(cycle));
        }
        static Result valid(List<String> order) { return new Result(order, Collections.emptyList()); }
        static Result cycle(List<String> cycle) { return new Result(Collections.emptyList(), cycle); }
        public boolean isValid() { return cyclePath.isEmpty(); }
        public List<String> getTopologicalOrder() { return topologicalOrder; }
        public List<String> getCyclePath() { return cyclePath; }
    }
}