dtrees_rs/caching/
entry.rs

1/// The `upper_bound` of a subproblem solved independently of any bound, such
2/// as a leaf at the maximum depth or a depth-2 tree.
3pub const EXACT: f64 = f64::MAX;
4
5/// What the search knows about one subproblem.
6///
7/// `error` is the best error found so far, an upper bound on the optimum;
8/// `lower_bound` is a proven lower bound. The two meet when the subproblem is
9/// solved.
10#[derive(Copy, Clone, Debug)]
11pub struct CacheEntry {
12    item: usize,
13    test: usize,
14    error: f64,
15    upper_bound: f64,
16    lower_bound: f64,
17    metric: f64,
18    size: usize,
19    leaf_error: f64,
20    out: f64,
21    is_optimal: bool,
22    is_leaf: bool,
23}
24impl CacheEntry {
25    /// An unsolved entry reached by `item`.
26    pub fn new(item: usize) -> Self {
27        Self {
28            item,
29            test: <usize>::MAX,
30            error: f64::INFINITY,
31            upper_bound: f64::INFINITY,
32            lower_bound: 0.0,
33            metric: 0.0,
34            size: 0,
35            leaf_error: f64::INFINITY,
36            out: 0.0,
37            is_optimal: false,
38            is_leaf: false,
39        }
40    }
41
42    /// The item leading to this entry from its parent in the trie.
43    pub fn item(&self) -> usize {
44        self.item
45    }
46
47    /// The feature tested at this node, `usize::MAX` if none.
48    pub fn test(&self) -> usize {
49        self.test
50    }
51
52    /// Best error found so far.
53    pub fn error(&self) -> f64 {
54        self.error
55    }
56
57    /// Upper bound of the last complete search of the subproblem, infinite
58    /// if none, [`EXACT`] if solved independently of any bound.
59    pub fn upper_bound(&self) -> f64 {
60        self.upper_bound
61    }
62
63    /// Proven lower bound on the error.
64    pub fn lower_bound(&self) -> f64 {
65        self.lower_bound
66    }
67
68    /// Score used by searches that optimise another metric.
69    pub fn metric(&self) -> f64 {
70        self.metric
71    }
72
73    /// Number of instances in the subproblem.
74    pub fn size(&self) -> usize {
75        self.size
76    }
77
78    /// Error of the subproblem as a leaf.
79    pub fn leaf_error(&self) -> f64 {
80        self.leaf_error
81    }
82
83    /// Prediction of the subproblem as a leaf.
84    pub fn out(&self) -> f64 {
85        self.out
86    }
87
88    /// Whether the subproblem is solved.
89    pub fn is_optimal(&self) -> bool {
90        self.is_optimal
91    }
92
93    /// Whether the best subtree is a leaf.
94    pub fn is_leaf(&self) -> bool {
95        self.is_leaf
96    }
97
98    /// Whether `error` is the optimum, which
99    /// [`UsableNodeRule`](crate::algorithms::optimal::rules::common::UsableNodeRule)
100    /// then reuses: a complete search found it at or below its bound.
101    pub fn is_solved(&self) -> bool {
102        self.upper_bound.is_finite() && self.error <= self.upper_bound
103    }
104
105    /// The best proven lower bound: the optimum when solved, the recorded
106    /// lower bound otherwise.
107    pub fn known_lower_bound(&self) -> f64 {
108        match self.is_solved() {
109            true => self.error,
110            false => self.lower_bound,
111        }
112    }
113
114    pub fn has_valid_test(&self) -> bool {
115        self.test != usize::MAX
116    }
117
118    pub fn has_finite_error(&self) -> bool {
119        self.error.is_finite()
120    }
121
122    pub fn has_finite_upper_bound(&self) -> bool {
123        self.upper_bound.is_finite()
124    }
125
126    pub fn has_finite_leaf_error(&self) -> bool {
127        self.leaf_error.is_finite()
128    }
129}
130
131impl Default for CacheEntry {
132    fn default() -> Self {
133        Self {
134            item: <usize>::MAX,
135            test: <usize>::MAX,
136            error: f64::INFINITY,
137            upper_bound: f64::INFINITY,
138            lower_bound: 0.0,
139            metric: 0.0,
140            size: 0,
141            leaf_error: f64::INFINITY,
142            out: 0.0,
143            is_optimal: false,
144            is_leaf: false,
145        }
146    }
147}
148
149/// Chained setters for a [`CacheEntry`].
150pub struct CacheEntryUpdater<'a> {
151    node: &'a mut CacheEntry,
152}
153
154impl<'a> CacheEntryUpdater<'a> {
155    pub fn new(node: &'a mut CacheEntry) -> Self {
156        Self { node }
157    }
158
159    pub fn item(self, item: usize) -> Self {
160        self.node.item = item;
161        self
162    }
163
164    /// Makes the entry split on `test`.
165    pub fn test(self, test: usize) -> Self {
166        self.node.test = test;
167        self.node.is_leaf = false;
168        self
169    }
170
171    pub fn error(self, error: f64) -> Self {
172        self.node.error = error;
173        self
174    }
175
176    pub fn upper_bound(self, upper_bound: f64) -> Self {
177        self.node.upper_bound = upper_bound;
178        self
179    }
180    pub fn lower_bound(self, lower_bound: f64) -> Self {
181        self.node.lower_bound = lower_bound;
182        self
183    }
184
185    pub fn metric(self, metric: f64) -> Self {
186        self.node.metric = metric;
187        self
188    }
189
190    pub fn size(self, size: usize) -> Self {
191        self.node.size = size;
192        self
193    }
194
195    pub fn leaf_error(self, leaf_error: f64) -> Self {
196        self.node.leaf_error = leaf_error;
197        self
198    }
199
200    pub fn output(self, output: f64) -> Self {
201        self.node.out = output;
202        self
203    }
204
205    /// Marks the entry as solved.
206    pub fn optimal(self) -> Self {
207        self.node.is_optimal = true;
208        self
209    }
210
211    /// Makes the entry a leaf, with its leaf error as its error.
212    pub fn leaf(self) -> Self {
213        self.node.is_leaf = true;
214        self.node.test = usize::MAX;
215        self.node.error = self.node.leaf_error;
216        self
217    }
218
219    pub fn get_error(&self) -> f64 {
220        self.node.error
221    }
222
223    pub fn get_leaf_error(&self) -> f64 {
224        self.node.leaf_error
225    }
226
227    pub fn get_lower_bound(&self) -> f64 {
228        self.node.lower_bound
229    }
230}
dtrees_rs/caching/entry.rs

dtrees_rs/caching/
entry.rs
