tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

mod.rs (2785B)

      1 mod parallel;
      2 mod serial;
      3 
      4 pub use parallel::{AsyncTester, ParallelProblemSolver};
      5 pub use serial::{SerialProblemSolver, SyncTester};
      6 
      7 pub struct ProblemSolver {
      8    width: usize,
      9    depth: usize,
     10 
     11    cache: Vec<Vec<Option<bool>>>,
     12 
     13    solution: Vec<usize>,
     14    idx: usize,
     15 
     16    dirty: bool,
     17 }
     18 
     19 impl ProblemSolver {
     20    pub fn new(width: usize, depth: usize) -> Self {
     21        Self {
     22            width,
     23            depth,
     24            cache: vec![vec![None; depth]; width],
     25 
     26            solution: vec![0; width],
     27            idx: 0,
     28 
     29            dirty: false,
     30        }
     31    }
     32 }
     33 
     34 impl ProblemSolver {
     35    pub fn bail(&mut self) -> bool {
     36        if self.try_advance_source() {
     37            true
     38        } else {
     39            self.try_backtrack()
     40        }
     41    }
     42 
     43    pub fn has_missing_cell(&self) -> Option<usize> {
     44        self.cache
     45            .iter()
     46            .position(|row| row.iter().all(|c| *c == Some(false)))
     47    }
     48 
     49    fn is_cell_missing(&self, res_idx: usize, source_idx: usize) -> bool {
     50        if let Some(false) = self.cache[res_idx][source_idx] {
     51            return true;
     52        }
     53        false
     54    }
     55 
     56    fn is_current_cell_missing(&self) -> bool {
     57        let res_idx = self.idx;
     58        let source_idx = self.solution[res_idx];
     59        let cell = &self.cache[res_idx][source_idx];
     60        if let Some(false) = cell {
     61            return true;
     62        }
     63        false
     64    }
     65 
     66    pub fn try_advance_resource(&mut self) -> bool {
     67        if self.idx >= self.width - 1 {
     68            false
     69        } else {
     70            self.idx += 1;
     71            while self.is_current_cell_missing() {
     72                if !self.try_advance_source() {
     73                    return false;
     74                }
     75            }
     76            true
     77        }
     78    }
     79 
     80    pub fn try_advance_source(&mut self) -> bool {
     81        while self.solution[self.idx] < self.depth - 1 {
     82            self.solution[self.idx] += 1;
     83            if !self.is_current_cell_missing() {
     84                return true;
     85            }
     86        }
     87        false
     88    }
     89 
     90    pub fn try_backtrack(&mut self) -> bool {
     91        while self.solution[self.idx] == self.depth - 1 {
     92            if self.idx == 0 {
     93                return false;
     94            }
     95            self.idx -= 1;
     96        }
     97        self.solution[self.idx] += 1;
     98        self.prune()
     99    }
    100 
    101    pub fn prune(&mut self) -> bool {
    102        for i in self.idx + 1..self.width {
    103            let mut source_idx = 0;
    104            while self.is_cell_missing(i, source_idx) {
    105                if source_idx >= self.depth - 1 {
    106                    return false;
    107                }
    108                source_idx += 1;
    109            }
    110            self.solution[i] = source_idx;
    111        }
    112        true
    113    }
    114 
    115    pub fn is_complete(&self) -> bool {
    116        self.idx == self.width - 1
    117    }
    118 }