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
101
102
103
104
105
106
107
108

//! This crate is a stable sorting algorithm with O(n) worst-case storage
//! requirements, O(n log n) worst-case comparisons, and O(n) comparisons
//! on an already-sorted list, smoothly becoming O(n log n) as the sorted
//! sections (runs) get smaller and smaller.

#![cfg_attr(not(test), no_std)]

extern crate alloc;

mod find_run;
mod gallop;
mod insort;
mod merge;
mod sort;

use core::cmp::Ordering;
use core::convert::Infallible;
use sort::try_sort_by as try_sort_by_cmp;

type NeverResult<T> = Result<T, Infallible>;
#[inline(always)]
fn never<T>(x: Infallible) -> T {
    match x {}
}

pub fn try_sort_by_gt<T, E, C: Fn(&T, &T) -> Result<bool, E>>(
    list: &mut [T],
    cmp: C,
) -> Result<(), E> {
    try_sort_by_cmp(list, cmp)
}

#[inline]
pub fn try_sort_by<T, E, C: Fn(&T, &T) -> Result<Ordering, E>>(
    list: &mut [T],
    cmp: C,
) -> Result<(), E> {
    try_sort_by_cmp(list, ord_comparator(cmp))
}

#[inline]
pub fn sort_by_gt<T, C: Fn(&T, &T) -> bool>(list: &mut [T], is_greater: C) {
    try_sort_by_gt(list, move |a, b| -> NeverResult<_> { Ok(is_greater(a, b)) })
        .unwrap_or_else(never)
}

#[inline]
pub fn sort_by<T, C: Fn(&T, &T) -> Ordering>(list: &mut [T], cmp: C) {
    try_sort_by(list, move |a, b| -> NeverResult<_> { Ok(cmp(a, b)) }).unwrap_or_else(never)
}

#[inline]
pub fn sort<T: Ord>(list: &mut [T]) {
    sort_by(list, Ord::cmp)
}

trait Comparator<T> {
    type Error;
    fn is_gt(&self, lhs: &T, rhs: &T) -> Result<bool, Self::Error>;
    fn ordering(&self, lhs: &T, rhs: &T) -> Result<Ordering, Self::Error> {
        let ord = if self.is_gt(lhs, rhs)? {
            Ordering::Greater
        } else if self.is_gt(rhs, lhs)? {
            Ordering::Less
        } else {
            Ordering::Equal
        };
        Ok(ord)
    }
}

impl<F, T, E> Comparator<T> for F
where
    F: Fn(&T, &T) -> Result<bool, E>,
{
    type Error = E;
    fn is_gt(&self, lhs: &T, rhs: &T) -> Result<bool, E> {
        self(lhs, rhs)
    }
}

// really weird, idk why this is necessary...
#[cfg(test)]
pub(crate) fn comparator<T>(
    f: impl Fn(&T, &T) -> NeverResult<bool>,
) -> impl Comparator<T, Error = Infallible> {
    f
}
#[cfg(test)]
pub(crate) fn ord_t_comparator<T: Ord>() -> impl Comparator<T, Error = Infallible> {
    ord_comparator(|a: &T, b| Ok(a.cmp(b)))
}

pub(crate) fn ord_comparator<T, E, F: Fn(&T, &T) -> Result<Ordering, E>>(
    f: F,
) -> impl Comparator<T, Error = E> {
    struct OrdComparator<F>(F);
    impl<T, E, F: Fn(&T, &T) -> Result<Ordering, E>> Comparator<T> for OrdComparator<F> {
        type Error = E;
        fn is_gt(&self, lhs: &T, rhs: &T) -> Result<bool, E> {
            (self.0)(lhs, rhs).map(|ord| ord == Ordering::Greater)
        }
        fn ordering(&self, lhs: &T, rhs: &T) -> Result<Ordering, Self::Error> {
            (self.0)(lhs, rhs)
        }
    }
    OrdComparator(f)
}