mapgraph 0.12.0

//! Contains the generic [`Graph`] and [`FrozenGraph`] structures.

use crate::{
    error::{AddEdgeError, InvalidEdgeError, NodeExistsError, RemoveNodeError},
    graph::entry::{Entry, OccupiedEntry, VacantEntry},
    map::{ExtKeyMap, IntKeyMap, Map, MapEntry, MapWithCapacity, MapWithEntry, OrderedKeyMap},
};
use core::{
    borrow::{Borrow, BorrowMut},
    fmt::Debug,
    mem,
    ops::{Deref, DerefMut, RangeBounds},
};
#[cfg(feature = "rayon")]
use {
    crate::{
        map::ParIterMap,
        util::{EdgeMapFn, EdgeMapMutFn, ParNodeWeightIter, ParNodeWeightIterMut},
    },
    rayon::iter::Map as ParMap,
};

/// An opaque structure the [`Graph`] type uses to represent its nodes.
///
/// # Internal representation
///
/// Internally the structure contains the node's weight and indices of its outgoing and incoming
/// edges that appear first in their internal corresponding linked lists (in case the lists are not
/// empty).
///
/// The internal representation should not be considered stable. This note exists to provide an
/// insight into the implementation details in the hope that it will be useful for choosing the
/// optimal parameters for a [`Graph`].
#[derive(Clone, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Node<N, EI: Copy + Eq + Debug + 'static> {
    weight: N,
    next_incoming_edge: Option<EI>,
    next_outgoing_edge: Option<EI>,
}

impl<N, EI: Copy + Eq + Debug + 'static> Node<N, EI> {
    /// Returns an immutable reference to the weight of a node.
    pub fn weight(&self) -> &N {
        &self.weight
    }

    /// Returns a mutable reference to the weight of a node.
    pub fn weight_mut(&mut self) -> &mut N {
        &mut self.weight
    }

    /// Returns a walker over a node's outputs which can be used either with a complete graph or
    /// with an [`Edges`] reference.
    pub fn walk_outputs(&self) -> iter::WalkOutputs<EI> {
        iter::WalkOutputs {
            next: self.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.
    pub fn walk_inputs(&self) -> iter::WalkInputs<EI> {
        iter::WalkInputs {
            next: self.next_incoming_edge,
        }
    }

    /// Returns a walker over a node's successors which can be used either with a complete graph or
    /// with an [`Edges`] reference.
    pub fn walk_successors(&self) -> iter::WalkSuccessors<EI> {
        iter::WalkSuccessors {
            next: self.next_outgoing_edge,
        }
    }

    /// Returns a walker over a node's predecessors which can be used either with a complete graph or
    /// with an [`Edges`] reference.
    pub fn walk_predecessors(&self) -> iter::WalkPredecessors<EI> {
        iter::WalkPredecessors {
            next: self.next_incoming_edge,
        }
    }
}

/// The structure the [`Graph`] type uses to represent its edges.
///
/// Unlike the [`Node`] structure this structure exposes some of its internal fields through methods
/// for convenience.
///
/// # Internal representation
///
/// Internally the structure contains the edge's weight, indices of the source and destination nodes
/// and indices of the outgoing and incoming edges that appear next in their internal corresponding
/// linked lists (in case the edge is not the last in the list).
///
/// The internal representation should not be considered stable. This note exists to provide an
/// insight into the implementation details in the hope that it will be useful for choosing the
/// optimal parameters for a [`Graph`].
#[derive(Clone, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Edge<E, NI, EI>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
{
    weight: E,
    from: NI,
    to: NI,
    next_incoming_edge: Option<EI>,
    next_outgoing_edge: Option<EI>,
}

impl<E, NI, EI> Edge<E, NI, EI>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
{
    /// Returns an immutable reference to the weight of an edge.
    pub fn weight(&self) -> &E {
        &self.weight
    }

    /// Returns a mutable reference to the weight of an edge.
    pub fn weight_mut(&mut self) -> &mut E {
        &mut self.weight
    }

    /// Returns the index of the node where the edge starts.
    pub fn from(&self) -> NI {
        self.from
    }

    /// Returns the index of the node where the edge ends.
    pub fn to(&self) -> NI {
        self.to
    }
}

fn find_edge_impl<E, NI, EI, EM>(
    edges: &Edges<E, NI, EI, EM>,
    first_index: Option<EI>,
    to: NI,
) -> Option<EI>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
{
    let mut next_edge_index = first_index;
    while let Some(edge_index) = next_edge_index {
        let edge = edges.get(edge_index).expect("edge list is broken");

        if edge.to == to {
            return Some(edge_index);
        }

        next_edge_index = edge.next_outgoing_edge;
    }

    None
}

fn insert_edge_impl<N, E, NI, EI, NM, EM, RF, ERR>(
    graph: &mut FrozenGraph<N, E, NI, EI, NM, EM>,
    from: NI,
    to: NI,
    weight: E,
    replace: RF,
) -> Result<(EI, Option<E>), ERR>
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>,
    RF: FnOnce(E, EI, &mut Edges<E, NI, EI, EM>) -> Result<E, ERR>,
    ERR: From<InvalidEdgeError>,
{
    let from_node = graph
        .nodes
        .get_mut(from)
        .ok_or(InvalidEdgeError::InvalidSourceIndex)?;

    if let Some(edge_index) = find_edge_impl(&graph.edges, from_node.next_outgoing_edge, to) {
        if !graph.nodes.contains_key(to) {
            return Err(InvalidEdgeError::InvalidDestIndex.into());
        }

        let old_weight = replace(weight, edge_index, &mut graph.edges)?;

        Ok((edge_index, Some(old_weight)))
    } else {
        let index = insert_edge(&mut graph.nodes.map, &mut graph.edges.map, from, to, weight)?;

        Ok((index, None))
    }
}

fn insert_edge<N, E, NI, EI, NM, EM>(
    nodes: &mut NM,
    edges: &mut EM,
    from: NI,
    to: NI,
    weight: E,
) -> Result<EI, InvalidEdgeError>
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>,
{
    let edge_index = edges.insert(Edge {
        weight,
        from,
        to,
        next_incoming_edge: None,
        next_outgoing_edge: None,
    });

    let next_outgoing_edge = nodes
        .get_mut(from)
        .ok_or_else(|| {
            edges.remove(edge_index);
            InvalidEdgeError::InvalidSourceIndex
        })
        .map(|node| node.next_outgoing_edge.replace(edge_index))?;

    if let Some(node) = nodes.get_mut(to) {
        let next_incoming_edge = node.next_incoming_edge.replace(edge_index);

        let edge = edges.get_mut(edge_index).expect("invalid edge map state");
        edge.next_outgoing_edge = next_outgoing_edge;
        edge.next_incoming_edge = next_incoming_edge;

        Ok(edge_index)
    } else {
        edges.remove(edge_index);
        nodes
            .get_mut(from)
            .expect("invalid node map state")
            .next_outgoing_edge = next_outgoing_edge;

        Err(InvalidEdgeError::InvalidDestIndex)
    }
}

#[cfg(test)]
#[derive(Copy, Clone, Eq, PartialEq, Debug)]
enum EdgeKind {
    Outgoing,
    Incoming,
}

/// A [`Graph`] with immutable structure.
///
/// You can not add/remove nodes/edges from a [`FrozenGraph`], but you can still mutate their
/// weights in case you have a mutable reference to the graph.
///
/// [`Graph`] is effectively a smart pointer into a [`FrozenGraph`] so the conversion is free.
#[derive(Clone, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct FrozenGraph<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>,
{
    nodes: Nodes<N, EI, NM>,
    edges: Edges<E, NI, EI, EM>,
}

impl<N, E, NI, EI, NM, EM> FrozenGraph<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>,
{
    /// Returns an immutable reference to a node by its index or [`None`] if the index is invalid.
    pub fn node(&self, index: NI) -> Option<&Node<N, EI>> {
        self.nodes.get(index)
    }

    /// Returns a mutable reference to a node by its index or [`None`] if the index is invalid.
    pub fn node_mut(&mut self, index: NI) -> Option<&mut Node<N, EI>> {
        self.nodes.get_mut(index)
    }

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

    /// Returns an immutable reference to the weight of a node by its index or `None` in case the
    /// index is not valid.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, ()>::default();
    ///
    /// let node = graph.add_node(1);
    /// assert_eq!(graph.node_weight(node), Some(&1));
    /// ```
    pub fn node_weight(&self, index: NI) -> Option<&N> {
        self.nodes.get(index).map(Node::weight)
    }

    /// Returns a mutable reference to the weight of a node by its index or `None` in case the
    /// index is not valid.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, ()>::default();
    ///
    /// let node = graph.add_node(1);
    /// let weight_mut = graph.node_weight_mut(node).unwrap();
    /// assert_eq!(*weight_mut, 1);
    ///
    /// *weight_mut = 2;
    /// assert_eq!(graph.node_weight(node), Some(&2));
    /// ```
    pub fn node_weight_mut(&mut self, index: NI) -> Option<&mut N> {
        self.nodes.get_mut(index).map(Node::weight_mut)
    }

    /// Returns an immutable reference to an edge by its index or [`None`] if the index is invalid.
    pub fn edge(&self, index: EI) -> Option<&Edge<E, NI, EI>> {
        self.edges.get(index)
    }

    /// Returns a mutable reference to an edge by its index or [`None`] if the index is invalid.
    pub fn edge_mut(&mut self, index: EI) -> Option<&mut Edge<E, NI, EI>> {
        self.edges.get_mut(index)
    }

    /// Returns the current amount of edges in the graph.
    pub fn edges_count(&self) -> usize {
        self.edges.len()
    }

    /// Returns an immutable reference to the weight of a node by its index or `None` in case the
    /// index is not valid.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, i32>::default();
    ///
    /// let from = graph.add_node(1234);
    /// let to = graph.add_node(1234);
    /// let edge = graph.add_edge(4567, from, to).unwrap();
    ///
    /// assert_eq!(graph.edge_weight(edge), Some(&4567));
    /// ```
    ///
    /// # Panics
    /// This function will panic if the provided edge index is not valid.
    pub fn edge_weight(&self, index: EI) -> Option<&E> {
        self.edge(index).map(Edge::weight)
    }

    /// Returns a mutable reference to the weight of an edge by its index.
    ///
    /// # Panics
    /// This function will panic if the provided edge index is not valid.
    pub fn edge_weight_mut(&mut self, index: EI) -> Option<&mut E> {
        self.edge_mut(index).map(Edge::weight_mut)
    }

    /// Given a mutable reference to a graph returns a mutable reference to its [`Nodes`] and an immutable reference to
    /// its [`Edges`].
    ///
    /// This is useful for parallel processing of a graph when its necessary to both mutate nodes and walk over edges.
    #[allow(clippy::type_complexity)]
    pub fn as_nodes_mut_and_edges(&mut self) -> (&mut Nodes<N, EI, NM>, &Edges<E, NI, EI, EM>) {
        (&mut self.nodes, &self.edges)
    }

    /// Given a mutable reference to a graph returns an immutable reference to its [`Nodes`] and a mutable reference to
    /// its [`Edges`].
    ///
    /// This is useful for parallel processing of a graph when its necessary to both mutate edges and walk over nodes.
    #[allow(clippy::type_complexity)]
    pub fn as_nodes_and_edges_mut(&mut self) -> (&Nodes<N, EI, NM>, &mut Edges<E, NI, EI, EM>) {
        (&self.nodes, &mut self.edges)
    }

    /// Given a mutable reference to a graph returns a mutable reference to its [`Nodes`] and a mutable reference to
    /// its [`Edges`].
    ///
    /// This is useful for parallel processing of a graph when its necessary to mutably process both nodes and edges
    /// in parallel somehow.
    #[allow(clippy::type_complexity)]
    pub fn as_nodes_mut_and_edges_mut(
        &mut self,
    ) -> (&mut Nodes<N, EI, NM>, &mut Edges<E, NI, EI, EM>) {
        (&mut self.nodes, &mut self.edges)
    }

    /// Finds an edge from one node to another and returns its index.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, ()>::default();
    ///
    /// let first = graph.add_node(1);
    /// let second = graph.add_node(2);
    /// let edge = graph.add_edge((), first, second).unwrap();
    ///
    /// assert_eq!(graph.find_edge(first, second).unwrap(), Some(edge));
    /// ```
    ///
    /// # Errors
    ///
    /// This function will return an [`InvalidEdgeError`] error in case either the source or the
    /// destination index is not valid which will be indicated by the error's value.
    pub fn find_edge(&self, from: NI, to: NI) -> Result<Option<EI>, InvalidEdgeError> {
        let from_node = self
            .node(from)
            .ok_or(InvalidEdgeError::InvalidSourceIndex)?;
        if !self.nodes.contains_key(to) {
            return Err(InvalidEdgeError::InvalidDestIndex);
        }

        Ok(find_edge_impl(
            &self.edges,
            from_node.next_outgoing_edge,
            to,
        ))
    }

    /// Calls the given closure on each node in the index growth order passing the node's weight as
    /// a parameter until the closure returns true. Returns the index of the node for which the
    /// closure returned true or None in case there was no such node.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<bool, ()>::default();
    /// let false_idx = graph.add_node(false);
    /// let true_idx = graph.add_node(true);
    ///
    /// assert_eq!(graph.find_node(|v| *v), Some(true_idx));
    /// assert_eq!(graph.find_node(|v| !*v), Some(false_idx));
    /// ```
    pub fn find_node<F: FnMut(&N) -> bool>(&self, mut f: F) -> Option<NI> {
        for (i, node) in &self.nodes {
            if f(&node.weight) {
                return Some(i);
            }
        }

        None
    }

    /// Returns an immutable iterator over the weights of nodes in a graph.
    ///
    /// # Order of iteration
    ///
    /// The order of iteration is specified by the iterator type provided by the node map in its
    /// [`Map`] implementation as the [`Map::Iter`] associated type.
    pub fn node_weights(&self) -> iter::NodeWeights<'_, N, NI, EI, NM> {
        iter::NodeWeights {
            inner: self.nodes.iter(),
        }
    }

    /// Returns a mutable iterator over the weights of nodes in a graph.
    ///
    /// # Order of iteration
    ///
    /// The order of iteration is specified by the iterator type provided by the node map in its
    /// [`Map`] implementation as the [`Map::IterMut`] associated type.
    pub fn node_weights_mut(&mut self) -> iter::NodeWeightsMut<'_, N, NI, EI, NM> {
        iter::NodeWeightsMut {
            inner: self.nodes.iter_mut(),
        }
    }

    /// Returns an immutable iterator over the weights of edges in a graph.
    ///
    /// # Order of iteration
    ///
    /// The order of iteration is specified by the iterator type provided by the edge map in its
    /// [`Map`] implementation as the [`Map::Iter`] associated type.
    pub fn edge_weights(&self) -> iter::EdgeWeights<'_, E, NI, EI, EM> {
        iter::EdgeWeights {
            inner: self.edges.iter(),
        }
    }

    /// Returns a mutable iterator over the weights of edges in a graph.
    ///
    /// # Order of iteration
    ///
    /// The order of iteration is specified by the iterator type provided by the edge map in its
    /// [`Map`] implementation as the [`Map::IterMut`] associated type.
    pub fn edge_weights_mut(&mut self) -> iter::EdgeWeightsMut<'_, E, NI, EI, EM> {
        iter::EdgeWeightsMut {
            inner: self.edges.iter_mut(),
        }
    }

    /// Returns an iterator over the outputs of a node.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashMap;
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, i32>::default();
    ///
    /// let entry = graph.add_node(1);
    /// let (left, left_ei) = graph.add_connected_node(2, entry, 22).unwrap();
    /// let (right, right_ei) = graph.add_connected_node(3, entry, 33).unwrap();
    ///
    /// // make a map for expected edge weights
    /// let mut map = HashMap::new();
    /// map.insert(left_ei, 22);
    /// map.insert(right_ei, 33);
    ///
    /// // check that they match what we get from the iterator
    /// for (ei, edge) in graph.outputs(entry) {
    ///     assert_eq!(map.remove(&ei), Some(*edge.weight()));
    /// }
    ///
    /// assert!(map.is_empty());
    /// ```
    pub fn outputs(&self, node_index: NI) -> iter::Outputs<'_, E, NI, EI, EM> {
        let next = self.nodes[node_index].next_outgoing_edge;

        iter::Outputs::new(&self.edges.map, next)
    }

    /// Returns an iterator over the inputs of a node.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashMap;
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, i32>::default();
    ///
    /// let left = graph.add_node(1);
    /// let right = graph.add_node(2);
    /// let exit = graph.add_node(3);
    /// let left_ei = graph.add_edge(11, left, exit).unwrap();
    /// let right_ei = graph.add_edge(22, right, exit).unwrap();
    ///
    /// // make a map for expected edge weights
    /// let mut map = HashMap::new();
    /// map.insert(left_ei, 11);
    /// map.insert(right_ei, 22);
    ///
    /// // check that they match what we get from the iterator
    /// for (ei, edge) in graph.inputs(exit) {
    ///     assert_eq!(map.remove(&ei), Some(*edge.weight()));
    /// }
    ///
    /// assert!(map.is_empty());
    /// ```
    pub fn inputs(&self, node_index: NI) -> iter::Inputs<'_, E, NI, EI, EM> {
        let next = self.nodes[node_index].next_incoming_edge;

        iter::Inputs::new(&self.edges.map, next)
    }

    /// Returns an iterator over successors of a node.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashMap;
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, ()>::default();
    ///
    /// let entry = graph.add_node(1);
    /// let (left, left_ei) = graph.add_connected_node(2, entry, ()).unwrap();
    /// let (right, right_ei) = graph.add_connected_node(3, entry, ()).unwrap();
    ///
    /// // make a map for expected edge weights
    /// let mut map = HashMap::new();
    /// map.insert(left, 2);
    /// map.insert(right, 3);
    ///
    /// // check that they match what we get from the iterator
    /// for (ni, weight) in graph.successors(entry) {
    ///     assert_eq!(map.remove(&ni), Some(*weight));
    /// }
    ///
    /// assert!(map.is_empty());
    /// ```
    pub fn successors(&self, node_index: NI) -> iter::Successors<'_, N, E, NI, EI, NM, EM> {
        let next = self.nodes[node_index].next_outgoing_edge;

        iter::Successors { graph: self, next }
    }

    /// Returns an iterator over predecessors of a node.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashMap;
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, ()>::default();
    ///
    /// let left = graph.add_node(1);
    /// let right = graph.add_node(2);
    /// let exit = graph.add_node(3);
    /// let left_ei = graph.add_edge((), left, exit).unwrap();
    /// let right_ei = graph.add_edge((), right, exit).unwrap();
    ///
    /// // make a map for expected edge weights
    /// let mut map = HashMap::new();
    /// map.insert(left, 1);
    /// map.insert(right, 2);
    ///
    /// // check that they match what we get from the iterator
    /// for (ni, weight) in graph.predecessors(exit) {
    ///     assert_eq!(map.remove(&ni), Some(*weight));
    /// }
    ///
    /// assert!(map.is_empty());
    /// ```
    pub fn predecessors(&self, node_index: NI) -> iter::Predecessors<'_, N, E, NI, EI, NM, EM> {
        let next = self.nodes[node_index].next_incoming_edge;

        iter::Predecessors { graph: self, next }
    }

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

        iter::WalkSuccessors { next }
    }

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

        iter::WalkPredecessors { next }
    }

    /// Returns a walker over the inputs of a node.
    pub fn walk_inputs(&self, node_index: NI) -> iter::WalkInputs<EI> {
        let next = self.nodes[node_index].next_incoming_edge;

        iter::WalkInputs { next }
    }

    /// Returns a walker over the outputs of a node.
    pub fn walk_outputs(&self, node_index: NI) -> iter::WalkOutputs<EI> {
        let next = self.nodes[node_index].next_outgoing_edge;

        iter::WalkOutputs { next }
    }

    /// Converts a [`FrozenGraph`] into a [`Graph`].
    pub fn unfreeze(self) -> Graph<N, E, NI, EI, NM, EM> {
        self.into()
    }

    #[cfg(test)]
    fn is_valid_node_index(&self, index: NI) -> bool {
        self.nodes.contains_key(index)
    }

    #[cfg(test)]
    fn is_valid_edge_index(&self, index: EI) -> bool {
        self.edges.contains_key(index)
    }

    #[cfg(test)]
    fn is_valid_edge_index_or_none(&self, index: Option<EI>) -> bool {
        if let Some(index) = index {
            self.is_valid_edge_index(index)
        } else {
            true
        }
    }

    #[cfg(test)]
    fn validate_edges_list(&self, first_edge_index: Option<EI>, node_index: NI, kind: EdgeKind) {
        assert!(self.is_valid_edge_index_or_none(first_edge_index));

        let mut next_edge_index = first_edge_index;

        while let Some(index) = next_edge_index {
            let edge = self.edges.get(index).unwrap();

            match kind {
                EdgeKind::Outgoing => {
                    next_edge_index = edge.next_outgoing_edge;

                    assert_eq!(edge.from, node_index);
                }
                EdgeKind::Incoming => {
                    next_edge_index = edge.next_incoming_edge;

                    assert_eq!(edge.to, node_index);
                }
            };
        }
    }

    /// Validates the internal structures of the graph.
    #[cfg(test)]
    #[allow(unused)]
    fn validate(&self) {
        for (_, edge) in self.edges.iter() {
            assert!(self.is_valid_edge_index_or_none(edge.next_outgoing_edge));
            assert!(self.is_valid_edge_index_or_none(edge.next_incoming_edge));
            assert!(self.is_valid_node_index(edge.from));
            assert!(self.is_valid_node_index(edge.to));
        }

        for (node_index, node) in self.nodes.iter() {
            self.validate_edges_list(node.next_outgoing_edge, node_index, EdgeKind::Outgoing);
            self.validate_edges_list(node.next_incoming_edge, node_index, EdgeKind::Incoming);
        }
    }
}

impl<N, E, NI, EI, NM, EM> FrozenGraph<N, E, NI, EI, NM, EM>
where
    NI: Copy + Eq + Ord + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: OrderedKeyMap<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
{
    /// 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 nodes_range<R: RangeBounds<NI>>(
        &self,
        range: R,
    ) -> impl DoubleEndedIterator<Item = (NI, &N)> {
        self.nodes.range(range).map(|(k, n)| (k, &n.weight))
    }

    /// Returns a mutable iterator over nodes with indices that fall into the specified range.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::BTreeSlotMapGraph;
    /// # use std::mem;
    /// let mut graph = BTreeSlotMapGraph::<i32, (), i32>::default();
    ///
    /// graph.try_add_node_at_index(1, 111).unwrap();
    /// graph.try_add_node_at_index(2, 222).unwrap();
    /// graph.try_add_node_at_index(3, 333).unwrap();
    ///
    /// let mut iter = graph.nodes_range_mut(2..=3);
    ///
    /// let (index, value) = iter.next().unwrap();
    /// assert_eq!(index, 2);
    /// assert_eq!(mem::replace(value, 223), 222);
    ///
    /// let (index, value) = iter.next().unwrap();
    /// assert_eq!(index, 3);
    /// assert_eq!(mem::replace(value, 334), 333);
    ///
    /// assert!(iter.next().is_none());
    ///
    /// drop(iter);
    ///
    /// assert_eq!(*graph.node_weight(1).unwrap(), 111);
    /// assert_eq!(*graph.node_weight(2).unwrap(), 223);
    /// assert_eq!(*graph.node_weight(3).unwrap(), 334);
    /// ```
    ///
    /// # 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::RangeMut`] associated
    /// type.
    pub fn nodes_range_mut<R: RangeBounds<NI>>(
        &mut self,
        range: R,
    ) -> impl DoubleEndedIterator<Item = (NI, &mut N)> {
        self.nodes.range_mut(range).map(|(k, n)| (k, &mut n.weight))
    }

    /// Returns the index and an immutable reference to the weight of the first node in the graph.
    ///
    /// # Order of nodes
    ///
    /// What node is first is defined by the underlying node map by its implementation of the
    /// [`OrderedKeyMap::first`] method.
    pub fn first_node(&self) -> Option<(NI, &N)> {
        self.nodes.first().map(|(k, v)| (k, &v.weight))
    }

    /// Returns the index and a mutable reference to the weight of the first node in the graph.
    ///
    /// # Order of nodes
    ///
    /// What node is first is defined by the underlying node map by its implementation of the
    /// [`OrderedKeyMap::first_mut`] method.
    pub fn first_node_mut(&mut self) -> Option<(NI, &mut N)> {
        self.nodes.first_mut().map(|(k, v)| (k, &mut v.weight))
    }

    /// Returns the index and an immutable reference to the weight of the first node in the graph.
    ///
    /// # Order of nodes
    ///
    /// What node is last is defined by the underlying node map by its implementation of the
    /// [`OrderedKeyMap::last`] method.
    pub fn last_node(&self) -> Option<(NI, &N)> {
        self.nodes.last().map(|(k, v)| (k, &v.weight))
    }

    /// Returns the index and a mutable reference to the weight of the first node in the graph.
    ///
    /// # Order of nodes
    ///
    /// What node is last is defined by the underlying node map by its implementation of the
    /// [`OrderedKeyMap::last_mut`] method.
    pub fn last_node_mut(&mut self) -> Option<(NI, &mut N)> {
        self.nodes.last_mut().map(|(k, v)| (k, &mut v.weight))
    }
}

#[cfg(feature = "rayon")]
impl<N, E, NI, EI, NM, EM> FrozenGraph<N, E, NI, EI, NM, EM>
where
    N: Send + Sync,
    NI: Copy + Eq + Ord + Send + Sync + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: ParIterMap<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
{
    /// Returns an immutable parallel iterator over the graph's nodes.
    pub fn par_iter_nodes(&self) -> NM::ParIter<'_> {
        self.nodes.par_iter()
    }

    /// Returns a mutable parallel iterator over the graph's nodes.
    pub fn par_iter_nodes_mut(&mut self) -> NM::ParIterMut<'_> {
        self.nodes.par_iter_mut()
    }

    /// Returns an immutable parallel iterator over the graph's nodes' weights.
    pub fn par_iter_node_weights(&self) -> ParNodeWeightIter<NM::ParIter<'_>, NI, EI, N> {
        self.nodes.par_iter_weights()
    }

    /// Returns a mutable parallel iterator over the graph's nodes' weights.
    pub fn par_iter_node_weights_mut(
        &mut self,
    ) -> ParNodeWeightIterMut<NM::ParIterMut<'_>, NI, EI, N> {
        self.nodes.par_iter_weights_mut()
    }
}

#[cfg(feature = "rayon")]
impl<N, E, NI, EI, NM, EM> FrozenGraph<N, E, NI, EI, NM, EM>
where
    E: Send + Sync,
    NI: Copy + Eq + Ord + Send + Sync + Debug + 'static,
    EI: Copy + Eq + Send + Sync + Debug + 'static,
    NM: Map<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + ParIterMap<Edge<E, NI, EI>, Key = EI>,
{
    /// Returns an immutable parallel iterator over the graph's edges.
    pub fn par_iter_edges(&self) -> EM::ParIter<'_> {
        self.edges.par_iter()
    }

    /// Returns a mutable parallel iterator over the graph's edges.
    pub fn par_iter_edges_mut(&mut self) -> EM::ParIterMut<'_> {
        self.edges.par_iter_mut()
    }

    /// Returns an immutable parallel iterator over the graph's edges' weights.
    pub fn par_iter_edge_weights(&self) -> ParMap<EM::ParIter<'_>, EdgeMapFn<NI, EI, E>> {
        self.edges.par_iter_weights()
    }

    /// Returns a mutable parallel iterator over the graph's edges' weights.
    pub fn par_iter_edge_weights_mut(
        &mut self,
    ) -> ParMap<EM::ParIterMut<'_>, EdgeMapMutFn<NI, EI, E>> {
        self.edges.par_iter_weights_mut()
    }
}

impl<N, E, NI, EI, NM, EM> Default for FrozenGraph<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>,
{
    fn default() -> Self {
        FrozenGraph {
            nodes: Nodes::default(),
            edges: Edges::default(),
        }
    }
}

impl<N, E, NI, EI, NM, EM> From<Graph<N, E, NI, EI, NM, EM>> for FrozenGraph<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>,
{
    fn from(value: Graph<N, E, NI, EI, NM, EM>) -> Self {
        value.inner
    }
}

/// A directed graph backed by two generic maps.
#[derive(Clone, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct 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>,
{
    inner: FrozenGraph<N, E, NI, EI, NM, EM>,
}

impl<N, E, NI, EI, NM, EM> Default for 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>,
{
    fn default() -> Self {
        Self {
            inner: FrozenGraph::default(),
        }
    }
}

impl<N, E, NI, EI, NM, EM> Graph<N, E, NI, EI, NM, EM>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: MapWithCapacity<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + MapWithCapacity<Edge<E, NI, EI>, Key = EI>,
{
    /// Creates a new [`Graph`] and preallocates space for the specified number of nodes and edges.
    #[must_use]
    pub fn with_capacities(nodes_capacity: usize, edges_capacity: usize) -> Self {
        Graph {
            inner: FrozenGraph {
                nodes: Nodes::with_capacity(nodes_capacity),
                edges: Edges::with_capacity(edges_capacity),
            },
        }
    }
}

impl<N, E, NI, EI, NM, EM> 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>,
{
    /// Removes all nodes and edges from the graph.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, ()>::default();
    ///
    /// // Create two nodes and add an edge between them.
    /// let first = graph.add_node(1);
    /// let second = graph.add_node(2);
    /// graph.add_edge((), first, second).unwrap();
    ///
    /// assert_eq!(graph.nodes_count(), 2);
    /// assert_eq!(graph.edges_count(), 1);
    ///
    /// // Clear the graph.
    /// graph.clear();
    ///
    /// assert_eq!(graph.nodes_count(), 0);
    /// assert_eq!(graph.edges_count(), 0);
    /// ```
    pub fn clear(&mut self) {
        self.nodes.map.clear();
        self.edges.map.clear();
    }

    /// Adds an edge from one node to another.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, ()>::default();
    ///
    /// let first = graph.add_node(1);
    /// let second = graph.add_node(2);
    /// let edge = graph.add_edge((), first, second).unwrap();
    ///
    /// // Adding an edge between the same two nodes again will cause an error.
    /// assert!(matches!(graph.add_edge((), first, second), Err(_)));
    /// ```
    ///
    /// # Errors
    ///
    /// Returns [`AddEdgeError`] in case either source index or destination index is invalid or an
    /// edge between the two nodes exists.
    ///
    /// # Panics
    ///
    /// This function will only panic when the underlying edge map's [`IntKeyMap::insert`] panics.
    pub fn add_edge(&mut self, weight: E, from: NI, to: NI) -> Result<EI, AddEdgeError> {
        insert_edge_impl(&mut self.inner, from, to, weight, |_, _, _| {
            Err(AddEdgeError::EdgeExists)
        })
        .map(|(index, _)| index)
    }

    /// Adds an edge from one node to another retrieving its weight by calling a closure with the
    /// index allocated for the edge.
    ///
    /// # Errors
    ///
    /// Returns [`AddEdgeError`] in case either source index or destination index is invalid or an
    /// edge between the two nodes exists.
    ///
    /// # Panics
    ///
    /// This function will only panic when the underlying edge map's [`IntKeyMap::insert_with_key`]
    /// panics.
    pub fn add_edge_with_index<F: FnOnce(EI) -> E>(
        &mut self,
        from: NI,
        to: NI,
        f: F,
    ) -> Result<EI, AddEdgeError> {
        let (nodes, edges) = self.as_nodes_mut_and_edges_mut();

        if !nodes.contains_key(to) {
            return Err(InvalidEdgeError::InvalidDestIndex.into());
        }

        let from_node = nodes
            .get_mut(from)
            .ok_or(InvalidEdgeError::InvalidSourceIndex)?;

        if find_edge_impl(edges, from_node.next_outgoing_edge, to).is_some() {
            Err(AddEdgeError::EdgeExists)
        } else {
            let index = edges.map.insert_with_key(|index| {
                let next_outgoing_edge = from_node.next_outgoing_edge.replace(index);

                Edge {
                    weight: f(index),
                    from,
                    to,
                    next_incoming_edge: None,
                    next_outgoing_edge,
                }
            });

            let to_node = nodes.get_mut(to).expect("invalid node map state");
            let next_incoming_edge = to_node.next_incoming_edge.replace(index);

            let edge = &mut self.edges[index];
            edge.next_incoming_edge = next_incoming_edge;

            Ok(index)
        }
    }

    /// Either inserts an edge between two nodes or replaces its weight in case the edge exists.
    /// Returns the edge's index and the old weight value if any.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, &str>::default();
    ///
    /// let first = graph.add_node(1);
    /// let second = graph.add_node(2);
    ///
    /// // Initially no edge exists between the first and the second nodes so old_weight will be
    /// // None.
    /// let (edge, old_weight) = graph.replace_edge("foo", first, second).unwrap();
    /// assert!(old_weight.is_none());
    ///
    /// // Adding an edge between the same two nodes again will replace its weight and return the
    /// // old one. The returned edge index will we the same as before.
    /// let (same_edge, old_weight) = graph.replace_edge("bar", first, second).unwrap();
    /// assert_eq!(old_weight, Some("foo"));
    /// assert_eq!(graph.edge_weight(edge).copied(), Some("bar"));
    /// assert_eq!(same_edge, edge);
    /// ```
    ///
    /// # Errors
    ///
    /// Returns [`InvalidEdgeError`] error in case either the source or the destination index is not valid.
    ///
    /// # Panics
    ///
    /// This function will only panic when the underlying edge map's [`IntKeyMap`] implementation
    /// panics.
    pub fn replace_edge(
        &mut self,
        weight: E,
        from: NI,
        to: NI,
    ) -> Result<(EI, Option<E>), InvalidEdgeError> {
        insert_edge_impl(
            &mut self.inner,
            from,
            to,
            weight,
            |weight, edge_index, edges| Ok(mem::replace(&mut edges[edge_index].weight, weight)),
        )
    }

    /// Removes a disconnected node from the graph.
    ///
    /// # Errors
    ///
    /// Returns a [`RemoveNodeError`] in case the node is still connected when being removed.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::SlotMapGraph;
    /// # use mapgraph::error::RemoveNodeError;
    /// let mut graph = SlotMapGraph::<i32, ()>::default();
    ///
    /// let first = graph.add_node(1);
    /// let second = graph.add_node(2);
    /// let edge = graph.add_edge((), first, second).unwrap();
    ///
    /// // Both nodes are connected by an edge so removing either one fails.
    /// assert!(graph.remove_node(first).is_err());
    /// assert!(graph.remove_node(second).is_err());
    ///
    /// graph.remove_edge(edge);
    ///
    /// // Now both nodes are disconnected so removing them is ok.
    /// assert_eq!(graph.remove_node(first), Ok(Some(1)));
    /// assert_eq!(graph.remove_node(second), Ok(Some(2)));
    ///
    /// // Removing the edges for the second time will cause None to be returned.
    /// assert_eq!(graph.remove_node(first), Ok(None));
    /// assert_eq!(graph.remove_node(second), Ok(None));
    /// ```
    #[allow(clippy::missing_panics_doc)]
    pub fn remove_node(&mut self, index: NI) -> Result<Option<N>, RemoveNodeError> {
        let Some(node) = self.nodes.get(index) else {
            return Ok(None);
        };

        if node.next_outgoing_edge.is_none() && node.next_incoming_edge.is_none() {
            Ok(Some(
                self.nodes
                    .map
                    .remove(index)
                    .expect("node should exist")
                    .weight,
            ))
        } else {
            Err(RemoveNodeError)
        }
    }

    /// Removes a node and all its outgoing and incoming edges from the graph.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, i32>::default();
    ///
    /// let first = graph.add_node(1);
    /// let second = graph.add_node(2);
    /// let third = graph.add_node(3);
    ///
    /// let first_edge = graph.add_edge(1, first, second).unwrap();
    /// let second_edge = graph.add_edge(2, second, third).unwrap();
    /// let third_edge = graph.add_edge(3, third, first).unwrap();
    ///
    /// // Removing the first node also removes the first and the third edges.
    /// assert_eq!(graph.unlink_and_remove_node(first), Some(1));
    ///
    /// // Removing the second node also removes the second edge.
    /// assert_eq!(graph.unlink_and_remove_node(second), Some(2));
    /// ```
    #[allow(clippy::missing_panics_doc)]
    pub fn unlink_and_remove_node(&mut self, index: NI) -> Option<N> {
        // remove outgoing edges using the linked list
        let removed_node = self.nodes.get(index)?;
        let next_outgoing_edge = removed_node.next_outgoing_edge;
        let next_incoming_edge = removed_node.next_incoming_edge;

        let outgoing_edges = iter::DrainOutgoingEdges {
            graph: self,
            next_edge_index: next_outgoing_edge,
        };
        for _ in outgoing_edges {}

        let incoming_edges = iter::DrainIncomingEdges {
            graph: self,
            next_edge_index: next_incoming_edge,
        };
        for _ in incoming_edges {}

        Some(
            self.nodes
                .map
                .remove(index)
                .expect("node should exist")
                .weight,
        )
    }

    /// Unlinks an edge from its outgoing edges list.
    fn unlink_edge_from_outgoing_list(&mut self, index: EI, edge: &Edge<E, NI, EI>) {
        let node = self
            .nodes
            .get_mut(edge.from)
            .expect("invalid source node index");

        if node.next_outgoing_edge == Some(index) {
            node.next_outgoing_edge = edge.next_outgoing_edge;
        } else {
            let mut next = node.next_outgoing_edge;
            while let Some(next_index) = next {
                let next_edge = self
                    .edges
                    .get_mut(next_index)
                    .expect("invalid edge index in outgoing edges list");

                next = next_edge.next_outgoing_edge;
                if next == Some(index) {
                    next_edge.next_outgoing_edge = edge.next_outgoing_edge;
                    break;
                }
            }

            if next != Some(index) {
                unreachable!("an edge wasn't found in its outgoing edges list");
            }
        }
    }

    fn unlink_edge_from_incoming_list(&mut self, index: EI, edge: &Edge<E, NI, EI>) {
        let node = self
            .nodes
            .get_mut(edge.to)
            .expect("invalid destination node index");

        if node.next_incoming_edge == Some(index) {
            node.next_incoming_edge = edge.next_incoming_edge;
        } else {
            let mut next = node.next_incoming_edge;
            while let Some(next_index) = next {
                let next_edge = self
                    .edges
                    .get_mut(next_index)
                    .expect("invalid edge index in incoming edges list");

                next = next_edge.next_incoming_edge;
                if next == Some(index) {
                    next_edge.next_incoming_edge = edge.next_incoming_edge;
                    break;
                }
            }

            if next != Some(index) {
                unreachable!("an edge wasn't found in its incoming edges list");
            }
        }
    }

    /// Removes an edge from the graph.
    ///
    /// # Example
    ///
    /// ```
    /// # use mapgraph::aliases::SlotMapGraph;
    /// let mut graph = SlotMapGraph::<i32, i32>::default();
    ///
    /// let first = graph.add_node(1);
    /// let second = graph.add_node(2);
    /// let third = graph.add_node(3);
    ///
    /// let first_edge = graph.add_edge(1, first, second).unwrap();
    /// let second_edge = graph.add_edge(2, first, third).unwrap();
    ///
    /// // Removing the first edge doesn't affect the second edge.
    /// assert_eq!(graph.remove_edge(first_edge), Some(1));
    /// assert_eq!(graph.find_edge(first, third).unwrap(), Some(second_edge));
    /// ```
    pub fn remove_edge(&mut self, index: EI) -> Option<E> {
        let removed_edge = self.edges.map.remove(index)?;

        self.unlink_edge_from_outgoing_list(index, &removed_edge);
        self.unlink_edge_from_incoming_list(index, &removed_edge);

        Some(removed_edge.weight)
    }

    /// Returns an iterator draining the outgoing edges of a node.
    ///
    /// # Panics
    ///
    /// This function will panic in case the provided node index is not valid.
    pub fn drain_outgoing_edges(
        &mut self,
        node_index: NI,
    ) -> iter::DrainOutgoingEdges<'_, N, E, NI, EI, NM, EM> {
        let (nodes, edges) = self.as_nodes_mut_and_edges();
        let node = &mut nodes[node_index];
        let next_edge_index = node.next_outgoing_edge.take();
        if let Some(ei) = next_edge_index {
            node.next_outgoing_edge = edges[ei].next_outgoing_edge;
        }

        iter::DrainOutgoingEdges {
            graph: self,
            next_edge_index,
        }
    }

    /// Returns an iterator draining the incoming edges of a node.
    ///
    /// # Panics
    ///
    /// This function will panic in case the provided node index is not valid.
    pub fn drain_incoming_edges(
        &mut self,
        node_index: NI,
    ) -> iter::DrainIncomingEdges<'_, N, E, NI, EI, NM, EM> {
        let (nodes, edges) = self.as_nodes_mut_and_edges();
        let node = &mut nodes[node_index];
        let next_edge_index = node.next_incoming_edge.take();
        if let Some(ei) = next_edge_index {
            node.next_incoming_edge = edges[ei].next_incoming_edge;
        }

        iter::DrainIncomingEdges {
            graph: self,
            next_edge_index,
        }
    }

    /// Converts a [`Graph`] into a [`FrozenGraph`].
    pub fn freeze(self) -> FrozenGraph<N, E, NI, EI, NM, EM> {
        self.into()
    }
}

impl<N, E, NI, EI, NM, EM> Graph<N, E, NI, EI, NM, EM>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: MapWithCapacity<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
{
    /// Allocates space for at least `additional` nodes.
    pub fn reserve_nodes(&mut self, additional: usize) {
        self.inner.nodes.map.reserve(additional)
    }
}

impl<N, E, NI, EI, NM, EM> 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> + MapWithCapacity<Edge<E, NI, EI>, Key = EI>,
{
    /// Allocates space for at least `additional` edges.
    pub fn reserve_edges(&mut self, additional: usize) {
        self.inner.edges.map.reserve(additional)
    }
}

impl<N, E, NI, EI, NM, EM> Graph<N, E, NI, EI, NM, EM>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: IntKeyMap<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
{
    /// Adds a node to the graph.
    pub fn add_node(&mut self, weight: N) -> NI {
        self.nodes.map.insert(Node {
            weight,
            next_incoming_edge: None,
            next_outgoing_edge: None,
        })
    }

    /// Adds a node to the graph and an incoming branch to it from another node.
    ///
    /// # Errors
    ///
    /// Returns [`InvalidEdgeError::InvalidSourceIndex`] in case the source node index is invalid.
    #[allow(clippy::missing_panics_doc)]
    pub fn add_connected_node(
        &mut self,
        node_weight: N,
        from: NI,
        edge_weight: E,
    ) -> Result<(NI, EI), InvalidEdgeError> {
        if !self.nodes.contains_key(from) {
            return Err(InvalidEdgeError::InvalidSourceIndex);
        }

        let to = self.nodes.map.insert(Node {
            weight: node_weight,
            next_incoming_edge: None,
            next_outgoing_edge: None,
        });

        let edge_index = insert_edge(
            &mut self.inner.nodes.map,
            &mut self.inner.edges.map,
            from,
            to,
            edge_weight,
        )
        .expect("all error conditions should have been prevented");

        Ok((to, edge_index))
    }

    /// Adds a node to the graph.
    ///
    /// This function calls a closure to produce the node's weight. The closure receives the key
    /// for the created node.
    pub fn add_node_with_key<F: FnOnce(NM::Key) -> N>(&mut self, f: F) -> NI {
        self.nodes.map.insert_with_key(|key| Node {
            weight: f(key),
            next_incoming_edge: None,
            next_outgoing_edge: None,
        })
    }

    /// Moves all outgoing edges of an existing node to a new node.
    ///
    /// The weight for the new node is provided by a `splitter` closure that receives a mutable
    /// reference to the weight of the original node. The returned value is the index of the new node.
    ///
    /// # Panics
    ///
    /// This function will panic in case the provided node index is not valid, the `splitter`
    /// closure panics or the node map's [`IntKeyMap::insert`] implementation panics.
    pub fn split_node<F: FnOnce(&mut N) -> N>(&mut self, index: NI, splitter: F) -> NI {
        let node = &mut self.nodes[index];
        let mut next_outgoing_edge = node.next_outgoing_edge.take();

        let new_weight = splitter(&mut node.weight);

        let new_node_index = self.nodes.map.insert(Node {
            weight: new_weight,
            next_incoming_edge: None,
            next_outgoing_edge,
        });

        while let Some(edge_index) = next_outgoing_edge {
            let edge = self.edge_mut(edge_index).expect("corrupt edge list");
            edge.from = new_node_index;
            next_outgoing_edge = edge.next_outgoing_edge;
        }

        new_node_index
    }
}

impl<N, E, NI, EI, NM, EM> Graph<N, E, NI, EI, NM, EM>
where
    N: Default,
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: IntKeyMap<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
{
    /// Adds a node to the graph.
    pub fn add_default_node(&mut self) -> NI {
        self.nodes.map.insert(Node {
            weight: Default::default(),
            next_incoming_edge: None,
            next_outgoing_edge: None,
        })
    }
}

impl<N, E, NI, EI, NM, EM> Graph<N, E, NI, EI, NM, EM>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: ExtKeyMap<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
{
    /// Tries to add a node to a graph at the specified index and returns an error in case a node
    /// with this index already exists.
    ///
    /// # Errors
    ///
    /// Returns [`NodeExistsError`] in case a node with the specified index exists in the graph.
    pub fn try_add_node_at_index(
        &mut self,
        index: NM::Key,
        weight: N,
    ) -> Result<(), NodeExistsError> {
        self.nodes
            .map
            .try_insert(
                index,
                Node {
                    weight,
                    next_incoming_edge: None,
                    next_outgoing_edge: None,
                },
            )
            .map_err(|_| NodeExistsError(()))
    }

    /// Moves all outgoing edges of an existing node to a new node. The weight for the new node is
    /// provided by a `splitter` closure that receives a mutable reference to the weight of the
    /// original node.
    ///
    /// # Example
    ///
    /// ```
    /// use mapgraph::aliases::HashSlotMapGraph;
    ///
    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
    /// let mut graph = HashSlotMapGraph::<i32, (), &'static str>::default();
    ///
    /// graph.try_add_node_at_index("start", 1)?;
    /// graph.try_add_node_at_index("end", 3)?;
    ///
    /// // add an edge between start and end nodes
    /// let ei = graph.add_edge((), "start", "end")?;
    ///
    /// // insert a middle node
    /// graph.try_split_node_at_index("start", "middle", |weight| *weight + 1)?;
    ///
    /// let start_outputs: Vec<_> = graph.outputs("start").map(|(ei, _)| ei).collect();
    /// let middle_outputs: Vec<_> = graph.outputs("middle").map(|(ei, _)| ei).collect();
    ///
    /// assert_eq!(graph.node_weight("middle").copied(), Some(2));
    /// assert_eq!(&start_outputs, &[]);
    /// assert_eq!(&middle_outputs, &[ei]);
    /// # Ok(())
    /// # }
    /// ```
    ///
    /// # Errors
    ///
    /// Returns [`NodeExistsError`] in case a node already exists at the `new_index`.
    ///
    /// # Panics
    ///
    /// This function will panic in case the provided node index is not valid, the `splitter`
    /// closure panics or the node map's [`IntKeyMap::insert`] implementation panics.
    pub fn try_split_node_at_index<F>(
        &mut self,
        index: NI,
        new_index: NI,
        splitter: F,
    ) -> Result<(), NodeExistsError>
    where
        F: FnOnce(&mut N) -> N,
    {
        let node = &mut self.nodes[index];
        let mut next_outgoing_edge = node.next_outgoing_edge.take();

        let new_weight = splitter(&mut node.weight);

        let result = self.nodes.map.try_insert(
            new_index,
            Node {
                weight: new_weight,
                next_incoming_edge: None,
                next_outgoing_edge,
            },
        );

        // we need to restore the edges liked list on error
        if result.is_err() {
            self.nodes[index].next_outgoing_edge = next_outgoing_edge;
            return Err(NodeExistsError(()));
        }

        while let Some(edge_index) = next_outgoing_edge {
            let edge = self.edge_mut(edge_index).expect("corrupt edge list");
            debug_assert_eq!(edge.from, index);
            edge.from = new_index;
            next_outgoing_edge = edge.next_outgoing_edge;
        }

        Ok(())
    }
}

impl<N, E, NI, EI, NM, EM> Deref for 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 Target = FrozenGraph<N, E, NI, EI, NM, EM>;

    fn deref(&self) -> &Self::Target {
        &self.inner
    }
}

impl<N, E, NI, EI, NM, EM> DerefMut for 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>,
{
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.inner
    }
}

impl<N, E, NI, EI, NM, EM> From<FrozenGraph<N, E, NI, EI, NM, EM>> for 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>,
{
    fn from(value: FrozenGraph<N, E, NI, EI, NM, EM>) -> Self {
        Graph { inner: value }
    }
}

impl<N, E, NI, EI, NM, EM> AsRef<FrozenGraph<N, E, NI, EI, NM, EM>> for 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>,
{
    fn as_ref(&self) -> &FrozenGraph<N, E, NI, EI, NM, EM> {
        self
    }
}

impl<N, E, NI, EI, NM, EM> AsMut<FrozenGraph<N, E, NI, EI, NM, EM>> for 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>,
{
    fn as_mut(&mut self) -> &mut FrozenGraph<N, E, NI, EI, NM, EM> {
        self
    }
}

impl<N, E, NI, EI, NM, EM> Borrow<FrozenGraph<N, E, NI, EI, NM, EM>> for 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>,
{
    fn borrow(&self) -> &FrozenGraph<N, E, NI, EI, NM, EM> {
        self
    }
}

impl<N, E, NI, EI, NM, EM> BorrowMut<FrozenGraph<N, E, NI, EI, NM, EM>>
    for 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>,
{
    fn borrow_mut(&mut self) -> &mut FrozenGraph<N, E, NI, EI, NM, EM> {
        self
    }
}

mod edges;
pub mod entry;
pub mod iter;
mod nodes;

pub use edges::Edges;
pub use nodes::Nodes;

impl<N, E, NI, EI, NM, EM> Graph<N, E, NI, EI, NM, EM>
where
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: MapWithEntry<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
{
    /// Returns an [`Entry`] for a node at the specified index.
    pub fn node_entry(&mut self, node_index: NI) -> Entry<'_, N, NI, EI, NM> {
        match self.inner.nodes.map.entry(node_index) {
            MapEntry::Vacant(entry) => Entry::Vacant(VacantEntry { entry }),
            MapEntry::Occupied(entry) => Entry::Occupied(OccupiedEntry { entry }),
        }
    }
}

#[cfg(all(test, feature = "alloc", feature = "slotmap"))]
mod tests;