aoclib_rs/
binary_search.rs

1use std::ops::{Add, Div};
2
3/// For example usage, see <https://github.com/glennhartmann/aoc19> day_14.rs.
4pub trait BinarySearchable<I, V>
5where
6    I: Copy + PartialOrd + Add<Output = I> + Div<usize, Output = I>,
7{
8    /// Gets the value at the given index. Called at with the midpoint at the beginning of each
9    /// loop. Can mutate internal state.
10    fn get_val(&mut self, index: &I) -> V;
11
12    /// Called immediately after retrieving the `val` at the midpoint using `get_val()`. Returns
13    /// whether the result has been found. Returning `true` will exit the loop, returning `val` and its
14    /// index. Can mutate internal state.
15    fn found_result(&mut self, val: &V, lower_bound: &I, mid_point: &I, upper_bound: &I) -> bool;
16
17    /// Called immediately after `found_result()`, provided that `found_result()` returned false. The
18    /// purpose is to mutate `lower_bound` and `upper_bound`. The return value indicates whether to
19    /// abort the search in failure. Returning `true` will result in the loop exiting and returning
20    /// `None`. Can mutate internal state.
21    fn set_next_bounds(
22        &mut self,
23        val: &V,
24        lower_bound: &mut I,
25        mid_point: &I,
26        upper_bound: &mut I,
27    ) -> bool;
28
29    fn binary_search(&mut self, mut lower_bound: I, mut upper_bound: I) -> Option<(I, V)> {
30        while upper_bound > lower_bound {
31            let mid_point = (lower_bound + upper_bound) / 2;
32            let val = self.get_val(&mid_point);
33            if self.found_result(&val, &lower_bound, &mid_point, &upper_bound) {
34                return Some((mid_point, val));
35            }
36            if self.set_next_bounds(&val, &mut lower_bound, &mid_point, &mut upper_bound) {
37                break;
38            }
39        }
40
41        None
42    }
43}
44
45pub struct BinarySearchableVec<V> {
46    v: Vec<V>,
47    t: V,
48}
49
50impl<V> BinarySearchableVec<V> {
51    pub fn new(value: Vec<V>, target: V) -> Self {
52        Self {
53            v: value,
54            t: target,
55        }
56    }
57}
58
59impl<V> BinarySearchable<usize, V> for BinarySearchableVec<V>
60where
61    V: Copy + PartialOrd + PartialEq,
62{
63    fn get_val(&mut self, index: &usize) -> V {
64        self.v[*index]
65    }
66
67    fn found_result(
68        &mut self,
69        val: &V,
70        _lower_bound: &usize,
71        _index: &usize,
72        _upper_bound: &usize,
73    ) -> bool {
74        *val == self.t
75    }
76
77    fn set_next_bounds(
78        &mut self,
79        val: &V,
80        lower_bound: &mut usize,
81        index: &usize,
82        upper_bound: &mut usize,
83    ) -> bool {
84        if *lower_bound == *index {
85            return true;
86        }
87
88        if *val > self.t {
89            *upper_bound = *index;
90        } else if *val < self.t {
91            *lower_bound = *index;
92        } else {
93            panic!("should be impossible");
94        }
95
96        false
97    }
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103
104    #[test]
105    fn test_normal() {
106        let v = vec![1, 2, 3, 4, 5];
107        let l = v.len();
108        let mut bs = BinarySearchableVec::new(v, 3);
109        assert_eq!(bs.binary_search(0, l), Some((2, 3)));
110    }
111
112    #[test]
113    fn test_upper() {
114        let v = vec![1, 2, 3, 4, 5];
115        let l = v.len();
116        let mut bs = BinarySearchableVec::new(v, 5);
117        assert_eq!(bs.binary_search(0, l), Some((4, 5)));
118    }
119
120    #[test]
121    fn test_lower() {
122        let v = vec![1, 2, 3, 4, 5];
123        let l = v.len();
124        let mut bs = BinarySearchableVec::new(v, 1);
125        assert_eq!(bs.binary_search(0, l), Some((0, 1)));
126    }
127
128    #[test]
129    fn test_even_mid_upper() {
130        let v = vec![1, 2, 3, 4];
131        let l = v.len();
132        let mut bs = BinarySearchableVec::new(v, 3);
133        assert_eq!(bs.binary_search(0, l), Some((2, 3)));
134    }
135
136    #[test]
137    fn test_even_mid_lower() {
138        let v = vec![1, 2, 3, 4];
139        let l = v.len();
140        let mut bs = BinarySearchableVec::new(v, 2);
141        assert_eq!(bs.binary_search(0, l), Some((1, 2)));
142    }
143}
aoclib_rs/binary_search.rs

aoclib_rs/
binary_search.rs
