willdo 0.0.1

use core::{fmt::Debug, marker::PhantomData};
use daggy::Walker;
use petgraph::visit::GraphBase;
use std::collections::VecDeque;

/// Recursively walks a graph using the recursive function `recursive_fn`.
#[derive(Clone, Debug)]
pub struct Recurse<G, F, T>
where
    G: GraphBase,
{
    queue: VecDeque<(G::NodeId, T)>,
    recursive_fn: F,
    pub depth_first: bool,
    _graph: PhantomData<G>,
}

impl<G, F, T> Walker<&G> for Recurse<G, F, T>
where
    G: GraphBase,
    F: FnMut(&G, G::NodeId, &T) -> Option<Vec<(G::NodeId, T)>>,
{
    type Item = (G::NodeId, T);
    #[inline]
    fn walk_next(&mut self, g: &G) -> Option<Self::Item> {
        self.next(g)
    }
}

impl<G, F, T> Recurse<G, F, T>
where
    G: GraphBase,
    F: FnMut(&G, G::NodeId, &T) -> Option<Vec<(G::NodeId, T)>>,
{
    /// Construct a new **Recursive** **Walker** starting from the node at the given index.
    pub fn new(start: impl IntoIterator<Item = G::NodeId>, recursive_fn: F) -> Self
    where
        T: Default,
    {
        Self::new_seeded(start.into_iter().map(|n| (n, T::default())), recursive_fn)
    }

    /// Construct a new **Recursive** **Walker** starting from the node at the given index.
    pub fn new_seeded(start: impl IntoIterator<Item = (G::NodeId, T)>, recursive_fn: F) -> Self {
        Recurse {
            queue: start.into_iter().collect(),
            recursive_fn,
            depth_first: false,
            _graph: PhantomData,
        }
    }

    /// Yield the next recursion step.
    pub fn next(&mut self, g: &G) -> Option<(G::NodeId, T)> {
        let Recurse {
            ref mut queue,
            ref mut recursive_fn,
            depth_first,
            ..
        } = *self;
        loop {
            let (current, path) = match depth_first {
                false => queue.pop_front()?,
                true => queue.pop_back()?,
            };
            let Some(accepted) = recursive_fn(g, current, &path) else {
                continue;
            };
            for (node, path) in accepted {
                queue.push_back((node, path));
            }

            break Some((current, path));
        }
    }

    pub fn depth_first(mut self) -> Self {
        self.depth_first = true;
        self
    }
}

#[test]
fn deps() {
    use crate::graph::linked::Stack;
    use daggy::Dag;
    use petgraph::prelude::EdgeIndex;

    let mut dag = Dag::new();
    let a: petgraph::prelude::NodeIndex<usize> = dag.add_node("a");
    let (eb, b) = dag.add_child(a, (), "b");
    let (ec, c) = dag.add_child(b, (), "c");

    let mut walk = Recurse::new(
        vec![c],
        |g: &Dag<&str, (), usize>, n, state: &Stack<EdgeIndex<usize>>| {
            use petgraph::visit::EdgeRef as _;
            use petgraph::visit::IntoEdgesDirected as _;
            println!("{n:?}");
            Some(
                g.edges_directed(n, petgraph::Direction::Incoming)
                    .map(|e| (e.source(), state + e.id()))
                    .collect(),
            )
        },
    );
    let (n, p) = walk.next(&dag).expect("c");
    assert!(p.iter().collect::<Vec<_>>().is_empty());
    assert_eq!(dag[n], "c");

    let (n, p) = walk.next(&dag).expect("b");
    assert_eq!(dag[n], "b");
    assert_eq!(p.iter().collect::<Vec<_>>(), vec![&ec]);

    let (n, p) = walk.next(&dag).expect("a");
    assert_eq!(dag[n], "a");
    assert_eq!(p.iter().collect::<Vec<_>>(), vec![&eb, &ec]);

    assert!(walk.next(&dag).is_none());
}

#[test]
fn deps_conditional() {
    use crate::graph::linked::Stack;
    use daggy::Dag;
    use petgraph::prelude::EdgeIndex;

    let mut dag = Dag::new();
    let a: petgraph::prelude::NodeIndex<usize> = dag.add_node(Some(0));
    let (_, b) = dag.add_child(a, true, Some(1));
    let (_, c) = dag.add_child(b, false, None);

    // this does not affect the game as a is already completed
    dag.add_parent(a, false, Some(2));

    // this does not affect the game as b is triggered by a
    dag.add_parent(b, false, None);

    // this does not affect the game as c is still waiting for b
    dag.add_parent(c, false, Some(0));

    let mut walk = Recurse::new(
        vec![c],
        |g: &Dag<Option<usize>, bool, usize>, n, state: &Stack<EdgeIndex<usize>>| {
            use petgraph::visit::EdgeRef as _;
            use petgraph::visit::IntoEdgesDirected as _;
            println!("{n:?}");
            let is_goal = state.iter().next().is_none();
            let is_completed = g[n].is_some();
            if is_goal && is_completed {
                return None;
            }
            let mut waiting = false;
            let mut due = false;
            let mut require = vec![];
            for e in g.edges_directed(n, petgraph::Direction::Incoming) {
                let passed = g[e.source()] == Some(0);
                let trigger = *e.weight();
                if trigger && passed {
                    due = true;
                    break;
                }
                if !trigger && !passed {
                    waiting = true;
                }
                if passed {
                    continue;
                }
                require.push((e.source(), state + e.id()));
            }
            if due || !waiting {
                Some(vec![])
            } else {
                Some(require)
            }
        },
    );

    let mut seq = vec![];
    while let Some(x) = walk.next(&dag) {
        seq.push(x);
    }
    insta::assert_debug_snapshot!(seq);

    // let (n, p) = walk.next(&dag).expect("c");
    // assert!(p.iter().collect::<Vec<_>>().is_empty());
    // assert_eq!(n.index(), 2);

    // let (n, p) = walk.next(&dag).expect("b");
    // assert_eq!(
    //     p.iter().map(|e| e.index()).collect::<Vec<_>>(),
    //     vec![ec.index()]
    // );
    // assert_eq!(n.index(), 1);

    // assert!(walk.next(&dag).is_none());
}