use std::collections::{BTreeSet, HashMap};
use std::hash::Hash;

/// Partition a DAG into topological layers (depth tiers) using Kahn's
/// algorithm.
///
/// Layer 0 contains all source nodes (in-degree 0), layer 1 contains nodes
/// whose predecessors are all in layer 0, and so on. Nodes within each layer
/// are sorted (since `N: Ord`). Returns an empty `Vec` only when `nodes` is
/// empty.
///
/// In-degree is computed internally from `successors`; callers only need to
/// provide the adjacency list and the full node set (nodes with no edges in
/// `successors` are treated as isolated sources).
///
/// # Complexity
///
/// O(V + E) time and space, where V = `nodes.len()` and E is the total
/// number of edges in `successors`.
///
/// # References
///
/// Kahn, A. B. (1962). *Topological sorting of large networks*.
/// Communications of the ACM, 5(11), 558--562.
pub fn topological_layers<N>(nodes: &BTreeSet<N>, successors: &HashMap<N, Vec<N>>) -> Vec<Vec<N>>
where
    N: Copy + Eq + Hash + Ord,
{
    let mut in_degree: HashMap<N, usize> = HashMap::new();
    for &node in nodes {
        in_degree.entry(node).or_default();
    }
    for (&src, targets) in successors {
        if !nodes.contains(&src) {
            continue;
        }
        for &tgt in targets {
            if nodes.contains(&tgt) {
                *in_degree.entry(tgt).or_default() += 1;
            }
        }
    }

    let mut queue: Vec<N> = nodes
        .iter()
        .filter(|n| *in_degree.get(n).unwrap_or(&0) == 0)
        .copied()
        .collect();

    let mut layers: Vec<Vec<N>> = Vec::new();

    while !queue.is_empty() {
        layers.push(queue.clone());

        let mut next_queue = Vec::new();
        for &node in &queue {
            if let Some(children) = successors.get(&node) {
                for &child in children {
                    if let Some(deg) = in_degree.get_mut(&child) {
                        *deg -= 1;
                        if *deg == 0 {
                            next_queue.push(child);
                        }
                    }
                }
            }
        }
        next_queue.sort();
        queue = next_queue;
    }

    layers
}
