lib 0.0.2

LIB: Math and container utilities for Rust. Notice: study purpose, not production ready.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

use std::cmp::Ordering;
use std::cmp::Ordering::Greater;
use std::{ptr};
use std::mem::{ MaybeUninit};
use crate::datas::array::Array;

pub fn merge_sort<T>(l:&mut [T], a:usize, b:usize,cmp:fn(&T,&T)->Ordering)
where T:{
    //when only 1 or no element, no need to sort
    if(b-a<=1){
        return;
    }
    //create a temp array to store
    let mut tmp=unsafe{Array::<MaybeUninit<T>>::with_uninit(b-a)};
    merge_sort_recur(l,a,b,&mut tmp,cmp);
}
pub fn merge_sort_recur<T>(l:&mut [T], a:usize, b:usize, tmp:&mut [MaybeUninit<T>], cmp:fn(&T,&T)->Ordering)
where T:{
    let len=b-a;
    //when only 1 or no element, no need to sort
    if(b-a<=1){
        return;
    }
    //goal: make all cmp return less or equal
    if(len==2&&cmp(&l[a],&l[a+1])==Greater){
        l.swap(a,a+1);
        return;
    }
    /*
    if(len<16){
        insertion_sort(l,a,b);
        return;
    }
    */
    let m:usize=a+len/2;
    merge_sort_recur(l,a,m,tmp,cmp);
    merge_sort_recur(l,m,b,tmp,cmp);
    merge(l,a,m,b,tmp,cmp);
}
pub fn merge<T>(l:&mut[T],a:usize,m:usize,b:usize,tmp:&mut [MaybeUninit<T>],cmp:fn(&T,&T)->Ordering)
where T:
{
    let mut i_left = a;
    let mut i_right = m;
    let mut i_tmp = 0;
    unsafe {
        while (i_left < m && i_right < b) {
            //less/equal
            if (cmp(&l[i_left], &l[i_right])!=Greater) {
                set_uninit(&mut tmp[i_tmp], &mut l[i_left]);
                i_left += 1;
                i_tmp += 1;
            } else {
                set_uninit(&mut tmp[i_tmp], &mut l[i_right]);
                i_right += 1;
                i_tmp += 1;
            }
        }
        while (i_left < m) {
            set_uninit(&mut tmp[i_tmp], &mut l[i_left]);
            i_left += 1;
            i_tmp += 1;
        }
        while (i_right < b) {
            set_uninit(&mut tmp[i_tmp], &mut l[i_right]);
            i_right += 1;
            i_tmp += 1;
        }
        i_tmp = a;
        while (i_tmp < b) {
            set_init_from_uninit(&mut l[i_tmp], &mut tmp[i_tmp]);
            i_tmp = i_tmp + 1;
        }
    }
}
pub fn insertion_sort<T>(l:&mut [T],a:usize,b:usize,cmp:fn(&T,&T)->Ordering)where T:PartialOrd{
    for i in a + 1..b {
        let mut j = i;
        while j > a && cmp(&l[j - 1], &l[j]) == Greater {
            l.swap(j - 1, j);
            j -= 1;
        }
    }
}
unsafe fn set_uninit<T>(dst: &mut MaybeUninit<T>,src: &mut T) {
    unsafe{
        // SAFETY: src 必须有效且不会再使用，dst 必须未初始化
        let val = ptr::read(src);              // move 出 src
        ptr::write(dst.as_mut_ptr(), val);
        // 写入 dst
    }
}
unsafe fn set_init_from_uninit<T>(dst: &mut T,src: &mut MaybeUninit<T>) {
    // SAFETY: src 必须已初始化且不会再使用
    unsafe{
        let val = ptr::read(src.as_ptr());          // move 出 src
        ptr::write(dst, val);
        // 写入 dst
    }
}