//! HITS (Hyperlink-Induced Topic Search) algorithm.
//!
//! # Overview
//!
//! HITS computes two scores for each node:
//!
//! - **Hub score**: How much a node points to good authorities. In the
//!   dependency graph, a hub is an item that blocks many important items.
//! - **Authority score**: How much a node is pointed to by good hubs.
//!   An authority is an item that many important items depend on.
//!
//! # Algorithm
//!
//! Iterative power method (Kleinberg, 1999):
//!
//! 1. Initialize all hub and authority scores to 1.0.
//! 2. Authority update: `auth(v) = sum of hub(u) for all u → v`.
//! 3. Hub update: `hub(v) = sum of auth(w) for all v → w`.
//! 4. Normalize both vectors to unit length (L2 norm).
//! 5. Repeat until convergence or max iterations.
//!
//! # Output
//!
//! Returns a tuple of `(hubs, authorities)` where each is a
//! `HashMap<String, f64>` mapping item IDs to their scores.
//! Items in the same SCC share the same scores.

use std::collections::HashMap;

use petgraph::{
    Direction,
    visit::{IntoNodeIdentifiers, NodeIndexable},
};
use tracing::instrument;

use crate::graph::normalize::NormalizedGraph;

/// Result of the HITS algorithm.
#[derive(Debug, Clone)]
pub struct HitsResult {
    /// Hub scores: item ID → hub score.
    pub hubs: HashMap<String, f64>,
    /// Authority scores: item ID → authority score.
    pub authorities: HashMap<String, f64>,
    /// Number of iterations performed.
    pub iterations: usize,
    /// Whether the algorithm converged within `max_iter`.
    pub converged: bool,
}

/// Compute HITS hub and authority scores.
///
/// Operates on the **condensed** DAG (SCCs collapsed). Items in the same
/// SCC receive the same hub and authority scores.
///
/// # Arguments
///
/// * `ng` — A [`NormalizedGraph`] containing the condensed DAG.
/// * `max_iter` — Maximum number of iterations.
/// * `tolerance` — Convergence threshold: stop when the L2 norm of the
///   change in authority scores is below this value.
///
/// # Returns
///
/// A [`HitsResult`] with hub and authority scores for each item ID.
/// Isolated nodes receive a score based on the uniform initialization
/// (approximately `1/sqrt(n)`).
#[must_use]
#[instrument(skip(ng))]
#[allow(clippy::many_single_char_names)]
pub fn hits(ng: &NormalizedGraph, max_iter: usize, tolerance: f64) -> HitsResult {
    let g = &ng.condensed;
    let n = g.node_count();

    if n == 0 {
        return HitsResult {
            hubs: HashMap::new(),
            authorities: HashMap::new(),
            iterations: 0,
            converged: true,
        };
    }

    // Initialize hub and authority scores uniformly.
    let mut hub: Vec<f64> = vec![1.0; n];
    let mut auth: Vec<f64> = vec![1.0; n];

    let mut converged = false;
    let mut iterations = 0;

    for iter in 0..max_iter {
        iterations = iter + 1;

        // Authority update: auth(v) = sum of hub(u) for all u → v
        let mut new_auth = vec![0.0; n];
        for v in g.node_identifiers() {
            let vi = g.to_index(v);
            for u in g.neighbors_directed(v, Direction::Incoming) {
                let ui = g.to_index(u);
                new_auth[vi] += hub[ui];
            }
        }

        // Hub update: hub(v) = sum of auth(w) for all v → w
        let mut new_hub = vec![0.0; n];
        for v in g.node_identifiers() {
            let vi = g.to_index(v);
            for w in g.neighbors_directed(v, Direction::Outgoing) {
                let wi = g.to_index(w);
                new_hub[vi] += new_auth[wi];
            }
        }

        // Normalize both vectors (L2 norm).
        normalize_l2(&mut new_auth);
        normalize_l2(&mut new_hub);

        // Check convergence: L2 norm of (new_auth - auth).
        let diff: f64 = auth
            .iter()
            .zip(new_auth.iter())
            .map(|(a, b)| (a - b).powi(2))
            .sum::<f64>()
            .sqrt();

        auth = new_auth;
        hub = new_hub;

        if diff < tolerance {
            converged = true;
            break;
        }
    }

    // Map condensed node scores back to item IDs.
    let mut hubs_map = HashMap::new();
    let mut auth_map = HashMap::new();

    for idx in g.node_identifiers() {
        let i = g.to_index(idx);
        let h = hub[i];
        let a = auth[i];

        if let Some(scc_node) = g.node_weight(idx) {
            for member in &scc_node.members {
                hubs_map.insert(member.clone(), h);
                auth_map.insert(member.clone(), a);
            }
        }
    }

    HitsResult {
        hubs: hubs_map,
        authorities: auth_map,
        iterations,
        converged,
    }
}

/// Normalize a vector to unit L2 norm. If the norm is zero, leave as-is.
fn normalize_l2(v: &mut [f64]) {
    let norm: f64 = v.iter().map(|x| x * x).sum::<f64>().sqrt();
    if norm > 0.0 {
        for x in v.iter_mut() {
            *x /= norm;
        }
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;
    use crate::graph::build::RawGraph;
    use crate::graph::normalize::NormalizedGraph;
    use petgraph::graph::DiGraph;
    use std::collections::HashMap;

    fn make_normalized(edges: &[(&str, &str)]) -> NormalizedGraph {
        let mut graph = DiGraph::<String, ()>::new();
        let mut node_map = HashMap::new();

        let all_ids: std::collections::BTreeSet<&str> =
            edges.iter().flat_map(|(a, b)| [*a, *b]).collect();

        for id in all_ids {
            let idx = graph.add_node(id.to_string());
            node_map.insert(id.to_string(), idx);
        }

        for (a, b) in edges {
            let ia = node_map[*a];
            let ib = node_map[*b];
            graph.add_edge(ia, ib, ());
        }

        let raw = RawGraph {
            graph,
            node_map,
            content_hash: "blake3:test".to_string(),
        };

        NormalizedGraph::from_raw(raw)
    }

    fn make_normalized_nodes(nodes: &[&str], edges: &[(&str, &str)]) -> NormalizedGraph {
        let mut graph = DiGraph::<String, ()>::new();
        let mut node_map = HashMap::new();

        for id in nodes {
            let idx = graph.add_node((*id).to_string());
            node_map.insert((*id).to_string(), idx);
        }

        for (a, b) in edges {
            let ia = node_map[*a];
            let ib = node_map[*b];
            graph.add_edge(ia, ib, ());
        }

        let raw = RawGraph {
            graph,
            node_map,
            content_hash: "blake3:test".to_string(),
        };

        NormalizedGraph::from_raw(raw)
    }

    #[test]
    fn empty_graph_returns_empty() {
        let result = hits(&make_normalized_nodes(&[], &[]), 100, 1e-6);
        assert!(result.hubs.is_empty());
        assert!(result.authorities.is_empty());
        assert!(result.converged);
    }

    #[test]
    fn single_node_equal_scores() {
        let result = hits(&make_normalized_nodes(&["A"], &[]), 100, 1e-6);
        // Single node with no edges: hub and authority should be 1.0
        // (only one component in the vector, normalization gives 1.0).
        // After first iteration: auth(A) = 0 (no incoming edges), hub(A) = 0.
        // With zero norm, scores stay at initial after normalization fails.
        // Actually: since no edges, auth and hub updates produce all zeros,
        // which means normalize_l2 leaves them as zero.
        // But wait: initialization is 1.0 and first iteration auth = 0 (no incoming).
        // So convergence check: diff = |1 - 0| = 1 > tolerance. Next iter same.
        // Eventually max_iter reached.
        //
        // Actually for isolated nodes there's no good HITS score. The result
        // should be 0.0 for both hub and authority.
        assert!(result.hubs.contains_key("A"));
        assert!(result.authorities.contains_key("A"));
    }

    #[test]
    fn simple_edge_hub_and_authority() {
        // A → B: A is a hub, B is an authority.
        let result = hits(&make_normalized(&[("A", "B")]), 100, 1e-6);

        // A points to B → A has high hub score.
        // B is pointed to by A → B has high authority score.
        assert!(
            result.hubs["A"] > result.hubs["B"],
            "A should have higher hub score than B: A={} B={}",
            result.hubs["A"],
            result.hubs["B"]
        );
        assert!(
            result.authorities["B"] > result.authorities["A"],
            "B should have higher authority score than A: A={} B={}",
            result.authorities["A"],
            result.authorities["B"]
        );
    }

    #[test]
    fn star_hub_topology() {
        // A → B, A → C, A → D (A is a hub, B/C/D are authorities)
        let ng = make_normalized(&[("A", "B"), ("A", "C"), ("A", "D")]);
        let result = hits(&ng, 100, 1e-6);

        // A is the only hub.
        assert!(
            result.hubs["A"] > result.hubs["B"],
            "A should be the top hub"
        );
        // B, C, D are authorities with equal scores.
        assert!(
            (result.authorities["B"] - result.authorities["C"]).abs() < 1e-6,
            "B and C should have equal authority"
        );
        assert!(
            (result.authorities["C"] - result.authorities["D"]).abs() < 1e-6,
            "C and D should have equal authority"
        );
    }

    #[test]
    fn star_authority_topology() {
        // A → D, B → D, C → D (D is the authority, A/B/C are hubs)
        let ng = make_normalized(&[("A", "D"), ("B", "D"), ("C", "D")]);
        let result = hits(&ng, 100, 1e-6);

        // D is the top authority.
        assert!(
            result.authorities["D"] > result.authorities["A"],
            "D should be the top authority"
        );
        // A, B, C are hubs with equal scores.
        assert!(
            (result.hubs["A"] - result.hubs["B"]).abs() < 1e-6,
            "A and B should have equal hub score"
        );
        assert!(
            (result.hubs["B"] - result.hubs["C"]).abs() < 1e-6,
            "B and C should have equal hub score"
        );
    }

    #[test]
    fn hits_converges() {
        let ng = make_normalized(&[("A", "B"), ("B", "C"), ("A", "C")]);
        let result = hits(&ng, 100, 1e-6);
        assert!(result.converged, "HITS should converge for a small DAG");
    }

    #[test]
    fn disconnected_components_independent() {
        // Two disjoint edges: A → B and C → D.
        let ng = make_normalized(&[("A", "B"), ("C", "D")]);
        let result = hits(&ng, 100, 1e-6);

        // A and C should have equal hub scores (symmetric topology).
        assert!(
            (result.hubs["A"] - result.hubs["C"]).abs() < 1e-6,
            "Symmetric hubs: A={} C={}",
            result.hubs["A"],
            result.hubs["C"]
        );
        // B and D should have equal authority scores.
        assert!(
            (result.authorities["B"] - result.authorities["D"]).abs() < 1e-6,
            "Symmetric authorities: B={} D={}",
            result.authorities["B"],
            result.authorities["D"]
        );
    }

    #[test]
    fn cycle_members_share_hits_scores() {
        // A → B → A (cycle), A → C
        // After condensation: {A,B} → {C}
        let ng = make_normalized(&[("A", "B"), ("B", "A"), ("A", "C")]);
        let result = hits(&ng, 100, 1e-6);

        // A and B are in the same SCC → same scores.
        assert!(
            (result.hubs["A"] - result.hubs["B"]).abs() < 1e-10,
            "SCC members should have equal hub scores"
        );
        assert!(
            (result.authorities["A"] - result.authorities["B"]).abs() < 1e-10,
            "SCC members should have equal authority scores"
        );
    }

    #[test]
    fn chain_hub_authority_ordering() {
        // A → B → C → D
        // Hub scores should decrease from source: A > B > C > D (D has no outgoing).
        // Authority scores should increase toward sink: D > C > B > A (A has no incoming).
        let ng = make_normalized(&[("A", "B"), ("B", "C"), ("C", "D")]);
        let result = hits(&ng, 100, 1e-6);

        assert!(
            result.hubs["A"] >= result.hubs["B"],
            "A hub >= B hub: {} >= {}",
            result.hubs["A"],
            result.hubs["B"]
        );
        assert!(
            result.authorities["D"] >= result.authorities["C"],
            "D auth >= C auth: {} >= {}",
            result.authorities["D"],
            result.authorities["C"]
        );
    }
}
