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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
* Copyright (c) Meta Platforms, Inc. and affiliates.
*
* This source code is licensed under the MIT license found in the
* LICENSE file in the root directory of this source tree.
*/
use std::cmp::Ordering;
use std::collections::VecDeque;
use Ordering::Equal;
use Ordering::Greater;
use Ordering::Less;
// Based on rust stdlib slice::binary_search_by:
// https://github.com/rust-lang/rust/blob/dbad8c93680710e80c54cbaf8416821f7a5750c8/library/core/src/slice/mod.rs#L1721
pub trait BinarySearchBy<T> {
/// Binary searches this sorted slice with a comparator function.
///
/// The comparator function should implement an order consistent
/// with the sort order of the underlying slice, returning an
/// order code that indicates whether its argument is `Less`,
/// `Equal` or `Greater` the desired target.
///
/// If the value is found then [`Result::Ok`] is returned, containing the
/// index of the matching element. If there are multiple matches, then any
/// one of the matches could be returned. If the value is not found then
/// [`Result::Err`] is returned, containing the index where a matching
/// element could be inserted while maintaining sorted order.
fn bsearch_by<F>(&self, f: F) -> Result<usize, usize>
where
F: FnMut(&T) -> Ordering;
}
impl<T> BinarySearchBy<T> for VecDeque<T> {
fn bsearch_by<F>(&self, mut f: F) -> Result<usize, usize>
where
F: FnMut(&T) -> Ordering,
{
let s = self;
let mut size = s.len();
if size == 0 {
return Err(0);
}
let mut base = 0usize;
while size > 1 {
let half = size / 2;
let mid = base + half;
// mid is always in [0, size), that means mid is >= 0 and < size.
// mid >= 0: by definition
// mid < size: mid = size / 2 + size / 4 + size / 8 ...
let cmp = f(s.get(mid).unwrap());
base = if cmp == Greater { base } else { mid };
size -= half;
}
// base is always in [0, size) because base <= mid.
let cmp = f(s.get(base).unwrap());
if cmp == Equal {
Ok(base)
} else {
Err(base + (cmp == Less) as usize)
}
}
}