struct Node<T> {
    val: T,
    next: Option<NonNull<Node<T>>>,
    prev: Option<NonNull<Node<T>>>,
}

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

    fn into_val(self: Box<Self>) -> T {
        self.val
    }
}

fn overwrite<T: Copy>(covarianced: &mut T, short: &mut T) {
    *covarianced = *short;
}

fn main() {
    let mut forever: &'static str = " 我会活到世界末日 ";
    'small {
        let short = String::from(" 我马上死了 ");
        overwrite(&mut forever, &mut &*short);
    }
    // 爆炸！用到了已经被释放的内存
    println!("{}", forever);
}

struct Node<T> {
    val: T,
    next: Option<NonNull<Node<T>>>,
    prev: Option<NonNull<Node<T>>>,
}

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

    fn into_val(self: Box<Self>) -> T {
        self.val
    }
}

pub struct LinkedList<T> {
    length: usize,
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    _marker: PhantomData<Box<Node<T>>>,
}

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        Self {
            length: 0,
            head: None,
            tail: None,
            _marker: PhantomData,
        }
    }
}

impl<T> Default for LinkedList<T> {
    fn default() -> Self {
        Self::new()
    }
}

let list: LinkedList<i32> = LinkedList::default();
let list: LinkedList<i32> = LinkedList::new();

/// Adds the given node to the front of the list.
pub fn push_front(&mut self, val: T) {
    // Use box to help generate raw ptr
    let mut node = Box::new(Node::new(val));
    node.next = self.head;
    node.prev = None;
    let node = NonNull::new(Box::into_raw(node));

    match self.head {
        None => self.tail = node,
        Some(head) => unsafe { (*head.as_ptr()).prev = node },
    }

    self.head = node;
    self.length += 1;
}

match self.head {
    None => self.tail = node,
    Some(head) => unsafe { (*head.as_ptr()).prev = node },
}

self.head = node;
self.length += 1;

pub fn push_back(&mut self, val: T) {
    // Use box to help generate raw ptr
    let mut node = Box::new(Node::new(val));
    node.next = None;
    node.prev = self.tail;
    let node = NonNull::new(Box::into_raw(node));

    match self.tail {
        None => self.head = node,
        // Not creating new mutable (unique!) references overlapping `element`.
        Some(tail) => unsafe { (*tail.as_ptr()).next = node },
    }

    self.tail = node;
    self.length += 1;
}

/// Removes the first element and returns it, or `None` if the list is
/// empty.
///
/// This operation should compute in *O*(1) time.
pub fn pop_front(&mut self) -> Option<T> {
    self.head.map(|node| {
        self.length -= 1;

        unsafe {
            let node = Box::from_raw(node.as_ptr());

            self.head = node.next;

            match self.head {
                None => self.tail = None,
                Some(head) => (*head.as_ptr()).prev = None,
            }
            node.into_val()
        }
    })
}

struct Foo {
    x: String,
    y: String,
}

let foo = Foo {
    x: "foo".to_string(),
    y: "bar".to_string(),
};

#[derive(Copy, PartialEq, PartialOrd, Eq, Ord, Debug, Hash)]
#[rustc_diagnostic_item = "Option"]
#[stable(feature = "rust1", since = "1.0.0")]
pub enum Option<T> {
    /// No value.
    #[lang = "None"]
    #[stable(feature = "rust1", since = "1.0.0")]
    None,
    /// Some value of type `T`.
    #[lang = "Some"]
    #[stable(feature = "rust1", since = "1.0.0")]
    Some(#[stable(feature = "rust1", since = "1.0.0")] T),
}

struct Foo {
    x: Option<String>,
    y: Option<String>,
}

let foo = Foo {
    x: Option::from("foo".to_string()),
    y: None,
};

struct Foo {
    x: Option<String>,
    y: Option<String>,
}

let a = Foo {
    x: Option::from("foo".to_string()),
    y: None,
};

let mut b: String = "".to_string();
if a.x.is_some() {
    b = a.x.unwrap();
}

let res = if b.ends_with("0") {
    Some(b)
} else {
    None
};

println!("{:?}", res); // None

pub const fn map<U, F>(self, f: F) -> Option<U>
where
F: ~const FnOnce(T) -> U,
F: ~const Drop,
{
    match self {
        Some(x) => Some(f(x)),
        None => None,
    }
}

let res = a.x.map(|str| {
    if str.ends_with("o") {
        str
    } else {
        None
    }
});

|node| {
    self.length -= 1;

    unsafe {
        let node = Box::from_raw(node.as_ptr());

        self.head = node.next;

        match self.head {
            None => self.tail = None,
            Some(head) => (*head.as_ptr()).prev = None,
        }
        node.into_val()
    }
}

/// Removes the last element from a list and returns it, or `None` if
/// it is empty.
///
/// This operation should compute in *O*(1) time.
pub fn pop_back(&mut self) -> Option<T> {
  self.tail.map(|node| {
    self.length -= 1;

    unsafe {
      let node = Box::from_raw(node.as_ptr());

      self.tail = node.prev;

      match self.tail {
        None => self.head = None,
        Some(tail) => (*tail.as_ptr()).next = None,
      }
      node.into_val()
    }
  })
}

pub fn peek_front(&self) -> Option<&T> {
    unsafe {
      self.head.as_ref().map(|node| &node.as_ref().val)
    }
}

#[stable(feature = "nonnull", since = "1.25.0")]
#[rustc_const_unstable(feature = "const_ptr_as_ref", issue = "91822")]
#[must_use]
#[inline]
pub const unsafe fn as_ref<'a>(&self) -> &'a T {
  // SAFETY: the caller must guarantee that `self` meets all the
  // requirements for a reference.
  unsafe { &*self.as_ptr() }
}

pub fn peek_back(&self) -> Option<&T> {
  unsafe { self.tail.as_ref().map(|node| &node.as_ref().val) }
}

pub fn peek_front_mut(&mut self) -> Option<&mut T> {
  unsafe { self.head.as_mut().map(|node| &mut node.as_mut().val) }
}

#[stable(feature = "nonnull", since = "1.25.0")]
#[rustc_const_unstable(feature = "const_ptr_as_ref", issue = "91822")]
#[must_use]
#[inline]
pub const unsafe fn as_mut<'a>(&mut self) -> &'a mut T {
  // SAFETY: the caller must guarantee that `self` meets all the
  // requirements for a mutable reference.
  unsafe { &mut *self.as_ptr() }
}

pub fn peek_back_mut(&mut self) -> Option<&mut T> {
  unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().val) }
}

#[derive(Copy, PartialEq, PartialOrd, Eq, Ord, Debug, Hash)]
#[must_use = "this `Result` may be an `Err` variant, which should be handled"]
#[rustc_diagnostic_item = "Result"]
#[stable(feature = "rust1", since = "1.0.0")]
pub enum Result<T, E> {
    /// Contains the success value
    #[lang = "Ok"]
    #[stable(feature = "rust1", since = "1.0.0")]
    Ok(#[stable(feature = "rust1", since = "1.0.0")] T),

    /// Contains the error value
    #[lang = "Err"]
    #[stable(feature = "rust1", since = "1.0.0")]
    Err(#[stable(feature = "rust1", since = "1.0.0")] E),
}

use std::{error, fmt};

#[derive(Debug, Clone)]
pub struct IndexOutOfRangeError;

impl fmt::Display for IndexOutOfRangeError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "index out of range")
    }
}

impl error::Error for IndexOutOfRangeError {}

pub fn get_by_idx(&self, idx: usize) -> Result<Option<&T>, Box<dyn Error>> {
  ......
}

pub fn get_by_idx(&self, idx: usize) -> Result<Option<&T>, Box<dyn Error>> {
  let len = self.length;

  if idx >= len {
    return Err(Box::new(IndexOutOfRangeError {}));
  }

  // Iterate towards the node at the given index, either from the start or the end,
  // depending on which would be faster.
  let offset_from_end = len - idx - 1;
  let mut cur;
  if idx <= offset_from_end {
    // Head to Tail
    cur = self.head;
    for _ in 0..idx {
      match cur.take() {
        None => {
          cur = self.head;
        }
        Some(current) => unsafe {
          cur = current.as_ref().next;
        },
      }
    }
  } else {
    // Tail to Head
    cur = self.tail;
    for _ in 0..offset_from_end {
      match cur.take() {
        None => {
          cur = self.tail;
        }
        Some(current) => unsafe {
          cur = current.as_ref().prev;
        },
      }
    }
  }

  unsafe { Ok(cur.as_ref().map(|node| &node.as_ref().val)) }
}

// Head to Tail
cur = self.head;
for _ in 0..idx {
  match cur.take() {
    None => {
      cur = self.head;
    }
    Some(current) => unsafe {
      cur = current.as_ref().next;
    },
  }
}

/// A common Trait for the ability to explicitly duplicate an object.
#[stable(feature = "rust1", since = "1.0.0")]
#[lang = "clone"]
#[rustc_diagnostic_item = "Clone"]
#[rustc_trivial_field_reads]
pub trait Clone: Sized {
    #[stable(feature = "rust1", since = "1.0.0")]
    #[must_use = "cloning is often expensive and is not expected to have side effects"]
    fn clone(&self) -> Self;

    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    fn clone_from(&mut self, source: &Self) {
        *self = source.clone()
    }
}


/// Types whose values can be duplicated simply by copying bits.
#[stable(feature = "rust1", since = "1.0.0")]
#[lang = "copy"]
#[rustc_unsafe_specialization_marker]
#[rustc_diagnostic_item = "Copy"]
pub trait Copy: Clone {
    // Empty.
}

let mut x = Some(1);
let y = x;
let z = x.take();
println!("{:?} {:?} {:?}", x, y, z); // None Some(1) Some(1)

#[stable(feature = "nonnull", since = "1.25.0")]
impl<T: ?Sized> Clone for NonNull<T> {
    #[inline]
    fn clone(&self) -> Self {
        *self
    }
}

#[stable(feature = "nonnull", since = "1.25.0")]
impl<T: ?Sized> Copy for NonNull<T> {}

for _ in 0..idx {
  match cur.take() {
    None => {
      cur = self.head;
    }
    Some(current) => unsafe {
      cur = current.as_ref().next;
    },
  }
}

else {
  // Tail to Head
  cur = self.tail;
  for _ in 0..offset_from_end {
    match cur.take() {
      None => {
        cur = self.tail;
      }
      Some(current) => unsafe {
        cur = current.as_ref().prev;
      },
    }
  }
}

unsafe { Ok(cur.as_ref().map(|node| &node.as_ref().val)) }

 fn _get_by_idx_mut(&self, idx: usize) -> Result<Option<NonNull<Node<T>>>, Box<dyn Error>> {
   let len = self.length;

   if idx >= len {
     return Err(Box::new(IndexOutOfRangeError {}));
   }

   // Iterate towards the node at the given index, either from the start or the end,
   // depending on which would be faster.
   let offset_from_end = len - idx - 1;
   let mut cur;
   if idx <= offset_from_end {
     // Head to Tail
     cur = self.head;
     for _ in 0..idx {
       match cur.take() {
         None => {
           cur = self.head;
         }
         Some(current) => unsafe {
           cur = current.as_ref().next;
         },
       }
     }
   } else {
     // Tail to Head
     cur = self.tail;
     for _ in 0..offset_from_end {
       match cur.take() {
         None => {
           cur = self.tail;
         }
         Some(current) => unsafe {
           cur = current.as_ref().prev;
         },
       }
     }
   }

   Ok(cur)
}

pub fn get_by_idx_mut(&self, idx: usize) -> Result<Option<&mut T>, Box<dyn Error>> {
  let mut cur = self._get_by_idx_mut(idx)?;
  unsafe { Ok(cur.as_mut().map(|node| &mut node.as_mut().val)) }
}

pub fn insert_by_idx(&mut self, idx: usize, data: T) -> Result<(), Box<dyn Error>> {
  let len = self.length;

  if idx > len {
    return Err(Box::new(IndexOutOfRangeError {}));
  }

  if idx == 0 {
    return Ok(self.push_front(data));
  } else if idx == len {
    return Ok(self.push_back(data));
  }

  unsafe {
    // Create Node
    let mut spliced_node = Box::new(Node::new(data));
    let before_node = self._get_by_idx_mut(idx - 1)?;
    let after_node = before_node.unwrap().as_mut().next;
    spliced_node.prev = before_node;
    spliced_node.next = after_node;
    let spliced_node = NonNull::new(Box::into_raw(spliced_node));

    // Insert Node
    before_node.unwrap().as_mut().next = spliced_node;
    after_node.unwrap().as_mut().prev = spliced_node;
  }

  self.length += 1;

  Ok(())
}

 // Create Node
let mut spliced_node = Box::new(Node::new(data));
let before_node = self._get_by_idx_mut(idx - 1)?;
let after_node = before_node.unwrap().as_mut().next;
spliced_node.prev = before_node;
spliced_node.next = after_node;
let spliced_node = NonNull::new(Box::into_raw(spliced_node));

// Insert Node
before_node.unwrap().as_mut().next = spliced_node;
after_node.unwrap().as_mut().prev = spliced_node;

spliced_node.prev = before_node;
spliced_node.next = after_node;
let spliced_node = NonNull::new(Box::into_raw(spliced_node));

// Insert Node
before_node.unwrap().as_mut().next = spliced_node;
after_node.unwrap().as_mut().prev = spliced_node;

/// Removes the element at the given index and returns it.
///
/// This operation should compute in *O*(*n*) time.
pub fn remove_by_idx(&mut self, idx: usize) -> Result<T, Box<dyn Error>> {
  let len = self.length;

  if idx >= len {
    return Err(Box::new(IndexOutOfRangeError {}));
  }

  if idx == 0 {
    return Ok(self.pop_front().unwrap());
  } else if idx == len - 1 {
    return Ok(self.pop_back().unwrap());
  };

  let cur = self._get_by_idx_mut(idx)?.unwrap();

  self.unlink_node(cur);

  unsafe {
    let unlinked_node = Box::from_raw(cur.as_ptr());
    Ok(unlinked_node.val)
  }
}

/// Unlinks the specified node from the current list.
///
/// Warning: this will not check that the provided node belongs to the current list.
///
/// This method takes care not to create mutable references to `element`,
/// to maintain validity of aliasing pointers.
#[inline]
fn unlink_node(&mut self, mut node: NonNull<Node<T>>) {
  let node = unsafe { node.as_mut() }; // this one is ours now, we can create an &mut.

  // Not creating new mutable (unique!) references overlapping `element`.
  match node.prev {
    Some(prev) => unsafe { (*prev.as_ptr()).next = node.next },
    // this node is the head node
    None => self.head = node.next,
  };

  match node.next {
    Some(next) => unsafe { (*next.as_ptr()).prev = node.prev },
    // this node is the tail node
    None => self.tail = node.prev,
  };

  self.length -= 1;
}

unsafe {
  let unlinked_node = Box::from_raw(cur.as_ptr());
  Ok(unlinked_node.val)
}

pub struct IntoIter<T> {
    list: LinkedList<T>,
}

pub struct Iter<'a, T: 'a> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<&'a Node<T>>,
}

pub struct IterMut<'a, T: 'a> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<&'a mut Node<T>>,
}

pub fn into_iter(self) -> IntoIter<T> {
  IntoIter { list: self }
}

pub fn iter(&self) -> Iter<'_, T> {
  Iter {
    head: self.head,
    tail: self.tail,
    len: self.length,
    _marker: PhantomData,
  }
}

pub fn iter_mut(&mut self) -> IterMut<'_, T> {
  IterMut {
    head: self.head,
    tail: self.tail,
    len: self.length,
    _marker: PhantomData,
  }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.list.pop_front()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.list.length, Some(self.list.length))
    }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        self.list.pop_back()
    }
}

impl<T> Drop for IntoIter<T> {
    fn drop(&mut self) {
        // only need to ensure all our elements are read;
        // buffer will clean itself up afterwards.
        for _ in &mut *self {}

        println!("IntoIter has been dropped!")
    }
}

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

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            self.head.map(|node| {
                self.len -= 1;

                unsafe {
                    let node = &*node.as_ptr();
                    self.head = node.next;
                    &node.val
                }
            })
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }

    #[inline]
    fn last(mut self) -> Option<&'a T> {
        self.next_back()
    }
}

impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            self.tail.map(|node| {
                self.len -= 1;

                unsafe {
                    // Need an unbound lifetime to get 'a
                    let node = &*node.as_ptr();
                    self.tail = node.prev;
                    &node.val
                }
            })
        }
    }
}

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

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            self.head.map(|node| {
                self.len -= 1;

                unsafe {
                    let node = &mut *node.as_ptr();
                    self.head = node.next;
                    &mut node.val
                }
            })
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len, Some(self.len))
    }

    #[inline]
    fn last(mut self) -> Option<&'a mut T> {
        self.next_back()
    }
}

impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            None
        } else {
            self.tail.map(|node| {
                self.len -= 1;

                unsafe {
                    // Need an unbound lifetime to get 'a
                    let node = &mut *node.as_ptr();
                    self.tail = node.prev;
                    &mut node.val
                }
            })
        }
    }
}

/// Returns `true` if the `LinkedList` contains an element equal to the given value.
///
/// This operation should compute in *O*(*n*) time.
///
/// # Examples
///
/// ```
/// use collection::list::linked_list::LinkedList;
///
/// let mut list = LinkedList::new();
///
/// list.push_back(0);
/// list.push_back(1);
/// list.push_back(2);
///
/// assert_eq!(list.contains(&0), true);
/// assert_eq!(list.contains(&10), false);
/// ```
pub fn contains(&self, elem: &T) -> bool
where
T: PartialEq<T>,
{
  self.iter().any(|x| x == elem)
}

pub enum Ordering {
    Less = -1,
    Equal = 0,
    Greater = 1,
}

#[derive(PartialEq)]
pub struct Person {
    pub id: u32,
    pub name: String,
    pub height: f64,
}

impl PartialEq for Person {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id &&
            self.name == other.name &&
            self.height == other.height
    }
}

impl PartialEq for Person {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id
    }
}

println!("NAN == NAN ? {}", std::f64::NAN == std::f64::NAN);

#[derive(Eq)]
struct Person {
    pub id: u32,
    pub name: String,
    pub height: f64,
}

struct Person {
    pub id: u32,
    pub name: String,
    pub height: f64,
}

impl Eq for Person {}

impl PartialOrd for Person {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.height.partial_cmp(&other.height)
    }
}

impl <A: TraitB + TraitC, D: TraitE + TraitF> MyTrait<A, D> for YourType {}

// 当分别指定泛型的类型和约束时，使用 where 会更清晰

impl <A, D> MyTrait<A, D> for YourType where
    A: TraitB + TraitC,
    D: TraitE + TraitF {}

impl<T: Debug> LinkedList<T> {
    pub fn traverse(&self) {
        print!("{{ ");
        for (idx, x) in self.iter().enumerate() {
            print!(" [{}: {:?}] ", idx, *x)
        }
        println!(" }}");
    }
}

#[derive(Debug)]
impl<T> LinkedList<T> {
  ......
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        struct DropGuard<'a, T>(&'a mut LinkedList<T>);

        impl<'a, T> Drop for DropGuard<'a, T> {
            fn drop(&mut self) {
                // Continue the same loop we do below. This only runs when a destructor has
                // panicked. If another one panics this will abort.
                while self.0.pop_front().is_some() {}
            }
        }

        while let Some(node) = self.pop_front() {
            let guard = DropGuard(self);
            drop(node);
            mem::forget(guard);
        }

        println!("LinkedList dropped!")
    }
}

impl<'a, T> Drop for DropGuard<'a, T> {
  fn drop(&mut self) {
    // Continue the same loop we do below. This only runs when a destructor has
    // panicked. If another one panics this will abort.
    while self.0.pop_front().is_some() {}
  }
}

while let Some(node) = self.pop_front() {
  let guard = DropGuard(self);
  drop(node);
  mem::forget(guard);
}

println!("LinkedList dropped!")

pub fn clear(&mut self) {
  *self = Self::new();
}

#[cfg(test)]
mod test {
    use crate::list::linked_list::LinkedList;

    #[test]
    fn test_compiling() {}

    #[test]
    fn test_push_and_pop() {
        let mut list = _new_list_i32();

        assert_eq!(list.length, 5);
        list.traverse();

        assert_eq!(list.pop_front(), Some(-1));
        assert_eq!(list.pop_back(), Some(i32::MAX));

        assert_eq!(list.length, 3);
        list.traverse();
    }

    #[test]
    fn test_peak() {
        let mut list = _new_list_string();

        assert_eq!(list.peek_front(), Some(&String::from("abc")));
        assert_eq!(list.peek_back(), Some(&String::from("hij")));

        let cur = list.peek_front_mut();
        assert_eq!(cur, Some(&mut String::from("abc")));
        cur.map(|x| x.push(' '));

        let cur = list.peek_back_mut();
        assert_eq!(cur, Some(&mut String::from("hij")));
        cur.map(|x| x.push(' '));

        assert_eq!(list.peek_front(), Some(&String::from("abc ")));
        assert_eq!(list.peek_back(), Some(&String::from("hij ")));
        assert_eq!(list.length, 3);

        list.traverse();
    }

    #[test]
    fn test_get_idx() {
        let list = _new_list_i32();

        assert_eq!(list.get_by_idx(2).unwrap(), Some(&456));
        assert_eq!(list.get_by_idx(3).unwrap(), Some(&789));

        print!("before change: ");
        list.traverse();
        let cur = list.get_by_idx_mut(2).unwrap().unwrap();
        assert_eq!(cur, &mut 456);

        *cur <<= 1;
        print!("after change: ");
        list.traverse();

        assert_eq!(list.get_by_idx(2).unwrap(), Some(&(456 << 1)));
    }

    #[test]
    fn test_get_idx_err() {
        let list = _new_list_i32();

        assert!(list.get_by_idx(99).is_err());
        assert!(list.get_by_idx_mut(99).is_err());
    }

    #[test]
    fn test_insert_idx() {
        let mut list = LinkedList::new();

        list.push_back(String::from("1"));
        list.push_back(String::from("2"));
        list.push_back(String::from("3"));

        list.insert_by_idx(1, String::from("99")).unwrap();
        list.traverse();

        assert_eq!(list.get_by_idx(0).unwrap(), Some(&String::from("1")));
        assert_eq!(list.get_by_idx(1).unwrap(), Some(&String::from("99")));
    }

    #[test]
    fn test_insert_idx_err() {
        let mut list = LinkedList::new();

        assert!(list.insert_by_idx(99, String::from("99")).is_err());
    }

    #[test]
    fn test_remove_idx() {
        let mut list = LinkedList::new();

        list.push_back(String::from("1"));
        list.push_back(String::from("2"));
        list.push_back(String::from("3"));

        let removed = list.remove_by_idx(1).unwrap();
        list.traverse();

        assert_eq!(removed, String::from("2"));

        assert_eq!(list.get_by_idx(0).unwrap(), Some(&String::from("1")));
        assert_eq!(list.get_by_idx(1).unwrap(), Some(&String::from("3")));
    }

    #[test]
    fn test_remove_idx_err() {
        let mut list: LinkedList<i32> = LinkedList::new();

        assert!(list.remove_by_idx(99).is_err());
    }

    #[test]
    fn test_contains() {
        let list = _new_list_i32();

        assert!(list.contains(&-1));
        assert!(!list.contains(&-2));
    }

    #[test]
    fn test_clear() {
        let mut list = _new_list_zst();

        assert_eq!(list.length(), 3);

        list.clear();

        assert_eq!(list.length(), 0);
    }

    #[test]
    fn test_iterator() {
        let mut list1 = _new_list_i32();

        print!("before change: ");
        list1.traverse();
        list1.iter_mut().for_each(|x| *x = *x - 1);
        print!("after change: ");
        list1.traverse();

        let list2 = _new_list_string();
        let list2_to_len = list2.into_iter().map(|x| x.len()).collect::<Vec<usize>>();
        println!(
            "transform list2 into len vec, list2_to_len: {:?}",
            list2_to_len
        );

        // Compiling err:
        // list2.traverse()
    }

    struct ZeroSizeType {}

    fn _new_list_i32() -> LinkedList<i32> {
        let mut list = LinkedList::new();

        list.push_front(456);
        list.push_front(123);
        list.push_back(789);
        list.push_front(-1);
        list.push_back(i32::MAX);

        list
    }

    fn _new_list_string() -> LinkedList<String> {
        let mut list = LinkedList::new();

        list.push_front(String::from("def"));
        list.push_front(String::from("abc"));
        list.push_back(String::from("hij"));

        list
    }

    fn _new_list_zst() -> LinkedList<ZeroSizeType> {
        let mut list = LinkedList::new();

        list.push_front(ZeroSizeType {});
        list.push_front(ZeroSizeType {});
        list.push_back(ZeroSizeType {});

        list
    }
}