summaryrefslogtreecommitdiffstats
path: root/intl/l10n/rust/l10nregistry-rs/src/solver/mod.rs
diff options
context:
space:
mode:
Diffstat (limited to 'intl/l10n/rust/l10nregistry-rs/src/solver/mod.rs')
-rw-r--r--intl/l10n/rust/l10nregistry-rs/src/solver/mod.rs122
1 files changed, 122 insertions, 0 deletions
diff --git a/intl/l10n/rust/l10nregistry-rs/src/solver/mod.rs b/intl/l10n/rust/l10nregistry-rs/src/solver/mod.rs
new file mode 100644
index 0000000000..f14fbfe641
--- /dev/null
+++ b/intl/l10n/rust/l10nregistry-rs/src/solver/mod.rs
@@ -0,0 +1,122 @@
+mod parallel;
+mod serial;
+pub mod testing;
+
+pub use parallel::{AsyncTester, ParallelProblemSolver};
+pub use serial::{SerialProblemSolver, SyncTester};
+
+pub struct ProblemSolver {
+ width: usize,
+ depth: usize,
+
+ cache: Vec<Vec<Option<bool>>>,
+
+ solution: Vec<usize>,
+ idx: usize,
+
+ dirty: bool,
+}
+
+impl ProblemSolver {
+ pub fn new(width: usize, depth: usize) -> Self {
+ Self {
+ width,
+ depth,
+ cache: vec![vec![None; depth]; width],
+
+ solution: vec![0; width],
+ idx: 0,
+
+ dirty: false,
+ }
+ }
+}
+
+impl ProblemSolver {
+ pub fn bail(&mut self) -> bool {
+ if self.try_advance_source() {
+ true
+ } else {
+ self.try_backtrack()
+ }
+ }
+
+ pub fn has_missing_cell(&self) -> Option<usize> {
+ for res_idx in 0..self.width {
+ if self.cache[res_idx].iter().all(|c| *c == Some(false)) {
+ return Some(res_idx);
+ }
+ }
+ None
+ }
+
+ fn is_cell_missing(&self, res_idx: usize, source_idx: usize) -> bool {
+ if let Some(false) = self.cache[res_idx][source_idx] {
+ return true;
+ }
+ false
+ }
+
+ fn is_current_cell_missing(&self) -> bool {
+ let res_idx = self.idx;
+ let source_idx = self.solution[res_idx];
+ let cell = &self.cache[res_idx][source_idx];
+ if let Some(false) = cell {
+ return true;
+ }
+ false
+ }
+
+ pub fn try_advance_resource(&mut self) -> bool {
+ if self.idx >= self.width - 1 {
+ false
+ } else {
+ self.idx += 1;
+ while self.is_current_cell_missing() {
+ if !self.try_advance_source() {
+ return false;
+ }
+ }
+ true
+ }
+ }
+
+ pub fn try_advance_source(&mut self) -> bool {
+ while self.solution[self.idx] < self.depth - 1 {
+ self.solution[self.idx] += 1;
+ if !self.is_current_cell_missing() {
+ return true;
+ }
+ }
+ false
+ }
+
+ pub fn try_backtrack(&mut self) -> bool {
+ while self.solution[self.idx] == self.depth - 1 {
+ if self.idx == 0 {
+ return false;
+ }
+ self.idx -= 1;
+ }
+ self.solution[self.idx] += 1;
+ self.prune()
+ }
+
+ pub fn prune(&mut self) -> bool {
+ for i in self.idx + 1..self.width {
+ let mut source_idx = 0;
+ while self.is_cell_missing(i, source_idx) {
+ if source_idx >= self.depth - 1 {
+ return false;
+ }
+ source_idx += 1;
+ }
+ self.solution[i] = source_idx;
+ }
+ true
+ }
+
+ pub fn is_complete(&self) -> bool {
+ self.idx == self.width - 1
+ }
+}