Mercurial > repos > alg_tools / file comparison

comparison: src/bounds.rs

src/bounds.rs

branch
dev
changeset 97
4e80fb049dca
child 124
6aa955ad8122
equal deleted inserted replaced
96:962c8e346ab9 97:4e80fb049dca
1 /*!
2 Bounded and minimizable/maximizable mappings.
3 */
4
5 use crate::instance::Instance;
6 use crate::loc::Loc;
7 use crate::mapping::RealMapping;
8 use crate::sets::{Cube, Set};
9 use crate::types::{Float, Num};
10
11 /// Trait for globally analysing a property `A` of a [`Mapping`].
12 ///
13 /// Typically `A` is an [`Aggregator`][super::aggregator::Aggregator] such as
14 /// [`Bounds`][super::aggregator::Bounds].
15 pub trait GlobalAnalysis<F: Num, A> {
16 /// Perform global analysis of the property `A` of `Self`.
17 ///
18 /// As an example, in the case of `A` being [`Bounds`][super::aggregator::Bounds],
19 /// this function will return global upper and lower bounds for the mapping
20 /// represented by `self`.
21 fn global_analysis(&self) -> A;
22 }
23
24 // default impl<F, A, N, L> GlobalAnalysis<F, A, N> for L
25 // where L : LocalAnalysis<F, A, N> {
26 // #[inline]
27 // fn global_analysis(&self) -> Bounds<F> {
28 // self.local_analysis(&self.support_hint())
29 // }
30 // }
31
32 /// Trait for locally analysing a property `A` of a [`Mapping`] (implementing [`Support`])
33 /// within a [`Cube`].
34 ///
35 /// Typically `A` is an [`Aggregator`][super::aggregator::Aggregator] such as
36 /// [`Bounds`][super::aggregator::Bounds].
37 pub trait LocalAnalysis<F: Num, A, const N: usize>: GlobalAnalysis<F, A> {
38 /// Perform local analysis of the property `A` of `Self`.
39 ///
40 /// As an example, in the case of `A` being [`Bounds`][super::aggregator::Bounds],
41 /// this function will return upper and lower bounds within `cube` for the mapping
42 /// represented by `self`.
43 fn local_analysis(&self, cube: &Cube<F, N>) -> A;
44 }
45
46 /// Trait for determining the upper and lower bounds of an float-valued [`Mapping`].
47 ///
48 /// This is a blanket-implemented alias for [`GlobalAnalysis`]`<F, Bounds<F>>`
49 /// [`Mapping`] is not a supertrait to allow flexibility in the implementation of either
50 /// reference or non-reference arguments.
51 pub trait Bounded<F: Float>: GlobalAnalysis<F, Bounds<F>> {
52 /// Return lower and upper bounds for the values of of `self`.
53 #[inline]
54 fn bounds(&self) -> Bounds<F> {
55 self.global_analysis()
56 }
57 }
58
59 impl<F: Float, T: GlobalAnalysis<F, Bounds<F>>> Bounded<F> for T {}
60
61 /// A [`RealMapping`] that provides rough bounds as well as minimisation and maximisation.
62 pub trait MinMaxMapping<F: Float, const N: usize>: RealMapping<F, N> + Bounded<F> {
63 /// Maximise the mapping within stated value `tolerance`.
64 ///
65 /// At most `max_steps` refinement steps are taken.
66 /// Returns the approximate maximiser and the corresponding function value.
67 fn maximise(&mut self, tolerance: F, max_steps: usize) -> (Loc<F, N>, F);
68
69 /// Maximise the mapping within stated value `tolerance` subject to a lower bound.
70 ///
71 /// At most `max_steps` refinement steps are taken.
72 /// Returns the approximate maximiser and the corresponding function value when one is found
73 /// above the `bound` threshold, otherwise `None`.
74 fn maximise_above(
75 &mut self,
76 bound: F,
77 tolerance: F,
78 max_steps: usize,
79 ) -> Option<(Loc<F, N>, F)>;
80
81 /// Minimise the mapping within stated value `tolerance`.
82 ///
83 /// At most `max_steps` refinement steps are taken.
84 /// Returns the approximate minimiser and the corresponding function value.
85 fn minimise(&mut self, tolerance: F, max_steps: usize) -> (Loc<F, N>, F);
86
87 /// Minimise the mapping within stated value `tolerance` subject to a lower bound.
88 ///
89 /// At most `max_steps` refinement steps are taken.
90 /// Returns the approximate minimiser and the corresponding function value when one is found
91 /// above the `bound` threshold, otherwise `None`.
92 fn minimise_below(
93 &mut self,
94 bound: F,
95 tolerance: F,
96 max_steps: usize,
97 ) -> Option<(Loc<F, N>, F)>;
98
99 /// Verify that the mapping has a given upper `bound` within indicated `tolerance`.
100 ///
101 /// At most `max_steps` refinement steps are taken.
102 fn has_upper_bound(&mut self, bound: F, tolerance: F, max_steps: usize) -> bool;
103
104 /// Verify that the mapping has a given lower `bound` within indicated `tolerance`.
105 ///
106 /// At most `max_steps` refinement steps are taken.
107 fn has_lower_bound(&mut self, bound: F, tolerance: F, max_steps: usize) -> bool;
108 }
109
110 /// Upper and lower bounds on an `F`-valued function.
111 #[derive(Copy, Clone, Debug)]
112 pub struct Bounds<F>(
113 /// Lower bound
114 pub F,
115 /// Upper bound
116 pub F,
117 );
118
119 impl<F: Copy> Bounds<F> {
120 /// Returns the lower bound
121 #[inline]
122 pub fn lower(&self) -> F {
123 self.0
124 }
125
126 /// Returns the upper bound
127 #[inline]
128 pub fn upper(&self) -> F {
129 self.1
130 }
131 }
132
133 impl<F: Float> Bounds<F> {
134 /// Returns a uniform bound.
135 ///
136 /// This is maximum over the absolute values of the upper and lower bound.
137 #[inline]
138 pub fn uniform(&self) -> F {
139 let &Bounds(lower, upper) = self;
140 lower.abs().max(upper.abs())
141 }
142
143 /// Construct a bounds, making sure `lower` bound is less than `upper`
144 #[inline]
145 pub fn corrected(lower: F, upper: F) -> Self {
146 if lower <= upper {
147 Bounds(lower, upper)
148 } else {
149 Bounds(upper, lower)
150 }
151 }
152
153 /// Refine the lower bound
154 #[inline]
155 pub fn refine_lower(&self, lower: F) -> Self {
156 let &Bounds(l, u) = self;
157 debug_assert!(l <= u);
158 Bounds(l.max(lower), u.max(lower))
159 }
160
161 /// Refine the lower bound
162 #[inline]
163 pub fn refine_upper(&self, upper: F) -> Self {
164 let &Bounds(l, u) = self;
165 debug_assert!(l <= u);
166 Bounds(l.min(upper), u.min(upper))
167 }
168 }
169
170 impl<'a, F: Float> std::ops::Add<Self> for Bounds<F> {
171 type Output = Self;
172 #[inline]
173 fn add(self, Bounds(l2, u2): Self) -> Self::Output {
174 let Bounds(l1, u1) = self;
175 debug_assert!(l1 <= u1 && l2 <= u2);
176 Bounds(l1 + l2, u1 + u2)
177 }
178 }
179
180 impl<'a, F: Float> std::ops::Mul<Self> for Bounds<F> {
181 type Output = Self;
182 #[inline]
183 fn mul(self, Bounds(l2, u2): Self) -> Self::Output {
184 let Bounds(l1, u1) = self;
185 debug_assert!(l1 <= u1 && l2 <= u2);
186 let a = l1 * l2;
187 let b = u1 * u2;
188 // The order may flip when negative numbers are involved, so need min/max
189 Bounds(a.min(b), a.max(b))
190 }
191 }
192
193 impl<F: Float> std::iter::Product for Bounds<F> {
194 #[inline]
195 fn product<I>(mut iter: I) -> Self
196 where
197 I: Iterator<Item = Self>,
198 {
199 match iter.next() {
200 None => Bounds(F::ZERO, F::ZERO),
201 Some(init) => iter.fold(init, |a, b| a * b),
202 }
203 }
204 }
205
206 impl<F: Float> Set<F> for Bounds<F> {
207 fn contains<I: Instance<F>>(&self, item: I) -> bool {
208 let v = item.own();
209 let &Bounds(l, u) = self;
210 debug_assert!(l <= u);
211 l <= v && v <= u
212 }
213 }
214
215 impl<F: Float> Bounds<F> {
216 /// Calculate a common bound (glb, lub) for two bounds.
217 #[inline]
218 pub fn common(&self, &Bounds(l2, u2): &Self) -> Self {
219 let &Bounds(l1, u1) = self;
220 debug_assert!(l1 <= u1 && l2 <= u2);
221 Bounds(l1.min(l2), u1.max(u2))
222 }
223
224 /// Indicates whether `Self` is a superset of the argument bound.
225 #[inline]
226 pub fn superset(&self, &Bounds(l2, u2): &Self) -> bool {
227 let &Bounds(l1, u1) = self;
228 debug_assert!(l1 <= u1 && l2 <= u2);
229 l1 <= l2 && u2 <= u1
230 }
231
232 /// Returns the greatest bound contained by both argument bounds, if one exists.
233 #[inline]
234 pub fn glb(&self, &Bounds(l2, u2): &Self) -> Option<Self> {
235 let &Bounds(l1, u1) = self;
236 debug_assert!(l1 <= u1 && l2 <= u2);
237 let l = l1.max(l2);
238 let u = u1.min(u2);
239 debug_assert!(l <= u);
240 if l < u {
241 Some(Bounds(l, u))
242 } else {
243 None
244 }
245 }
246 }

Mercurial Repository: alg_tools

mercurial