use anyhow::Result;
use serde::Serialize;
use std::collections::{HashMap, HashSet};
use std::path::Path;
use workgraph::format_hours;
use workgraph::graph::{Status, WorkGraph};

/// Information about a task on the critical path
#[derive(Debug, Clone, Serialize)]
struct CriticalTask {
    id: String,
    title: String,
    status: Status,
    hours: Option<f64>,
    after: Option<String>,
}

/// Slack information for non-critical tasks
#[derive(Debug, Clone, Serialize)]
struct SlackInfo {
    id: String,
    title: String,
    slack_hours: f64,
    note: String,
}

/// JSON output structure
#[derive(Debug, Serialize)]
struct CriticalPathOutput {
    critical_path: Vec<CriticalTask>,
    task_count: usize,
    total_hours: f64,
    slack_analysis: Vec<SlackInfo>,
    cycles_skipped: Vec<Vec<String>>,
}

pub fn run(dir: &Path, json: bool) -> Result<()> {
    let (graph, _path) = super::load_workgraph(dir)?;

    // Get active tasks only (exclude terminal states: done, failed, abandoned)
    let active_tasks: Vec<_> = graph.tasks().filter(|t| !t.status.is_terminal()).collect();

    if active_tasks.is_empty() {
        if json {
            let output = CriticalPathOutput {
                critical_path: vec![],
                task_count: 0,
                total_hours: 0.0,
                slack_analysis: vec![],
                cycles_skipped: vec![],
            };
            println!("{}", serde_json::to_string_pretty(&output)?);
        } else {
            println!("No active tasks found.");
        }
        return Ok(());
    }

    // Build set of active task IDs for filtering
    let active_ids: HashSet<&str> = active_tasks.iter().map(|t| t.id.as_str()).collect();

    // Detect cycles among active tasks
    let cycles = detect_cycles_among_active(&graph, &active_ids);
    let cycle_nodes: HashSet<&str> = cycles.iter().flatten().map(String::as_str).collect();

    // Build dependency graph (task_id -> list of tasks it blocks)
    // This is the "forward" direction for finding paths
    let forward_index = build_forward_index(&graph, &active_ids, &cycle_nodes);

    // Find tasks with no active blockers (entry points)
    let entry_points: Vec<&str> = active_tasks
        .iter()
        .filter(|t| !cycle_nodes.contains(t.id.as_str()))
        .filter(|t| {
            t.after.iter().all(|blocker_id| {
                // Not blocked by any active non-terminal task
                !active_ids.contains(blocker_id.as_str())
                    || cycle_nodes.contains(blocker_id.as_str())
                    || graph
                        .get_task(blocker_id)
                        .map(|bt| bt.status.is_terminal())
                        .unwrap_or(true)
            })
        })
        .map(|t| t.id.as_str())
        .collect();

    // Calculate longest path from each entry point using dynamic programming
    // longest_path[task_id] = (total_hours, path_as_vec)
    let mut memo: HashMap<&str, (f64, Vec<String>)> = HashMap::new();

    for entry in &entry_points {
        calculate_longest_path(entry, &graph, &forward_index, &mut memo, &cycle_nodes);
    }

    // Find the overall longest path
    let (critical_path, total_hours) = if let Some((_, (hours, path))) =
        memo.iter().max_by(|a, b| {
            a.1.0
                .partial_cmp(&b.1.0)
                .unwrap_or(std::cmp::Ordering::Equal)
        }) {
        (path.clone(), *hours)
    } else {
        (vec![], 0.0)
    };

    // Build critical task info
    let critical_set: HashSet<&str> = critical_path.iter().map(String::as_str).collect();
    let critical_tasks: Vec<CriticalTask> = critical_path
        .iter()
        .enumerate()
        .filter_map(|(i, task_id)| {
            graph.get_task(task_id).map(|t| {
                let after = if i == 0 {
                    None
                } else {
                    Some(critical_path[i - 1].clone())
                };
                CriticalTask {
                    id: t.id.clone(),
                    title: t.title.clone(),
                    status: t.status,
                    hours: t.estimate.as_ref().and_then(|e| e.hours),
                    after,
                }
            })
        })
        .collect();

    // Calculate slack for non-critical tasks
    let slack_analysis: Vec<SlackInfo> = active_tasks
        .iter()
        .filter(|t| !critical_set.contains(t.id.as_str()) && !cycle_nodes.contains(t.id.as_str()))
        .filter_map(|t| {
            // Slack = critical path hours - hours if this task were on the path
            // Simplified: just show the difference from total hours for this task's path
            let task_hours = t.estimate.as_ref().and_then(|e| e.hours).unwrap_or(0.0);
            let slack = total_hours - task_hours;
            if slack > 0.0 {
                Some(SlackInfo {
                    id: t.id.clone(),
                    title: t.title.clone(),
                    slack_hours: slack,
                    note: "can delay without affecting deadline".to_string(),
                })
            } else {
                None
            }
        })
        .collect();

    if json {
        let output = CriticalPathOutput {
            critical_path: critical_tasks,
            task_count: critical_path.len(),
            total_hours,
            slack_analysis,
            cycles_skipped: cycles,
        };
        println!("{}", serde_json::to_string_pretty(&output)?);
    } else {
        if critical_path.is_empty() {
            println!("No critical path found (no active dependency chains).");
            if !cycles.is_empty() {
                println!("\nNote: {} cycle(s) were skipped.", cycles.len());
            }
            return Ok(());
        }

        println!(
            "Critical path ({} tasks, estimated {} hours):\n",
            critical_path.len(),
            format_hours(total_hours)
        );

        for (i, task_id) in critical_path.iter().enumerate() {
            if let Some(task) = graph.get_task(task_id) {
                let status_str = match task.status {
                    Status::Open | Status::InProgress => "ready",
                    Status::Blocked => "blocked",
                    Status::Done => "done",
                    Status::Failed => "failed",
                    Status::Abandoned => "abandoned",
                    Status::Waiting => "waiting",
                    Status::PendingValidation => "pending-validation",
                    Status::PendingEval => "pending-eval",
                    Status::FailedPendingEval => "failed-pending-eval",
                    Status::Incomplete => "incomplete",
                };

                let hours_str = task
                    .estimate
                    .as_ref()
                    .and_then(|e| e.hours)
                    .map(|h| format!(" ({}h)", h))
                    .unwrap_or_default();

                let blocked_str = if i == 0 {
                    String::new()
                } else {
                    format!(" <- blocked by {}", critical_path[i - 1])
                };

                println!(
                    "{}. [{}] {}{}{}",
                    i + 1,
                    status_str,
                    task.id,
                    hours_str,
                    blocked_str
                );
            }
        }

        if !slack_analysis.is_empty() {
            println!("\nSlack analysis:");
            for slack in &slack_analysis {
                println!(
                    "  {}: {}h slack ({})",
                    slack.id,
                    format_hours(slack.slack_hours),
                    slack.note
                );
            }
        }

        if !cycles.is_empty() {
            println!(
                "\nNote: {} cycle(s) were skipped in analysis.",
                cycles.len()
            );
        }
    }

    Ok(())
}

/// Build forward index: task_id -> tasks that it blocks (among active non-cycle tasks)
fn build_forward_index<'a>(
    graph: &'a WorkGraph,
    active_ids: &HashSet<&str>,
    cycle_nodes: &HashSet<&str>,
) -> HashMap<&'a str, Vec<&'a str>> {
    let mut index: HashMap<&str, Vec<&str>> = HashMap::new();

    for task in graph.tasks() {
        if !active_ids.contains(task.id.as_str()) || cycle_nodes.contains(task.id.as_str()) {
            continue;
        }

        // For each blocker, add this task to its forward list
        for blocker_id in &task.after {
            if active_ids.contains(blocker_id.as_str())
                && !cycle_nodes.contains(blocker_id.as_str())
            {
                index
                    .entry(blocker_id.as_str())
                    .or_default()
                    .push(task.id.as_str());
            }
        }
    }

    index
}

/// Calculate longest path starting from this task using memoization
fn calculate_longest_path<'a>(
    task_id: &'a str,
    graph: &'a WorkGraph,
    forward_index: &HashMap<&'a str, Vec<&'a str>>,
    memo: &mut HashMap<&'a str, (f64, Vec<String>)>,
    cycle_nodes: &HashSet<&str>,
) -> (f64, Vec<String>) {
    // Skip cycle nodes
    if cycle_nodes.contains(task_id) {
        return (0.0, vec![]);
    }

    // Return memoized result if available
    if let Some(result) = memo.get(task_id) {
        return result.clone();
    }

    let task = match graph.get_task(task_id) {
        Some(t) => t,
        None => return (0.0, vec![]),
    };

    let task_hours = task
        .estimate
        .as_ref()
        .and_then(|e| e.hours)
        .unwrap_or(1.0)
        .max(0.0); // Clamp negative estimates to zero

    // Get tasks blocked by this one
    let blocked_tasks = forward_index.get(task_id);

    let (longest_child_hours, longest_child_path) = if let Some(children) = blocked_tasks {
        children
            .iter()
            .map(|child_id| {
                calculate_longest_path(child_id, graph, forward_index, memo, cycle_nodes)
            })
            .max_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal))
            .unwrap_or((0.0, vec![]))
    } else {
        (0.0, vec![])
    };

    let total_hours = task_hours + longest_child_hours;
    let mut path = vec![task_id.to_string()];
    path.extend(longest_child_path);

    memo.insert(task_id, (total_hours, path.clone()));
    (total_hours, path)
}

/// Detect cycles among active tasks using DFS
fn detect_cycles_among_active(graph: &WorkGraph, active_ids: &HashSet<&str>) -> Vec<Vec<String>> {
    let mut cycles = Vec::new();
    let mut visited = HashSet::new();
    let mut rec_stack = HashSet::new();
    let mut path = Vec::new();

    for task_id in active_ids {
        if !visited.contains(*task_id) {
            find_cycles_dfs(
                graph,
                task_id,
                active_ids,
                &mut visited,
                &mut rec_stack,
                &mut path,
                &mut cycles,
            );
        }
    }

    cycles
}

fn find_cycles_dfs(
    graph: &WorkGraph,
    node_id: &str,
    active_ids: &HashSet<&str>,
    visited: &mut HashSet<String>,
    rec_stack: &mut HashSet<String>,
    path: &mut Vec<String>,
    cycles: &mut Vec<Vec<String>>,
) {
    visited.insert(node_id.to_string());
    rec_stack.insert(node_id.to_string());
    path.push(node_id.to_string());

    if let Some(task) = graph.get_task(node_id) {
        for dep_id in &task.after {
            if !active_ids.contains(dep_id.as_str()) {
                continue;
            }

            if !visited.contains(dep_id) {
                find_cycles_dfs(graph, dep_id, active_ids, visited, rec_stack, path, cycles);
            } else if rec_stack.contains(dep_id) {
                // Found a cycle
                if let Some(pos) = path.iter().position(|x| x == dep_id) {
                    let cycle: Vec<String> = path[pos..].to_vec();
                    cycles.push(cycle);
                }
            }
        }
    }

    path.pop();
    rec_stack.remove(node_id);
}

#[cfg(test)]
mod tests {
    use super::*;
    use workgraph::graph::{Estimate, Node, PRIORITY_DEFAULT, Task};

    fn make_task(id: &str, title: &str) -> Task {
        Task {
            id: id.to_string(),
            title: title.to_string(),
            ..Task::default()
        }
    }

    fn make_task_with_hours(id: &str, title: &str, hours: f64) -> Task {
        Task {
            id: id.to_string(),
            title: title.to_string(),
            description: None,
            status: Status::Open,
            priority: PRIORITY_DEFAULT,
            assigned: None,
            estimate: Some(Estimate {
                hours: Some(hours),
                cost: None,
            }),
            before: vec![],
            after: vec![],
            requires: vec![],
            tags: vec![],
            skills: vec![],
            inputs: vec![],
            deliverables: vec![],
            artifacts: vec![],
            exec: None,
            timeout: None,
            not_before: None,
            created_at: None,
            started_at: None,
            completed_at: None,
            last_interaction_at: None,
            log: vec![],
            retry_count: 0,
            max_retries: None,
            failure_reason: None,
            failure_class: None,
            model: None,
            provider: None,
            endpoint: None,
            command_argv: vec![],
            working_dir: None,
            executor_preset_name: None,
            verify: None,
            verify_timeout: None,
            agent: None,
            loop_iteration: 0,
            last_iteration_completed_at: None,
            cycle_failure_restarts: 0,
            ready_after: None,
            paused: false,
            visibility: "internal".to_string(),
            context_scope: None,
            exec_mode: None,
            cycle_config: None,
            token_usage: None,
            session_id: None,
            wait_condition: None,
            checkpoint: None,
            triage_count: 0,
            resurrection_count: 0,
            last_resurrected_at: None,
            validation: None,
            validation_commands: vec![],
            validator_agent: None,
            validator_model: None,
            gate_attempts: 0,
            test_required: false,
            rejection_count: 0,
            max_rejections: None,
            verify_failures: 0,
            rescue_count: 0,
            rescued: false,
            meta_eval_attempts: 0,
            spawn_failures: 0,
            dispatch_count: 0,
            tier: None,
            no_tier_escalation: false,
            tried_models: vec![],
            superseded_by: vec![],
            supersedes: None,
            unplaced: false,
            place_near: vec![],
            place_before: vec![],
            independent: false,
            iteration_anchor: None,
            iteration_config: None,
            iteration_round: 0,
            iteration_parent: None,
            cron_schedule: None,
            cron_enabled: false,
            last_cron_fire: None,
            next_cron_fire: None,
        }
    }

    #[test]
    fn test_format_hours_whole() {
        assert_eq!(format_hours(8.0), "8");
        assert_eq!(format_hours(47.0), "47");
    }

    #[test]
    fn test_format_hours_decimal() {
        assert_eq!(format_hours(8.5), "8.5");
        assert_eq!(format_hours(47.25), "47.2");
    }

    #[test]
    fn test_empty_graph_has_no_critical_path() {
        let graph = WorkGraph::new();
        let active_ids: HashSet<&str> = HashSet::new();
        let cycles = detect_cycles_among_active(&graph, &active_ids);
        assert!(cycles.is_empty());
    }

    #[test]
    fn test_single_task_is_critical_path() {
        let mut graph = WorkGraph::new();
        let task = make_task_with_hours("t1", "Task 1", 8.0);
        graph.add_node(Node::Task(task));

        let active_ids: HashSet<&str> = vec!["t1"].into_iter().collect();
        let cycle_nodes: HashSet<&str> = HashSet::new();
        let forward_index = build_forward_index(&graph, &active_ids, &cycle_nodes);
        let mut memo = HashMap::new();

        let (hours, path) =
            calculate_longest_path("t1", &graph, &forward_index, &mut memo, &cycle_nodes);

        assert_eq!(hours, 8.0);
        assert_eq!(path, vec!["t1".to_string()]);
    }

    #[test]
    fn test_linear_chain_critical_path() {
        let mut graph = WorkGraph::new();

        // t1 (8h) -> t2 (16h) -> t3 (4h)
        let t1 = make_task_with_hours("t1", "Task 1", 8.0);
        let mut t2 = make_task_with_hours("t2", "Task 2", 16.0);
        t2.after = vec!["t1".to_string()];
        let mut t3 = make_task_with_hours("t3", "Task 3", 4.0);
        t3.after = vec!["t2".to_string()];

        graph.add_node(Node::Task(t1));
        graph.add_node(Node::Task(t2));
        graph.add_node(Node::Task(t3));

        let active_ids: HashSet<&str> = vec!["t1", "t2", "t3"].into_iter().collect();
        let cycle_nodes: HashSet<&str> = HashSet::new();
        let forward_index = build_forward_index(&graph, &active_ids, &cycle_nodes);
        let mut memo = HashMap::new();

        let (hours, path) =
            calculate_longest_path("t1", &graph, &forward_index, &mut memo, &cycle_nodes);

        assert_eq!(hours, 28.0);
        assert_eq!(
            path,
            vec!["t1".to_string(), "t2".to_string(), "t3".to_string()]
        );
    }

    #[test]
    fn test_parallel_paths_picks_longest() {
        let mut graph = WorkGraph::new();

        // t1 (8h) -> t2 (16h) -> t4 (4h)
        // t1 (8h) -> t3 (2h) -> t4 (4h)
        // Longest: t1 -> t2 -> t4 = 28h
        let t1 = make_task_with_hours("t1", "Task 1", 8.0);
        let mut t2 = make_task_with_hours("t2", "Task 2", 16.0);
        t2.after = vec!["t1".to_string()];
        let mut t3 = make_task_with_hours("t3", "Task 3", 2.0);
        t3.after = vec!["t1".to_string()];
        let mut t4 = make_task_with_hours("t4", "Task 4", 4.0);
        t4.after = vec!["t2".to_string(), "t3".to_string()];

        graph.add_node(Node::Task(t1));
        graph.add_node(Node::Task(t2));
        graph.add_node(Node::Task(t3));
        graph.add_node(Node::Task(t4));

        let active_ids: HashSet<&str> = vec!["t1", "t2", "t3", "t4"].into_iter().collect();
        let cycle_nodes: HashSet<&str> = HashSet::new();
        let forward_index = build_forward_index(&graph, &active_ids, &cycle_nodes);
        let mut memo = HashMap::new();

        let (hours, path) =
            calculate_longest_path("t1", &graph, &forward_index, &mut memo, &cycle_nodes);

        assert_eq!(hours, 28.0);
        assert_eq!(
            path,
            vec!["t1".to_string(), "t2".to_string(), "t4".to_string()]
        );
    }

    #[test]
    fn test_done_tasks_excluded() {
        let mut graph = WorkGraph::new();

        let mut t1 = make_task_with_hours("t1", "Task 1", 8.0);
        t1.status = Status::Done;
        let mut t2 = make_task_with_hours("t2", "Task 2", 16.0);
        t2.after = vec!["t1".to_string()];

        graph.add_node(Node::Task(t1));
        graph.add_node(Node::Task(t2));

        // Only t2 is active
        let active_ids: HashSet<&str> = vec!["t2"].into_iter().collect();
        let cycle_nodes: HashSet<&str> = HashSet::new();
        let forward_index = build_forward_index(&graph, &active_ids, &cycle_nodes);
        let mut memo = HashMap::new();

        let (hours, path) =
            calculate_longest_path("t2", &graph, &forward_index, &mut memo, &cycle_nodes);

        assert_eq!(hours, 16.0);
        assert_eq!(path, vec!["t2".to_string()]);
    }

    #[test]
    fn test_cycle_detection() {
        let mut graph = WorkGraph::new();

        // t1 -> t2 -> t1 (cycle)
        let mut t1 = make_task("t1", "Task 1");
        t1.after = vec!["t2".to_string()];
        let mut t2 = make_task("t2", "Task 2");
        t2.after = vec!["t1".to_string()];

        graph.add_node(Node::Task(t1));
        graph.add_node(Node::Task(t2));

        let active_ids: HashSet<&str> = vec!["t1", "t2"].into_iter().collect();
        let cycles = detect_cycles_among_active(&graph, &active_ids);

        assert!(!cycles.is_empty());
    }

    #[test]
    fn test_tasks_without_hours_default_to_one() {
        let mut graph = WorkGraph::new();

        let t1 = make_task("t1", "Task 1");
        let mut t2 = make_task("t2", "Task 2");
        t2.after = vec!["t1".to_string()];

        graph.add_node(Node::Task(t1));
        graph.add_node(Node::Task(t2));

        let active_ids: HashSet<&str> = vec!["t1", "t2"].into_iter().collect();
        let cycle_nodes: HashSet<&str> = HashSet::new();
        let forward_index = build_forward_index(&graph, &active_ids, &cycle_nodes);
        let mut memo = HashMap::new();

        let (hours, path) =
            calculate_longest_path("t1", &graph, &forward_index, &mut memo, &cycle_nodes);

        // Each task defaults to 1 hour
        assert_eq!(hours, 2.0);
        assert_eq!(path, vec!["t1".to_string(), "t2".to_string()]);
    }

    #[test]
    fn test_build_forward_index() {
        let mut graph = WorkGraph::new();

        // t1 -> t2, t1 -> t3
        let t1 = make_task("t1", "Task 1");
        let mut t2 = make_task("t2", "Task 2");
        t2.after = vec!["t1".to_string()];
        let mut t3 = make_task("t3", "Task 3");
        t3.after = vec!["t1".to_string()];

        graph.add_node(Node::Task(t1));
        graph.add_node(Node::Task(t2));
        graph.add_node(Node::Task(t3));

        let active_ids: HashSet<&str> = vec!["t1", "t2", "t3"].into_iter().collect();
        let cycle_nodes: HashSet<&str> = HashSet::new();
        let forward_index = build_forward_index(&graph, &active_ids, &cycle_nodes);

        let t1_blocks = forward_index.get("t1").unwrap();
        assert_eq!(t1_blocks.len(), 2);
        assert!(t1_blocks.contains(&"t2"));
        assert!(t1_blocks.contains(&"t3"));
    }

    #[test]
    fn test_nan_estimate_does_not_panic() {
        let mut graph = WorkGraph::new();

        // Create tasks where one has NaN hours (simulates corrupt estimate)
        let t1 = make_task_with_hours("t1", "Task 1", f64::NAN);
        let t2 = make_task_with_hours("t2", "Task 2", 4.0);
        let mut t3 = make_task_with_hours("t3", "Task 3", 2.0);
        t3.after = vec!["t1".to_string(), "t2".to_string()];

        graph.add_node(Node::Task(t1));
        graph.add_node(Node::Task(t2));
        graph.add_node(Node::Task(t3));

        let active_ids: HashSet<&str> = vec!["t1", "t2", "t3"].into_iter().collect();
        let cycle_nodes: HashSet<&str> = HashSet::new();
        let forward_index = build_forward_index(&graph, &active_ids, &cycle_nodes);
        let mut memo = HashMap::new();

        // Should not panic — NaN comparison falls back to Equal
        for entry in &["t1", "t2"] {
            calculate_longest_path(entry, &graph, &forward_index, &mut memo, &cycle_nodes);
        }

        let result = memo.iter().max_by(|a, b| {
            a.1.0
                .partial_cmp(&b.1.0)
                .unwrap_or(std::cmp::Ordering::Equal)
        });
        // Just verify we don't crash — the exact result with NaN is implementation-defined
        assert!(result.is_some());
    }

    #[test]
    fn test_orphan_blocker_in_critical_path() {
        // A task references a blocker that doesn't exist in the graph
        let mut graph = WorkGraph::new();

        let mut t1 = make_task_with_hours("t1", "Task 1", 8.0);
        t1.after = vec!["ghost".to_string()]; // orphan reference

        graph.add_node(Node::Task(t1));

        let active_ids: HashSet<&str> = vec!["t1"].into_iter().collect();
        let cycle_nodes: HashSet<&str> = HashSet::new();
        let forward_index = build_forward_index(&graph, &active_ids, &cycle_nodes);
        let mut memo = HashMap::new();

        // Should not panic even with orphan blocker references
        let (hours, path) =
            calculate_longest_path("t1", &graph, &forward_index, &mut memo, &cycle_nodes);

        assert_eq!(hours, 8.0);
        assert_eq!(path, vec!["t1".to_string()]);
    }

    #[test]
    fn test_negative_estimate_clamped_to_zero() {
        // Negative estimates should be clamped to 0 and not corrupt path calculations
        let mut graph = WorkGraph::new();

        let t1 = make_task_with_hours("t1", "Task 1", 10.0);
        let mut t2 = make_task_with_hours("t2", "Task 2", -5.0);
        t2.after = vec!["t1".to_string()];

        graph.add_node(Node::Task(t1));
        graph.add_node(Node::Task(t2));

        let active_ids: HashSet<&str> = graph.tasks().map(|t| t.id.as_str()).collect();
        let cycle_nodes: HashSet<&str> = HashSet::new();
        let forward_index = build_forward_index(&graph, &active_ids, &cycle_nodes);
        let mut memo = HashMap::new();

        let (hours, _path) =
            calculate_longest_path("t1", &graph, &forward_index, &mut memo, &cycle_nodes);

        // t1 = 10h, t2 = 0h (clamped from -5), total path should be 10
        assert!(
            hours >= 10.0,
            "negative estimate should not reduce path length, got {}",
            hours
        );
    }

    #[test]
    fn test_format_hours_nan_and_infinity() {
        assert_eq!(format_hours(f64::NAN), "?");
        assert_eq!(format_hours(f64::INFINITY), "?");
        assert_eq!(format_hours(f64::NEG_INFINITY), "?");
        assert_eq!(format_hours(5.0), "5");
        assert_eq!(format_hours(2.5), "2.5");
    }
}
