pub struct Heap<T>(Vec<T>);

impl<T: Ord> Heap<T> {
    pub fn new() -> Self {
        Self(Vec::new())
    }

    pub fn push(&mut self, value: T) {
        self.0.push(value);
        self.heap_insert();
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.0.is_empty() {
            return None;
        }

        let last = self.0.len() - 1;
        self.0.swap(0, last);
        let result = self.0.pop();
        self.heapify();
        result
    }

    fn heapify(&mut self) {
        let len = self.0.len();

        let mut index = 0;
        let mut left = index * 2 + 1;

        while left < len {
            let right = left + 1;
            let greatest = if right < len && self.0[left] < self.0[right] {
                right
            } else {
                left
            };

            if self.0[greatest] <= self.0[index] {
                break;
            }

            self.0.swap(index, greatest);
            index = greatest;
            left = index * 2 + 1;
        }
    }

    fn heap_insert(&mut self) {
        if self.0.is_empty() {
            return;
        }

        let mut index = self.0.len() - 1;
        if index == 0 {
            return;
        }
        let mut parent = (index - 1) / 2;

        while self.0[parent] < self.0[index] {
            self.0.swap(index, parent);
            index = parent;
            if index == 0 {
                break;
            }
            parent = (index - 1) / 2;
        }
    }
}

impl<T: Ord> Iterator for Heap<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.pop()
    }
}

#[test]
fn test_heap() {
    for _ in 0..1000 {
        let array: [u8; 32] = rand::random();
        let sorted = {
            let mut s = array.clone();
            s.sort_by(|a, b| b.cmp(a));
            s
        };

        let mut heap = Heap::new();

        for a in array {
            heap.push(a);
        }

        let heap_sorted: Vec<u8> = heap.collect();

        assert_eq!(heap_sorted, sorted);
    }
}

pub trait Component {
    fn do_sth(&self);
}

pub struct Component1;

impl Component for Component1 {
    fn do_sth(&self) {
        print!("1");
    }
}

pub struct Component2;

impl Component for Component2 {
    fn do_sth(&self) {
        print!("2");
    }
}

pub trait Decorator<T: Component>: Component {
    fn wrap(inner: T) -> Self;
}

struct DecoratorA<T> {
    inner: T,
}

impl<T: Component> Component for DecoratorA<T> {
    fn do_sth(&self) {
        self.inner.do_sth();
        print!("A");
    }
}

impl<T: Component> Decorator<T> for DecoratorA<T> {
    fn wrap(inner: T) -> Self {
        Self { inner }
    }
}

struct DecoratorB<T> {
    inner: T,
}

impl<T: Component> Component for DecoratorB<T> {
    fn do_sth(&self) {
        self.inner.do_sth();
        print!("B");
    }
}

impl<T: Component> Decorator<T> for DecoratorB<T> {
    fn wrap(inner: T) -> Self {
        Self { inner }
    }
}

#[test]
fn test_decorator() {
    let c1 = Component1;
    c1.do_sth();
    println!();
    let ab1 = DecoratorA::wrap(DecoratorB::wrap(Component1));
    ab1.do_sth();
    println!();
    let abbaa2 = DecoratorA::wrap(DecoratorB::wrap(DecoratorB::wrap(DecoratorA::wrap(
        DecoratorA::wrap(Component2),
    ))));
    abbaa2.do_sth();
    println!();

    // 在Rust中，如果不需要运行时动态装饰，就没有必要产生很多小对象
    // 装饰了好几轮，最后占用内存还是 Component2 的大小
    assert_eq!(
        std::mem::size_of::<
            DecoratorA<DecoratorB<DecoratorB<DecoratorA<DecoratorA<Component2>>>>>,
        >(),
        0
    );
}

use std::cmp::Ordering;

#[test]
fn test_netherlands_flag_partition() {
    let mut array = [7, 1, 2, 0, 8, 5, 3, 9, 2, 6, 5, 1, 0, 8, 7, 4];
    // sorted:      [0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9]
    // index(hex):  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F]
    assert_eq!(array.netherlands_flag_partition(2), (Some(4), Some(6)));
    assert_eq!(array.netherlands_flag_partition(7), (Some(0xB), Some(0xD)));
    assert_eq!(array.netherlands_flag_partition(-1), (None, Some(0)));
    assert_eq!(array.netherlands_flag_partition(0), (None, Some(2)));
    assert_eq!(
        array.netherlands_flag_partition(10),
        (Some(array.len()), None)
    );
    assert_eq!(
        array.netherlands_flag_partition(9),
        (Some(array.len() - 1), None)
    );
}

pub trait NetherlandsFlagPartition<T> {
    fn netherlands_flag_partition(&mut self, value: T) -> (Option<usize>, Option<usize>);
}

impl<T: Ord> NetherlandsFlagPartition<T> for [T] {
    // 返回相等部分和大于部分的起始索引
    fn netherlands_flag_partition(&mut self, value: T) -> (Option<usize>, Option<usize>) {
        let len = self.len();
        let mut left = None;
        let mut right = None;
        let mut i = 0;
        while i < right.unwrap_or(len) {
            match self[i].cmp(&value) {
                Ordering::Less => {
                    match left {
                        None => {
                            self.swap(0, i);
                            left = Some(0);
                        }
                        Some(left_value) => {
                            let new_left = left_value + 1;
                            self.swap(new_left, i);
                            left = Some(new_left);
                        }
                    }
                    i += 1;
                }
                Ordering::Equal => {
                    i += 1;
                }
                Ordering::Greater => {
                    match right {
                        None => {
                            self.swap(len - 1, i);
                            right = Some(len - 1);
                        }
                        Some(right_value) => {
                            let new_right = right_value - 1;
                            self.swap(new_right, i);
                            right = Some(new_right);
                        }
                    }

                    // i 不要自增，让下一次循环检查新换到前面的值
                }
            }
        }

        (left.map(|v| v + 1), right)
    }
}

use std::cmp::Ordering;

#[test]
fn test_netherlands_flag_partition() {
    let mut array = [7, 1, 2, 0, 8, 5, 3, 9, 2, 6, 5, 1, 0, 8, 7, 4];
    assert_eq!(
        array.netherlands_flag_partition(2),
        NetherlandsFlagResult::Three(4, 6)
    );
    assert_eq!(
        array.netherlands_flag_partition(7),
        NetherlandsFlagResult::Three(11, 13)
    );
    assert_eq!(
        array.netherlands_flag_partition(-1),
        NetherlandsFlagResult::Greater
    );
    assert_eq!(
        array.netherlands_flag_partition(0),
        NetherlandsFlagResult::ValueStart(2)
    );
    assert_eq!(
        array.netherlands_flag_partition(10),
        NetherlandsFlagResult::Less
    );
    assert_eq!(
        array.netherlands_flag_partition(9),
        NetherlandsFlagResult::ValueEnd(15)
    );

    let mut array = [2, 2, 2, 2, 2];
    assert_eq!(
        array.netherlands_flag_partition(2),
        NetherlandsFlagResult::Equal
    );
}

#[derive(Debug, Eq, PartialEq)]
pub enum NetherlandsFlagResult {
    /// 分为三部分，分别是 < value, == value, > value, 返回后两部分的起始索引
    Three(usize, usize),
    /// 分为两部分，== value, > value, 返回第二部分的起始索引
    ValueStart(usize),
    /// 分为两部分，< value, == value, 返回第二部分的起始索引
    ValueEnd(usize),
    /// 所有值都小于 value
    Less,
    /// 所有值都大于 value
    Greater,
    /// 所有值都等于 value
    Equal,
}

pub trait NetherlandsFlagPartition<T> {
    fn netherlands_flag_partition(&mut self, value: T) -> NetherlandsFlagResult;
}

impl<T: Ord> NetherlandsFlagPartition<T> for [T] {
    // 返回相等部分和大于部分的起始索引
    fn netherlands_flag_partition(&mut self, value: T) -> NetherlandsFlagResult {
        let len = self.len();
        let mut left = None;
        let mut right = None;
        let mut i = 0;
        while i < right.unwrap_or(len) {
            match self[i].cmp(&value) {
                Ordering::Less => {
                    match left {
                        None => {
                            self.swap(0, i);
                            left = Some(0);
                        }
                        Some(left_value) => {
                            let new_left = left_value + 1;
                            self.swap(new_left, i);
                            left = Some(new_left);
                        }
                    }
                    i += 1;
                }
                Ordering::Equal => {
                    i += 1;
                }
                Ordering::Greater => {
                    match right {
                        None => {
                            self.swap(len - 1, i);
                            right = Some(len - 1);
                        }
                        Some(right_value) => {
                            let new_right = right_value - 1;
                            self.swap(new_right, i);
                            right = Some(new_right);
                        }
                    }

                    // i 不要自增，让下一次循环检查新换到前面的值
                }
            }
        }

        match (left.map(|v| v + 1), right) {
            (None, Some(i)) => {
                if i == 0 {
                    NetherlandsFlagResult::Greater
                } else {
                    NetherlandsFlagResult::ValueStart(i)
                }
            }
            (Some(i), None) => {
                if i >= self.len() {
                    NetherlandsFlagResult::Less
                } else {
                    NetherlandsFlagResult::ValueEnd(i)
                }
            }
            (Some(i), Some(j)) => {
                if i >= self.len() {
                    NetherlandsFlagResult::Greater
                } else {
                    NetherlandsFlagResult::Three(i, j)
                }
            }
            (None, None) => NetherlandsFlagResult::Equal,
        }
    }
}

#[test]
fn test_quick_sort1() {
    for _ in 0..1000 {
        let mut array0: [u8; 32] = rand::random();
        let mut array1 = array0.clone();

        array0.sort();
        array1.quick_sort1();

        assert_eq!(array0, array1);
    }
}

pub trait QuickSort1 {
    fn quick_sort1(&mut self);
}

impl<T: Ord + Clone> QuickSort1 for [T] {
    fn quick_sort1(&mut self) {
        let len = self.len();
        if len < 2 {
            return;
        }

        let value = self[len - 1].clone();

        match self[..len - 1].partition(value) {
            // value 比所有元素都小，把 value 挪到第一个位置，排序剩下的
            Index::Less => {
                self.swap(0, len - 1);
                self[1..].quick_sort1();
            }
            // 把 value 与第一个大于区的数交换
            Index::Position(i) => {
                self.swap(i, len - 1);
                self[..i].quick_sort1();
                self[i + 1..].quick_sort1();
            }
            // value比所有元素都大，不动，排序前面所有的
            Index::Greater => {
                self[..len - 1].quick_sort1();
            }
        }
    }
}

#[test]
fn test_quick_sort2() {
    for _ in 0..1000 {
        let mut array0: [i32; 32] = random();
        let mut array1 = array0.clone();

        array0.sort();
        array1.quick_sort2();

        assert_eq!(array0, array1);
    }
}

pub trait QuickSort2 {
    fn quick_sort2(&mut self);
}

impl<T: Ord + Clone> QuickSort2 for [T] {
    fn quick_sort2(&mut self) {
        if self.len() < 2 {
            return;
        }

        let value = self[0].clone();

        match self.netherlands_flag_partition(value) {
            NetherlandsFlagResult::Three(start, end) => {
                self[..start].quick_sort2();
                self[end..].quick_sort2();
            }
            NetherlandsFlagResult::ValueStart(start) => {
                self[start..].quick_sort2();
            }
            NetherlandsFlagResult::ValueEnd(end) => {
                self[..end].quick_sort2();
            }
            NetherlandsFlagResult::Less | NetherlandsFlagResult::Greater => {
                self.quick_sort2();
            }
            NetherlandsFlagResult::Equal => {
                return;
            }
        }
    }
}

#[test]
fn test_quick_sort3() {
    for _ in 0..1000 {
        let mut array0: [i32; 32] = random();
        let mut array1 = array0.clone();

        array0.sort();
        array1.quick_sort3();

        assert_eq!(array0, array1);
    }
}

pub trait QuickSort3 {
    fn quick_sort3(&mut self);
}

impl<T: Ord + Clone> QuickSort for [T] {
    fn quick_sort3(&mut self) {
        if self.len() < 2 {
            return;
        }

        let index = rand::thread_rng().gen_range(0..self.len());
        let value = self[index].clone();

        match self.netherlands_flag_partition(value) {
            NetherlandsFlagResult::Three(start, end) => {
                self[..start].quick_sort3();
                self[end..].quick_sort3();
            }
            NetherlandsFlagResult::ValueStart(start) => {
                self[start..].quick_sort3();
            }
            NetherlandsFlagResult::ValueEnd(end) => {
                self[..end].quick_sort3();
            }
            NetherlandsFlagResult::Less | NetherlandsFlagResult::Greater => {
                self.quick_sort3();
            }
            NetherlandsFlagResult::Equal => {
                return;
            }
        }
    }
}

#[test]
fn test_merge_sort() {
    for _ in 0..100 {
        let mut array0: [u8; 32] = rand::random();
        let mut array1 = array0.clone();
        array0.merge_sort();
        array1.sort();
        assert_eq!(array0, array1);
    }
}

trait MergeSort {
    fn merge_sort(&mut self);
}

impl<T: Ord + Clone> MergeSort for [T] {
    fn merge_sort(&mut self) {
        let len = self.len();
        if len == 0 || len == 1 {
            return;
        }

        let mid = len >> 1;
        self[..mid].merge_sort();
        self[mid..].merge_sort();

        let mut i = 0;
        let mut j = mid;
        let mut vec = Vec::with_capacity(len);

        while i < mid && j < len {
            if self[i] <= self[j] {
                vec.push(self[i].clone());
                i += 1;
            } else {
                vec.push(self[j].clone());
                j += 1;
            }
        }

        while i < mid {
            vec.push(self[i].clone());
            i += 1;
        }

        while j < len {
            vec.push(self[j].clone());
            j += 1;
        }

        self.clone_from_slice(&vec);
    }
}

#[test]
fn test_get_descending_pairs() {
    for _ in 0..100 {
        let mut array0: [u8; 32] = rand::random();
        let mut array1 = array0.clone();
        let set0 = array0.get_descending_pairs();
        let set1 = array1.get_descending_pairs_simple();
        assert_eq!(set0, set1);
    }
}

trait DescendingPair<T> {
    fn get_descending_pairs(&mut self) -> HashSet<(T, T)>;
    fn get_descending_pairs_simple(&mut self) -> HashSet<(T, T)>;
}

impl<T: Ord + Clone + Hash> DescendingPair<T> for [T] {
    fn get_descending_pairs(&mut self) -> HashSet<(T, T)> {
        let mut set = HashSet::new();
        if self.len() < 2 {
            return set;
        }

        let mid = self.len() >> 1;
        let mut left = self[..mid].get_descending_pairs();
        let mut right = self[mid..].get_descending_pairs();
        set.extend(left.drain());
        set.extend(right.drain());

        let mut help = Vec::with_capacity(self.len());
        let mut j = 0;
        let mut k = mid;
        let len = self.len();

        while j < mid && k < len {
            if self[j] > self[k] {
                let mut temp = self[k..]
                    .iter()
                    .map(|v| (self[j].clone(), v.clone()))
                    .collect::<HashSet<_>>();
                set.extend(temp.drain());

                help.push(self[j].clone());
                j += 1;
            } else {
                help.push(self[k].clone());
                k += 1;
            }
        }

        help.extend_from_slice(&self[j..mid]);
        help.extend_from_slice(&self[k..]);

        assert_eq!(help.len(), self.len());
        self.clone_from_slice(&help);

        set
    }

    fn get_descending_pairs_simple(&mut self) -> HashSet<(T, T)> {
        let mut set = HashSet::new();
        for i in 0..self.len() {
            for j in 0..i {
                if self[j] > self[i] {
                    set.insert((self[j].clone(), self[i].clone()));
                }
            }
        }
        set
    }
}