spokes 0.4.0-rc.4

//! The following is the generic trait for arc information storage [`ArcStorage`] and several
//! implementations:
//!  * [`ForwardAndReverseStar`] - A space efficient arc storage format.
//!  * [`HashMapStorage`] - A flexible hash map based storage format.

use crate::ArcInfo;

mod forward_star;
pub use self::forward_star::ForwardAndReverseStar;

mod hash_map;
pub use self::hash_map::HashMapStorage;

/// Arc storage for (tail, head) pairs with attributes.
pub trait ArcStorage<I, A>: Default {
    /// Create an empty storage with pre-allocated memory
    fn with_capacity(n_nodes: usize, n_arcs: usize) -> Self;

    /// Return the number of arcs
    fn m_arcs(&self) -> usize;

    /// Get the attributes for an arc
    fn arc(&self, tail: &I, head: &I) -> Option<&A>;

    /// Get the attributes for an arc, with a mutable reference
    fn arc_mut(&mut self, tail: &I, head: &I) -> Option<&mut A>;

    /// Check if arc exists
    fn contains_arc(&self, tail: &I, head: &I) -> bool;

    /// Add an arc to the store. This will remove an existing arc with the (tail, head) pair.
    fn add_arc<T: Into<ArcInfo<I, A>>>(&mut self, arc: T);

    /// Remove an arc from the store, optionally returning the attributes if such an arc existed.
    fn remove_arc(&mut self, tail: &I, head: &I) -> Option<A>;

    /// Remove all arcs with head or tail equal to id.
    fn remove_arcs_with_node(&mut self, id: &I);

    /// Add multiple arcs to the arc store
    fn add_arcs<E: IntoIterator<Item = T>, T: Into<ArcInfo<I, A>>>(&mut self, to_add: E) {
        to_add.into_iter().for_each(|arc| self.add_arc(arc));
    }

    /// Remove multiple arcs to the arc store
    fn remove_arcs<'a, T: IntoIterator<Item = (&'a I, &'a I)>>(
        &mut self,
        to_remove: T,
    ) -> Vec<Option<A>>
    where
        I: 'a,
    {
        to_remove
            .into_iter()
            .map(|arc| self.remove_arc(arc.0, arc.1))
            .collect()
    }

    /// Return true if there are forward arcs from the given node
    fn has_forward_arcs(&self, node: &I) -> bool;

    /// Return true if there are reverse arcs to the given node
    fn has_reverse_arcs(&self, node: &I) -> bool;

    /// Iterate through all arcs
    fn arc_iter<'a>(&'a self) -> impl Iterator<Item = &'a ArcInfo<I, A>> + 'a
    where
        A: 'a,
        I: 'a;

    /// Iterate through all arcs, mutibly
    fn arc_iter_mut<'a>(&'a mut self) -> impl Iterator<Item = &'a mut ArcInfo<I, A>> + 'a
    where
        A: 'a,
        I: 'a;

    /// Return an iterator of arcs which depart the given node
    fn forward_arcs<'a>(&'a self, node: &'a I) -> impl Iterator<Item = &'a ArcInfo<I, A>> + 'a
    where
        A: 'a,
        I: 'a;

    /// Return an iterator of arcs which terminate at the given node
    fn reverse_arcs<'a>(&'a self, node: &'a I) -> impl Iterator<Item = &'a ArcInfo<I, A>> + 'a
    where
        A: 'a,
        I: 'a;

    /// Return an iterator of all arcs, forward and reverse, for a node.
    fn all_arcs<'a>(&'a self, node: &'a I) -> impl Iterator<Item = &'a ArcInfo<I, A>> + 'a
    where
        A: 'a,
        I: 'a,
    {
        self.forward_arcs(node).chain(self.reverse_arcs(node))
    }
}