use crate::api::Formula;
use crate::error::{Result, OilError};
use std::collections::{HashMap, HashSet, VecDeque};
use tracing::{debug, instrument};

#[derive(Debug, Clone)]
pub struct DependencyGraph {
    nodes: HashMap<String, Vec<String>>,
}

impl DependencyGraph {
    pub fn new() -> Self {
        Self {
            nodes: HashMap::new(),
        }
    }

    pub fn add_node(&mut self, name: String, deps: Vec<String>) {
        self.nodes.insert(name, deps);
    }

    #[instrument(skip(self))]
    pub fn topological_sort(&self) -> Result<Vec<String>> {
        debug!("Performing topological sort on dependency graph");

        let mut in_degree: HashMap<String, usize> = HashMap::new();
        let mut adj_list: HashMap<String, Vec<String>> = HashMap::new();

        for (node, deps) in &self.nodes {
            in_degree.entry(node.clone()).or_insert(0);

            for dep in deps {
                in_degree.entry(dep.clone()).or_insert(0);
                adj_list.entry(dep.clone()).or_default().push(node.clone());
            }
        }

        for (node, deps) in &self.nodes {
            let count = deps.len();
            *in_degree.entry(node.clone()).or_insert(0) = count;
        }

        let mut queue: VecDeque<String> = in_degree
            .iter()
            .filter(|(_, &count)| count == 0)
            .map(|(node, _)| node.clone())
            .collect();

        let mut result = Vec::new();

        while let Some(node) = queue.pop_front() {
            result.push(node.clone());

            if let Some(neighbors) = adj_list.get(&node) {
                for neighbor in neighbors {
                    if let Some(count) = in_degree.get_mut(neighbor) {
                        *count -= 1;
                        if *count == 0 {
                            queue.push_back(neighbor.clone());
                        }
                    }
                }
            }
        }

        if result.len() != in_degree.len() {
            return Err(OilError::DependencyCycle(
                "Circular dependency detected".to_string(),
            ));
        }

        debug!("Topological sort result: {:?}", result);
        Ok(result)
    }
}

impl Default for DependencyGraph {
    fn default() -> Self {
        Self::new()
    }
}

#[instrument(skip(formulae))]
pub fn resolve_dependencies(
    formula: &Formula,
    formulae: &[Formula],
    installed: &HashSet<String>,
) -> Result<Vec<String>> {
    resolve_dependencies_with_satisfied(formula, formulae, installed, |_| false)
}

pub fn resolve_dependencies_with_satisfied<F>(
    formula: &Formula,
    formulae: &[Formula],
    installed: &HashSet<String>,
    mut satisfied: F,
) -> Result<Vec<String>>
where
    F: FnMut(&str) -> bool,
{
    debug!("Resolving dependencies for {}", formula.name);

    let mut graph = DependencyGraph::new();
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();

    let mut is_satisfied = |name: &str| installed.contains(name) || satisfied(name);

    queue.push_back(formula.name.clone());

    while let Some(name) = queue.pop_front() {
        if visited.contains(&name) || is_satisfied(&name) {
            continue;
        }
        visited.insert(name.clone());

        let f = formulae
            .iter()
            .find(|f| f.name == name)
            .ok_or_else(|| OilError::FormulaNotFound(name.clone()))?;

        let deps = f.dependencies.clone().unwrap_or_default();

        graph.add_node(name.clone(), deps.clone());

        for dep in deps {
            if !is_satisfied(&dep) {
                queue.push_back(dep);
            }
        }
    }

    let sorted = graph.topological_sort()?;

    let to_install: Vec<String> = sorted
        .into_iter()
        .filter(|name| !is_satisfied(name))
        .collect();

    debug!("Packages to install: {:?}", to_install);
    Ok(to_install)
}

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

    fn formula(name: &str, deps: &[&str]) -> Formula {
        use crate::api::Versions;
        Formula {
            name: name.to_string(),
            full_name: name.to_string(),
            desc: None,
            homepage: String::new(),
            versions: Versions {
                stable: "1".into(),
                bottle: false,
            },
            revision: 0,
            installed: None,
            dependencies: if deps.is_empty() {
                None
            } else {
                Some(deps.iter().map(|d| (*d).to_string()).collect())
            },
            build_dependencies: None,
            bottle: None,
            deprecated: false,
            disabled: false,
            deprecation_reason: None,
            disable_reason: None,
            keg_only: None,
            keg_only_reason: None,
            post_install_defined: false,
            rb_path: None,
        }
    }

    #[test]
    fn resolve_dependencies_with_satisfied_skips_host_deps() {
        let formulae = vec![formula("app", &["libfoo"]), formula("libfoo", &[])];
        let installed = HashSet::new();
        let out = resolve_dependencies_with_satisfied(
            &formulae[0],
            &formulae,
            &installed,
            |name| name == "libfoo",
        )
        .unwrap();
        assert_eq!(out, vec!["app"]);
    }

    #[test]
    fn resolve_dependencies_with_satisfied_keeps_unsatisfied_deps() {
        let formulae = vec![formula("app", &["libfoo"]), formula("libfoo", &[])];
        let installed = HashSet::new();
        let out =
            resolve_dependencies_with_satisfied(&formulae[0], &formulae, &installed, |_| false)
                .unwrap();
        assert_eq!(out, vec!["libfoo", "app"]);
    }
}
