timsort 0.1.3

Rust implementation of the modified MergeSort used in Python and Java
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

//! The galloping search algorithm.

#[cfg(test)]
mod tests;

use crate::Comparator;
use core::cmp::Ordering;

#[derive(Copy, Clone)]
pub(crate) enum Mode {
    Forward,
    Reverse,
}

/// Returns the index where key should be inserted, assuming it shoul be placed
/// at the beginning of any cluster of equal items.
pub(crate) fn gallop_left<T, C: Comparator<T>>(
    key: &T,
    list: &[T],
    mode: Mode,
    cmp: &C,
) -> Result<usize, C::Error> {
    let (mut base, mut lim) = gallop(key, list, mode, cmp)?;
    while lim != 0 {
        let ix = base + (lim / 2);
        match cmp.ordering(&list[ix], key)? {
            Ordering::Less => {
                base = ix + 1;
                lim -= 1;
            }
            Ordering::Greater => (),
            Ordering::Equal => {
                if ix == 0 || cmp.is_gt(key, &list[ix - 1])? {
                    base = ix;
                    break;
                }
            }
        };
        lim /= 2;
    }
    Ok(base)
}

/// Returns the index where key should be inserted, assuming it shoul be placed
/// at the end of any cluster of equal items.
pub(crate) fn gallop_right<T, C: Comparator<T>>(
    key: &T,
    list: &[T],
    mode: Mode,
    cmp: &C,
) -> Result<usize, C::Error> {
    let list_len = list.len();
    let (mut base, mut lim) = gallop(key, list, mode, cmp)?;
    while lim != 0 {
        let ix = base + (lim / 2);
        match cmp.ordering(&list[ix], key)? {
            Ordering::Less => {
                base = ix + 1;
                lim -= 1;
            }
            Ordering::Greater => (),
            Ordering::Equal => {
                base = ix + 1;
                if ix == list_len - 1 || cmp.is_gt(&list[ix + 1], key)? {
                    break;
                } else {
                    lim -= 1;
                }
            }
        };
        lim /= 2;
    }
    Ok(base)
}

fn gallop<T, C: Comparator<T>>(
    key: &T,
    list: &[T],
    mode: Mode,
    cmp: &C,
) -> Result<(usize, usize), C::Error> {
    let list_len = list.len();
    if list_len == 0 {
        return Ok((0, 0));
    }
    let ret = match mode {
        Mode::Forward => {
            let mut prev_val = 0;
            let mut next_val = 1;
            while next_val < list_len {
                match cmp.ordering(&list[next_val], key)? {
                    Ordering::Less => {
                        prev_val = next_val;
                        next_val = ((next_val + 1) * 2) - 1;
                    }
                    Ordering::Greater => {
                        break;
                    }
                    Ordering::Equal => {
                        next_val += 1;
                        break;
                    }
                }
            }
            if next_val > list_len {
                next_val = list_len;
            }
            (prev_val, next_val - prev_val)
        }
        Mode::Reverse => {
            let mut prev_val = list_len;
            let mut next_val = ((prev_val + 1) / 2) - 1;
            while cmp.is_gt(&list[next_val], key)? {
                prev_val = next_val + 1;
                next_val = (next_val + 1) / 2;
                if next_val != 0 {
                    next_val -= 1;
                } else {
                    break;
                }
            }
            (next_val, prev_val - next_val)
        }
    };
    Ok(ret)
}