rsalgo/base/
search.rs

1/// Dichotomy in interval `[lower_bound, upper_bound)`, return the first value that makes checker true.
2///
3/// # Examples
4///
5/// ```
6/// assert_eq!(Some(5), rsalgo::base::dichotomy(0, 10, |val| val >= 5));
7/// ```
8pub fn dichotomy<TC: Fn(isize) -> bool>(
9    lower_bound: isize,
10    upper_bound: isize,
11    checker: TC,
12) -> Option<isize> {
13    let mut l = lower_bound;
14    let mut r = upper_bound;
15    let mut ans = None;
16
17    while l < r {
18        let mid = (l + r) / 2;
19        if checker(mid) {
20            ans = Some(mid);
21            r = mid;
22        } else {
23            l = mid + 1;
24        }
25    }
26
27    ans
28}
29
30/// Get the position of the lower bound of value in the slice.
31///
32/// # Examples
33///
34/// ```
35/// let slice = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
36///
37/// assert_eq!(Some(5), rsalgo::base::lower_bound(&slice, &5));
38/// ```
39pub fn lower_bound<T: PartialOrd>(slice: &[T], value: &T) -> Option<usize> {
40    match dichotomy(0, slice.len() as isize, |pos| &slice[pos as usize] >= value) {
41        Some(val) => Some(val as usize),
42        None => None,
43    }
44}
45
46/// Get the position of the upper bound of value in the slice.
47///
48/// # Examples
49///
50/// ```
51/// let slice = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
52///
53/// assert_eq!(Some(6), rsalgo::base::upper_bound(&slice, &5));
54/// ```
55pub fn upper_bound<T: PartialOrd>(slice: &[T], value: &T) -> Option<usize> {
56    match dichotomy(0, slice.len() as isize, |pos| &slice[pos as usize] > value) {
57        Some(val) => Some(val as usize),
58        None => None,
59    }
60}
61
62/// Get the position interval that those values equal to the value.
63///
64/// # Examples
65///
66/// ```
67/// let slice = [0, 1, 2, 2, 2, 5, 6, 7, 8, 9];
68///
69/// assert_eq!(Some((2, 5)), rsalgo::base::equal_range(&slice, &2));
70/// ```
71pub fn equal_range<T: PartialOrd>(slice: &[T], value: &T) -> Option<(usize, usize)> {
72    match (lower_bound(slice, value), upper_bound(slice, value)) {
73        (Some(first), Some(last)) => Some((first, last)),
74        (Some(first), None) => Some((first, slice.len() as usize)),
75        (None, Some(last)) => Some((0, last)),
76        (None, None) => None,
77    }
78}
79
80/// Build a vector with the rank of each item in origin vector.
81///
82/// # Examples
83///
84/// ```
85/// let slice = [0, 1, 2, 1, 5];
86///
87/// assert_eq!([0, 1, 2, 1, 3], rsalgo::base::discretization(&slice).as_slice());
88/// ```
89pub fn discretization<T: PartialEq + Ord + Clone>(slice: &[T]) -> Vec<usize> {
90    let mut temp = slice.to_vec();
91    temp.sort();
92    temp.dedup();
93    let mut ans: Vec<usize> = Vec::new();
94    for item in slice {
95        ans.push(lower_bound(&temp, &item).unwrap());
96    }
97    ans
98}
99
100#[cfg(test)]
101mod tests {
102    use rand::Rng;
103
104    #[test]
105    fn dichotomy() {
106        assert_eq!(Some(5), super::dichotomy(0, 10, |val| val >= 5));
107        assert_eq!(None, super::dichotomy(0, 10, |val| val > 10));
108    }
109
110    #[test]
111    fn lower_bound() {
112        let slice = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
113        assert_eq!(Some(5), super::lower_bound(&slice, &5));
114        assert_eq!(Some(0), super::lower_bound(&slice, &-1));
115        assert_eq!(None, super::lower_bound(&slice, &10));
116    }
117
118    #[test]
119    fn upper_bound() {
120        let slice = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
121        assert_eq!(Some(6), super::upper_bound(&slice, &5));
122        assert_eq!(Some(0), super::upper_bound(&slice, &-1));
123        assert_eq!(None, super::upper_bound(&slice, &10));
124    }
125
126    #[test]
127    fn equal_range() {
128        let slice = [0, 1, 2, 2, 2, 5, 6, 7, 8, 9];
129        assert_eq!(Some((2, 5)), super::equal_range(&slice, &2));
130    }
131
132    #[test]
133    fn discretization() {
134        let slice = [0, 1, 2, 1, 5];
135        assert_eq!([0, 1, 2, 1, 3], super::discretization(&slice).as_slice());
136
137        const LEN: usize = 128;
138        let mut data = [0; LEN];
139        let mut rng = rand::thread_rng();
140        rng.fill(&mut data[..]);
141
142        let d_data = super::discretization(&data);
143        for &val in &d_data {
144            assert!(val < LEN);
145        }
146
147        for i in 0..LEN {
148            for j in 0..LEN {
149                assert!(data[i].cmp(&data[j]) == d_data[i].cmp(&d_data[j]));
150            }
151        }
152    }
153}
rsalgo/base/search.rs

rsalgo/base/
search.rs
