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
pub use smallvec::SmallVec;
use std::cmp::Ordering;
pub trait SmallVecOps {
type Item;
fn binary_search_by<F>(&self, f:F) -> Result<usize,usize>
where F:FnMut(&Self::Item) -> Ordering;
fn binary_search(&self, t:&Self::Item) -> Result<usize, usize>
where Self::Item:Ord;
}
impl<T:smallvec::Array> SmallVecOps for SmallVec<T> {
type Item = <T as smallvec::Array>::Item;
#[allow(unsafe_code)]
fn binary_search_by<F>(&self, mut f:F) -> Result<usize, usize>
where F:FnMut(&Self::Item) -> Ordering {
let s = self;
let mut size = s.len();
if size == 0 {
return Err(0);
}
let mut base = 0usize;
while size > 1 {
let half = size / 2;
let mid = base + half;
let cmp = f(unsafe { s.get_unchecked(mid) });
base = if cmp == Ordering::Greater { base } else { mid };
size -= half;
}
let cmp = f(unsafe { s.get_unchecked(base) });
if cmp == Ordering::Equal { Ok(base) } else { Err(base + (cmp == Ordering::Less) as usize) }
}
fn binary_search(&self, t:&Self::Item) -> Result<usize, usize>
where Self::Item:Ord {
self.binary_search_by(|p| p.cmp(t))
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::iter::FromIterator;
#[test]
fn test_binary_search_by() {
let v = SmallVec::<[usize;4]>::from_iter([5,10,20,40].iter().copied());
assert_eq!(v.binary_search_by(|probe| probe.cmp(&0)), Err(0));
assert_eq!(v.binary_search_by(|probe| probe.cmp(&5)), Ok(0));
assert_eq!(v.binary_search_by(|probe| probe.cmp(&6)), Err(1));
assert_eq!(v.binary_search_by(|probe| probe.cmp(&9)), Err(1));
assert_eq!(v.binary_search_by(|probe| probe.cmp(&10)), Ok(1));
assert_eq!(v.binary_search_by(|probe| probe.cmp(&11)), Err(2));
}
#[test]
fn test_binary_search() {
let v = SmallVec::<[usize;4]>::from_iter([5,10,20,40].iter().copied());
assert_eq!(v.binary_search(&0), Err(0));
assert_eq!(v.binary_search(&5), Ok(0));
assert_eq!(v.binary_search(&6), Err(1));
assert_eq!(v.binary_search(&9), Err(1));
assert_eq!(v.binary_search(&10), Ok(1));
assert_eq!(v.binary_search(&11), Err(2));
}
}