intrex 0.1.1

//! Immutable linked list accessor.
use super::*;

/// Borrow the [`Link`] for `$index`. Panics if
/// [`ListAccessor::map_link`] returns `None`.
macro_rules! link {
    ($accessor:expr, $index:expr) => {
        ($accessor.map_link)($accessor.pool.index($index))
            .as_ref()
            .unwrap()
    };
}

mod formatting;
mod iter;

pub use iter::*;

/// A storage for elements.
///
/// This is automatically implemented for all types implementing [`ops::Index`].
pub trait Pool<Index> {
    /// The element type.
    type Element: ?Sized;

    /// Borrow the element at index `index`.
    fn index(&self, index: Index) -> &Self::Element;
}

impl<T, Index> Pool<Index> for T
where
    T: ?Sized + ops::Index<Index>,
{
    type Element = <Self as ops::Index<Index>>::Output;

    #[inline]
    fn index(&self, index: Index) -> &Self::Element {
        ops::Index::index(self, index)
    }
}

impl<Index> Head<Index> {
    /// Construct an accessor to the list.
    ///
    /// Created by [`Head::accessor`].
    #[inline]
    pub fn accessor<'head, 'pool, Pool, MapLink, Element>(
        &'head self,
        pool: &'pool Pool,
        map_link: MapLink,
    ) -> ListAccessor<'head, 'pool, Index, Pool, MapLink>
    where
        Pool: 'pool + ops::Index<Index, Output = Element>,
        MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
        Element: 'pool,
        Index: 'pool,
    {
        ListAccessor {
            head: self,
            pool,
            map_link,
        }
    }
}

/// Accessor to a linked list.
#[derive(Debug)]
pub struct ListAccessor<'head, 'pool, Index, Pool: ?Sized, MapLink> {
    head: &'head Head<Index>,
    pool: &'pool Pool,
    map_link: MapLink,
}

impl<'head, 'pool, Index, Pool, MapLink: Clone> Clone
    for ListAccessor<'head, 'pool, Index, Pool, MapLink>
{
    #[inline]
    fn clone(&self) -> Self {
        Self {
            head: self.head,
            pool: self.pool,
            map_link: self.map_link.clone(),
        }
    }
}

impl<'head, 'pool, Index, Pool, MapLink: Copy> Copy
    for ListAccessor<'head, 'pool, Index, Pool, MapLink>
{
}

impl<'head, 'pool, Index, Pool, MapLink, Element> ListAccessor<'head, 'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + self::Pool<Index, Element = Element>,
    MapLink: Fn(&'pool Element) -> &'pool Option<Link<Index>>,
    Element: 'pool,
    Index: PartialEq + Clone + 'pool,
{
    /// Borrow the list header.
    #[inline]
    pub fn head(&self) -> &'head Head<Index> {
        self.head
    }

    /// Borrow the element pool.
    #[inline]
    pub fn pool(&self) -> &'pool Pool {
        self.pool
    }

    /// 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<&'pool Element> {
        if let Some(p) = self.front_index() {
            Some(self.pool.index(p))
        } else {
            None
        }
    }

    /// Borrow the last element.
    #[doc(alias = "last")]
    #[inline]
    pub fn back(&self) -> Option<&'pool Element> {
        if let Some(p) = self.back_index() {
            Some(self.pool.index(p))
        } else {
            None
        }
    }

    /// 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<(), impl core::error::Error + use<Index, Pool, MapLink, Element>>
    where
        Index: core::fmt::Debug,
    {
        let Some(first) = &self.head.first else {
            return Ok(());
        };

        #[derive(thiserror::Error, Debug)]
        enum Error<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),
        }

        let mut current = first.clone();
        loop {
            let link = (self.map_link)(self.pool.index(current.clone()))
                .as_ref()
                .ok_or_else(|| Error::LinkNone(current.clone()))?;
            let next_link = (self.map_link)(self.pool.index(link.next.clone()))
                .as_ref()
                .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(())
    }
}