dtrees_rs/algorithms/optimal/rules/
helpers.rs

1/// A sequence of budgets used to relax a rule between passes.
2pub trait StepStrategy: Send + Sync {
3    /// The next value of the sequence.
4    fn next(&mut self) -> usize;
5}
6
7/// `0, n, 2n, 3n, …`
8pub struct Monotonic {
9    increment: usize,
10    current: usize,
11}
12
13impl Default for Monotonic {
14    fn default() -> Self {
15        Self {
16            increment: 1,
17            current: 0,
18        }
19    }
20}
21
22impl StepStrategy for Monotonic {
23    fn next(&mut self) -> usize {
24        let value = self.current;
25        self.current += self.increment;
26        value
27    }
28}
29
30impl Monotonic {
31    /// A sequence with step `increment`.
32    pub fn new(increment: usize) -> Self {
33        Self {
34            current: 0,
35            increment,
36        }
37    }
38}
39
40/// `1, b, b², b³, …`
41pub struct Exponential {
42    current: usize,
43    base: usize,
44}
45
46impl Default for Exponential {
47    fn default() -> Self {
48        Self {
49            current: 1,
50            base: 2,
51        }
52    }
53}
54
55impl Exponential {
56    /// A sequence with base `base`.
57    pub fn new(base: usize) -> Self {
58        Self { current: 1, base }
59    }
60}
61
62impl StepStrategy for Exponential {
63    fn next(&mut self) -> usize {
64        let value = self.current;
65        self.current *= self.base;
66        value
67    }
68}
69
70/// Running sums of the Luby sequence `1, 1, 2, 1, 1, 2, 4, …`, scaled by a
71/// multiplier, as used for restarts in SAT solvers.
72pub struct Luby {
73    multiplier: usize,
74    steps: Vec<usize>,
75    current: usize,
76    iter: usize,
77}
78
79impl Default for Luby {
80    fn default() -> Self {
81        Self {
82            multiplier: 1,
83            steps: vec![1],
84            current: 1,
85            iter: 1,
86        }
87    }
88}
89
90impl Luby {
91    /// A sequence scaled by `multiplier`.
92    pub fn new(multiplier: usize) -> Self {
93        Self {
94            multiplier,
95            steps: vec![1],
96            current: multiplier,
97            iter: 1,
98        }
99    }
100}
101
102impl StepStrategy for Luby {
103    fn next(&mut self) -> usize {
104        let value = self.current;
105        self.iter += 1;
106        let increment = match (self.iter + 1).is_power_of_two() {
107            true => 2_usize.pow((self.iter + 1).ilog2() - 1),
108            false => {
109                let index = self.iter - 2_usize.pow(self.iter.ilog2());
110                self.steps[index]
111            }
112        };
113        self.steps.push(increment);
114        self.current += increment * self.multiplier;
115        value
116    }
117}
dtrees_rs/algorithms/optimal/rules/helpers.rs

dtrees_rs/algorithms/optimal/rules/
helpers.rs
