use std::fmt::Display;
use std::fmt::Formatter;

struct Node {
    value: i32,
    next: Option<Box<Node>>,
}

pub struct SortedLinkedList {
    head: Option<Box<Node>>,
    count: usize,
}

pub struct Iter<'a> {
    next: Option<&'a Node>,
}
impl Node {
    fn new(value: i32, next: Option<Box<Node>>) -> Self {
        Node { value, next }
    }
}

impl Default for SortedLinkedList {
    fn default() -> Self {
        Self::new()
    }
}

impl SortedLinkedList {
    pub fn new() -> Self {
        SortedLinkedList {
            head: Option::None,
            count: 0,
        }
    }

    pub fn add_item(&mut self, item: i32) {
        let mut curr = &mut self.head;
        while let Some(node) = curr
            && node.value < item
        {
            curr = &mut curr.as_mut().unwrap().next;
        }
        let old_tail = curr.take();

        *curr = Some(Box::new(Node::new(item, old_tail)));
        self.count += 1;
    }

    pub fn delete_value(&mut self, item: i32) {
        let mut curr = &mut self.head;
        while curr.is_some() && curr.as_ref().unwrap().value != item {
            curr = &mut curr.as_mut().unwrap().next;
        }
        if curr.is_none() {
            return;
        }
        if let Some(mut old_node) = curr.take() {
            *curr = old_node.next.take();
            self.count -= 1;
        }
    }

    pub fn iter(&self) -> Iter<'_> {
        Iter {
            next: self.head.as_deref(),
        }
    }
}

impl Display for SortedLinkedList {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
        write!(f, "[")?;
        let mut first = true;
        for val in self.iter() {
            if !first {
                write!(f, ", ")?;
            }
            write!(f, "{}", val)?;
            first = false;
        }
        write!(f, "]")?;
        Ok(())
    }
}

impl<'a> Iterator for Iter<'a> {
    type Item = &'a i32;
    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        self.next.map(|node| {
            self.next = node.next.as_deref();
            &node.value
        })
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn sorted_corr() {
        let mut sll = SortedLinkedList::new();
        sll.add_item(23);
        sll.add_item(24);
        sll.add_item(22);
        sll.add_item(23);
        assert!(format!("{}", sll) == "[22, 23, 23, 24]")
    }
    #[test]
    fn deletion() {
        let mut sll = SortedLinkedList::new();
        sll.add_item(23);
        sll.add_item(24);
        sll.add_item(22);
        sll.delete_value(22);
        assert!(format!("{}", sll) == "[23, 24]")
    }
}
