intrex 0.2.0

//! Immutable linked list accessor.
use crate::node_data::{NodesDataLend, NodesDataLendGat};

use super::*;

/// Clone the [`Link`] for `$index`. Panics if
/// [`NodesLink::expect_node_link`] returns `None`.
macro_rules! link {
    ($accessor:expr, $index:expr) => {
        $accessor.nodes.expect_node_link($index)
    };
}

mod formatting;
mod iter;

pub use iter::*;

/// Provides the hidden error type for [`ListAccessor::validate`].
// FIXME: Replace the return type with RPIT when `precise_capturing_of_types` is
// stabilized (rust-lang/rust#130043)
mod validate_error {
    #[derive(thiserror::Error, Debug)]
    pub enum OpaqueError<Index: core::fmt::Debug> {
        #[error("`map_link` returned `None` for element at {0:?}")]
        LinkNone(Index),
        #[error(
            "element {0:?} says the next element is {1:?}, but \
            element {1:?} says the previous element is {2:?}"
        )]
        LinkInconsistent(Index, Index, Index),
    }
}

impl<Index> Head<Index> {
    /// Create an accessor to the list, using `Nodes: `[`NodesLink`] to access
    /// nodes.
    #[inline]
    pub fn read<Nodes>(&self, nodes: Nodes) -> ListAccessor<'_, Nodes, Index>
    where
        Nodes: NodesLink<Index>,
    {
        ListAccessor { head: self, nodes }
    }

    /// Create an accessor to the list, using an indexable pool (providing
    /// references to nodes) and a closure to borrow the [`Link`] from a given
    /// node.
    #[inline]
    pub fn read_ref<'pool, Pool, MapLink, Element>(
        &self,
        pool: &'pool Pool,
        map_link: MapLink,
    ) -> ListAccessor<'_, NodesWithMapLink<'pool, Pool, MapLink>, Index>
    where
        Pool: ?Sized + core::ops::Index<Index, Output = Element>,
        MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
        Element: 'pool,
        Index: 'pool + Clone,
    {
        self.read(NodesWithMapLink { pool, map_link })
    }
}

/// Accessor to a linked list.
#[derive(Debug)]
pub struct ListAccessor<'head, Nodes, Index> {
    head: &'head Head<Index>,
    nodes: Nodes,
}

impl<'head, Nodes, Index> Clone for ListAccessor<'head, Nodes, Index>
where
    Nodes: Clone,
{
    #[inline]
    fn clone(&self) -> Self {
        ListAccessor {
            head: self.head,
            nodes: self.nodes.clone(),
        }
    }
}

impl<'head, Nodes, Index> Copy for ListAccessor<'head, Nodes, Index> where Nodes: Copy {}

impl<'head, Nodes, Index> ListAccessor<'head, Nodes, Index>
where
    Nodes: NodesLink<Index>,
    Index: PartialEq + Clone,
{
    /// Borrow the node accessor.
    #[inline]
    pub fn nodes(&self) -> &Nodes {
        &self.nodes
    }

    /// Mutably borrow the node accessor.
    #[inline]
    pub fn nodes_mut(&mut self) -> &mut Nodes {
        &mut self.nodes
    }

    /// Borrow the list header.
    #[inline]
    pub fn head(&self) -> &'head Head<Index> {
        self.head
    }

    /// Check if the list is empty.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.head.is_empty()
    }

    /// Get the first element's index.
    #[inline]
    pub fn front_index(&self) -> Option<Index> {
        self.head.first.clone()
    }

    /// Get the last element's index.
    #[inline]
    pub fn back_index(&self) -> Option<Index> {
        self.head.first.clone().map(|p| link!(self, p).prev.clone())
    }

    /// Borrow the first element.
    #[doc(alias = "first")]
    #[inline]
    pub fn front(&self) -> Option<<Nodes as NodesDataLendGat<'_, Index>>::Data>
    where
        Nodes: NodesDataLend<Index>,
    {
        self.front_index().map(|p| self.nodes.node_data_lend(p))
    }

    /// Borrow the last element.
    #[doc(alias = "last")]
    #[inline]
    pub fn back(&self) -> Option<<Nodes as NodesDataLendGat<'_, Index>>::Data>
    where
        Nodes: NodesDataLend<Index>,
    {
        self.back_index().map(|p| self.nodes.node_data_lend(p))
    }

    /// Find the next element of the element at index `i`.
    #[inline]
    pub fn next_index(&self, i: Index) -> Option<Index> {
        Some(link!(self, i).next.clone()).filter(|i| *i != *self.head.first.as_ref().unwrap())
    }

    /// Find the previous element of the element at index `i`.
    #[inline]
    pub fn prev_index(&self, i: Index) -> Option<Index> {
        (i != *self.head.first.as_ref().unwrap()).then(|| link!(self, i).prev.clone())
    }

    /// Check integrity of the linked list structure.
    #[track_caller]
    pub fn validate(&self) -> Result<(), validate_error::OpaqueError<Index>>
    where
        Index: core::fmt::Debug,
    {
        use validate_error::OpaqueError as Error;

        let Some(first) = &self.head.first else {
            return Ok(());
        };

        let mut current = first.clone();
        loop {
            let link = self
                .nodes
                .node_link(current.clone())
                .ok_or_else(|| Error::LinkNone(current.clone()))?;
            let next_link = self
                .nodes
                .node_link(link.next.clone())
                .ok_or_else(|| Error::LinkNone(link.next.clone()))?;
            if current != next_link.prev {
                return Err(Error::LinkInconsistent(
                    current,
                    link.next.clone(),
                    next_link.prev.clone(),
                ));
            }
            if link.next == *first {
                break;
            } else {
                current = link.next.clone();
            }
        }

        Ok(())
    }
}