ngen 0.1.4

use std::{
    marker::PhantomData,
    ptr::NonNull,
};

use super::TempArena;

// Prior Art: This linked list implementation is heavily inspired by Rust's own `LinkedList`
// implementation. Instead of dealing with challenging lifetime issues, we follow suit with
// `Option<NonNull<Node<T>>>`. One of the biggest differences, is that we aren't (at the moment)
// tracking front and tail nodes, and we don't drop anything pushed to the temp arena.

// TODO: This implmentation may change if we introduce a long-term memory arena that can be used as
// an allocator. Then, this implementation may need to implement `Drop`.

struct Node<T> {
    pub value: T,
    pub next: Option<NonNull<Node<T>>>,
}

impl<T> Node<T> {
    #[inline]
    const fn new(value: T, next: Option<NonNull<Node<T>>>) -> Self {
        Self { value, next }
    }
}

/// A simple linked-list implementation that does LIFO stack-based insertions.
pub struct List<T> {
    next: Option<NonNull<Node<T>>>,
    len: usize,
}

impl<T> List<T> {
    /// Creates a new `List<T>`.
    ///
    /// # Example
    /// ```
    ///# use ngen::arena::List;
    /// let mut list = List::<u32>::new();
    /// ```
    #[inline]
    pub fn new() -> Self {
        Self { next: None, len: 0, }
    }

    /// Pushes a new element into the list, replacing the head element.
    ///
    /// # Example
    /// ```
    ///# use ngen::arena::{List, TempArena};
    ///# let mut temp_arena = TempArena::with_capacity(1024).unwrap();
    /// let mut list = List::new();
    /// list.push(&mut temp_arena, 42);
    /// ```
    #[inline]
    pub fn push(&mut self, arena: &TempArena, value: T) {
        let ptr = arena.push(Node::new(value, self.next.take()));
        self.next = NonNull::new(ptr as *mut _);
        self.len += 1;
    }

    /// Returns an iterator over all elements in the list.
    ///
    /// # Example
    /// ```
    ///# use ngen::arena::{List, TempArena};
    ///# let mut temp_arena = TempArena::with_capacity(1024).unwrap();
    /// let mut list = List::new();
    /// for i in 0..42 {
    ///     list.push(&mut temp_arena, i);
    /// }
    ///
    /// // Items in the list are stored in a LIFO manner.
    /// let mut current = 41;
    /// for v in list.iter() {
    ///     assert_eq!(v, &current);
    ///     current -= 1;
    /// }
    /// ```
    #[inline]
    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.next, marker: PhantomData, }
    }

    /// Returns a mutable iterator over all elements in the list.
    ///
    /// # Example
    /// ```
    ///# use ngen::arena::{List, TempArena};
    ///# let mut temp_arena = TempArena::with_capacity(1024).unwrap();
    /// let mut list = List::new();
    /// for i in 0..42 {
    ///     list.push(&mut temp_arena, i);
    /// }
    ///
    /// for v in list.iter_mut() {
    ///     *v *= 2;
    /// }
    /// ```
    #[inline]
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut { next: self.next, marker: PhantomData, }
    }
}

/// An iterator over a linked list.
pub struct Iter<'l, T> {
    next: Option<NonNull<Node<T>>>,
    marker: PhantomData<&'l Node<T>>,
}

impl<'l, T> Iterator for Iter<'l, T> {
    type Item = &'l T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| unsafe {
            let node = &*node.as_ptr();
            self.next = node.next;
            &node.value
        })
    }
}

/// A mutable iterator over a linked list.
pub struct IterMut<'l, T> {
    next: Option<NonNull<Node<T>>>,
    marker: PhantomData<&'l Node<T>>,
}

impl<'l, T> Iterator for IterMut<'l, T> {
    type Item = &'l mut T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| unsafe {
            let node = &mut *node.as_ptr();
            self.next = node.next;
            &mut node.value
        })
    }
}