hypergraphx 0.0.5

use std::{iter, marker::PhantomData};

use fixedbitset::FixedBitSet;

use crate::prelude::*;

/// A depth first search (DFS) visitor event.
#[derive(Copy, Clone, Debug)]
pub enum DfsEvent<N> {
    Discover(N, usize),
    /// An edge of the tree formed by the traversal.
    TreeEdge(N, N),
    /// An edge to an already visited node.
    BackEdge(N, N),
    /// A cross or forward edge.
    ///
    /// For an edge *(u, v)*, if the discover time of *v* is greater than *u*,
    /// then it is a forward edge, else a cross edge.
    CrossForwardEdge(N, N),
    /// All edges from a node have been reported.
    Finish(N, usize),
}

/// Return if the expression is a break value, execute the provided statement
/// if it is a prune value.
macro_rules! try_control {
    ($e:expr, $p:stmt) => {
        try_control!($e, $p, ());
    };
    ($e:expr, $p:stmt, $q:stmt) => {
        match $e {
            x => {
                if x.should_break() {
                    return x;
                } else if x.should_prune() {
                    $p
                } else {
                    $q
                }
            }
        }
    };
}

/// Control flow for `depth_first_search` callbacks.
#[derive(Copy, Clone, Debug)]
pub enum Control<B> {
    /// Continue the DFS traversal as normal.
    Continue,
    /// Prune the current node from the DFS traversal. No more edges from this
    /// node will be reported to the callback. A `DfsEvent::Finish` for this
    /// node will still be reported. This can be returned in response to any
    /// `DfsEvent`, except `Finish`, which will panic.
    Prune,
    /// Stop the DFS traversal and return the provided value.
    Break(B),
}

impl<B> Control<B> {
    pub fn breaking() -> Control<()> {
        Control::Break(())
    }
    /// Get the value in `Control::Break(_)`, if present.
    pub fn break_value(self) -> Option<B> {
        match self {
            Control::Continue | Control::Prune => None,
            Control::Break(b) => Some(b),
        }
    }
}

/// Control flow for callbacks.
///
/// The empty return value `()` is equivalent to continue.
pub trait ControlFlow {
    fn continuing() -> Self;
    fn should_break(&self) -> bool;
    fn should_prune(&self) -> bool;
}

impl ControlFlow for () {
    fn continuing() {}
    #[inline]
    fn should_break(&self) -> bool {
        false
    }
    #[inline]
    fn should_prune(&self) -> bool {
        false
    }
}

impl<B> ControlFlow for Control<B> {
    fn continuing() -> Self {
        Control::Continue
    }
    fn should_break(&self) -> bool {
        if let Control::Break(_) = *self {
            true
        } else {
            false
        }
    }
    fn should_prune(&self) -> bool {
        match *self {
            Control::Prune => true,
            Control::Continue | Control::Break(_) => false,
        }
    }
}

impl<C: ControlFlow, E> ControlFlow for Result<C, E> {
    fn continuing() -> Self {
        Ok(C::continuing())
    }
    fn should_break(&self) -> bool {
        if let Ok(ref c) = *self {
            c.should_break()
        } else {
            true
        }
    }
    fn should_prune(&self) -> bool {
        if let Ok(ref c) = *self {
            c.should_prune()
        } else {
            false
        }
    }
}

/// The default is `Continue`.
impl<B> Default for Control<B> {
    fn default() -> Self {
        Control::Continue
    }
}

/// A recursive depth first search.
///
/// Starting points are the nodes in the iterator `starts` (specify just one
/// start vertex *x* by using `Some(x)`).
///
/// The traversal emits discovery and finish events for each reachable vertex,
/// and edge classification of each reachable edge. `visitor` is called for each
/// event, see [`DfsEvent`][de] for possible values.
///
/// The return value should implement the trait `ControlFlow`, and can be used to change
/// the control flow of the search.
///
/// `Control` Implements `ControlFlow` such that `Control::Continue` resumes the search.
/// `Control::Break` will stop the visit early, returning the contained value.
/// `Control::Prune` will stop traversing any additional edges from the current
/// node and proceed immediately to the `Finish` event.
///
/// There are implementations of `ControlFlow` for `()`, and `Result<C, E>` where
/// `C: ControlFlow`. The implementation for `()` will continue until finished.
/// For `Result`, upon encountering an `E` it will break, otherwise acting the same as `C`.
///
/// ***Panics** if you attempt to prune a node from its `Finish` event.
///
/// [de]: enum.DfsEvent.html
///
/// # Example returning `Control`.
///
/// Find a path from vertex 0 to 5, and exit the visit as soon as we reach
/// the goal vertex.
///
/// ```
/// ```
pub fn depth_first_search<'a, G, I, F, C>(graph: &'a G, starts: I, mut visitor: F) -> C
where
    G: GraphProperties<'a>,
    I: IntoIterator<Item = <G as GraphBasics<'a>>::NodeIndex>,
    F: FnMut(DfsEvent<<G as GraphBasics<'a>>::NodeIndex>) -> C,
    C: ControlFlow,
{
    let time = &mut 0_usize;
    let discovered = &mut graph.visit_map();
    let finished = &mut graph.visit_map();

    for start in starts {
        try_control!(
            dfs_visitor(graph, start, &mut visitor, discovered, finished, time),
            unreachable!()
        );
    }
    C::continuing()
}

fn dfs_visitor<'a, G, F, C>(
    graph: &'a G,
    u: G::NodeIndex,
    visitor: &mut F,
    discovered: &mut FixedBitSet,
    finished: &mut FixedBitSet,
    time: &mut usize,
) -> C
where
    G: GraphProperties<'a>,
    F: FnMut(DfsEvent<G::NodeIndex>) -> C,
    C: ControlFlow,
{
    if !discovered.put(u.into()) {
        return C::continuing();
    }

    try_control!(
        visitor(DfsEvent::Discover(u, time_post_inc(time))),
        {},
        for v in graph.neighbours(u).unwrap() {
            if !discovered.contains(v.into()) {
                try_control!(visitor(DfsEvent::TreeEdge(u, v)), continue);
                try_control!(
                    dfs_visitor(graph, v, visitor, discovered, finished, time),
                    unreachable!()
                );
            } else if !finished.contains(v.into()) {
                try_control!(visitor(DfsEvent::BackEdge(u, v)), continue);
            } else {
                try_control!(visitor(DfsEvent::CrossForwardEdge(u, v)), continue);
            }
        }
    );
    let first_finish = finished.put(u.into());
    debug_assert!(first_finish);
    try_control!(
        visitor(DfsEvent::Finish(u, time_post_inc(time))),
        panic!("Pruning on the `DfsEvent::Finish` is not supported!")
    );
    C::continuing()
}

fn time_post_inc(x: &mut usize) -> usize {
    let v = *x;
    *x += 1;
    v
}

/// Visit nodes in a depth-first-search (DFS) emitting nodes in postorder
/// (each node after all its descendants have been emitted).
///
/// `DfsPostOrder` is not recursive.
///
/// The traversal starts at a given node and only traverses nodes reachable
/// from it.
#[derive(Clone, Debug)]
pub struct DfsPostOrder<T: GraphType> {
    /// The stack of nodes to visit
    pub stack: Vec<usize>,
    /// The map of discovered nodes
    pub discovered: FixedBitSet,
    /// The map of finished nodes
    pub finished: FixedBitSet,
    _pd: PhantomData<T>,
}

#[derive(Clone, Debug)]
pub struct DfsPostOrderWithEdges<T: GraphType> {
    /// The stack of nodes to visit
    pub stack: Vec<usize>,
    pub edge_stack: Vec<usize>,
    /// The map of discovered nodes
    pub discovered: FixedBitSet,
    /// The map of finished nodes
    pub finished: FixedBitSet,
    _pd: PhantomData<T>,
}

impl<T: GraphType> Default for DfsPostOrder<T> {
    fn default() -> Self {
        DfsPostOrder {
            stack: vec![],
            discovered: FixedBitSet::default(),
            finished: FixedBitSet::default(),
            _pd: PhantomData,
        }
    }
}

impl<T: GraphType> Default for DfsPostOrderWithEdges<T> {
    fn default() -> Self {
        DfsPostOrderWithEdges {
            stack: vec![],
            edge_stack: vec![],
            discovered: FixedBitSet::default(),
            finished: FixedBitSet::default(),
            _pd: PhantomData,
        }
    }
}

impl<'a, T: GraphType> DfsPostOrder<T> {
    /// Create a new `DfsPostOrder` using the graph's visitor map, and put
    /// `start` in the stack of nodes to visit.
    pub fn new<G: ?Sized>(graph: &'a G, start: G::NodeIndex) -> Self
    where
        G: CommonProperties<'a, T>,
    {
        let mut dfs = Self::empty(graph);
        dfs.move_to(start.into());
        dfs
    }

    /// Create a new `DfsPostOrder` using the graph's visitor map, and no stack.
    pub fn empty<G: ?Sized>(graph: &'a G) -> Self
    where
        G: CommonProperties<'a, T>,
    {
        DfsPostOrder {
            stack: Vec::new(),
            discovered: graph.visit_map(),
            finished: graph.visit_map(),
            _pd: PhantomData,
        }
    }

    /// Clear the visit state
    pub fn reset<G>(&mut self)
    where
    // G: GraphProperties<'a>,
    {
        self.discovered.clear();
        self.finished.clear();
        self.stack.clear();
    }

    /// Keep the discovered and finished map, but clear the visit stack and restart
    /// the dfs from a particular node.
    pub fn move_to(&mut self, start: usize) {
        self.stack.clear();
        self.stack.push(start);
    }

    /// Return the next node in the traversal, or `None` if the traversal is done.
    pub fn next_node<G: ?Sized>(&mut self, graph: &'a G) -> Option<usize>
    where
        G: CommonProperties<'a, T> + GraphBasics<'a>,
    {
        while let Some(&nx) = self.stack.last() {
            if self.discovered.put(self.stack.len() - 1) {
                // First time visiting `nx`: Push neighbors, don't pop `nx`
                // for graph.neighbours_with_edges(node_index)
                for succ in graph
                    .neighbours_or_out_neighbours((self.stack.len() - 1).into())
                    .unwrap()
                {
                    if !self.discovered.contains(succ.into()) {
                        self.stack.push(succ.into());
                    }
                }
            } else {
                self.stack.pop();
                if self.finished.put(self.stack.len() - 1) {
                    // Second time: All reachable nodes must have been finished
                    return Some(nx);
                }
            }
        }
        None
    }
}

impl<'a, T: GraphType> DfsPostOrderWithEdges<T> {
    /// Create a new `DfsPostOrder` using the graph's visitor map, and put
    /// `start` in the stack of nodes to visit.
    pub fn new<G: ?Sized>(graph: &'a G, start: G::NodeIndex) -> Self
    where
        G: CommonProperties<'a, T>,
    {
        let mut dfs = Self::empty(graph);
        dfs.move_to(start.into());
        dfs
    }

    /// Create a new `DfsPostOrder` using the graph's visitor map, and no stack.
    pub fn empty<G: ?Sized>(graph: &'a G) -> Self
    where
        G: CommonProperties<'a, T>,
    {
        DfsPostOrderWithEdges {
            stack: Vec::new(),
            edge_stack: vec![],
            discovered: graph.visit_map(),
            finished: graph.visit_map(),
            _pd: PhantomData,
        }
    }

    /// Clear the visit state
    pub fn reset<G>(&mut self)
    where
    // G: GraphProperties<'a>,
    {
        self.discovered.clear();
        self.finished.clear();
        self.stack.clear();
        self.edge_stack.clear();
    }

    /// Keep the discovered and finished map, but clear the visit stack and restart
    /// the dfs from a particular node.
    pub fn move_to(&mut self, start: usize) {
        self.stack.clear();
        self.edge_stack.clear();
        self.stack.push(start);
    }

    /// Return the next node in the traversal, or `None` if the traversal is done.
    pub fn next_node<G: ?Sized>(&mut self, graph: &'a G) -> Option<(usize, usize)>
    where
        G: CommonProperties<'a, T> + GraphBasics<'a>,
    {
        while let Some(&nx) = self.stack.last() {
            if self.discovered.put(self.stack.len() - 1) {
                // First time visiting `nx`: Push neighbors, don't pop `nx`
                for (e, nodes) in graph.neighbours_with_edges((self.stack.len() - 1).into()) {
                    if nodes.iter().any(|&succ| {
                        if !self.discovered.contains(succ.into()) {
                            self.stack.push(succ.into());
                            return true;
                        }
                        false
                    }) {
                        self.edge_stack.push(e.into());
                    }
                }
            } else {
                self.stack.pop();
                self.edge_stack.pop();
                if self.finished.put(self.stack.len() - 1) {
                    // Second time: All reachable nodes must have been finished
                    return Some((nx, *self.edge_stack.last().unwrap()));
                }
            }
        }
        None
    }

    pub(crate) fn make_cycle(
        &self,
        curr_node: usize,
        curr_edge: usize,
    ) -> impl Iterator<Item = (usize, usize)> {
        self.stack
            .iter()
            .copied()
            .zip(self.edge_stack.iter().copied())
            .chain(iter::once((curr_node, curr_edge)))
    }
}

/// A walker is a traversal state, but where part of the traversal
/// information is supplied manually to each next call.
///
/// This for example allows graph traversals that don't hold a borrow of the
/// graph they are traversing.
pub trait Walker<'a, Context: ?Sized, T: GraphType> {
    type Item;
    /// Advance to the next item
    fn walk_next(&mut self, context: &'a Context) -> Option<Self::Item>;

    /// Create an iterator out of the walker and given `context`.
    fn iter(self, context: &'a Context) -> WalkerIter<'a, Self, Context, T>
    where
        Self: Sized,
    {
        WalkerIter {
            walker: self,
            context,
            _pd: PhantomData,
        }
    }
}

/// A walker and its context wrapped into an iterator.
#[derive(Clone, Debug)]
pub struct WalkerIter<'a, W, C: ?Sized, T> {
    walker: W,
    context: &'a C,
    _pd: PhantomData<T>,
}

impl<'a, W, C, T: GraphType> WalkerIter<'a, W, C, T>
where
    W: Walker<'a, C, T>,
    C: Clone,
{
    pub fn context(&self) -> C {
        self.context.clone()
    }

    pub fn inner_ref(&self) -> &W {
        &self.walker
    }

    pub fn inner_mut(&mut self) -> &mut W {
        &mut self.walker
    }
}

impl<'a, W, C: ?Sized, T: GraphType> Iterator for WalkerIter<'a, W, C, T>
where
    W: Walker<'a, C, T>,
    // C: Clone,
{
    type Item = W::Item;
    fn next(&mut self) -> Option<Self::Item> {
        self.walker.walk_next(self.context)
    }
}

impl<'a, C, W: ?Sized, T: GraphType> Walker<'a, C, T> for &'a mut W
where
    W: Walker<'a, C, T>,
{
    type Item = W::Item;
    fn walk_next(&mut self, context: &'a C) -> Option<Self::Item> {
        (**self).walk_next(context)
    }
}

impl<'a, G: ?Sized, T: GraphType> Walker<'a, G, T> for DfsPostOrder<T>
where
    G: CommonProperties<'a, T> + GraphBasics<'a>,
{
    type Item = usize;
    fn walk_next(&mut self, context: &'a G) -> Option<Self::Item> {
        self.next_node(context)
    }
}

impl<'a, G: ?Sized, T: GraphType> Walker<'a, G, T> for DfsPostOrderWithEdges<T>
where
    G: CommonProperties<'a, T> + GraphBasics<'a>,
{
    type Item = (usize, usize);
    fn walk_next(&mut self, context: &'a G) -> Option<Self::Item> {
        self.next_node(context)
    }
}