sim_lib_pitch_ratio/
approximate.rs

1//! Bounded ratio approximation search.
2
3use sim_lib_discrete_search::{
4    NeverInterrupt, SearchControl, SearchProblem, SearchRun, SearchStep, solve,
5};
6
7use crate::{PitchRatio, RatioPolicy};
8
9/// Default numerator/denominator bound used by approximation search.
10pub const DEFAULT_APPROXIMATION_BOUND: u64 = 256;
11
12/// Approximation search ordering.
13#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
14pub enum ApproximationStrategy {
15    /// Return candidates ordered by absolute cents error.
16    Nearest,
17    /// Return the first admissible candidates in ascending denominator/numerator order.
18    First,
19    /// Balance low error with smaller numerator/denominator complexity.
20    Balanced,
21}
22
23/// One bounded approximation result.
24#[derive(Clone, Debug, PartialEq)]
25pub struct RatioApproximation {
26    /// Candidate exact ratio.
27    pub ratio: PitchRatio,
28    /// Candidate cents.
29    pub cents: f64,
30    /// Signed cents error against the target.
31    pub error_cents: f64,
32    /// Strategy score used for deterministic ordering.
33    pub score: i64,
34}
35
36/// Approximate a cents value using nearest-error ordering.
37pub fn approximate_ratio(
38    cents: f64,
39    policy: RatioPolicy,
40    control: SearchControl,
41) -> SearchRun<RatioApproximation> {
42    approximate_ratio_with_strategy(cents, policy, control, ApproximationStrategy::Nearest)
43}
44
45/// Approximate a cents value using an explicit deterministic strategy.
46pub fn approximate_ratio_with_strategy(
47    cents: f64,
48    policy: RatioPolicy,
49    control: SearchControl,
50    strategy: ApproximationStrategy,
51) -> SearchRun<RatioApproximation> {
52    solve(
53        &ApproximationProblem {
54            target_cents: cents,
55            policy,
56            strategy,
57            bound: DEFAULT_APPROXIMATION_BOUND,
58        },
59        control,
60        &NeverInterrupt,
61    )
62}
63
64#[derive(Clone, Debug, PartialEq, Eq)]
65enum ApproximationState {
66    Root,
67    Candidate(RatioApproximationKey),
68}
69
70#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
71struct RatioApproximationKey {
72    score: i64,
73    denominator: u64,
74    numerator: u64,
75}
76
77struct ApproximationProblem {
78    target_cents: f64,
79    policy: RatioPolicy,
80    strategy: ApproximationStrategy,
81    bound: u64,
82}
83
84impl SearchProblem for ApproximationProblem {
85    type State = ApproximationState;
86    type Choice = RatioApproximationKey;
87    type Output = RatioApproximation;
88
89    fn initial_state(&self) -> Self::State {
90        ApproximationState::Root
91    }
92
93    fn expand(&self, state: &Self::State, out: &mut Vec<Self::Choice>) {
94        if !matches!(state, ApproximationState::Root) {
95            return;
96        }
97        for denominator in 1..=self.bound {
98            for numerator in 1..=self.bound {
99                let Ok(ratio) = PitchRatio::new(numerator, denominator) else {
100                    continue;
101                };
102                let Ok(ratio) = ratio.canonical(self.policy) else {
103                    continue;
104                };
105                if ratio.numerator() != numerator || ratio.denominator() != denominator {
106                    continue;
107                }
108                let error = ratio.cents() - self.target_cents;
109                out.push(RatioApproximationKey {
110                    score: approximation_score(ratio, error, self.strategy),
111                    denominator,
112                    numerator,
113                });
114            }
115        }
116    }
117
118    fn apply(&self, state: &Self::State, choice: &Self::Choice) -> SearchStep<Self::State> {
119        if !matches!(state, ApproximationState::Root) {
120            return SearchStep::pruned("candidate leaves do not expand");
121        }
122        SearchStep::Continue(ApproximationState::Candidate(choice.clone()))
123    }
124
125    fn finish(&self, state: &Self::State) -> Option<Self::Output> {
126        let ApproximationState::Candidate(candidate) = state else {
127            return None;
128        };
129        let ratio = PitchRatio::new(candidate.numerator, candidate.denominator)
130            .ok()?
131            .canonical(self.policy)
132            .ok()?;
133        let cents = ratio.cents();
134        let error_cents = cents - self.target_cents;
135        Some(RatioApproximation {
136            ratio,
137            cents,
138            error_cents,
139            score: candidate.score,
140        })
141    }
142
143    fn score_state(&self, state: &Self::State) -> i64 {
144        match state {
145            ApproximationState::Root => 0,
146            ApproximationState::Candidate(candidate) => candidate.score,
147        }
148    }
149
150    fn output_score(&self, output: &Self::Output) -> Option<i64> {
151        Some(output.score)
152    }
153}
154
155fn approximation_score(
156    ratio: PitchRatio,
157    error_cents: f64,
158    strategy: ApproximationStrategy,
159) -> i64 {
160    match strategy {
161        ApproximationStrategy::Nearest => (error_cents.abs() * 1_000_000.0).round() as i64,
162        ApproximationStrategy::First => {
163            let denominator = i64::try_from(ratio.denominator()).unwrap_or(i64::MAX / 2);
164            let numerator = i64::try_from(ratio.numerator()).unwrap_or(i64::MAX / 2);
165            denominator.saturating_mul(10_000).saturating_add(numerator)
166        }
167        ApproximationStrategy::Balanced => {
168            let complexity = ratio.numerator().saturating_add(ratio.denominator()) as f64;
169            (error_cents.abs() * 1_000_000.0 + complexity * 1_000.0).round() as i64
170        }
171    }
172}
sim_lib_pitch_ratio/approximate.rs

sim_lib_pitch_ratio/
approximate.rs
