varstack 0.2.4

use core::{clone, cmp, fmt, marker};

/// A call-stack based singly-linked list
#[derive(Copy, Clone, Eq, Hash)]
pub struct RefStack<'s, V> {
    pub parent: Option<&'s RefStack<'s, V>>,
    pub value: V,
}

impl<V: cmp::PartialEq> cmp::PartialEq for RefStack<'_, V> {
    fn eq(mut self: &Self, mut other: &Self) -> bool {
        loop {
            if self.value != other.value {
                return false;
            }
            break match (self.parent, other.parent) {
                (None, None) => true,
                (Some(lhs), Some(rhs)) => {
                    self = lhs;
                    other = rhs;
                    continue;
                }
                _ => false,
            };
        }
    }
}

impl<V: cmp::PartialOrd> cmp::PartialOrd for RefStack<'_, V> {
    fn partial_cmp(mut self: &Self, mut other: &Self) -> Option<cmp::Ordering> {
        use cmp::Ordering as Orde;
        loop {
            match self.value.partial_cmp(&other.value) {
                Some(Orde::Equal) => (),
                non_eq => return non_eq,
            }
            break Some(match (self.parent, other.parent) {
                (None, None) => Orde::Equal,
                (Some(lhs), Some(rhs)) => {
                    self = lhs;
                    other = rhs;
                    continue;
                }
                (None, Some(_)) => Orde::Less,
                (Some(_), None) => Orde::Greater,
            });
        }
    }
}

impl<V: cmp::Ord> cmp::Ord for RefStack<'_, V> {
    fn cmp(mut self: &Self, mut other: &Self) -> cmp::Ordering {
        use cmp::Ordering as Orde;
        loop {
            match self.value.cmp(&other.value) {
                Orde::Equal => (),
                non_eq => return non_eq,
            }
            break match (self.parent, other.parent) {
                (None, None) => Orde::Equal,
                (Some(lhs), Some(rhs)) => {
                    self = lhs;
                    other = rhs;
                    continue;
                }
                (None, Some(_)) => Orde::Less,
                (Some(_), None) => Orde::Greater,
            };
        }
    }
}

impl<V: fmt::Debug> fmt::Debug for RefStack<'_, V> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self.iter()).finish()
    }
}

impl<'s, V> RefStack<'s, V> {
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        false
    }

    #[inline(always)]
    pub fn len(&self) -> usize {
        self.iter().count()
    }

    #[inline(always)]
    pub fn iter(&'s self) -> RefIter<'s, V> {
        RefIter(Some(self))
    }
}

impl<'s, V> IntoIterator for &'s RefStack<'s, V> {
    type Item = &'s V;
    type IntoIter = RefIter<'s, V>;

    #[inline(always)]
    fn into_iter(self) -> RefIter<'s, V> {
        RefIter(Some(self))
    }
}

pub struct RefIter<'s, V>(pub Option<&'s RefStack<'s, V>>);

impl<'s, V> RefIter<'s, V> {
    #[inline(always)]
    pub fn is_empty(&self) -> bool {
        self.0.is_none()
    }

    #[inline(always)]
    pub fn len(&self) -> usize {
        self.count()
    }
}

impl<V> marker::Copy for RefIter<'_, V> {}

impl<V> clone::Clone for RefIter<'_, V> {
    #[inline(always)]
    fn clone(&self) -> Self {
        Self(self.0)
    }
}

impl<V: fmt::Debug> fmt::Debug for RefIter<'_, V> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(*self).finish()
    }
}

impl<'s, V> Iterator for RefIter<'s, V> {
    type Item = &'s V;

    #[inline]
    fn next(&mut self) -> Option<&'s V> {
        let inner = self.0?;
        self.0 = inner.parent;
        Some(&inner.value)
    }

    #[inline]
    fn fold<B, F>(mut self, mut accum: B, mut f: F) -> B
    where
        F: FnMut(B, &'s V) -> B,
    {
        while let Some(x) = self.0 {
            self.0 = x.parent;
            accum = f(accum, &x.value);
        }
        accum
    }
}

#[cfg(test)]
mod tests {
    macro_rules! stack_then {
        ($e:expr => $th:expr) => {{
            ($th)($crate::RefStack {
                parent: None,
                value: $e,
            })
        }};
        ($efi:expr, $($e:expr),* => $th:expr) => {{
            let x = $crate::RefStack {
                parent: None,
                value: $efi,
                };
            $(
                let x = $crate::RefStack {
                    parent: Some(&x),
                    value: $e,
                };
            )+
            ($th)(x)
        }}
    }

    #[test]
    fn stack_eq() {
        stack_then![0, 1, 2, 3 => |a| {
            stack_then![0, 1, 2, 3 => |b| assert_eq!(a, b)];
            stack_then![1, 2, 3 => |c| assert_ne!(a, c)];
            stack_then![1, 2, 3, 0 => |d| assert_ne!(a, d)];
        }];
    }

    #[test]
    fn stack_len() {
        stack_then![0 => |a: crate::RefStack<'_, u32>| assert_eq!(a.len(), 1)];
        stack_then![0, 1, 2, 3 => |a: crate::RefStack<'_, u32>| assert_eq!(a.len(), 4)];
    }
}