使用链表实现 Vec 容器

use std::fmt::Debug;

/// 使用链表实现 Vec 数据容器
fn main() {
    let mut lvec = LVec::new();

    lvec.push(1);
    lvec.push(2);
    lvec.push(3);
    lvec.push(4);

    // 打印 1, 2, 3, 4
    lvec.print();

    lvec.pop();
    // 打印 1, 2, 3
    lvec.print();

    // 移除第一个元素
    lvec.remove(0);
    // 打印 2, 3
    lvec.print();

    let mut lvec2 = LVec::new();
    lvec2.push(4);
    lvec2.push(5);
    // 将 lvec 和 lvec2 进行拼接，将 lvec2 所有权转进 lvec 中
    lvec.append(lvec2);
    // 打印 2, 3, 4, 5
    lvec.print();
}

type Link<T> = Option<Box<Node<T>>>;

#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Link<T>,
}

impl<T> Node<T> {
    fn new(data: T) -> Node<T> {
        Self { data, next: None }
    }
}

#[derive(Debug)]
struct LVec<T> {
    size: usize,
    head: Link<T>,
}

impl<T: Copy + Debug> LVec<T> {
    fn new() -> LVec<T> {
        Self {
            size: 0,
            head: None,
        }
    }

    fn clear(&mut self) {
        self.size = 0;
        self.head = None;
    }

    fn len(&self) -> usize {
        self.size
    }

    fn is_empty(&self) -> bool {
        self.size == 0
    }

    fn push(&mut self, data: T) {
        let new_node = Node::new(data);

        if self.is_empty() {
            self.head = Some(Box::new(new_node));
        } else {
            let mut current = &mut self.head;

            for _ in 0..self.size - 1 {
                if let Some(node) = current {
                    current = &mut node.next;
                }
            }

            if let Some(node) = current {
                node.next = Some(Box::new(new_node));
            }
        }

        self.size += 1;
    }

    // 往 Vec 中追加另一个 Vec，用于两个 Vec 合并
    fn append(&mut self, mut other_vec: LVec<T>) {
        let mut other_vec_current = &mut other_vec.head;

        while let Some(node) = other_vec_current {
            self.push(node.data);
            other_vec_current = &mut node.next;
        }

        other_vec.clear();
    }

    // 往 Vec 中指定位置插入数据
    fn insert(&mut self, mut index: usize, data: T) {
        if index >= self.size {
            index = self.size
        }

        let mut new_node = Node::new(data);

        if self.is_empty() {
            self.head = Some(Box::new(new_node));
        } else if index == 0 {
            // 插入链表的头部
            new_node.next = self.head.take();
            self.head = Some(Box::new(new_node));
        } else {
            // 插入链表中间
            let mut current = &mut self.head;

            for _ in 0..index - 1 {
                if let Some(node) = current {
                    current = &mut node.next;
                }
            }

            if let Some(mut node) = current.take() {
                new_node.next = node.next;
                node.next = Some(Box::new(new_node));
            }
        }

        self.size += 1;
    }

    // 移除指定下标的节点
    fn remove(&mut self, index: usize) -> Option<T> {
        if index >= self.size {
            return None;
        }

        // 删除下标为 0 的节点
        if index == 0 {
            let head = self.head.take();
            if let Some(mut node) = head {
                self.head = node.next.take();
                self.size -= 1;
                return Some(node.data);
            }
        }

        let mut current = &mut self.head;
        let mut current_index = 0;

        while let Some(node) = current {
            // 找到被删除节点的前一个节点
            if current_index + 1 == index {
                if let Some(removed_node) = node.next.take() {
                    let removed_data = removed_node.data;
                    node.next = removed_node.next;
                    self.size -= 1;

                    return Some(removed_data);
                }
            }

            current_index += 1;
            current = &mut node.next;
        }

        None
    }

    fn pop(&mut self) -> Option<T> {
        self.remove(self.size - 1)
    }

    fn print(&self) {
        let mut current = &self.head;
        let mut current_index = 0;
        while let Some(node) = current {
            print!(
                "{:?}{}",
                &node.data,
                if current_index == self.size - 1 {
                    "\n"
                } else {
                    ", "
                }
            );
            current = &node.next;
            current_index += 1;
        }
    }
}