use std::cmp::Ordering::{self, Equal, Greater, Less};
#[inline]
pub(crate) fn leaf_search<'a, T, F>(
ord: Ordering,
slice: &'a [T],
f: F,
) -> Option<usize>
where
F: FnMut(&'a T) -> Ordering,
{
match ord {
Less => binary_search_lt(slice, f),
Equal => slice.binary_search_by(f).ok(),
Greater => binary_search_gt(slice, f),
}
}
#[inline]
pub(crate) fn binary_search_gt<'a, T, F>(
slice: &'a [T],
mut f: F,
) -> Option<usize>
where
F: FnMut(&'a T) -> Ordering,
{
let s = slice;
let mut size = s.len();
if size == 0 {
return None;
}
let mut base = size - 1;
while size > 1 {
let half = size / 2;
let mid = base - half;
let cmp = f(unsafe { s.get_unchecked(mid) });
base = if cmp == Greater { mid } else { base };
size -= half;
}
let cmp = f(unsafe { s.get_unchecked(base) });
if cmp == Greater {
Some(base)
} else {
None
}
}
#[inline]
pub(crate) fn binary_search_lt<'a, T, F>(
slice: &'a [T],
mut f: F,
) -> Option<usize>
where
F: FnMut(&'a T) -> Ordering,
{
let s = slice;
let mut size = s.len();
if size == 0 {
return None;
}
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 == Less { mid } else { base };
size -= half;
}
let cmp = f(unsafe { s.get_unchecked(base) });
if cmp == Less {
Some(base)
} else {
None
}
}
#[inline]
pub(crate) fn binary_search_lub<'a, T, F>(
s: &'a [T],
f: F,
) -> Option<usize>
where
F: FnMut(&'a T) -> ::std::cmp::Ordering,
{
match s.binary_search_by(f) {
Ok(i) => Some(i),
Err(i) if i == 0 => None,
Err(i) => Some(i - 1),
}
}
#[test]
fn test_binary_search_lub() {
let s = &*vec![4, 5, 5, 6, 9];
assert_eq!(binary_search_lub(s, |e| e.cmp(&3)), None);
assert_eq!(binary_search_lub(s, |e| e.cmp(&4)), Some(0));
assert_eq!(binary_search_lub(s, |e| e.cmp(&5)), Some(2));
assert_eq!(binary_search_lub(s, |e| e.cmp(&6)), Some(3));
assert_eq!(binary_search_lub(s, |e| e.cmp(&7)), Some(3));
assert_eq!(binary_search_lub(s, |e| e.cmp(&8)), Some(3));
assert_eq!(binary_search_lub(s, |e| e.cmp(&9)), Some(4));
assert_eq!(binary_search_lub(s, |e| e.cmp(&10)), Some(4));
let s: &[u8] = &*vec![];
assert_eq!(binary_search_lub(s, |e| e.cmp(&8)), None);
}
#[test]
fn test_binary_search_gt() {
let s = &*vec![4, 5, 5, 6, 9];
assert_eq!(binary_search_gt(s, |e| e.cmp(&3)), Some(0));
assert_eq!(binary_search_gt(s, |e| e.cmp(&4)), Some(1));
assert_eq!(binary_search_gt(s, |e| e.cmp(&5)), Some(3));
assert_eq!(binary_search_gt(s, |e| e.cmp(&6)), Some(4));
assert_eq!(binary_search_gt(s, |e| e.cmp(&7)), Some(4));
assert_eq!(binary_search_gt(s, |e| e.cmp(&8)), Some(4));
assert_eq!(binary_search_gt(s, |e| e.cmp(&9)), None);
assert_eq!(binary_search_gt(s, |e| e.cmp(&10)), None);
let s: &[u8] = &*vec![];
assert_eq!(binary_search_gt(s, |e| e.cmp(&8)), None);
}
#[test]
fn test_binary_search_lt() {
let s = &*vec![4, 5, 5, 6, 9];
assert_eq!(binary_search_lt(s, |e| e.cmp(&3)), None);
assert_eq!(binary_search_lt(s, |e| e.cmp(&4)), None);
assert_eq!(binary_search_lt(s, |e| e.cmp(&5)), Some(0));
assert_eq!(binary_search_lt(s, |e| e.cmp(&6)), Some(2));
assert_eq!(binary_search_lt(s, |e| e.cmp(&7)), Some(3));
assert_eq!(binary_search_lt(s, |e| e.cmp(&8)), Some(3));
assert_eq!(binary_search_lt(s, |e| e.cmp(&9)), Some(3));
assert_eq!(binary_search_lt(s, |e| e.cmp(&10)), Some(4));
let s: &[u8] = &*vec![];
assert_eq!(binary_search_lt(s, |e| e.cmp(&8)), None);
}