mapgraph 0.12.0

use crate::{
    graph::{iter, Node},
    Map, MapWithCapacity, OrderedKeyMap,
};
use core::{
    fmt::Debug,
    marker::PhantomData,
    ops::{Index, IndexMut, RangeBounds},
};
#[cfg(feature = "rayon")]
use {
    crate::{
        map::ParIterMap,
        util::{ParNodeWeightIter, ParNodeWeightIterMut},
    },
    rayon::iter::ParallelIterator,
};

/// A wrapper for node maps that disallows structural changes to the graph.
#[derive(Clone, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[repr(transparent)]
pub struct Nodes<N, EI, NM>
where
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>>,
{
    pub(super) map: NM,
    #[cfg_attr(feature = "serde", serde(skip_serializing, default))]
    _marker: PhantomData<(N, EI)>,
}

impl<N, EI, NM> Nodes<N, EI, NM>
where
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>>,
{
    /// Returns true if the node map contains the provided index.
    pub fn contains_key(&self, index: NM::Key) -> bool {
        self.map.contains_key(index)
    }

    /// Returns an immutable reference to a node if the index is present in the node map.
    pub fn get(&self, index: NM::Key) -> Option<&Node<N, EI>> {
        self.map.get(index)
    }

    /// Returns a mutable reference to a node if the index is present in the node map.
    pub fn get_mut(&mut self, index: NM::Key) -> Option<&mut Node<N, EI>> {
        self.map.get_mut(index)
    }

    /// Returns an immutable reference to a node's weight if the index is present in the node map.
    pub fn weight(&self, index: NM::Key) -> Option<&N> {
        self.map.get(index).map(Node::weight)
    }

    /// Returns a mutable reference to a node's weight if the index is present in the node map.
    pub fn weight_mut(&mut self, index: NM::Key) -> Option<&mut N> {
        self.map.get_mut(index).map(Node::weight_mut)
    }

    /// Returns an immutable iterator over the nodes in the node map.
    pub fn iter(&self) -> NM::Iter<'_> {
        self.map.iter()
    }

    /// Returns a mutable iterator over the nodes in the node map.
    pub fn iter_mut(&mut self) -> NM::IterMut<'_> {
        self.map.iter_mut()
    }

    /// Returns an immutable iterator over the weights of nodes stored in the node map.
    pub fn iter_weights(&self) -> iter::NodeWeights<'_, N, NM::Key, EI, NM> {
        iter::NodeWeights { inner: self.iter() }
    }

    /// Returns a mutable iterator over the weights of nodes stored in the node map.
    pub fn iter_weights_mut(&mut self) -> iter::NodeWeightsMut<'_, N, NM::Key, EI, NM> {
        iter::NodeWeightsMut {
            inner: self.iter_mut(),
        }
    }

    /// Returns the amount of nodes stored in the nodes map.
    pub fn len(&self) -> usize {
        self.map.len()
    }

    /// Returns a boolean indicating whether the nodes map contains no nodes.
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Returns a walker over the successors of a node.
    pub fn walk_successors(&self, index: NM::Key) -> iter::WalkSuccessors<EI> {
        let next = self[index].next_outgoing_edge;

        iter::WalkSuccessors { next }
    }

    /// Returns a walker over the predecessors of a node.
    pub fn walk_predecessors(&self, index: NM::Key) -> iter::WalkPredecessors<EI> {
        let next = self[index].next_incoming_edge;

        iter::WalkPredecessors { next }
    }

    /// Returns a walker over a node's outputs which can be used either with a complete graph or
    /// with an [`Edges`] reference.
    ///
    /// # Panics
    ///
    /// This function will panic in case the passed in node index is invalid.
    ///
    /// Additionally, the walker may panic in case one of the outgoing edges of the node are
    /// removed.
    ///
    /// [`Edges`]: super::Edges
    pub fn walk_outputs(&self, index: NM::Key) -> iter::WalkOutputs<EI> {
        iter::WalkOutputs {
            next: self
                .get(index)
                .expect("invalid node index")
                .next_outgoing_edge,
        }
    }

    /// Returns a walker over a node's inputs which can be used either with a complete graph or
    /// with an [`Edges`] reference.
    ///
    /// # Panics
    ///
    /// This function will panic in case the passed in node index is invalid.
    ///
    /// Additionally, the walker may panic in case one of the incoming edges of the node are
    /// removed.
    ///
    /// [`Edges`]: super::Edges
    pub fn walk_inputs(&self, index: NM::Key) -> iter::WalkInputs<EI> {
        iter::WalkInputs {
            next: self
                .get(index)
                .expect("invalid node index")
                .next_incoming_edge,
        }
    }
}

impl<N, EI, NM> Nodes<N, EI, NM>
where
    EI: Copy + Eq + Debug + 'static,
    NM: MapWithCapacity<Node<N, EI>>,
{
    pub(super) fn with_capacity(capacity: usize) -> Self {
        Self {
            map: NM::with_capacity(capacity),
            _marker: PhantomData,
        }
    }
}

impl<N, EI, NM> Nodes<N, EI, NM>
where
    EI: Copy + Eq + Debug + 'static,
    NM: OrderedKeyMap<Node<N, EI>>,
    NM::Key: Ord,
{
    /// Returns an immutable iterator over nodes with indices that fall into the specified range.
    ///
    /// # Order of iteration
    ///
    /// The order the nodes are returned in depends on the range iterator type provided by the node
    /// map in its [`OrderedKeyMap`] implementation as the [`OrderedKeyMap::Range`] associated type.
    pub fn range<R: RangeBounds<NM::Key>>(&self, range: R) -> NM::Range<'_> {
        self.map.range(range)
    }
    /// Returns a mutable iterator over nodes with indices that fall into the specified range.
    ///
    /// # Order of iteration
    ///
    /// The order the nodes are returned in depends on the range iterator type provided by the node
    /// map in its [`OrderedKeyMap`] implementation as the [`OrderedKeyMap::Range`] associated type.
    pub fn range_mut<R: RangeBounds<NM::Key>>(&mut self, range: R) -> NM::RangeMut<'_> {
        self.map.range_mut(range)
    }

    /// Returns an immutable reference to the first node in the node map in case it isn't empty.
    pub fn first(&self) -> Option<(NM::Key, &Node<N, EI>)> {
        self.map.first()
    }

    /// Returns an immutable reference to the last node in the node map in case it isn't empty.
    pub fn last(&self) -> Option<(NM::Key, &Node<N, EI>)> {
        self.map.last()
    }

    /// Returns a mutable reference to the first node in the node map in case it isn't empty.
    pub fn first_mut(&mut self) -> Option<(NM::Key, &mut Node<N, EI>)> {
        self.map.first_mut()
    }

    /// Returns a mutable reference to the last node in the node map in case it isn't empty.
    pub fn last_mut(&mut self) -> Option<(NM::Key, &mut Node<N, EI>)> {
        self.map.last_mut()
    }

    /// Returns an immutable reference to the weight of the first node in the node map in case the
    /// map isn't empty.
    pub fn first_weight(&self) -> Option<(NM::Key, &N)> {
        self.map.first().map(|(index, node)| (index, node.weight()))
    }

    /// Returns an immutable reference to the weight of the last node in the node map in case the
    /// map isn't empty.
    pub fn last_weight(&self) -> Option<(NM::Key, &N)> {
        self.map.last().map(|(index, node)| (index, node.weight()))
    }

    /// Returns a mutable reference to the weight of the first node in the node map in case the
    /// map isn't empty.
    pub fn first_weight_mut(&mut self) -> Option<(NM::Key, &mut N)> {
        self.map
            .first_mut()
            .map(|(index, node)| (index, node.weight_mut()))
    }

    /// Returns a mutable reference to the weight of the last node in the node map in case the
    /// map isn't empty.
    pub fn last_weight_mut(&mut self) -> Option<(NM::Key, &mut N)> {
        self.map
            .last_mut()
            .map(|(index, node)| (index, node.weight_mut()))
    }
}

#[cfg(feature = "rayon")]
impl<N, EI, NM> Nodes<N, EI, NM>
where
    N: Sync + Send,
    EI: Copy + Eq + Debug + 'static,
    NM: ParIterMap<Node<N, EI>>,
    NM::Key: Send + Sync,
{
    /// Returns an immutable parallel iterator over the nodes in the node map.
    pub fn par_iter(&self) -> NM::ParIter<'_> {
        self.map.par_iter()
    }

    /// Returns a mutable iterator over the nodes in the node map.
    pub fn par_iter_mut(&mut self) -> NM::ParIterMut<'_> {
        self.map.par_iter_mut()
    }

    /// Returns an immutable iterator over the weights of nodes stored in the node map.
    pub fn par_iter_weights(&self) -> ParNodeWeightIter<NM::ParIter<'_>, NM::Key, EI, N> {
        self.map
            .par_iter()
            .map(|(index, node)| (index, node.weight()))
    }

    /// Returns a mutable iterator over the weights of nodes stored in the node map.
    pub fn par_iter_weights_mut(
        &mut self,
    ) -> ParNodeWeightIterMut<NM::ParIterMut<'_>, NM::Key, EI, N> {
        self.map
            .par_iter_mut()
            .map(|(index, node)| (index, node.weight_mut()))
    }
}

impl<N, EI, NM> Default for Nodes<N, EI, NM>
where
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>>,
{
    fn default() -> Self {
        Self {
            map: Default::default(),
            _marker: PhantomData,
        }
    }
}

impl<N, EI, NM> Index<NM::Key> for Nodes<N, EI, NM>
where
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>>,
{
    type Output = Node<N, EI>;

    fn index(&self, index: NM::Key) -> &Self::Output {
        self.map.get(index).expect("invalid node index")
    }
}

impl<N, EI, NM> IndexMut<NM::Key> for Nodes<N, EI, NM>
where
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>>,
{
    fn index_mut(&mut self, index: NM::Key) -> &mut Self::Output {
        self.map.get_mut(index).expect("invalid node index")
    }
}

impl<'a, N, EI, NM> IntoIterator for &'a Nodes<N, EI, NM>
where
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>>,
{
    type Item = (NM::Key, &'a Node<N, EI>);
    type IntoIter = NM::Iter<'a>;

    fn into_iter(self) -> Self::IntoIter {
        self.map.iter()
    }
}

impl<'a, N, EI, NM> IntoIterator for &'a mut Nodes<N, EI, NM>
where
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>>,
{
    type Item = (NM::Key, &'a mut Node<N, EI>);
    type IntoIter = NM::IterMut<'a>;

    fn into_iter(self) -> Self::IntoIter {
        self.map.iter_mut()
    }
}