//! Dependency graph primitives for asset pipelines.

use std::collections::{BTreeMap, BTreeSet, VecDeque};

/// A directed acyclic asset dependency graph.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct AssetGraph {
    edges: BTreeMap<String, BTreeSet<String>>,
    reverse_edges: BTreeMap<String, BTreeSet<String>>,
    nodes: BTreeSet<String>,
}

/// Errors produced by graph operations.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum GraphError {
    /// A cycle was found while sorting the graph.
    #[error("dependency graph contains a cycle")]
    Cycle,
}

impl AssetGraph {
    /// Creates an empty graph.
    pub fn new() -> Self {
        Self::default()
    }

    /// Adds a node if it does not already exist.
    pub fn add_node(&mut self, node: impl Into<String>) {
        self.nodes.insert(node.into());
    }

    /// Adds a dependency edge from `input` to `output`.
    pub fn add_edge(&mut self, input: impl Into<String>, output: impl Into<String>) {
        let input = input.into();
        let output = output.into();
        self.nodes.insert(input.clone());
        self.nodes.insert(output.clone());
        self.edges
            .entry(input.clone())
            .or_default()
            .insert(output.clone());
        self.reverse_edges.entry(output).or_default().insert(input);
    }

    /// Returns all graph nodes in stable order.
    pub fn nodes(&self) -> impl Iterator<Item = &str> {
        self.nodes.iter().map(String::as_str)
    }

    /// Returns direct outputs that depend on `node`.
    pub fn outputs_of(&self, node: &str) -> Vec<&str> {
        self.edges
            .get(node)
            .into_iter()
            .flat_map(|outputs| outputs.iter().map(String::as_str))
            .collect()
    }

    /// Returns direct inputs of `node`.
    pub fn inputs_of(&self, node: &str) -> Vec<&str> {
        self.reverse_edges
            .get(node)
            .into_iter()
            .flat_map(|inputs| inputs.iter().map(String::as_str))
            .collect()
    }

    /// Returns all transitive dependents of `node` in traversal order.
    pub fn transitive_dependents(&self, node: &str) -> Vec<String> {
        let mut seen = BTreeSet::new();
        let mut queue: VecDeque<String> = self
            .outputs_of(node)
            .into_iter()
            .map(str::to_owned)
            .collect();
        let mut dependents = Vec::new();

        while let Some(current) = queue.pop_front() {
            if !seen.insert(current.clone()) {
                continue;
            }
            dependents.push(current.clone());
            for next in self.outputs_of(&current) {
                queue.push_back(next.to_owned());
            }
        }

        dependents
    }

    /// Topologically sorts nodes with inputs before derived outputs.
    pub fn topological_sort(&self) -> Result<Vec<String>, GraphError> {
        let mut incoming: BTreeMap<String, usize> = self
            .nodes
            .iter()
            .map(|node| {
                (
                    node.clone(),
                    self.reverse_edges.get(node).map_or(0, BTreeSet::len),
                )
            })
            .collect();
        let mut ready: VecDeque<String> = incoming
            .iter()
            .filter_map(|(node, count)| (*count == 0).then_some(node.clone()))
            .collect();
        let mut sorted = Vec::with_capacity(self.nodes.len());

        while let Some(node) = ready.pop_front() {
            sorted.push(node.clone());
            if let Some(outputs) = self.edges.get(&node) {
                for output in outputs {
                    let count = incoming
                        .get_mut(output)
                        .expect("edge output must be registered as a node");
                    *count -= 1;
                    if *count == 0 {
                        ready.push_back(output.clone());
                    }
                }
            }
        }

        if sorted.len() == self.nodes.len() {
            Ok(sorted)
        } else {
            Err(GraphError::Cycle)
        }
    }

    /// Returns true when the graph contains a cycle.
    pub fn has_cycle(&self) -> bool {
        self.topological_sort().is_err()
    }

    /// Renders a simple text view of the graph.
    pub fn render_text(&self) -> Result<String, GraphError> {
        Ok(self.topological_sort()?.join("\n↓\n"))
    }
}

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

    #[test]
    fn creates_graph() {
        let mut graph = AssetGraph::new();
        graph.add_edge("audio/crow.wav", "compiled/crow_horror.wav");

        assert_eq!(
            graph.outputs_of("audio/crow.wav"),
            vec!["compiled/crow_horror.wav"]
        );
        assert_eq!(
            graph.inputs_of("compiled/crow_horror.wav"),
            vec!["audio/crow.wav"]
        );
    }

    #[test]
    fn detects_cycles() {
        let mut graph = AssetGraph::new();
        graph.add_edge("a", "b");
        graph.add_edge("b", "a");

        assert!(graph.has_cycle());
        assert_eq!(graph.topological_sort(), Err(GraphError::Cycle));
    }

    #[test]
    fn resolves_incremental_dependents() {
        let mut graph = AssetGraph::new();
        graph.add_edge("crow.wav", "crow_horror.wav");
        graph.add_edge("crow_horror.wav", "enemy_spawn.wav");

        assert_eq!(
            graph.transitive_dependents("crow.wav"),
            vec!["crow_horror.wav".to_string(), "enemy_spawn.wav".to_string()]
        );
    }
}
