mapgraph 0.12.0

//! Contains the iterator and walker types that may be returned by methods on [`Graph`] and
//! [`FrozenGraph`].

use super::{Edge, Edges, FrozenGraph, Graph, IntKeyMap, Map, Node};
use core::{fmt::Debug, iter::FusedIterator, marker::PhantomData};

macro_rules! impl_drain_edges {
    ($name:ident, $word:literal, $word2:literal, $next:ident, $unlink:ident, $node_field:ident, $other_node_field:ident) => {
        #[doc = concat!(
            "A draining iterator over the ", $word, " edges of a node. The iterator yields a tuple with ",
            "the index of the ", $word, " node and the weight of the edge.\n\n"
        )]
        /// Dropping an iterator will cause some edges to be left in place. Which edges will stay is
        /// implementation defined.
        #[derive(Debug)]
        pub struct $name<'graph, N, E, NI, EI, NM, EM>
        where
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI>,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
        {
            pub(super) graph: &'graph mut Graph<N, E, NI, EI, NM, EM>,
            pub(super) next_edge_index: Option<EI>,
        }

        impl<'graph, N, E, NI, EI, NM, EM> Iterator for $name<'graph, N, E, NI, EI, NM, EM>
        where
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI>,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
        {
            type Item = (NI, E);

            fn next(&mut self) -> Option<Self::Item> {
                let next_edge_index = self.next_edge_index?;

                // Since we're draining an edges chain here anyway, we only need to unlink the
                // edge from the other edges chain.
                let edge = self.graph.edges.map.remove(next_edge_index).unwrap();
                self.graph.$unlink(next_edge_index, &edge);

                self.next_edge_index = edge.$next;
                self.graph.nodes[edge.$other_node_field].$next = edge.$next;

                Some((edge.$node_field, edge.weight))
            }
        }

        impl<'graph, N, E, NI, EI, NM, EM> FusedIterator
            for $name<'graph, N, E, NI, EI, NM, EM>
        where
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI>,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
        {
        }
    };
}

impl_drain_edges!(
    DrainOutgoingEdges,
    "outgoing",
    "destination",
    next_outgoing_edge,
    unlink_edge_from_incoming_list,
    to,
    from
);
impl_drain_edges!(
    DrainIncomingEdges,
    "incoming",
    "source",
    next_incoming_edge,
    unlink_edge_from_outgoing_list,
    from,
    to
);

macro_rules! impl_node_weights {
    ($name:ident, $word:literal, $iter:ident, $item:ty, $weight:ident) => {
        #[doc = concat!($word, " iterator over the [`Graph`]'s nodes' weights.")]
        #[derive(Debug)]
        pub struct $name<'graph, N, NI, EI, NM>
        where
            N: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI> + 'graph,
        {
            pub(super) inner: NM::$iter<'graph>,
        }

        impl<'graph, N, NI, EI, NM> Iterator for $name<'graph, N, NI, EI, NM>
        where
            N: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI> + 'graph,
        {
            type Item = (NM::Key, $item);

            #[inline]
            fn next(&mut self) -> Option<Self::Item> {
                self.inner
                    .next()
                    .map(|(index, node)| (index, node.$weight()))
            }

            #[inline]
            fn size_hint(&self) -> (usize, Option<usize>) {
                self.inner.size_hint()
            }
        }

        impl<'graph, N, NI, EI, NM> ExactSizeIterator for $name<'graph, N, NI, EI, NM>
        where
            N: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI> + 'graph,
            NM::$iter<'graph>: ExactSizeIterator,
        {
            #[inline]
            fn len(&self) -> usize {
                self.inner.len()
            }
        }

        impl<'graph, N, NI, EI, NM> FusedIterator for $name<'graph, N, NI, EI, NM>
        where
            N: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI> + 'graph,
            NM::$iter<'graph>: FusedIterator,
        {
        }

        impl<'graph, N, NI, EI, NM> DoubleEndedIterator for $name<'graph, N, NI, EI, NM>
        where
            N: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI> + 'graph,
            NM::$iter<'graph>: DoubleEndedIterator,
        {
            fn next_back(&mut self) -> Option<Self::Item> {
                self.inner
                    .next_back()
                    .map(|(index, node)| (index, node.$weight()))
            }
        }
    };
}

impl_node_weights!(NodeWeights, "An immutable", Iter, &'graph N, weight);
impl_node_weights!(
    NodeWeightsMut,
    "A mutable",
    IterMut,
    &'graph mut N,
    weight_mut
);

macro_rules! impl_edge_weights {
    ($name:ident, $word:literal, $iter:ident, $item:ty, $weight:ident) => {
        #[doc = concat!($word, " iterator over the [`Graph`]'s edges' weights.")]
        #[derive(Debug)]
        pub struct $name<'graph, E, NI, EI, EM>
        where
            E: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + 'graph,
        {
            pub(super) inner: EM::$iter<'graph>,
        }

        impl<'graph, E, NI, EI, EM> Iterator for $name<'graph, E, NI, EI, EM>
        where
            E: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + 'graph,
        {
            type Item = (EM::Key, $item);

            #[inline]
            fn next(&mut self) -> Option<Self::Item> {
                self.inner
                    .next()
                    .map(|(index, edge)| (index, edge.$weight()))
            }

            #[inline]
            fn size_hint(&self) -> (usize, Option<usize>) {
                self.inner.size_hint()
            }
        }

        impl<'graph, E, NI, EI, EM> ExactSizeIterator for $name<'graph, E, NI, EI, EM>
        where
            E: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + 'graph,
            EM::$iter<'graph>: ExactSizeIterator,
        {
            #[inline]
            fn len(&self) -> usize {
                self.inner.len()
            }
        }

        impl<'graph, E, NI, EI, EM> FusedIterator for $name<'graph, E, NI, EI, EM>
        where
            E: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + 'graph,
            EM::$iter<'graph>: FusedIterator,
        {
        }
    };
}

impl_edge_weights!(EdgeWeights, "An immutable", Iter, &'graph E, weight);
impl_edge_weights!(
    EdgeWeightsMut,
    "A mutable",
    IterMut,
    &'graph mut E,
    weight_mut
);

macro_rules! impl_edges_iter {
    ($name:ident, $word:literal, $next:ident) => {
        #[doc = concat!("Iterator over ", $word, "s of a graph's node.\n")]
        /// This iterator yields a tuple containing both the edge index and a reference to its
        /// [`Edge`] structure.
        #[derive(Debug)]
        pub struct $name<'graph, E, NI, EI, EM>
        where
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            EM: Map<Edge<E, NI, EI>, Key = EI>,
        {
            edges: &'graph EM,
            next: Option<EI>,
            _phantom: PhantomData<(E, NI, EI)>,
        }

        impl<'graph, E, NI, EI, EM> $name<'graph, E, NI, EI, EM>
        where
            E: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            EM: Map<Edge<E, NI, EI>, Key = EI> + 'graph,
        {
            pub(super) fn new(edges: &'graph EM, next: Option<EI>) -> Self {
                $name {
                    edges,
                    next,
                    _phantom: Default::default(),
                }
            }
        }

        impl<'graph, E, NI, EI, EM> Iterator for $name<'graph, E, NI, EI, EM>
        where
            E: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            EM: Map<Edge<E, NI, EI>, Key = EI> + 'graph,
        {
            type Item = (EI, &'graph Edge<E, NI, EI>);

            #[inline]
            fn next(&mut self) -> Option<Self::Item> {
                let next = self.next;
                if let Some(idx) = next {
                    let edge = self.edges.get(idx).unwrap();
                    self.next = edge.$next;
                    Some((idx, edge))
                } else {
                    None
                }
            }
        }
    };
}

impl_edges_iter!(Inputs, "input", next_incoming_edge);
impl_edges_iter!(Outputs, "output", next_outgoing_edge);

macro_rules! impl_neighbours_iter {
    ($name:ident, $word:literal, $next:ident, $node:ident) => {
        #[doc = concat!(
            "Iterator over ", $word, "s of a graph node.\n\n",
            "Emits tuples containing ", $word, "s' node indices and immutable references to ",
            "their weights."
        )]
        #[derive(Debug)]
        pub struct $name<'graph, N, E, NI, EI, NM, EM>
        where
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI>,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
        {
            pub(super) graph: &'graph FrozenGraph<N, E, NI, EI, NM, EM>,
            pub(super) next: Option<EI>,
        }

        impl<'graph, N, E, NI, EI, NM, EM> Iterator for $name<'graph, N, E, NI, EI, NM, EM>
        where
            N: 'graph,
            E: 'graph,
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI> + 'graph,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + 'graph,
        {
            type Item = (NI, &'graph N);

            #[inline]
            fn next(&mut self) -> Option<Self::Item> {
                let next = self.next;
                next.map(|index| {
                    let edge = self.graph.edges.get(index).unwrap();
                    self.next = edge.$next;

                    let node_index = edge.$node;
                    let node = self.graph.nodes.get(node_index).unwrap();
                    (node_index, &node.weight)
                })
            }
        }
    };
}

impl_neighbours_iter!(Successors, "successor", next_outgoing_edge, to);
impl_neighbours_iter!(Predecessors, "predecessor", next_incoming_edge, from);

/// A walker is an alternative for an iterator that accepts a reference to a graph on each call
/// to its `walk_next` methods instead of storing a reference to the graph as an iterator would
/// do.
///
/// Walkers provide an ability to arbitrarily mutate graphs during traversals without exposing
/// the internal implementation of the graph.
pub trait Walker<N, E, NI, EI, NM, EM>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
{
    /// The item returned by the walker.
    type Item<'a>
    where
        N: 'a,
        E: 'a,
        EM: 'a,
        NM: 'a;

    /// Retrieve the next item from the walker if any.
    fn walk_next<'a>(
        &mut self,
        graph: &'a FrozenGraph<N, E, NI, EI, NM, EM>,
    ) -> Option<Self::Item<'a>>;
}

/// A walker is an alternative for an iterator that accepts a reference to a graph on each call
/// to its `walk_next` methods instead of storing a reference to the graph as an iterator would
/// do.
///
/// Walkers provide an ability to arbitrarily mutate graphs during traversals without exposing
/// the internal implementation of the graph.
pub trait WalkerMut<N, E, NI, EI, NM, EM>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
    Self: Walker<N, E, NI, EI, NM, EM>,
{
    /// Retrieve the next item from the walker if any.
    fn walk_next_mut<'a>(
        &mut self,
        graph: &'a mut FrozenGraph<N, E, NI, EI, NM, EM>,
    ) -> Option<Self::Item<'a>>;
}

/// A walker is an alternative for an iterator that accepts a reference to a graph on each call
/// to its `walk_next` methods instead of storing a reference to the graph as an iterator would
/// do.
///
/// Walkers provide an ability to arbitrarily mutate graphs during traversals without exposing
/// the internal implementation of the graph.
pub trait EdgesWalker<E, NI, EI, EM>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
{
    /// The item returned by the walker.
    type Item<'a>
    where
        E: 'a,
        EM: 'a;

    /// Retrieve the next item from the walker if any.
    fn walk_edges_next<'a>(&mut self, edges: &'a Edges<E, NI, EI, EM>) -> Option<Self::Item<'a>>;
}

/// A walker is an alternative for an iterator that accepts a reference to a graph on each call
/// to its `walk_next` methods instead of storing a reference to the graph as an iterator would
/// do.
///
/// Walkers provide an ability to arbitrarily mutate graphs during traversals without exposing
/// the internal implementation of the graph.
pub trait EdgesWalkerMut<E, NI, EI, EM>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
    Self: EdgesWalker<E, NI, EI, EM>,
{
    /// Retrieve the next item from the walker if any.
    fn walk_edges_next_mut<'a>(
        &mut self,
        edges: &'a mut Edges<E, NI, EI, EM>,
    ) -> Option<Self::Item<'a>>;
}

macro_rules! impl_walk_neighbours {
    ($name:ident, $word:literal, $next:ident, $node:ident) => {
        #[doc = concat!("A \"walker\" over the ", $word, "s of a node.")]
        #[derive(Clone, Debug)]
        pub struct $name<EI: Copy + Eq + Debug + 'static> {
            pub(super) next: Option<EI>,
        }

        impl<N, E, NI, EI, NM, EM> Walker<N, E, NI, EI, NM, EM> for $name<EI>
        where
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI>,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
        {
            type Item<'a> = NI where N: 'a, E: 'a, EM: 'a, NM: 'a;

            fn walk_next<'a>(
                &mut self,
                graph: &'a FrozenGraph<N, E, NI, EI, NM, EM>,
            ) -> Option<Self::Item<'a>> {
                let cur_index = self.next?;
                let edge = graph.edges.get(cur_index).unwrap();
                self.next = edge.$next;
                Some(edge.$node)
            }
        }

        impl<E, NI, EI, EM> EdgesWalker<E, NI, EI, EM> for $name<EI>
        where
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
        {
            type Item<'a> = NI where E: 'a, EM: 'a;

            fn walk_edges_next<'a>(
                &mut self,
                edges: &'a Edges<E, NI, EI, EM>,
            ) -> Option<Self::Item<'a>> {
                let cur_index = self.next?;
                let edge = edges.get(cur_index).unwrap();
                self.next = edge.$next;
                Some(edge.$node)
            }
        }
    };
}

impl_walk_neighbours!(WalkSuccessors, "successor", next_outgoing_edge, to);
impl_walk_neighbours!(WalkPredecessors, "predecessor", next_incoming_edge, from);

macro_rules! impl_walk_edges {
    ($name:ident, $word:literal, $next:ident) => {
        #[doc = concat!("A \"walker\" over the ", $word, " edges of a node.")]
        #[derive(Clone, Debug)]
        pub struct $name<EI: Copy + Eq + Debug + 'static> {
            pub(super) next: Option<EI>,
        }

        impl<N, E, NI, EI, NM, EM> Walker<N, E, NI, EI, NM, EM> for $name<EI>
        where
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            NM: Map<Node<N, EI>, Key = NI>,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
        {
            type Item<'a> = (EI, &'a Edge<E, NI, EI>) where N: 'a, E: 'a, EM: 'a, NM: 'a;

            fn walk_next<'a>(
                &mut self,
                graph: &'a FrozenGraph<N, E, NI, EI, NM, EM>,
            ) -> Option<Self::Item<'a>> {
                let cur_index = self.next?;
                let edge = &graph.edges[cur_index];
                self.next = edge.$next;
                Some((cur_index, edge))
            }
        }

        impl<E, NI, EI, EM> EdgesWalker<E, NI, EI, EM> for $name<EI>
        where
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
        {
            type Item<'a> = (EI, &'a Edge<E, NI, EI>) where E: 'a, EM: 'a;

            fn walk_edges_next<'a>(
                &mut self,
                edges: &'a Edges<E, NI, EI, EM>,
            ) -> Option<Self::Item<'a>> {
                let cur_index = self.next?;
                let edge = &edges[cur_index];
                self.next = edge.$next;
                Some((cur_index, edge))
            }
        }

        impl<E, NI, EI, EM> EdgesWalkerMut<E, NI, EI, EM> for $name<EI>
        where
            NI: Copy + Eq + Debug + 'static,
            EI: Copy + Eq + Debug + 'static,
            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
        {
            fn walk_edges_next_mut<'a>(
                &mut self,
                edges: &'a mut Edges<E, NI, EI, EM>,
            ) -> Option<Self::Item<'a>> {
                let cur_index = self.next?;
                let edge = &mut edges[cur_index];
                self.next = edge.$next;
                Some((cur_index, edge))
            }
        }
    };
}

impl_walk_edges!(WalkOutputs, "outgoing", next_outgoing_edge);
impl_walk_edges!(WalkInputs, "incoming", next_incoming_edge);