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
/*#[inline] // this is much slower than the ones below (which is adopted from standard library)
pub(super) fn partition_point<T, P>(tab: &[T], mut pred: P) -> usize
where P: FnMut(&T, usize) -> bool
{
let mut len = tab.len();
let mut first = 0;
while len > 0 {
let half = len / 2;
let mid = first + half;
if pred(unsafe { tab.get_unchecked(mid) }, mid) { // tab[mid] < value
first = mid + 1;
len = len - half - 1;
} else {
len = half;
}
}
return first;
}*/
pub
/*#[inline]
pub(super) fn partition_index<F>(mut size: usize, mut f: F) -> usize
where F: FnMut(usize) -> bool,
{
// INVARIANTS:
// - 0 <= left <= left + size = right <= self.len()
// - f returns true for everything in self[..left]
// - f returns false for everything in self[right..]
let mut left = 0;
let mut right = size;
while size > 0 { // size > 0 | in original code was: left < right
let mid = left + size / 2;
if f(mid) {
left = mid + 1;
} else {
right = mid;
}
size = right - left;
}
right // left==right | in original code was: left
}*/
/*#[inline]
pub(super) fn partition_index<F>(mut left: usize, mut right: usize, mut f: F) -> usize
where F: FnMut(usize) -> bool,
{
// INVARIANTS:
// - 0 <= left <= left + size = right <= self.len()
// - f returns true for everything in self[..left]
// - f returns false for everything in self[right..]
let mut size = right - left;
while size > 0 { // size > 0 | in original code was: left < right
let mid = left + size / 2;
if f(mid) {
left = mid + 1;
} else {
right = mid;
}
size = right - left;
}
right // left==right | in original code was: left
}*/