problemreductions/
types.rs

1//! Common types used across the problemreductions library.
2
3use serde::{Deserialize, Serialize};
4use std::fmt;
5
6/// Bound for objective value types (i32, f64, etc.)
7pub trait NumericSize:
8    Clone
9    + Default
10    + PartialOrd
11    + num_traits::Num
12    + num_traits::Zero
13    + num_traits::Bounded
14    + std::ops::AddAssign
15    + 'static
16{
17}
18
19impl<T> NumericSize for T where
20    T: Clone
21        + Default
22        + PartialOrd
23        + num_traits::Num
24        + num_traits::Zero
25        + num_traits::Bounded
26        + std::ops::AddAssign
27        + 'static
28{
29}
30
31/// Maps a weight element to its sum/metric type.
32///
33/// This decouples the per-element weight type from the accumulation type.
34/// For concrete weights (`i32`, `f64`), `Sum` is the same type.
35/// For the unit weight `One`, `Sum = i32`.
36pub trait WeightElement: Clone + Default + 'static {
37    /// The numeric type used for sums and comparisons.
38    type Sum: NumericSize;
39    /// Whether this is the unit weight type (`One`).
40    const IS_UNIT: bool;
41    /// Convert this weight element to the sum type.
42    fn to_sum(&self) -> Self::Sum;
43}
44
45impl WeightElement for i32 {
46    type Sum = i32;
47    const IS_UNIT: bool = false;
48    fn to_sum(&self) -> i32 {
49        *self
50    }
51}
52
53impl WeightElement for f64 {
54    type Sum = f64;
55    const IS_UNIT: bool = false;
56    fn to_sum(&self) -> f64 {
57        *self
58    }
59}
60
61/// The constant 1. Unit weight for unweighted problems.
62///
63/// When used as the weight type parameter `W`, indicates that all weights
64/// are uniformly 1. `One::to_sum()` returns `1i32`.
65#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default, Serialize, Deserialize)]
66pub struct One;
67
68impl WeightElement for One {
69    type Sum = i32;
70    const IS_UNIT: bool = true;
71    fn to_sum(&self) -> i32 {
72        1
73    }
74}
75
76impl std::fmt::Display for One {
77    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
78        write!(f, "One")
79    }
80}
81
82impl From<i32> for One {
83    fn from(_: i32) -> Self {
84        One
85    }
86}
87
88/// Backward-compatible alias for `One`.
89pub type Unweighted = One;
90
91/// Result of evaluating a constrained optimization problem.
92///
93/// For optimization problems with constraints (like MaximumIndependentSet),
94/// configurations may be infeasible. This enum explicitly represents validity.
95///
96/// # Example
97///
98/// ```
99/// use problemreductions::types::SolutionSize;
100///
101/// let valid = SolutionSize::Valid(42);
102/// assert!(valid.is_valid());
103/// assert_eq!(valid.size(), Some(&42));
104///
105/// let invalid: SolutionSize<i32> = SolutionSize::Invalid;
106/// assert!(!invalid.is_valid());
107/// ```
108#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default, Serialize, Deserialize)]
109pub enum SolutionSize<T> {
110    /// A valid (feasible) solution with the given objective value.
111    Valid(T),
112    /// An invalid (infeasible) solution that violates constraints.
113    #[default]
114    Invalid,
115}
116
117impl<T> SolutionSize<T> {
118    /// Returns true if this is a valid solution.
119    pub fn is_valid(&self) -> bool {
120        matches!(self, SolutionSize::Valid(_))
121    }
122
123    /// Returns the size if valid, None if invalid.
124    pub fn size(&self) -> Option<&T> {
125        match self {
126            SolutionSize::Valid(t) => Some(t),
127            SolutionSize::Invalid => None,
128        }
129    }
130
131    /// Unwraps the size, panicking if invalid.
132    pub fn unwrap(self) -> T {
133        match self {
134            SolutionSize::Valid(t) => t,
135            SolutionSize::Invalid => panic!("called unwrap on Invalid SolutionSize"),
136        }
137    }
138
139    /// Maps the inner value if valid.
140    pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> SolutionSize<U> {
141        match self {
142            SolutionSize::Valid(t) => SolutionSize::Valid(f(t)),
143            SolutionSize::Invalid => SolutionSize::Invalid,
144        }
145    }
146}
147
148impl<T: PartialOrd> SolutionSize<T> {
149    /// Returns true if self is a better solution than other for the given direction.
150    ///
151    /// - For maximization: larger values are better
152    /// - For minimization: smaller values are better
153    /// - Valid solutions are always better than invalid ones
154    /// - Two invalid solutions are equally bad (neither is better)
155    ///
156    /// # Panics
157    ///
158    /// Panics if comparing two valid values that are not comparable (e.g., NaN for f64).
159    pub fn is_better(&self, other: &Self, direction: Direction) -> bool {
160        match (self, other) {
161            (SolutionSize::Valid(a), SolutionSize::Valid(b)) => {
162                use std::cmp::Ordering;
163                let ord = a.partial_cmp(b).expect("cannot compare values (NaN?)");
164                match direction {
165                    Direction::Maximize => ord == Ordering::Greater,
166                    Direction::Minimize => ord == Ordering::Less,
167                }
168            }
169            (SolutionSize::Valid(_), SolutionSize::Invalid) => true,
170            (SolutionSize::Invalid, SolutionSize::Valid(_)) => false,
171            (SolutionSize::Invalid, SolutionSize::Invalid) => false,
172        }
173    }
174}
175
176/// Optimization direction.
177#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
178pub enum Direction {
179    /// Maximize the objective value.
180    Maximize,
181    /// Minimize the objective value.
182    Minimize,
183}
184
185/// Problem size metadata (varies by problem type).
186#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
187pub struct ProblemSize {
188    /// Named size components.
189    pub components: Vec<(String, usize)>,
190}
191
192impl ProblemSize {
193    /// Create a new problem size with named components.
194    pub fn new(components: Vec<(&str, usize)>) -> Self {
195        Self {
196            components: components
197                .into_iter()
198                .map(|(k, v)| (k.to_string(), v))
199                .collect(),
200        }
201    }
202
203    /// Get a size component by name.
204    pub fn get(&self, name: &str) -> Option<usize> {
205        self.components
206            .iter()
207            .find(|(k, _)| k == name)
208            .map(|(_, v)| *v)
209    }
210}
211
212impl fmt::Display for ProblemSize {
213    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
214        write!(f, "ProblemSize{{")?;
215        for (i, (name, value)) in self.components.iter().enumerate() {
216            if i > 0 {
217                write!(f, ", ")?;
218            }
219            write!(f, "{}: {}", name, value)?;
220        }
221        write!(f, "}}")
222    }
223}
224
225use crate::impl_variant_param;
226
227impl_variant_param!(f64, "weight");
228impl_variant_param!(i32, "weight", parent: f64, cast: |w| *w as f64);
229impl_variant_param!(One, "weight", parent: i32, cast: |_| 1i32);
230
231#[cfg(test)]
232#[path = "unit_tests/types.rs"]
233mod tests;
problemreductions/types.rs

problemreductions/
types.rs
