1use serde::de::{self, DeserializeOwned, Visitor};
4use serde::{Deserialize, Deserializer, Serialize, Serializer};
5use std::fmt;
6
7pub const MAX_EXACT_F64_INTEGER: i64 = (1_i64 << 53) - 1;
9
10#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
12#[error(
13 "integer {value} is outside the exactly representable f64 range [{min}, {max}]",
14 min = -MAX_EXACT_F64_INTEGER,
15 max = MAX_EXACT_F64_INTEGER
16)]
17pub struct ExactI64ToF64Error {
18 pub value: i64,
19}
20
21#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
23pub enum NumericArithmeticError {
24 #[error("integer overflow")]
26 IntegerOverflow,
27 #[error("non-finite floating-point result")]
29 NonFiniteResult,
30}
31
32pub fn i64_to_exact_f64(value: i64) -> Result<f64, ExactI64ToF64Error> {
34 if (-MAX_EXACT_F64_INTEGER..=MAX_EXACT_F64_INTEGER).contains(&value) {
35 Ok(value as f64)
36 } else {
37 Err(ExactI64ToF64Error { value })
38 }
39}
40
41pub trait NumericSize:
43 Clone
44 + Default
45 + PartialOrd
46 + num_traits::Num
47 + num_traits::Zero
48 + num_traits::Bounded
49 + std::ops::AddAssign
50 + 'static
51{
52 fn checked_add_value(self, other: Self) -> Result<Self, NumericArithmeticError>;
54 fn checked_mul_value(self, other: Self) -> Result<Self, NumericArithmeticError>;
56}
57
58macro_rules! impl_integer_numeric_size {
59 ($($type:ty),* $(,)?) => {
60 $(
61 impl NumericSize for $type {
62 fn checked_add_value(self, other: Self) -> Result<Self, NumericArithmeticError> {
63 self.checked_add(other).ok_or(NumericArithmeticError::IntegerOverflow)
64 }
65
66 fn checked_mul_value(self, other: Self) -> Result<Self, NumericArithmeticError> {
67 self.checked_mul(other).ok_or(NumericArithmeticError::IntegerOverflow)
68 }
69 }
70 )*
71 };
72}
73
74impl_integer_numeric_size!(i64, u64, usize);
75
76impl NumericSize for f64 {
77 fn checked_add_value(self, other: Self) -> Result<Self, NumericArithmeticError> {
78 let result = self + other;
79 result
80 .is_finite()
81 .then_some(result)
82 .ok_or(NumericArithmeticError::NonFiniteResult)
83 }
84
85 fn checked_mul_value(self, other: Self) -> Result<Self, NumericArithmeticError> {
86 let result = self * other;
87 result
88 .is_finite()
89 .then_some(result)
90 .ok_or(NumericArithmeticError::NonFiniteResult)
91 }
92}
93
94fn evaluation_arithmetic_error(
95 error: NumericArithmeticError,
96 context: &str,
97) -> crate::traits::EvaluationError {
98 match error {
99 NumericArithmeticError::IntegerOverflow => {
100 crate::traits::EvaluationError::IntegerOverflow(context.to_string())
101 }
102 NumericArithmeticError::NonFiniteResult => {
103 crate::traits::EvaluationError::NonFiniteResult(context.to_string())
104 }
105 }
106}
107
108pub trait WeightElement: Clone + Default + 'static {
115 type Sum: NumericSize;
117 const IS_UNIT: bool;
119 fn unit() -> Self;
121 fn validate_element(&self, context: &str) -> Result<(), crate::registry::ConstructionError>;
123 fn to_sum(&self) -> Self::Sum;
125 fn checked_add_to_sum(
127 total: Self::Sum,
128 value: Self::Sum,
129 context: &str,
130 ) -> Result<Self::Sum, crate::traits::EvaluationError> {
131 total
132 .checked_add_value(value)
133 .map_err(|error| evaluation_arithmetic_error(error, context))
134 }
135 fn checked_mul_sum(
137 left: Self::Sum,
138 right: Self::Sum,
139 context: &str,
140 ) -> Result<Self::Sum, crate::traits::EvaluationError> {
141 left.checked_mul_value(right)
142 .map_err(|error| evaluation_arithmetic_error(error, context))
143 }
144}
145
146impl WeightElement for i64 {
147 type Sum = i64;
148 const IS_UNIT: bool = false;
149 fn unit() -> Self {
150 1
151 }
152 fn validate_element(&self, _context: &str) -> Result<(), crate::registry::ConstructionError> {
153 Ok(())
154 }
155 fn to_sum(&self) -> i64 {
156 *self
157 }
158}
159
160impl WeightElement for f64 {
161 type Sum = f64;
162 const IS_UNIT: bool = false;
163 fn unit() -> Self {
164 1.0
165 }
166 fn validate_element(&self, context: &str) -> Result<(), crate::registry::ConstructionError> {
167 if self.is_finite() {
168 Ok(())
169 } else {
170 Err(crate::registry::ConstructionError::NonFiniteFloat(format!(
171 "{context} must be finite"
172 )))
173 }
174 }
175 fn to_sum(&self) -> f64 {
176 *self
177 }
178}
179
180#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
185pub struct One;
186
187impl Serialize for One {
188 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
189 where
190 S: Serializer,
191 {
192 serializer.serialize_i64(1)
193 }
194}
195
196impl<'de> Deserialize<'de> for One {
197 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
198 where
199 D: Deserializer<'de>,
200 {
201 struct OneVisitor;
202
203 impl<'de> Visitor<'de> for OneVisitor {
204 type Value = One;
205
206 fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
207 formatter.write_str("the unit weight `One` encoded as 1 or unit/null")
208 }
209
210 fn visit_i64<E>(self, value: i64) -> Result<One, E>
211 where
212 E: de::Error,
213 {
214 if value == 1 {
215 Ok(One)
216 } else {
217 Err(E::custom(format!("expected 1 for One, got {value}")))
218 }
219 }
220
221 fn visit_u64<E>(self, value: u64) -> Result<One, E>
222 where
223 E: de::Error,
224 {
225 if value == 1 {
226 Ok(One)
227 } else {
228 Err(E::custom(format!("expected 1 for One, got {value}")))
229 }
230 }
231
232 fn visit_unit<E>(self) -> Result<One, E>
233 where
234 E: de::Error,
235 {
236 Ok(One)
237 }
238
239 fn visit_none<E>(self) -> Result<One, E>
240 where
241 E: de::Error,
242 {
243 Ok(One)
244 }
245
246 fn visit_str<E>(self, value: &str) -> Result<One, E>
247 where
248 E: de::Error,
249 {
250 if value == "One" {
251 Ok(One)
252 } else {
253 Err(E::custom(format!("expected \"One\" for One, got {value}")))
254 }
255 }
256 }
257
258 deserializer.deserialize_any(OneVisitor)
259 }
260}
261
262impl WeightElement for One {
263 type Sum = i64;
264 const IS_UNIT: bool = true;
265 fn unit() -> Self {
266 One
267 }
268 fn validate_element(&self, _context: &str) -> Result<(), crate::registry::ConstructionError> {
269 Ok(())
270 }
271 fn to_sum(&self) -> i64 {
272 1
273 }
274}
275
276impl std::fmt::Display for One {
277 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
278 write!(f, "One")
279 }
280}
281
282#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
284pub enum AggregationError {
285 #[error("aggregate arithmetic overflow or non-finite result")]
286 ArithmeticOverflow,
287 #[error("aggregate values are not comparable")]
288 UnorderedComparison,
289 #[error("cannot combine extrema with different optimization senses")]
290 IncompatibleExtremumSense,
291}
292
293pub trait Aggregate: Clone + fmt::Debug + Serialize + DeserializeOwned {
295 fn identity() -> Self;
297
298 fn combine(self, other: Self) -> Result<Self, AggregationError>;
300
301 fn is_absorbing(&self) -> bool {
303 false
304 }
305}
306
307pub trait SolutionAggregate: Aggregate {
309 fn contributes_to_solution(value: &Self, total: &Self) -> bool;
311}
312
313#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
315pub struct Max<V>(pub Option<V>);
316
317impl<V: fmt::Debug + PartialOrd + Clone + Serialize + DeserializeOwned> Aggregate for Max<V> {
318 fn identity() -> Self {
319 Max(None)
320 }
321
322 fn combine(self, other: Self) -> Result<Self, AggregationError> {
323 use std::cmp::Ordering;
324
325 Ok(match (self.0, other.0) {
326 (None, rhs) => Max(rhs),
327 (lhs, None) => Max(lhs),
328 (Some(lhs), Some(rhs)) => {
329 let ord = lhs
330 .partial_cmp(&rhs)
331 .ok_or(AggregationError::UnorderedComparison)?;
332 match ord {
333 Ordering::Less => Max(Some(rhs)),
334 Ordering::Equal | Ordering::Greater => Max(Some(lhs)),
335 }
336 }
337 })
338 }
339}
340
341impl<V: fmt::Debug + PartialOrd + Clone + Serialize + DeserializeOwned> SolutionAggregate
342 for Max<V>
343{
344 fn contributes_to_solution(value: &Self, total: &Self) -> bool {
345 matches!((value, total), (Max(Some(value)), Max(Some(best))) if value == best)
346 }
347}
348
349impl<V: fmt::Display> fmt::Display for Max<V> {
350 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
351 match &self.0 {
352 Some(value) => write!(f, "Max({value})"),
353 None => write!(f, "Max(None)"),
354 }
355 }
356}
357
358impl<V> Max<V> {
359 pub fn is_valid(&self) -> bool {
360 self.0.is_some()
361 }
362
363 pub fn size(&self) -> Option<&V> {
364 self.0.as_ref()
365 }
366
367 pub fn unwrap(self) -> V {
368 self.0.expect("called unwrap on invalid Max value")
369 }
370}
371
372#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
374pub struct Min<V>(pub Option<V>);
375
376impl<V: fmt::Debug + PartialOrd + Clone + Serialize + DeserializeOwned> Aggregate for Min<V> {
377 fn identity() -> Self {
378 Min(None)
379 }
380
381 fn combine(self, other: Self) -> Result<Self, AggregationError> {
382 use std::cmp::Ordering;
383
384 Ok(match (self.0, other.0) {
385 (None, rhs) => Min(rhs),
386 (lhs, None) => Min(lhs),
387 (Some(lhs), Some(rhs)) => {
388 let ord = lhs
389 .partial_cmp(&rhs)
390 .ok_or(AggregationError::UnorderedComparison)?;
391 match ord {
392 Ordering::Greater => Min(Some(rhs)),
393 Ordering::Equal | Ordering::Less => Min(Some(lhs)),
394 }
395 }
396 })
397 }
398}
399
400impl<V: fmt::Debug + PartialOrd + Clone + Serialize + DeserializeOwned> SolutionAggregate
401 for Min<V>
402{
403 fn contributes_to_solution(value: &Self, total: &Self) -> bool {
404 matches!((value, total), (Min(Some(value)), Min(Some(best))) if value == best)
405 }
406}
407
408impl<V: fmt::Display> fmt::Display for Min<V> {
409 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
410 match &self.0 {
411 Some(value) => write!(f, "Min({value})"),
412 None => write!(f, "Min(None)"),
413 }
414 }
415}
416
417impl<V> Min<V> {
418 pub fn is_valid(&self) -> bool {
419 self.0.is_some()
420 }
421
422 pub fn size(&self) -> Option<&V> {
423 self.0.as_ref()
424 }
425
426 pub fn unwrap(self) -> V {
427 self.0.expect("called unwrap on invalid Min value")
428 }
429}
430
431pub trait OptimizationValue: Aggregate {
433 type Inner: Clone + PartialOrd + fmt::Debug + Serialize + DeserializeOwned;
435
436 fn meets_bound(value: &Self, bound: &Self::Inner) -> bool;
438}
439
440impl<V: fmt::Debug + PartialOrd + Clone + Serialize + DeserializeOwned> OptimizationValue
441 for Min<V>
442{
443 type Inner = V;
444
445 fn meets_bound(value: &Self, bound: &V) -> bool {
446 matches!(&value.0, Some(v) if *v <= *bound)
447 }
448}
449
450impl<V: fmt::Debug + PartialOrd + Clone + Serialize + DeserializeOwned> OptimizationValue
451 for Max<V>
452{
453 type Inner = V;
454
455 fn meets_bound(value: &Self, bound: &V) -> bool {
456 matches!(&value.0, Some(v) if *v >= *bound)
457 }
458}
459
460#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
462pub struct Sum<W>(pub W);
463
464impl<W: fmt::Debug + NumericSize + Serialize + DeserializeOwned> Aggregate for Sum<W> {
465 fn identity() -> Self {
466 Sum(W::zero())
467 }
468
469 fn combine(self, other: Self) -> Result<Self, AggregationError> {
470 self.0
471 .checked_add_value(other.0)
472 .map(Sum)
473 .map_err(|_| AggregationError::ArithmeticOverflow)
474 }
475}
476
477impl<W: fmt::Display> fmt::Display for Sum<W> {
478 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
479 write!(f, "Sum({})", self.0)
480 }
481}
482
483#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
485pub struct Or(pub bool);
486
487impl Or {
488 pub fn is_valid(&self) -> bool {
489 self.0
490 }
491
492 pub fn unwrap(self) -> bool {
493 self.0
494 }
495}
496
497impl Aggregate for Or {
498 fn identity() -> Self {
499 Or(false)
500 }
501
502 fn combine(self, other: Self) -> Result<Self, AggregationError> {
503 Ok(Or(self.0 || other.0))
504 }
505
506 fn is_absorbing(&self) -> bool {
507 self.0
508 }
509}
510
511impl SolutionAggregate for Or {
512 fn contributes_to_solution(value: &Self, total: &Self) -> bool {
513 value.0 && total.0
514 }
515}
516
517impl fmt::Display for Or {
518 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
519 write!(f, "Or({})", self.0)
520 }
521}
522
523impl std::ops::Not for Or {
524 type Output = bool;
525
526 fn not(self) -> Self::Output {
527 !self.0
528 }
529}
530
531impl PartialEq<bool> for Or {
532 fn eq(&self, other: &bool) -> bool {
533 self.0 == *other
534 }
535}
536
537impl PartialEq<Or> for bool {
538 fn eq(&self, other: &Or) -> bool {
539 *self == other.0
540 }
541}
542
543#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
545pub struct And(pub bool);
546
547impl Aggregate for And {
548 fn identity() -> Self {
549 And(true)
550 }
551
552 fn combine(self, other: Self) -> Result<Self, AggregationError> {
553 Ok(And(self.0 && other.0))
554 }
555
556 fn is_absorbing(&self) -> bool {
557 !self.0
558 }
559}
560
561impl fmt::Display for And {
562 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
563 write!(f, "And({})", self.0)
564 }
565}
566
567#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
568pub enum ExtremumSense {
569 Maximize,
570 Minimize,
571}
572
573#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
574pub struct Extremum<V> {
575 pub sense: ExtremumSense,
576 pub value: Option<V>,
577}
578
579impl<V> Extremum<V> {
580 pub fn maximize(value: Option<V>) -> Self {
581 Self {
582 sense: ExtremumSense::Maximize,
583 value,
584 }
585 }
586
587 pub fn minimize(value: Option<V>) -> Self {
588 Self {
589 sense: ExtremumSense::Minimize,
590 value,
591 }
592 }
593
594 pub fn is_valid(&self) -> bool {
595 self.value.is_some()
596 }
597
598 pub fn size(&self) -> Option<&V> {
599 self.value.as_ref()
600 }
601
602 pub fn unwrap(self) -> V {
603 self.value.expect("called unwrap on invalid Extremum value")
604 }
605}
606
607impl<V: fmt::Debug + PartialOrd + Clone + Serialize + DeserializeOwned> Aggregate for Extremum<V> {
608 fn identity() -> Self {
609 Self::maximize(None)
610 }
611
612 fn combine(self, other: Self) -> Result<Self, AggregationError> {
613 use std::cmp::Ordering;
614
615 Ok(match (self.value, other.value) {
616 (None, rhs) => Self {
617 sense: other.sense,
618 value: rhs,
619 },
620 (lhs, None) => Self {
621 sense: self.sense,
622 value: lhs,
623 },
624 (Some(lhs), Some(rhs)) => {
625 if self.sense != other.sense {
626 return Err(AggregationError::IncompatibleExtremumSense);
627 }
628 let ord = lhs
629 .partial_cmp(&rhs)
630 .ok_or(AggregationError::UnorderedComparison)?;
631 let keep_self = match self.sense {
632 ExtremumSense::Maximize => matches!(ord, Ordering::Equal | Ordering::Greater),
633 ExtremumSense::Minimize => matches!(ord, Ordering::Equal | Ordering::Less),
634 };
635 if keep_self {
636 Self {
637 sense: self.sense,
638 value: Some(lhs),
639 }
640 } else {
641 Self {
642 sense: other.sense,
643 value: Some(rhs),
644 }
645 }
646 }
647 })
648 }
649}
650
651impl<V: fmt::Debug + PartialOrd + Clone + Serialize + DeserializeOwned> SolutionAggregate
652 for Extremum<V>
653{
654 fn contributes_to_solution(candidate: &Self, total: &Self) -> bool {
655 matches!(
656 (candidate.value.as_ref(), total.value.as_ref()),
657 (Some(value), Some(best)) if candidate.sense == total.sense && value == best
658 )
659 }
660}
661
662impl<V: fmt::Display> fmt::Display for Extremum<V> {
663 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
664 match (&self.sense, &self.value) {
665 (ExtremumSense::Maximize, Some(value)) => write!(f, "Max({value})"),
666 (ExtremumSense::Maximize, None) => write!(f, "Max(None)"),
667 (ExtremumSense::Minimize, Some(value)) => write!(f, "Min({value})"),
668 (ExtremumSense::Minimize, None) => write!(f, "Min(None)"),
669 }
670 }
671}
672
673#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
675pub struct ProblemParameters {
676 #[serde(deserialize_with = "deserialize_parameter_components")]
678 pub(crate) components: Vec<(String, u64)>,
679}
680
681impl ProblemParameters {
682 pub fn new(components: Vec<(&str, u64)>) -> Self {
687 Self::from_owned(
688 components
689 .into_iter()
690 .map(|(name, value)| (name.to_string(), value))
691 .collect(),
692 )
693 }
694
695 pub fn from_owned(components: Vec<(String, u64)>) -> Self {
700 if let Some(name) = duplicate_parameter_name(&components) {
701 panic!("duplicate problem parameter `{name}`");
702 }
703 Self { components }
704 }
705
706 pub fn iter(&self) -> impl Iterator<Item = (&str, u64)> {
708 self.components
709 .iter()
710 .map(|(name, value)| (name.as_str(), *value))
711 }
712
713 pub fn get(&self, name: &str) -> Option<u64> {
715 self.components
716 .iter()
717 .find(|(k, _)| k == name)
718 .map(|(_, v)| *v)
719 }
720}
721
722fn duplicate_parameter_name(components: &[(String, u64)]) -> Option<&str> {
723 components
724 .iter()
725 .enumerate()
726 .find_map(|(index, (name, _))| {
727 components[..index]
728 .iter()
729 .any(|(previous, _)| previous == name)
730 .then_some(name.as_str())
731 })
732}
733
734fn deserialize_parameter_components<'de, D>(deserializer: D) -> Result<Vec<(String, u64)>, D::Error>
735where
736 D: serde::Deserializer<'de>,
737{
738 let components = Vec::<(String, u64)>::deserialize(deserializer)?;
739 if let Some(name) = duplicate_parameter_name(&components) {
740 return Err(serde::de::Error::custom(format!(
741 "duplicate problem parameter `{name}`"
742 )));
743 }
744 Ok(components)
745}
746
747impl fmt::Display for ProblemParameters {
748 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
749 write!(f, "ProblemParameters{{")?;
750 for (i, (name, value)) in self.components.iter().enumerate() {
751 if i > 0 {
752 write!(f, ", ")?;
753 }
754 write!(f, "{}: {}", name, value)?;
755 }
756 write!(f, "}}")
757 }
758}
759
760use crate::impl_variant_param;
761
762impl_variant_param!(f64, "weight");
763impl_variant_param!(i64, "weight");
764impl_variant_param!(One, "weight");
765
766#[cfg(test)]
767#[path = "unit_tests/types.rs"]
768mod tests;
769
770#[cfg(test)]
771#[path = "unit_tests/types_optimization_value.rs"]
772mod optimization_value_tests;