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
 10/// Extend a sorted vector with a sorted sequence of items, maintaining the vector's sort order and
 11/// enforcing a maximum length. Sort the items according to the given callback. Before calling this,
 12/// both `vec` and `new_items` should already be sorted according to the `cmp` comparator.
 13pub fn extend_sorted<T, I, F>(vec: &mut Vec<T>, new_items: I, limit: usize, mut cmp: F)
 14where
 15    I: IntoIterator<Item = T>,
 16    F: FnMut(&T, &T) -> Ordering,
 17{
 18    let mut start_index = 0;
 19    for new_item in new_items {
 20        if let Err(i) = vec[start_index..].binary_search_by(|m| cmp(m, &new_item)) {
 21            let index = start_index + i;
 22            if vec.len() < limit {
 23                vec.insert(index, new_item);
 24            } else if index < vec.len() {
 25                vec.pop();
 26                vec.insert(index, new_item);
 27            }
 28            start_index = index;
 29        }
 30    }
 31}
 32
 33pub fn find_insertion_index<'a, F, T, E>(slice: &'a [T], mut f: F) -> Result<usize, E>
 34where
 35    F: FnMut(&'a T) -> Result<Ordering, E>,
 36{
 37    use Ordering::*;
 38
 39    let s = slice;
 40    let mut size = s.len();
 41    if size == 0 {
 42        return Ok(0);
 43    }
 44    let mut base = 0usize;
 45    while size > 1 {
 46        let half = size / 2;
 47        let mid = base + half;
 48        // mid is always in [0, size), that means mid is >= 0 and < size.
 49        // mid >= 0: by definition
 50        // mid < size: mid = size / 2 + size / 4 + size / 8 ...
 51        let cmp = f(unsafe { s.get_unchecked(mid) })?;
 52        base = if cmp == Greater { base } else { mid };
 53        size -= half;
 54    }
 55    // base is always in [0, size) because base <= mid.
 56    let cmp = f(unsafe { s.get_unchecked(base) })?;
 57    if cmp == Equal {
 58        Ok(base)
 59    } else {
 60        Ok(base + (cmp == Less) as usize)
 61    }
 62}
 63
 64pub struct RandomCharIter<T: Rng>(T);
 65
 66impl<T: Rng> RandomCharIter<T> {
 67    pub fn new(rng: T) -> Self {
 68        Self(rng)
 69    }
 70}
 71
 72impl<T: Rng> Iterator for RandomCharIter<T> {
 73    type Item = char;
 74
 75    fn next(&mut self) -> Option<Self::Item> {
 76        if self.0.gen_bool(1.0 / 5.0) {
 77            Some('\n')
 78        } else {
 79            Some(self.0.gen_range(b'a'..b'z' + 1).into())
 80        }
 81    }
 82}
 83
 84#[cfg(test)]
 85mod tests {
 86    use super::*;
 87
 88    #[test]
 89    fn test_find_insertion_index() {
 90        assert_eq!(
 91            find_insertion_index(&[0, 4, 8], |probe| Ok::<Ordering, ()>(probe.cmp(&2))),
 92            Ok(1)
 93        );
 94    }
 95
 96    #[test]
 97    fn test_extend_sorted() {
 98        let mut vec = vec![];
 99
100        extend_sorted(&mut vec, vec![21, 17, 13, 8, 1, 0], 5, |a, b| b.cmp(a));
101        assert_eq!(vec, &[21, 17, 13, 8, 1]);
102
103        extend_sorted(&mut vec, vec![101, 19, 17, 8, 2], 8, |a, b| b.cmp(a));
104        assert_eq!(vec, &[101, 21, 19, 17, 13, 8, 2, 1]);
105
106        extend_sorted(&mut vec, vec![1000, 19, 17, 9, 5], 8, |a, b| b.cmp(a));
107        assert_eq!(vec, &[1000, 101, 21, 19, 17, 13, 9, 8]);
108    }
109}