use crate::graph_builder::build_graph;
use serde::{Deserialize, Serialize};
use std::collections::HashSet;

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct HealthScore {
    pub name: String,
    pub overall: f64,
    pub connectivity: f64,
    pub reachability: f64,
    pub centrality: f64,
    pub cycle_risk: f64,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct HealthReport {
    pub scores: Vec<HealthScore>,
    pub avg_connectivity: f64,
    pub avg_reachability: f64,
    pub avg_centrality: f64,
    pub avg_cycle_risk: f64,
    pub avg_overall: f64,
    pub node_count: usize,
    pub edge_count: usize,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct TerseHealthReport {
    pub top_scores: Vec<TerseHealthScore>,
    pub bottom_scores: Vec<TerseHealthScore>,
    pub avg_overall: f64,
    pub avg_cycle_risk: f64,
    pub node_count: usize,
    pub edge_count: usize,
}

#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct TerseHealthScore {
    pub name: String,
    pub overall: f64,
}

pub fn terse_health_report(edges: &[(String, String)], n: usize) -> TerseHealthReport {
    if edges.is_empty() {
        return TerseHealthReport {
            top_scores: Vec::new(),
            bottom_scores: Vec::new(),
            avg_overall: 0.0,
            avg_cycle_risk: 0.0,
            node_count: 0,
            edge_count: 0,
        };
    }

    let graph = build_graph(edges);
    let node_vec = &graph.node_vec;
    let out_adj = &graph.out_adj;
    let in_adj = &graph.in_adj;
    let node_count = graph.node_count();
    if node_count == 0 {
        return TerseHealthReport {
            top_scores: Vec::new(),
            bottom_scores: Vec::new(),
            avg_overall: 0.0,
            avg_cycle_risk: 0.0,
            node_count: 0,
            edge_count: 0,
        };
    }

    let fwd_sccs = compute_sccs(node_count, out_adj);
    let bwd_sccs = compute_sccs(node_count, in_adj);
    let cycle_nodes = find_cycles_from_sccs(out_adj, &fwd_sccs);

    let fwd_reach = compute_reachability_with_sccs(node_count, out_adj, &fwd_sccs);
    let bwd_reach = compute_reachability_with_sccs(node_count, in_adj, &bwd_sccs);

    let total_possible = (node_count - 1).max(1) as f64;
    let total_degree: f64 = out_adj.iter().map(|s| s.len()).sum::<usize>() as f64;
    let avg_degree = total_degree / node_count as f64;

    let mut raw_scores: Vec<TerseHealthScore> = Vec::with_capacity(node_count);
    let mut sum_overall: f64 = 0.0;
    let mut sum_cycle_risk: f64 = 0.0;

    for (i, name) in node_vec.iter().enumerate() {
        let out_degree = out_adj[i].len() as f64;
        let in_degree = in_adj[i].len() as f64;
        let connectivity =
            (out_degree + in_degree) / (2.0 * avg_degree.max(1.0)).min(total_degree.max(1.0));
        let connectivity = connectivity.min(1.0);

        let reach_fwd = (fwd_reach[i] as f64 - 1.0) / total_possible;
        let reach_bwd = (bwd_reach[i] as f64 - 1.0) / total_possible;
        let reachability = (reach_fwd + reach_bwd) / 2.0;

        let centrality = if node_count > 1 {
            (fwd_reach[i] + bwd_reach[i]) as f64 / (2.0 * node_count as f64)
        } else {
            1.0
        };

        let cycle_risk = if cycle_nodes.contains(&i) { 1.0 } else { 0.0 };

        let overall = connectivity * 0.25
            + reachability * 0.25
            + centrality * 0.25
            + (1.0 - cycle_risk) * 0.25;

        sum_overall += overall;
        sum_cycle_risk += cycle_risk;

        raw_scores.push(TerseHealthScore {
            name: name.clone(),
            overall,
        });
    }

    let n = n.min(node_count);

    let (mut top_candidates, mut bottom_candidates) = {
        let mut sorted = raw_scores;
        sorted.sort_by(|a, b| {
            b.overall
                .partial_cmp(&a.overall)
                .unwrap_or(std::cmp::Ordering::Equal)
        });
        let top: Vec<TerseHealthScore> = sorted.iter().take(n).cloned().collect();
        let bottom: Vec<TerseHealthScore> = sorted.iter().rev().take(n).cloned().collect();
        (top, bottom)
    };

    top_candidates.sort_by(|a, b| {
        b.overall
            .partial_cmp(&a.overall)
            .unwrap_or(std::cmp::Ordering::Equal)
    });
    bottom_candidates.sort_by(|a, b| {
        a.overall
            .partial_cmp(&b.overall)
            .unwrap_or(std::cmp::Ordering::Equal)
    });

    TerseHealthReport {
        top_scores: top_candidates,
        bottom_scores: bottom_candidates,
        avg_overall: sum_overall / node_count as f64,
        avg_cycle_risk: sum_cycle_risk / node_count as f64,
        node_count,
        edge_count: edges.len(),
    }
}

fn compute_reachability_with_sccs(
    n: usize,
    adj: &[HashSet<usize>],
    sccs: &[Vec<usize>],
) -> Vec<usize> {
    let mut comp_of = vec![0usize; n];
    for (comp_id, members) in sccs.iter().enumerate() {
        for &node in members {
            comp_of[node] = comp_id;
        }
    }
    let num_comps = sccs.len();
    let mut comp_adj: Vec<HashSet<usize>> = vec![HashSet::new(); num_comps];
    for u in 0..n {
        for &v in &adj[u] {
            let cu = comp_of[u];
            let cv = comp_of[v];
            if cu != cv {
                comp_adj[cu].insert(cv);
            }
        }
    }
    let mut comp_reach = vec![0usize; num_comps];
    for c in 0..num_comps {
        let mut visited = vec![false; num_comps];
        visited[c] = true;
        let mut count = 0usize;
        let mut queue = std::collections::VecDeque::from([c]);
        while let Some(cur) = queue.pop_front() {
            count += sccs[cur].len();
            for &next in &comp_adj[cur] {
                if !visited[next] {
                    visited[next] = true;
                    queue.push_back(next);
                }
            }
        }
        comp_reach[c] = count;
    }
    let mut reach = vec![0usize; n];
    for i in 0..n {
        reach[i] = comp_reach[comp_of[i]];
    }
    reach
}

fn compute_sccs(n: usize, adj: &[HashSet<usize>]) -> Vec<Vec<usize>> {
    struct Tarjan<'a> {
        adj: &'a [HashSet<usize>],
        index: usize,
        stack: Vec<usize>,
        on_stack: Vec<bool>,
        indices: Vec<Option<usize>>,
        lowlinks: Vec<usize>,
        components: Vec<Vec<usize>>,
    }

    impl<'a> Tarjan<'a> {
        fn new(n: usize, adj: &'a [HashSet<usize>]) -> Self {
            Self {
                adj,
                index: 0,
                stack: Vec::new(),
                on_stack: vec![false; n],
                indices: vec![None; n],
                lowlinks: vec![0; n],
                components: Vec::new(),
            }
        }

        fn strongconnect(&mut self, v: usize) {
            self.indices[v] = Some(self.index);
            self.lowlinks[v] = self.index;
            self.index += 1;
            self.stack.push(v);
            self.on_stack[v] = true;

            let neighbors: Vec<usize> = self.adj[v].iter().copied().collect();
            for w in neighbors {
                if self.indices[w].is_none() {
                    self.strongconnect(w);
                }
                if self.on_stack[w] {
                    self.lowlinks[v] = self.lowlinks[v].min(self.indices[w].unwrap());
                }
            }

            if self.indices[v] == Some(self.lowlinks[v]) {
                let mut component = Vec::new();
                loop {
                    let w = self.stack.pop().unwrap();
                    self.on_stack[w] = false;
                    component.push(w);
                    if w == v {
                        break;
                    }
                }
                self.components.push(component);
            }
        }
    }

    let mut tarjan = Tarjan::new(n, adj);
    for v in 0..n {
        if tarjan.indices[v].is_none() {
            tarjan.strongconnect(v);
        }
    }
    tarjan.components
}

fn find_cycles_from_sccs(adj: &[HashSet<usize>], sccs: &[Vec<usize>]) -> HashSet<usize> {
    let mut in_cycle = HashSet::new();
    for component in sccs {
        if component.len() > 1 {
            for &node in component {
                in_cycle.insert(node);
            }
        } else if component.len() == 1 {
            let v = component[0];
            if adj[v].contains(&v) {
                in_cycle.insert(v);
            }
        }
    }
    in_cycle
}

pub fn composite_health_score(edges: &[(String, String)]) -> HealthReport {
    if edges.is_empty() {
        return HealthReport {
            scores: Vec::new(),
            avg_connectivity: 0.0,
            avg_reachability: 0.0,
            avg_centrality: 0.0,
            avg_cycle_risk: 0.0,
            avg_overall: 0.0,
            node_count: 0,
            edge_count: 0,
        };
    }

    let graph = build_graph(edges);
    let node_vec = &graph.node_vec;
    let out_adj = &graph.out_adj;
    let in_adj = &graph.in_adj;
    let n = graph.node_count();
    if n == 0 {
        return HealthReport {
            scores: Vec::new(),
            avg_connectivity: 0.0,
            avg_reachability: 0.0,
            avg_centrality: 0.0,
            avg_cycle_risk: 0.0,
            avg_overall: 0.0,
            node_count: 0,
            edge_count: 0,
        };
    }

    let fwd_sccs = compute_sccs(n, out_adj);
    let bwd_sccs = compute_sccs(n, in_adj);
    let cycle_nodes = find_cycles_from_sccs(out_adj, &fwd_sccs);

    let fwd_reach = compute_reachability_with_sccs(n, out_adj, &fwd_sccs);
    let bwd_reach = compute_reachability_with_sccs(n, in_adj, &bwd_sccs);

    let total_possible = (n - 1).max(1) as f64;
    let total_degree: f64 = out_adj.iter().map(|s| s.len()).sum::<usize>() as f64;
    let avg_degree = total_degree / n as f64;

    let mut scores = Vec::with_capacity(n);
    for (i, name) in node_vec.iter().enumerate() {
        let out_degree = out_adj[i].len() as f64;
        let in_degree = in_adj[i].len() as f64;
        let connectivity =
            (out_degree + in_degree) / (2.0 * avg_degree.max(1.0)).min(total_degree.max(1.0));
        let connectivity = connectivity.min(1.0);

        let reach_fwd = (fwd_reach[i] as f64 - 1.0) / total_possible;
        let reach_bwd = (bwd_reach[i] as f64 - 1.0) / total_possible;
        let reachability = (reach_fwd + reach_bwd) / 2.0;

        let centrality = if n > 1 {
            (fwd_reach[i] + bwd_reach[i]) as f64 / (2.0 * n as f64)
        } else {
            1.0
        };

        let cycle_risk = if cycle_nodes.contains(&i) { 1.0 } else { 0.0 };

        let overall = connectivity * 0.25
            + reachability * 0.25
            + centrality * 0.25
            + (1.0 - cycle_risk) * 0.25;

        scores.push(HealthScore {
            name: name.clone(),
            overall,
            connectivity,
            reachability,
            centrality,
            cycle_risk,
        });
    }

    let avg_connectivity = scores.iter().map(|s| s.connectivity).sum::<f64>() / n as f64;
    let avg_reachability = scores.iter().map(|s| s.reachability).sum::<f64>() / n as f64;
    let avg_centrality = scores.iter().map(|s| s.centrality).sum::<f64>() / n as f64;
    let avg_cycle_risk = scores.iter().map(|s| s.cycle_risk).sum::<f64>() / n as f64;
    let avg_overall = scores.iter().map(|s| s.overall).sum::<f64>() / n as f64;

    scores.sort_by(|a, b| {
        b.overall
            .partial_cmp(&a.overall)
            .unwrap_or(std::cmp::Ordering::Equal)
    });

    HealthReport {
        scores,
        avg_connectivity,
        avg_reachability,
        avg_centrality,
        avg_cycle_risk,
        avg_overall,
        node_count: n,
        edge_count: edges.len(),
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn e(a: &str, b: &str) -> (String, String) {
        (a.to_string(), b.to_string())
    }

    #[test]
    fn empty_graph() {
        let report = composite_health_score(&[]);
        assert_eq!(report.node_count, 0);
        assert_eq!(report.scores.len(), 0);
    }

    #[test]
    fn single_edge() {
        let edges = vec![e("a", "b")];
        let report = composite_health_score(&edges);
        assert_eq!(report.node_count, 2);
        assert_eq!(report.scores.len(), 2);
    }

    #[test]
    fn hub_node_scores_higher() {
        let edges = vec![e("hub", "a"), e("hub", "b"), e("hub", "c"), e("a", "b")];
        let report = composite_health_score(&edges);
        let hub = report.scores.iter().find(|s| s.name == "hub").unwrap();
        let a = report.scores.iter().find(|s| s.name == "a").unwrap();
        assert!(hub.overall > a.overall, "hub should score higher than leaf");
    }

    #[test]
    fn cycle_free_zero_cycle_risk() {
        let edges = vec![e("a", "b"), e("b", "c")];
        let report = composite_health_score(&edges);
        for score in &report.scores {
            assert_eq!(
                score.cycle_risk, 0.0,
                "{} should have no cycle risk",
                score.name
            );
        }
    }

    #[test]
    fn cycle_increases_cycle_risk() {
        let edges = vec![e("a", "b"), e("b", "a")];
        let report = composite_health_score(&edges);
        for score in &report.scores {
            assert_eq!(
                score.cycle_risk, 1.0,
                "{} should have cycle risk",
                score.name
            );
        }
    }

    #[test]
    fn dense_cycle_does_not_recurse_on_current_node() {
        let edges = vec![
            e("alpha", "beta"),
            e("alpha", "gamma"),
            e("beta", "alpha"),
            e("beta", "gamma"),
            e("gamma", "alpha"),
            e("gamma", "beta"),
        ];
        let report = composite_health_score(&edges);
        assert_eq!(report.node_count, 3);
        assert_eq!(report.avg_cycle_risk, 1.0);
    }

    #[test]
    fn overall_scores_bounded() {
        let edges = vec![
            e("a", "b"),
            e("b", "c"),
            e("c", "d"),
            e("d", "a"),
            e("a", "c"),
        ];
        let report = composite_health_score(&edges);
        for score in &report.scores {
            assert!(
                score.overall >= 0.0 && score.overall <= 1.0,
                "{} overall={}",
                score.name,
                score.overall
            );
            assert!(score.connectivity >= 0.0 && score.connectivity <= 1.0);
            assert!(score.reachability >= 0.0 && score.reachability <= 1.0);
            assert!(score.centrality >= 0.0 && score.centrality <= 1.0);
        }
    }

    #[test]
    fn sorted_by_overall_descending() {
        let edges = vec![e("a", "b"), e("a", "c"), e("b", "c")];
        let report = composite_health_score(&edges);
        for i in 1..report.scores.len() {
            assert!(report.scores[i - 1].overall >= report.scores[i].overall);
        }
    }

    #[test]
    fn terse_empty() {
        let report = terse_health_report(&[], 5);
        assert_eq!(report.node_count, 0);
        assert_eq!(report.top_scores.len(), 0);
        assert_eq!(report.bottom_scores.len(), 0);
        assert_eq!(report.avg_overall, 0.0);
    }

    #[test]
    fn terse_matches_composite() {
        let edges = vec![
            e("a", "b"),
            e("a", "c"),
            e("b", "c"),
            e("c", "d"),
            e("d", "a"),
        ];
        let full = composite_health_score(&edges);
        let terse = terse_health_report(&edges, 2);
        assert_eq!(terse.node_count, full.node_count);
        assert_eq!(terse.edge_count, full.edge_count);
        assert!((terse.avg_overall - full.avg_overall).abs() < 1e-10);
        assert!((terse.avg_cycle_risk - full.avg_cycle_risk).abs() < 1e-10);
        assert_eq!(terse.top_scores.len(), 2);
        assert_eq!(terse.bottom_scores.len(), 2);
        assert_eq!(terse.top_scores[0].name, full.scores[0].name);
        assert!((terse.top_scores[0].overall - full.scores[0].overall).abs() < 1e-10);
    }

    #[test]
    fn terse_top_sorted_descending() {
        let edges = vec![e("hub", "a"), e("hub", "b"), e("hub", "c"), e("a", "b")];
        let terse = terse_health_report(&edges, 2);
        for i in 1..terse.top_scores.len() {
            assert!(terse.top_scores[i - 1].overall >= terse.top_scores[i].overall);
        }
    }

    #[test]
    fn terse_bottom_sorted_ascending() {
        let edges = vec![e("hub", "a"), e("hub", "b"), e("hub", "c"), e("a", "b")];
        let terse = terse_health_report(&edges, 2);
        for i in 1..terse.bottom_scores.len() {
            assert!(terse.bottom_scores[i - 1].overall <= terse.bottom_scores[i].overall);
        }
    }

    #[test]
    fn terse_n_larger_than_nodes() {
        let edges = vec![e("a", "b")];
        let terse = terse_health_report(&edges, 10);
        assert_eq!(terse.top_scores.len(), 2);
        assert_eq!(terse.bottom_scores.len(), 2);
    }

    #[test]
    fn terse_scores_bounded() {
        let edges = vec![
            e("a", "b"),
            e("b", "c"),
            e("c", "d"),
            e("d", "a"),
            e("a", "c"),
        ];
        let terse = terse_health_report(&edges, 2);
        for s in terse.top_scores.iter().chain(terse.bottom_scores.iter()) {
            assert!(
                s.overall >= 0.0 && s.overall <= 1.0,
                "{} overall={}",
                s.name,
                s.overall
            );
        }
    }

    #[test]
    fn terse_cycle_avg() {
        let edges = vec![e("a", "b"), e("b", "a")];
        let terse = terse_health_report(&edges, 1);
        assert!((terse.avg_cycle_risk - 1.0).abs() < 1e-10);
    }
}
