use std::fmt::Display;

pub struct List {
    head: Link,
}
type Link = Option<Box<Node>>;

#[derive(Debug)]
struct Node {
    elem: i32,
    next: Link,
}
impl Node {
    fn new(elem: i32) -> Self {
        Self { elem, next: None }
    }
}

impl Display for List {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "链表：")?;
        if self.head.is_none() {
            write!(f, "None")?;
            return Ok(());
        }
        let mut next = self.head.as_ref();

        while let Some(node) = next {
            write!(f, "{} -> ", node.elem)?;
            next = node.next.as_ref();
        }
        write!(f, "None")?;

        Ok(())
    }
}

impl List {
    fn new() -> Self {
        Self { head: None }
    }

    fn push(&mut self, elem: i32) -> &mut Self {
        if self.head.is_none() {
            self.head = Some(Box::new(Node::new(elem)));
            return self;
        }

        let mut pnode = self.head.as_mut();
        while let Some(cur_node) = pnode {
            if cur_node.next.is_none() {
                pnode = Some(cur_node);
                break;
            }
            pnode = cur_node.next.as_mut();
        }
        pnode.map(|node| node.next = Some(Box::new(Node::new(elem))));

        self
    }
}

fn reverse(&mut self) {
    let mut rnode: Link = self.head.take();
    let mut lnode: Link = None;

    while let Some(mut node) = rnode {
        rnode = node.next;
        node.next = lnode;
        lnode = Some(node);
    }
    self.head = lnode;
}

fn rev(&mut self) -> &mut Self {
    let mut curlink = self.head.take();
    let mut prevlink: Option<Box<Node>> = None;
    let mut nextlink;

    while let Some(mut curnode) = curlink {
        nextlink = curnode.next;
        curnode.next = prevlink;
        prevlink = Some(curnode);
        curlink = nextlink;
    }

    self.head = prevlink;

    self
}

fn middle_node(&self) -> Option<&Box<Node>> {
    if self.head.is_none() {
        return None;
    }

    let mut fast = self.head.as_ref();
    let mut slow = self.head.as_ref();

    while fast.is_some() && fast.unwrap().next.is_some() {
        slow = slow.unwrap().next.as_ref();
        fast = fast.unwrap().next.as_ref().unwrap().next.as_ref();
    }
    slow
}

fn middle(&self) -> Option<&Box<Node>> {
    if self.head.is_none() {
        return None;
    }

    let mut slow = self.head.as_ref();
    let mut fast = self.head.as_ref();

    while let Some(fnode) = fast {
        fast = fnode.next.as_ref().and_then(|node| node.next.as_ref());
        slow = slow.unwrap().next.as_ref();
    }

    slow
}

fn is_palindrome1(&self) -> bool {
    if self.head.is_none() {
        return true;
    }

    let mut cur = self.head.as_ref();
    let mut v = vec![];
    while let Some(node) = cur {
        v.push(node.elem);
        cur = node.next.as_ref();
    }

    cur = self.head.as_ref();
    for elem in v.into_iter().rev() {
        let node = cur.unwrap();
        if node.elem != elem {
            return false;
        }
        cur = node.next.as_ref();
    }
    true
}

#![feature(linked_list_cursors)]
use std::cmp::Ordering;
use std::collections::LinkedList;

fn main() {
    let list1 = LinkedList::from([1, 2, 3, 4, 5]);
    let list2 = LinkedList::from([1, 3, 5]);

    let mut list1 = list1.cursor_front();
    let mut list2 = list2.cursor_front();

    while list1.current().is_some() && list2.current().is_some() {
        match list1.current().cmp(&list2.current()) {
            Ordering::Greater => list2.move_next(),
            Ordering::Less => list1.move_next(),
            Ordering::Equal => {
                print!("{} ", list2.current().unwrap());
                list1.move_next();
                list2.move_next();
            }
        }
    }
    println!();
}

fn partition(nums: &mut [i32], num: i32) -> &mut [i32] {
    let mut nlt: usize = 0;
    let mut gt: usize = nums.len();
    let mut i: usize = 0;

    while i < gt {
        match nums[i].cmp(&num) {
            Ordering::Greater => {
                gt -= 1;
                nums.swap(i, gt);
            }
            Ordering::Equal => i += 1,
            Ordering::Less => {
                nums.swap(i, nlt);
                nlt += 1;
                i += 1;
            }
        }
    }

    nums
}

fn split_list(mut list: List, num: i32) -> List {
    let mut curlink = list.head.take();
    let mut v: Vec<i32> = vec![];

    while let Some(curnode) = curlink {
        v.push(curnode.elem);
        curlink = curnode.next;
    }

    partition(&mut v, num);
    for elem in v {
        list.push(elem);
    }

    list
}

/// 找到链表的最后一个节点
fn list_tail(link: &mut Link) -> &mut Box<Node> {
    let mut curlink = link.as_mut();

    while let Some(curnode) = curlink {
        if curnode.next.is_none() {
            curlink = Some(curnode);
            break;
        }
        curlink = curnode.next.as_mut();
    }

    curlink.unwrap()
}

/// 把节点加到链表的最后
fn append_list(mut curnode: Box<Node>, hd: &mut Link) -> Link {
    let next = curnode.next.take();
    if hd.is_none() {
        *hd = Some(curnode);
    } else {
        list_tail(hd).next = Some(curnode);
    }
    next
}

fn split_list2(list: &mut List, num: i32) -> List {
    let mut sh: Link = None;
    let mut eh: Link = None;
    let mut bh: Link = None;
    let mut curlink = list.head.take();

    while let Some(curnode) = curlink {
        let link = match curnode.elem.cmp(&num) {
            Ordering::Equal => &mut eh,
            Ordering::Greater => &mut bh,
            Ordering::Less => &mut sh,
        };
        curlink = append_list(curnode, link);
    }

    if sh.is_none() {
        sh = eh;
    } else {
        list_tail(&mut sh).next = eh;
    }
    list_tail(&mut sh).next = bh;

    List { head: sh }
}


fn main() {
    let mut list = List::new();
    list.from(&random_array(10));
    println!("list: {}", list);
    let num = random_num(0..5);
    println!("num: {}", num);
    println!("{}", split_list2(&mut list, num));
}