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