dtrees_rs/algorithms/optimal/rules/
common.rs

1//! The rules that define the DL8.5 problem, plus the time limit. None of them
2//! is relaxable except, optionally, the time limit.
3
4use crate::algorithms::optimal::rules::core::Reason;
5use crate::algorithms::optimal::rules::{Rule, RuleContext, RuleResult, RuleState};
6use crate::globals::float_is_null;
7use std::time::Instant;
8
9/// Turns nodes at the maximum depth into leaves.
10#[derive(Debug)]
11pub struct MaxDepthRule {
12    max_depth: usize,
13    priority: u8,
14}
15
16impl MaxDepthRule {
17    /// A rule for trees of at most `max_depth` levels.
18    pub fn new(max_depth: usize) -> Self {
19        Self {
20            max_depth,
21            priority: 98,
22        }
23    }
24}
25
26impl Rule for MaxDepthRule {
27    fn evaluate(&self, context: &RuleContext) -> RuleResult {
28        if context.depth >= self.max_depth {
29            RuleResult::stop_with_bound(context.upper_bound, Reason::MaxDepthReached)
30                .optimal()
31                .leaf()
32        } else {
33            RuleResult::continue_search()
34        }
35    }
36
37    fn priority(&self) -> u8 {
38        self.priority
39    }
40
41    fn description(&self) -> String {
42        format!("Max depth {}", self.max_depth)
43    }
44
45    fn state(&self) -> RuleState {
46        RuleState::Active
47    }
48
49    fn is_relaxable(&self) -> bool {
50        false
51    }
52
53    fn as_any(&self) -> &dyn std::any::Any {
54        self
55    }
56
57    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
58        self
59    }
60}
61
62/// Turns nodes with fewer than `min_support` instances into leaves.
63#[derive(Debug)]
64pub struct MinSupportRule {
65    min_support: usize,
66    priority: u8,
67}
68
69impl MinSupportRule {
70    /// A rule requiring `min_support` instances to split a node.
71    pub fn new(min_support: usize) -> Self {
72        Self {
73            min_support,
74            priority: 97,
75        }
76    }
77}
78
79impl Rule for MinSupportRule {
80    fn evaluate(&self, context: &RuleContext) -> RuleResult {
81        if context.support < self.min_support {
82            RuleResult::stop_with_bound(context.upper_bound, Reason::NotEnoughSupport)
83                .optimal()
84                .leaf()
85        } else {
86            RuleResult::continue_search()
87        }
88    }
89
90    fn priority(&self) -> u8 {
91        self.priority
92    }
93
94    fn description(&self) -> String {
95        format!("Min support {}", self.min_support)
96    }
97
98    fn state(&self) -> RuleState {
99        RuleState::Active
100    }
101
102    fn is_relaxable(&self) -> bool {
103        false
104    }
105
106    fn as_any(&self) -> &dyn std::any::Any {
107        self
108    }
109
110    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
111        self
112    }
113}
114
115/// Stops the search once the time limit is reached.
116///
117/// It also serves as the search's clock. When made relaxable, reaching the
118/// limit ends the current pass and the clock restarts for the next one.
119#[derive(Debug)]
120pub struct TimeLimitRule {
121    time_limit: f64,
122    priority: u8,
123    start_time: Instant,
124    current_state: RuleState,
125    relaxable: bool,
126}
127
128impl Default for TimeLimitRule {
129    fn default() -> Self {
130        Self::new(f64::INFINITY)
131    }
132}
133
134impl TimeLimitRule {
135    /// A rule that stops the search after `time_limit` seconds.
136    pub fn new(time_limit: f64) -> Self {
137        Self {
138            time_limit,
139            priority: 100,
140            start_time: Instant::now(),
141            current_state: RuleState::Disabled,
142            relaxable: false,
143        }
144    }
145    /// Makes the limit apply per pass rather than to the whole search.
146    pub fn relaxable(mut self) -> Self {
147        self.relaxable = true;
148        self
149    }
150
151    /// Seconds since the rule was activated or reset.
152    pub fn elapsed_seconds(&self) -> f64 {
153        self.start_time.elapsed().as_secs_f64()
154    }
155
156    /// Seconds left before the limit, never negative.
157    pub fn remaining_seconds(&self) -> f64 {
158        (self.time_limit - self.elapsed_seconds()).max(0.0)
159    }
160
161    /// Whether the limit is reached.
162    pub fn exhausted(&self) -> bool {
163        self.elapsed_seconds() >= self.time_limit
164    }
165}
166
167impl Rule for TimeLimitRule {
168    fn evaluate(&self, _context: &RuleContext) -> RuleResult {
169        if !self.is_active() {
170            return RuleResult::continue_search();
171        }
172
173        if self.exhausted() {
174            let reason = match self.is_relaxable() {
175                true => Reason::RuleReason,
176                false => Reason::TimeLimitReached,
177            };
178            RuleResult::stop_with_bound(f64::INFINITY, reason)
179        } else {
180            RuleResult::continue_search()
181        }
182    }
183
184    fn priority(&self) -> u8 {
185        self.priority
186    }
187
188    fn description(&self) -> String {
189        "Time limit rule".to_string()
190    }
191
192    fn state(&self) -> RuleState {
193        self.current_state
194    }
195
196    fn activate(&mut self) {
197        self.current_state = RuleState::Active;
198        self.reset();
199    }
200
201    fn deactivate(&mut self) {
202        self.current_state = RuleState::Disabled;
203    }
204
205    fn reset(&mut self) {
206        self.start_time = Instant::now()
207    }
208
209    fn is_relaxable(&self) -> bool {
210        self.relaxable
211    }
212
213    fn relax(&mut self) {
214        if self.is_relaxable() {
215            self.reset()
216        }
217    }
218
219    fn as_any(&self) -> &dyn std::any::Any {
220        self
221    }
222
223    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
224        self
225    }
226}
227
228/// Stops at nodes whose lower bound reaches the upper bound, or whose upper
229/// bound is zero: no subtree there can improve the parent.
230#[derive(Debug)]
231pub struct LowerBoundRule {
232    priority: u8,
233    current_state: RuleState,
234}
235
236impl Default for LowerBoundRule {
237    fn default() -> Self {
238        Self::new()
239    }
240}
241
242impl LowerBoundRule {
243    /// A new, inactive rule.
244    pub fn new() -> Self {
245        Self {
246            priority: 100,
247            current_state: RuleState::Disabled,
248        }
249    }
250}
251
252impl Rule for LowerBoundRule {
253    fn evaluate(&self, context: &RuleContext) -> RuleResult {
254        if !self.is_active() {
255            return RuleResult::continue_search();
256        }
257
258        if context.upper_bound <= context.node_lower_bound || float_is_null(context.upper_bound) {
259            RuleResult::stop_search(Reason::LowerBoundConstrained)
260        } else {
261            RuleResult::continue_search()
262        }
263    }
264
265    fn priority(&self) -> u8 {
266        self.priority
267    }
268
269    fn description(&self) -> String {
270        "Lower bound rule".to_string()
271    }
272
273    fn state(&self) -> RuleState {
274        self.current_state
275    }
276
277    fn activate(&mut self) {
278        self.current_state = RuleState::Active;
279    }
280
281    fn deactivate(&mut self) {
282        self.current_state = RuleState::Disabled;
283    }
284
285    fn is_relaxable(&self) -> bool {
286        false
287    }
288
289    fn as_any(&self) -> &dyn std::any::Any {
290        self
291    }
292
293    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
294        self
295    }
296}
297
298/// Stops at nodes already solved in an earlier visit: their error and the
299/// bound they were solved under are both known. Always active.
300#[derive(Debug)]
301pub struct UsableNodeRule {
302    priority: u8,
303}
304
305impl Default for UsableNodeRule {
306    fn default() -> Self {
307        Self::new()
308    }
309}
310
311impl UsableNodeRule {
312    /// A new rule.
313    pub fn new() -> Self {
314        Self { priority: 101 }
315    }
316}
317
318impl Rule for UsableNodeRule {
319    fn evaluate(&self, context: &RuleContext) -> RuleResult {
320        if !self.is_active() {
321            return RuleResult::continue_search();
322        }
323
324        if context.error.is_finite() && context.node_upper_bound.is_finite() {
325            RuleResult::stop_search(Reason::Done)
326        } else {
327            RuleResult::continue_search()
328        }
329    }
330
331    fn priority(&self) -> u8 {
332        self.priority
333    }
334
335    fn description(&self) -> String {
336        "Usable node rule".to_string()
337    }
338
339    fn state(&self) -> RuleState {
340        RuleState::Active
341    }
342
343    fn is_relaxable(&self) -> bool {
344        false
345    }
346
347    fn as_any(&self) -> &dyn std::any::Any {
348        self
349    }
350
351    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
352        self
353    }
354}
355
356/// Turns nodes with zero error into leaves.
357#[derive(Debug)]
358pub struct PureNodeRule {
359    priority: u8,
360}
361
362impl Default for PureNodeRule {
363    fn default() -> Self {
364        Self::new()
365    }
366}
367
368impl PureNodeRule {
369    /// A new rule.
370    pub fn new() -> Self {
371        Self { priority: 99 }
372    }
373}
374
375impl Rule for PureNodeRule {
376    fn evaluate(&self, context: &RuleContext) -> RuleResult {
377        if float_is_null(context.error) {
378            RuleResult::stop_with_bound(context.upper_bound, Reason::PureNode)
379                .optimal()
380                .leaf()
381        } else {
382            RuleResult::continue_search()
383        }
384    }
385
386    fn priority(&self) -> u8 {
387        self.priority
388    }
389
390    fn description(&self) -> String {
391        "Pure node rule".to_string()
392    }
393
394    fn state(&self) -> RuleState {
395        RuleState::Active
396    }
397
398    fn is_relaxable(&self) -> bool {
399        false
400    }
401
402    fn as_any(&self) -> &dyn std::any::Any {
403        self
404    }
405
406    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
407        self
408    }
409}
410
411/// Applies the similarity lower bound of DL8.5: stops when the bound reaches
412/// the upper bound, and makes the node a leaf when its error already meets
413/// the bound.
414#[derive(Debug)]
415pub struct SimilarityLowerBoundRule {
416    priority: u8,
417    current_state: RuleState,
418}
419
420impl Default for SimilarityLowerBoundRule {
421    fn default() -> Self {
422        Self::new()
423    }
424}
425
426impl SimilarityLowerBoundRule {
427    /// A new, inactive rule.
428    pub fn new() -> Self {
429        Self {
430            priority: 100,
431            current_state: RuleState::Disabled,
432        }
433    }
434}
435
436impl Rule for SimilarityLowerBoundRule {
437    fn evaluate(&self, context: &RuleContext) -> RuleResult {
438        if !self.is_active() {
439            return RuleResult::continue_search();
440        }
441        if context.node_lower_bound >= context.upper_bound {
442            return RuleResult::stop_search(Reason::LowerBoundConstrained);
443        }
444        if context.error <= context.node_lower_bound {
445            return RuleResult::stop_search(Reason::PureNode).leaf();
446        }
447        RuleResult::continue_search()
448    }
449
450    fn priority(&self) -> u8 {
451        self.priority
452    }
453
454    fn description(&self) -> String {
455        "Similarity Lower Bound Rule".to_string()
456    }
457
458    fn state(&self) -> RuleState {
459        self.current_state
460    }
461
462    fn is_active(&self) -> bool {
463        self.current_state == RuleState::Active
464    }
465
466    fn activate(&mut self) {
467        self.current_state = RuleState::Active
468    }
469
470    fn deactivate(&mut self) {
471        self.current_state = RuleState::Disabled
472    }
473
474    fn is_relaxable(&self) -> bool {
475        false
476    }
477
478    fn as_any(&self) -> &dyn std::any::Any {
479        self
480    }
481
482    fn as_any_mut(&mut self) -> &mut dyn std::any::Any {
483        self
484    }
485}
dtrees_rs/algorithms/optimal/rules/common.rs

dtrees_rs/algorithms/optimal/rules/
common.rs
