dezoomify_rs/generic/
dichotomy_2d.rs

1#[derive(Default, Debug)]
2pub struct Dichotomy {
3    min: u32,
4    max: Option<u32>,
5}
6
7impl Dichotomy {
8    fn best_guess(&self) -> u32 {
9        if let Some(max) = self.max {
10            (max + self.min) / 2
11        } else {
12            self.min * 3 + 1
13        }
14    }
15    fn next(&mut self, previous_success: bool) -> Option<u32> {
16        let last_guess = self.best_guess();
17        if previous_success {
18            self.min = last_guess;
19        } else {
20            self.max = Some(last_guess)
21        }
22        let next_guess = self.best_guess();
23        if next_guess != last_guess { Some(next_guess) } else { None }
24    }
25}
26
27#[derive(Debug)]
28pub enum Dichotomy2d {
29    Diagonal(Dichotomy),
30    Orientation { diagonal: u32 },
31    LastDim { diagonal: u32, is_landscape: bool, last_dim: Dichotomy },
32}
33
34impl Dichotomy2d {
35    pub fn next(&mut self, previous_success: bool) -> Option<(u32, u32)> {
36        let mut next = None;
37        let res = match self {
38            Dichotomy2d::Diagonal(d) => {
39                if let Some(n) = d.next(previous_success) {
40                    Some((n, n))
41                } else {
42                    let diagonal = d.best_guess();
43                    next = Some(Dichotomy2d::Orientation { diagonal });
44                    Some((diagonal + 1, diagonal))
45                }
46            },
47            Dichotomy2d::Orientation { diagonal } => {
48                let dichotomy = Dichotomy {
49                    min: *diagonal + previous_success as u32,
50                    max: None,
51                };
52                let best = dichotomy.best_guess();
53                next = Some(Dichotomy2d::LastDim {
54                    diagonal: *diagonal,
55                    is_landscape: previous_success,
56                    last_dim: dichotomy,
57                });
58                if previous_success {
59                    Some((best, *diagonal))
60                } else {
61                    Some((*diagonal, best))
62                }
63            },
64            Dichotomy2d::LastDim { diagonal, is_landscape, last_dim } => {
65                last_dim.next(previous_success).map(|next| if *is_landscape {
66                    (next, *diagonal)
67                } else {
68                    (*diagonal, next)
69                })
70            }
71        };
72        if let Some(next) = next {
73            *self = next;
74        }
75        res
76    }
77}
78
79impl Default for Dichotomy2d {
80    fn default() -> Self {
81        Dichotomy2d::Diagonal(Default::default())
82    }
83}
84
85#[test]
86fn test_dichotomy1d() {
87    for mystery in 0..1000 {
88        let mut d: Dichotomy = Default::default();
89        let mut tries = 1;
90        while let Some(prop) = d.next(d.best_guess() <= mystery) {
91            tries += 1;
92            assert!(tries <= 20, "guessed {} on {}th try", prop, tries);
93        }
94        assert_eq!(d.best_guess(), mystery,
95                   "Guessed {} instead of {} in {} tries", d.best_guess(), mystery, tries);
96    }
97}
98
99#[test]
100fn test_dichotomy2d() {
101    for x in 0..10 {
102        for y in 0..10 {
103            let mut d: Dichotomy2d = Default::default();
104            let mut tries = 1;
105            let mut guess = (1, 1);
106            while let Some(g) = d.next(guess.0 <= x && guess.1 <= y) {
107                guess = g;
108                tries += 1;
109                assert!(tries <= 20, "guessed {:?} on {}th try", g, tries);
110            }
111            assert_eq!(guess, (x, y),
112                       "Guessed {:?} instead of {:?} in {} tries", guess, (x, y), tries);
113        }
114    }
115}
dezoomify_rs/generic/dichotomy_2d.rs

dezoomify_rs/generic/
dichotomy_2d.rs
