1use rand::prelude::*;
 2use std::cmp::Ordering;
 3
 4pub fn post_inc(value: &mut usize) -> usize {
 5    let prev = *value;
 6    *value += 1;
 7    prev
 8}
 9
10pub fn find_insertion_index<'a, F, T, E>(slice: &'a [T], mut f: F) -> Result<usize, E>
11where
12    F: FnMut(&'a T) -> Result<Ordering, E>,
13{
14    use Ordering::*;
15
16    let s = slice;
17    let mut size = s.len();
18    if size == 0 {
19        return Ok(0);
20    }
21    let mut base = 0usize;
22    while size > 1 {
23        let half = size / 2;
24        let mid = base + half;
25        // mid is always in [0, size), that means mid is >= 0 and < size.
26        // mid >= 0: by definition
27        // mid < size: mid = size / 2 + size / 4 + size / 8 ...
28        let cmp = f(unsafe { s.get_unchecked(mid) })?;
29        base = if cmp == Greater { base } else { mid };
30        size -= half;
31    }
32    // base is always in [0, size) because base <= mid.
33    let cmp = f(unsafe { s.get_unchecked(base) })?;
34    if cmp == Equal {
35        Ok(base)
36    } else {
37        Ok(base + (cmp == Less) as usize)
38    }
39}
40
41pub struct RandomCharIter<T: Rng>(T);
42
43impl<T: Rng> RandomCharIter<T> {
44    pub fn new(rng: T) -> Self {
45        Self(rng)
46    }
47}
48
49impl<T: Rng> Iterator for RandomCharIter<T> {
50    type Item = char;
51
52    fn next(&mut self) -> Option<Self::Item> {
53        if self.0.gen_bool(1.0 / 5.0) {
54            Some('\n')
55        } else {
56            Some(self.0.gen_range(b'a'..b'z' + 1).into())
57        }
58    }
59}
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_find_insertion_index() {
67        assert_eq!(
68            find_insertion_index(&[0, 4, 8], |probe| Ok::<Ordering, ()>(probe.cmp(&2))),
69            Ok(1)
70        );
71    }
72}