jimtcl 0.6.0-alpha1

//! Simple cons-cell list.

use std::rc::Rc;

/// Cons-cell singly-linked list.
#[derive(Clone)]
#[repr(transparent)]
pub struct ConsList<T> {
    head: Rc<ConsCell<T>>,
}

/// Individual cell in a singly-linked cons list.
#[derive(Clone, Default)]
pub enum ConsCell<T> {
    #[default]
    Tail,
    Entry(T, Rc<ConsCell<T>>),
}

impl<T> ConsList<T> {
    /// Create a new, empty cons list.
    pub fn new() -> Self {
        Self::default()
    }

    /// Query whether this cons list is empty.
    pub fn is_empty(&self) -> bool {
        self.head.is_empty()
    }

    /// Get the cons list's cell.
    pub fn cell(&self) -> &ConsCell<T> {
        &self.head
    }

    /// Iterate the cons list.
    pub fn iter(&self) -> impl Iterator<Item = &T> {
        ConsListIter { head: &self.head }
    }

    /// Prepend to this list.
    pub fn prepend(&self, value: T) -> ConsList<T> {
        let head = self.head.prepend(value);
        ConsList { head }
    }

    /// Get the first element of this cons list, if nonempty.
    pub fn first(&self) -> Option<&T> {
        match &*self.head {
            ConsCell::Tail => None,
            ConsCell::Entry(val, _) => Some(val),
        }
    }

    /// Get the rest of this cons list, if nonempty.
    pub fn rest(&self) -> ConsList<T> {
        match &*self.head {
            ConsCell::Tail => ConsList::new(),
            ConsCell::Entry(_, rest) => ConsList { head: rest.clone() },
        }
    }
}

impl<'list, T: 'list> IntoIterator for &'list ConsList<T> {
    type Item = &'list T;
    type IntoIter = ConsListIter<'list, T>;

    fn into_iter(self) -> Self::IntoIter {
        ConsListIter { head: &self.head }
    }
}

impl<T> FromIterator<T> for ConsList<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let work: Vec<_> = iter.into_iter().collect();
        let mut head = Rc::new(ConsCell::Tail);
        for item in work.into_iter().rev() {
            head = head.prepend(item);
        }
        ConsList { head }
    }
}

impl<T> Default for ConsList<T> {
    fn default() -> Self {
        ConsList {
            head: Default::default(),
        }
    }
}

impl<T> ConsCell<T> {
    pub fn is_empty(&self) -> bool {
        matches!(self, ConsCell::Tail)
    }

    pub fn iter(&self) -> impl Iterator<Item = &T> {
        ConsListIter { head: self }
    }

    pub fn prepend(self: &Rc<Self>, value: T) -> Rc<Self> {
        let new = ConsCell::Entry(value, self.clone());
        Rc::new(new)
    }
}

impl<'a, T> From<&'a [T]> for ConsList<&'a T> {
    fn from(value: &'a [T]) -> Self {
        let mut result = ConsList::default();
        for v in value.iter().rev() {
            result = result.prepend(v);
        }
        result
    }
}

pub struct ConsListIter<'list, T: 'list> {
    head: &'list ConsCell<T>,
}

impl<'list, T: 'list> Iterator for ConsListIter<'list, T> {
    type Item = &'list T;

    fn next(&mut self) -> Option<Self::Item> {
        match self.head {
            ConsCell::Tail => None,
            ConsCell::Entry(value, rest) => {
                self.head = rest;
                Some(value)
            }
        }
    }
}