shine-stdext 0.2.0

SHINE. General utilities for the general purpose multi-threaded rendering engine.
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

use std::cmp::Ordering;

/// Extension trait for slices of #Ord items
pub trait SliceOrdExt {
    type Item: Ord;

    fn lower_bound(&self, x: &Self::Item) -> usize;

    fn lower_bound_by<'a, F>(&'a self, f: F) -> usize
    where
        F: FnMut(&'a Self::Item) -> Ordering;
}

impl<T: Ord> SliceOrdExt for [T] {
    type Item = T;

    fn lower_bound(&self, x: &T) -> usize {
        self.lower_bound_by(|y| y.cmp(x))
    }

    fn lower_bound_by<'a, F>(&'a self, mut f: F) -> usize
    where
        F: FnMut(&'a Self::Item) -> Ordering,
    {
        let mut size = self.len();
        if size == 0 {
            return 0;
        }
        let mut base = 0usize;
        while size > 1 {
            let half = size / 2;
            let mid = base + half;
            let cmp = f(unsafe { self.get_unchecked(mid) });
            base = if cmp == Ordering::Less { mid } else { base };
            size -= half;
        }
        let cmp = f(unsafe { self.get_unchecked(base) });
        base + (cmp == Ordering::Less) as usize
    }
}