linked_list.rs

use std::{
    fmt::{Debug, Display},
    mem,
};

fn main() {
    let mut list = List::new();
    list.add(42);
    list.add(1);
    list.add(5);
    list.add(43);
    println!("{list}");
    let v: Vec<i32> = list.into_iter().collect();
    assert_eq!(v, vec![1, 5, 42, 43]);
}

#[derive(Default)]
enum List<T> {
    #[default]
    Empty,
    Some {
        val: T,
        next: Box<List<T>>,
    },
}

impl<T: Clone> Iterator for List<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        match self {
            Self::Empty => None,
            Self::Some { val, next } => {
                let val = val.clone();
                let next = mem::replace(next.as_mut(), List::Empty);
                *self = next;
                Some(val)
            }
        }
    }
}

impl<'a, T> Iterator for &'a List<T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        match self {
            List::Empty => None,
            List::Some { val, next } => {
                *self = &next;
                Some(val)
            }
        }
    }
}

impl<T: Display> Display for List<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "[")?;
        for (idx, v) in self.enumerate() {
            if idx > 0 {
                write!(f, ", ")?;
            }
            write!(f, "{v}")?;
        }
        write!(f, "]")?;
        Ok(())
    }
}

impl<T: Debug> Debug for List<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let v = self.map(|t| format!("{t:?}")).collect::<Vec<_>>();
        write!(f, "{v:?}")
    }
}

impl<T: Ord + Clone> List<T> {
    fn new() -> Self {
        Self::Empty
    }

    fn add(&mut self, iv: T) {
        let mut cur = self;
        loop {
            match cur {
                Self::Empty => {
                    *cur = List::Some {
                        val: iv,
                        next: Box::new(List::Empty),
                    };
                    return;
                }
                Self::Some { val, next } => {
                    if *val >= iv {
                        *next = Box::new(List::Some {
                            val: val.clone(),
                            next: Box::new(mem::take(next.as_mut())),
                        });
                        *val = iv;
                        return;
                    }
                    match next.as_mut() {
                        List::Empty => {
                            *next = Box::new(Self::Some {
                                val: iv,
                                next: Box::new(Self::Empty),
                            });
                            return;
                        }
                        List::Some { val, next } => {
                            if *val >= iv {
                                *next = Box::new(List::Some {
                                    val: val.clone(),
                                    next: Box::new(mem::take(next.as_mut())),
                                });
                                *val = iv;
                                return;
                            }
                        }
                    }
                    cur = next.as_mut();
                }
            }
        }
    }
}

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

    #[test]
    fn test_list() {
        let mut list = List::new();
        list.add(42);
        list.add(1);
        list.add(5);
        list.add(43);
        list.add(4);
        list.add(0);
        list.add(44);
        list.add(41);
        let v: Vec<i32> = list.collect();
        assert_eq!(v, vec![0, 1, 4, 5, 41, 42, 43, 44]);
    }
}