Mercurial > repos > alg_tools / file comparison

comparison: src/bisection_tree/btfn.rs

src/bisection_tree/btfn.rs

branch
dev
changeset 124
6aa955ad8122
parent 97
4e80fb049dca
child 125
25b6c8b20d1b
equal deleted inserted replaced
122:495448cca603 124:6aa955ad8122
20 use crate::sets::Set; 20 use crate::sets::Set;
21 21
22 /// Presentation for (mathematical) functions constructed as a sum of components functions with 22 /// Presentation for (mathematical) functions constructed as a sum of components functions with
23 /// typically small support. 23 /// typically small support.
24 /// 24 ///
25 /// The domain of the function is [`Loc`]`<F, N>`, where `F` is the type of floating point numbers, 25 /// The domain of the function is [`Loc`]`<N, F>`, where `F` is the type of floating point numbers,
26 /// and `N` the dimension. 26 /// and `N` the dimension.
27 /// 27 ///
28 /// The `generator` lists the component functions that have to implement [`Support`]. 28 /// The `generator` lists the component functions that have to implement [`Support`].
29 /// Identifiers of the components ([`SupportGenerator::Id`], usually `usize`) are stored stored 29 /// Identifiers of the components ([`SupportGenerator::Id`], usually `usize`) are stored stored
30 /// in a [bisection tree][BTImpl], when one is provided as `bt`. However `bt` may also be `()` 30 /// in a [bisection tree][BTImpl], when one is provided as `bt`. However `bt` may also be `()`
31 /// for a [`PreBTFN`] that is only useful for vector space operations with a full [`BTFN`]. 31 /// for a [`PreBTFN`] that is only useful for vector space operations with a full [`BTFN`].
32 #[derive(Clone, Debug)] 32 #[derive(Clone, Debug)]
33 pub struct BTFN<F: Float, G: SupportGenerator<F, N>, BT /*: BTImpl<F, N>*/, const N: usize> /*where G::SupportType : LocalAnalysis<F, A, N>*/ 33 pub struct BTFN<F: Float, G: SupportGenerator<N, F>, BT /*: BTImpl< N, F>*/, const N: usize> /*where G::SupportType : LocalAnalysis<F, A, N>*/
34 { 34 {
35 bt: BT, 35 bt: BT,
36 generator: Arc<G>, 36 generator: Arc<G>,
37 _phantoms: PhantomData<F>, 37 _phantoms: PhantomData<F>,
38 } 38 }
39 39
40 impl<F: Float, G, BT, const N: usize> Space for BTFN<F, G, BT, N> 40 impl<F: Float, G, BT, const N: usize> Space for BTFN<F, G, BT, N>
41 where 41 where
42 G: SupportGenerator<F, N, Id = BT::Data>, 42 G: SupportGenerator<N, F, Id = BT::Data>,
43 G::SupportType: LocalAnalysis<F, BT::Agg, N>, 43 G::SupportType: LocalAnalysis<F, BT::Agg, N>,
44 BT: BTImpl<F, N>, 44 BT: BTImpl<N, F>,
45 { 45 {
46 type Decomp = BasicDecomposition; 46 type Decomp = BasicDecomposition;
47 } 47 }
48 48
49 impl<F: Float, G, BT, const N: usize> BTFN<F, G, BT, N> 49 impl<F: Float, G, BT, const N: usize> BTFN<F, G, BT, N>
50 where 50 where
51 G: SupportGenerator<F, N, Id = BT::Data>, 51 G: SupportGenerator<N, F, Id = BT::Data>,
52 G::SupportType: LocalAnalysis<F, BT::Agg, N>, 52 G::SupportType: LocalAnalysis<F, BT::Agg, N>,
53 BT: BTImpl<F, N>, 53 BT: BTImpl<N, F>,
54 { 54 {
55 /// Create a new BTFN from a support generator and a pre-initialised bisection tree. 55 /// Create a new BTFN from a support generator and a pre-initialised bisection tree.
56 /// 56 ///
57 /// The bisection tree `bt` should be pre-initialised to correspond to the `generator`. 57 /// The bisection tree `bt` should be pre-initialised to correspond to the `generator`.
58 /// Use [`Self::construct`] if no preinitialised tree is available. Use [`Self::new_refresh`] 58 /// Use [`Self::construct`] if no preinitialised tree is available. Use [`Self::new_refresh`]
90 /// Create a new BTFN from a support generator, domain, and depth for a new [`BT`]. 90 /// Create a new BTFN from a support generator, domain, and depth for a new [`BT`].
91 /// 91 ///
92 /// The top node of the created [`BT`] will have the given `domain`. 92 /// The top node of the created [`BT`] will have the given `domain`.
93 /// 93 ///
94 /// See the documentation for [`BTFN`] on the role of the `generator`. 94 /// See the documentation for [`BTFN`] on the role of the `generator`.
95 pub fn construct(domain: Cube<F, N>, depth: BT::Depth, generator: G) -> Self { 95 pub fn construct(domain: Cube<N, F>, depth: BT::Depth, generator: G) -> Self {
96 Self::construct_arc(domain, depth, Arc::new(generator)) 96 Self::construct_arc(domain, depth, Arc::new(generator))
97 } 97 }
98 98
99 fn construct_arc(domain: Cube<F, N>, depth: BT::Depth, generator: Arc<G>) -> Self { 99 fn construct_arc(domain: Cube<N, F>, depth: BT::Depth, generator: Arc<G>) -> Self {
100 let mut bt = BT::new(domain, depth); 100 let mut bt = BT::new(domain, depth);
101 for (d, support) in generator.all_data() { 101 for (d, support) in generator.all_data() {
102 bt.insert(d, &support); 102 bt.insert(d, &support);
103 } 103 }
104 Self::new_arc(bt, generator) 104 Self::new_arc(bt, generator)
109 /// This will construct a [`BTFN`] with the same components and generator as the (consumed) 109 /// This will construct a [`BTFN`] with the same components and generator as the (consumed)
110 /// `self`, but a new `BT` with [`Aggregator`]s of type `ANew`. 110 /// `self`, but a new `BT` with [`Aggregator`]s of type `ANew`.
111 pub fn convert_aggregator<ANew>(self) -> BTFN<F, G, BT::Converted<ANew>, N> 111 pub fn convert_aggregator<ANew>(self) -> BTFN<F, G, BT::Converted<ANew>, N>
112 where 112 where
113 ANew: Aggregator, 113 ANew: Aggregator,
114 G: SupportGenerator<F, N, Id = BT::Data>, 114 G: SupportGenerator<N, F, Id = BT::Data>,
115 G::SupportType: LocalAnalysis<F, ANew, N>, 115 G::SupportType: LocalAnalysis<F, ANew, N>,
116 { 116 {
117 BTFN::new_arc(self.bt.convert_aggregator(&*self.generator), self.generator) 117 BTFN::new_arc(self.bt.convert_aggregator(&*self.generator), self.generator)
118 } 118 }
119 119
128 } 128 }
129 } 129 }
130 130
131 impl<F: Float, G, BT, const N: usize> BTFN<F, G, BT, N> 131 impl<F: Float, G, BT, const N: usize> BTFN<F, G, BT, N>
132 where 132 where
133 G: SupportGenerator<F, N>, 133 G: SupportGenerator<N, F>,
134 { 134 {
135 /// Change the [bisection tree][BTImpl] of the [`BTFN`] to a different one. 135 /// Change the [bisection tree][BTImpl] of the [`BTFN`] to a different one.
136 /// 136 ///
137 /// This can be used to convert a [`PreBTFN`] to a full [`BTFN`], or the change 137 /// This can be used to convert a [`PreBTFN`] to a full [`BTFN`], or the change
138 /// the aggreagator; see also [`self.convert_aggregator`]. 138 /// the aggreagator; see also [`self.convert_aggregator`].
139 pub fn instantiate<BTNew: BTImpl<F, N, Data = G::Id>>( 139 pub fn instantiate<BTNew: BTImpl<N, F, Data = G::Id>>(
140 self, 140 self,
141 domain: Cube<F, N>, 141 domain: Cube<N, F>,
142 depth: BTNew::Depth, 142 depth: BTNew::Depth,
143 ) -> BTFN<F, G, BTNew, N> 143 ) -> BTFN<F, G, BTNew, N>
144 where 144 where
145 G::SupportType: LocalAnalysis<F, BTNew::Agg, N>, 145 G::SupportType: LocalAnalysis<F, BTNew::Agg, N>,
146 { 146 {
155 /// that would be shortly dropped. 155 /// that would be shortly dropped.
156 pub type PreBTFN<F, G, const N: usize> = BTFN<F, G, (), N>; 156 pub type PreBTFN<F, G, const N: usize> = BTFN<F, G, (), N>;
157 157
158 impl<F: Float, G, const N: usize> PreBTFN<F, G, N> 158 impl<F: Float, G, const N: usize> PreBTFN<F, G, N>
159 where 159 where
160 G: SupportGenerator<F, N>, 160 G: SupportGenerator<N, F>,
161 { 161 {
162 /// Create a new [`PreBTFN`] with no bisection tree. 162 /// Create a new [`PreBTFN`] with no bisection tree.
163 pub fn new_pre(generator: G) -> Self { 163 pub fn new_pre(generator: G) -> Self {
164 BTFN { 164 BTFN {
165 bt: (), 165 bt: (),
169 } 169 }
170 } 170 }
171 171
172 impl<F: Float, G, BT, const N: usize> BTFN<F, G, BT, N> 172 impl<F: Float, G, BT, const N: usize> BTFN<F, G, BT, N>
173 where 173 where
174 G: SupportGenerator<F, N, Id = usize>, 174 G: SupportGenerator<N, F, Id = usize>,
175 G::SupportType: LocalAnalysis<F, BT::Agg, N>, 175 G::SupportType: LocalAnalysis<F, BT::Agg, N>,
176 BT: BTImpl<F, N, Data = usize>, 176 BT: BTImpl<N, F, Data = usize>,
177 { 177 {
178 /// Helper function for implementing [`std::ops::Add`]. 178 /// Helper function for implementing [`std::ops::Add`].
179 fn add_another<G2>(&self, g2: Arc<G2>) -> BTFN<F, BothGenerators<G, G2>, BT, N> 179 fn add_another<G2>(&self, g2: Arc<G2>) -> BTFN<F, BothGenerators<G, G2>, BT, N>
180 where 180 where
181 G2: SupportGenerator<F, N, Id = usize>, 181 G2: SupportGenerator<N, F, Id = usize>,
182 G2::SupportType: LocalAnalysis<F, BT::Agg, N>, 182 G2::SupportType: LocalAnalysis<F, BT::Agg, N>,
183 { 183 {
184 let mut bt = self.bt.clone(); 184 let mut bt = self.bt.clone();
185 let both = BothGenerators(Arc::clone(&self.generator), g2); 185 let both = BothGenerators(Arc::clone(&self.generator), g2);
186 186
199 macro_rules! make_btfn_add { 199 macro_rules! make_btfn_add {
200 ($lhs:ty, $preprocess:path, $($extra_trait:ident)?) => { 200 ($lhs:ty, $preprocess:path, $($extra_trait:ident)?) => {
201 impl<'a, F : Float, G1, G2, BT1, BT2, const N : usize> 201 impl<'a, F : Float, G1, G2, BT1, BT2, const N : usize>
202 std::ops::Add<BTFN<F, G2, BT2, N>> for 202 std::ops::Add<BTFN<F, G2, BT2, N>> for
203 $lhs 203 $lhs
204 where BT1 : BTImpl<F, N, Data=usize>, 204 where BT1 : BTImpl< N, F, Data=usize>,
205 G1 : SupportGenerator<F, N, Id=usize> + $($extra_trait)?, 205 G1 : SupportGenerator< N, F, Id=usize> + $($extra_trait)?,
206 G2 : SupportGenerator<F, N, Id=usize>, 206 G2 : SupportGenerator< N, F, Id=usize>,
207 G1::SupportType : LocalAnalysis<F, BT1::Agg, N>, 207 G1::SupportType : LocalAnalysis<F, BT1::Agg, N>,
208 G2::SupportType : LocalAnalysis<F, BT1::Agg, N> { 208 G2::SupportType : LocalAnalysis<F, BT1::Agg, N> {
209 type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>; 209 type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>;
210 #[inline] 210 #[inline]
211 fn add(self, other : BTFN<F, G2, BT2, N>) -> Self::Output { 211 fn add(self, other : BTFN<F, G2, BT2, N>) -> Self::Output {
214 } 214 }
215 215
216 impl<'a, 'b, F : Float, G1, G2, BT1, BT2, const N : usize> 216 impl<'a, 'b, F : Float, G1, G2, BT1, BT2, const N : usize>
217 std::ops::Add<&'b BTFN<F, G2, BT2, N>> for 217 std::ops::Add<&'b BTFN<F, G2, BT2, N>> for
218 $lhs 218 $lhs
219 where BT1 : BTImpl<F, N, Data=usize>, 219 where BT1 : BTImpl< N, F, Data=usize>,
220 G1 : SupportGenerator<F, N, Id=usize> + $($extra_trait)?, 220 G1 : SupportGenerator< N, F, Id=usize> + $($extra_trait)?,
221 G2 : SupportGenerator<F, N, Id=usize>, 221 G2 : SupportGenerator< N, F, Id=usize>,
222 G1::SupportType : LocalAnalysis<F, BT1::Agg, N>, 222 G1::SupportType : LocalAnalysis<F, BT1::Agg, N>,
223 G2::SupportType : LocalAnalysis<F, BT1::Agg, N> { 223 G2::SupportType : LocalAnalysis<F, BT1::Agg, N> {
224 224
225 type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>; 225 type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>;
226 #[inline] 226 #[inline]
237 macro_rules! make_btfn_sub { 237 macro_rules! make_btfn_sub {
238 ($lhs:ty, $preprocess:path, $($extra_trait:ident)?) => { 238 ($lhs:ty, $preprocess:path, $($extra_trait:ident)?) => {
239 impl<'a, F : Float, G1, G2, BT1, BT2, const N : usize> 239 impl<'a, F : Float, G1, G2, BT1, BT2, const N : usize>
240 std::ops::Sub<BTFN<F, G2, BT2, N>> for 240 std::ops::Sub<BTFN<F, G2, BT2, N>> for
241 $lhs 241 $lhs
242 where BT1 : BTImpl<F, N, Data=usize>, 242 where BT1 : BTImpl< N, F, Data=usize>,
243 G1 : SupportGenerator<F, N, Id=usize> + $($extra_trait)?, 243 G1 : SupportGenerator< N, F, Id=usize> + $($extra_trait)?,
244 G2 : SupportGenerator<F, N, Id=usize>, 244 G2 : SupportGenerator< N, F, Id=usize>,
245 G1::SupportType : LocalAnalysis<F, BT1::Agg, N>, 245 G1::SupportType : LocalAnalysis<F, BT1::Agg, N>,
246 G2::SupportType : LocalAnalysis<F, BT1::Agg, N> { 246 G2::SupportType : LocalAnalysis<F, BT1::Agg, N> {
247 type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>; 247 type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>;
248 #[inline] 248 #[inline]
249 fn sub(self, other : BTFN<F, G2, BT2, N>) -> Self::Output { 249 fn sub(self, other : BTFN<F, G2, BT2, N>) -> Self::Output {
256 } 256 }
257 257
258 impl<'a, 'b, F : Float, G1, G2, BT1, BT2, const N : usize> 258 impl<'a, 'b, F : Float, G1, G2, BT1, BT2, const N : usize>
259 std::ops::Sub<&'b BTFN<F, G2, BT2, N>> for 259 std::ops::Sub<&'b BTFN<F, G2, BT2, N>> for
260 $lhs 260 $lhs
261 where BT1 : BTImpl<F, N, Data=usize>, 261 where BT1 : BTImpl< N, F, Data=usize>,
262 G1 : SupportGenerator<F, N, Id=usize> + $($extra_trait)?, 262 G1 : SupportGenerator< N, F, Id=usize> + $($extra_trait)?,
263 G2 : SupportGenerator<F, N, Id=usize> + Clone, 263 G2 : SupportGenerator< N, F, Id=usize> + Clone,
264 G1::SupportType : LocalAnalysis<F, BT1::Agg, N>, 264 G1::SupportType : LocalAnalysis<F, BT1::Agg, N>,
265 G2::SupportType : LocalAnalysis<F, BT1::Agg, N>, 265 G2::SupportType : LocalAnalysis<F, BT1::Agg, N>,
266 &'b G2 : std::ops::Neg<Output=G2> { 266 &'b G2 : std::ops::Neg<Output=G2> {
267 267
268 type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>; 268 type Output = BTFN<F, BothGenerators<G1, G2>, BT1, N>;
279 279
280 macro_rules! make_btfn_scalarop_rhs { 280 macro_rules! make_btfn_scalarop_rhs {
281 ($trait:ident, $fn:ident, $trait_assign:ident, $fn_assign:ident) => { 281 ($trait:ident, $fn:ident, $trait_assign:ident, $fn_assign:ident) => {
282 impl<F: Float, G, BT, const N: usize> std::ops::$trait_assign<F> for BTFN<F, G, BT, N> 282 impl<F: Float, G, BT, const N: usize> std::ops::$trait_assign<F> for BTFN<F, G, BT, N>
283 where 283 where
284 BT: BTImpl<F, N>, 284 BT: BTImpl<N, F>,
285 G: SupportGenerator<F, N, Id = BT::Data>, 285 G: SupportGenerator<N, F, Id = BT::Data>,
286 G::SupportType: LocalAnalysis<F, BT::Agg, N>, 286 G::SupportType: LocalAnalysis<F, BT::Agg, N>,
287 { 287 {
288 #[inline] 288 #[inline]
289 fn $fn_assign(&mut self, t: F) { 289 fn $fn_assign(&mut self, t: F) {
290 Arc::make_mut(&mut self.generator).$fn_assign(t); 290 Arc::make_mut(&mut self.generator).$fn_assign(t);
292 } 292 }
293 } 293 }
294 294
295 impl<F: Float, G, BT, const N: usize> std::ops::$trait<F> for BTFN<F, G, BT, N> 295 impl<F: Float, G, BT, const N: usize> std::ops::$trait<F> for BTFN<F, G, BT, N>
296 where 296 where
297 BT: BTImpl<F, N>, 297 BT: BTImpl<N, F>,
298 G: SupportGenerator<F, N, Id = BT::Data>, 298 G: SupportGenerator<N, F, Id = BT::Data>,
299 G::SupportType: LocalAnalysis<F, BT::Agg, N>, 299 G::SupportType: LocalAnalysis<F, BT::Agg, N>,
300 { 300 {
301 type Output = Self; 301 type Output = Self;
302 #[inline] 302 #[inline]
303 fn $fn(mut self, t: F) -> Self::Output { 303 fn $fn(mut self, t: F) -> Self::Output {
307 } 307 }
308 } 308 }
309 309
310 impl<'a, F: Float, G, BT, const N: usize> std::ops::$trait<F> for &'a BTFN<F, G, BT, N> 310 impl<'a, F: Float, G, BT, const N: usize> std::ops::$trait<F> for &'a BTFN<F, G, BT, N>
311 where 311 where
312 BT: BTImpl<F, N>, 312 BT: BTImpl<N, F>,
313 G: SupportGenerator<F, N, Id = BT::Data>, 313 G: SupportGenerator<N, F, Id = BT::Data>,
314 G::SupportType: LocalAnalysis<F, BT::Agg, N>, 314 G::SupportType: LocalAnalysis<F, BT::Agg, N>,
315 &'a G: std::ops::$trait<F, Output = G>, 315 &'a G: std::ops::$trait<F, Output = G>,
316 { 316 {
317 type Output = BTFN<F, G, BT, N>; 317 type Output = BTFN<F, G, BT, N>;
318 #[inline] 318 #[inline]
329 macro_rules! make_btfn_scalarop_lhs { 329 macro_rules! make_btfn_scalarop_lhs {
330 ($trait:ident, $fn:ident, $fn_assign:ident, $($f:ident)+) => { $( 330 ($trait:ident, $fn:ident, $fn_assign:ident, $($f:ident)+) => { $(
331 impl<G, BT, const N : usize> 331 impl<G, BT, const N : usize>
332 std::ops::$trait<BTFN<$f, G, BT, N>> 332 std::ops::$trait<BTFN<$f, G, BT, N>>
333 for $f 333 for $f
334 where BT : BTImpl<$f, N>, 334 where BT : BTImpl< N, $f>,
335 G : SupportGenerator<$f, N, Id=BT::Data>, 335 G : SupportGenerator< N, $f, Id=BT::Data>,
336 G::SupportType : LocalAnalysis<$f, BT::Agg, N> { 336 G::SupportType : LocalAnalysis<$f, BT::Agg, N> {
337 type Output = BTFN<$f, G, BT, N>; 337 type Output = BTFN<$f, G, BT, N>;
338 #[inline] 338 #[inline]
339 fn $fn(self, mut a : BTFN<$f, G, BT, N>) -> Self::Output { 339 fn $fn(self, mut a : BTFN<$f, G, BT, N>) -> Self::Output {
340 Arc::make_mut(&mut a.generator).$fn_assign(self); 340 Arc::make_mut(&mut a.generator).$fn_assign(self);
344 } 344 }
345 345
346 impl<'a, G, BT, const N : usize> 346 impl<'a, G, BT, const N : usize>
347 std::ops::$trait<&'a BTFN<$f, G, BT, N>> 347 std::ops::$trait<&'a BTFN<$f, G, BT, N>>
348 for $f 348 for $f
349 where BT : BTImpl<$f, N>, 349 where BT : BTImpl< N, $f>,
350 G : SupportGenerator<$f, N, Id=BT::Data> + Clone, 350 G : SupportGenerator< N, $f, Id=BT::Data> + Clone,
351 G::SupportType : LocalAnalysis<$f, BT::Agg, N>, 351 G::SupportType : LocalAnalysis<$f, BT::Agg, N>,
352 // FIXME: This causes compiler overflow 352 // FIXME: This causes compiler overflow
353 /*&'a G : std::ops::$trait<$f,Output=G>*/ { 353 /*&'a G : std::ops::$trait<$f,Output=G>*/ {
354 type Output = BTFN<$f, G, BT, N>; 354 type Output = BTFN<$f, G, BT, N>;
355 #[inline] 355 #[inline]
369 369
370 macro_rules! make_btfn_unaryop { 370 macro_rules! make_btfn_unaryop {
371 ($trait:ident, $fn:ident) => { 371 ($trait:ident, $fn:ident) => {
372 impl<F: Float, G, BT, const N: usize> std::ops::$trait for BTFN<F, G, BT, N> 372 impl<F: Float, G, BT, const N: usize> std::ops::$trait for BTFN<F, G, BT, N>
373 where 373 where
374 BT: BTImpl<F, N>, 374 BT: BTImpl<N, F>,
375 G: SupportGenerator<F, N, Id = BT::Data>, 375 G: SupportGenerator<N, F, Id = BT::Data>,
376 G::SupportType: LocalAnalysis<F, BT::Agg, N>, 376 G::SupportType: LocalAnalysis<F, BT::Agg, N>,
377 { 377 {
378 type Output = Self; 378 type Output = Self;
379 #[inline] 379 #[inline]
380 fn $fn(mut self) -> Self::Output { 380 fn $fn(mut self) -> Self::Output {
385 } 385 }
386 386
387 /*impl<'a, F : Float, G, BT, const N : usize> 387 /*impl<'a, F : Float, G, BT, const N : usize>
388 std::ops::$trait 388 std::ops::$trait
389 for &'a BTFN<F, G, BT, N> 389 for &'a BTFN<F, G, BT, N>
390 where BT : BTImpl<F, N>, 390 where BT : BTImpl< N, F>,
391 G : SupportGenerator<F, N, Id=BT::Data>, 391 G : SupportGenerator< N, F, Id=BT::Data>,
392 G::SupportType : LocalAnalysis<F, BT::Agg, N>, 392 G::SupportType : LocalAnalysis<F, BT::Agg, N>,
393 &'a G : std::ops::$trait<Output=G> { 393 &'a G : std::ops::$trait<Output=G> {
394 type Output = BTFN<F, G, BT, N>; 394 type Output = BTFN<F, G, BT, N>;
395 #[inline] 395 #[inline]
396 fn $fn(self) -> Self::Output { 396 fn $fn(self) -> Self::Output {
404 404
405 // 405 //
406 // Apply, Mapping, Differentiate 406 // Apply, Mapping, Differentiate
407 // 407 //
408 408
409 impl<F: Float, G, BT, V, const N: usize> Mapping<Loc<F, N>> for BTFN<F, G, BT, N> 409 impl<F: Float, G, BT, V, const N: usize> Mapping<Loc<N, F>> for BTFN<F, G, BT, N>
410 where 410 where
411 BT: BTImpl<F, N>, 411 BT: BTImpl<N, F>,
412 G: SupportGenerator<F, N, Id = BT::Data>, 412 G: SupportGenerator<N, F, Id = BT::Data>,
413 G::SupportType: LocalAnalysis<F, BT::Agg, N> + Mapping<Loc<F, N>, Codomain = V>, 413 G::SupportType: LocalAnalysis<F, BT::Agg, N> + Mapping<Loc<N, F>, Codomain = V>,
414 V: Sum + Space, 414 V: Sum + Space,
415 { 415 {
416 type Codomain = V; 416 type Codomain = V;
417 417
418 fn apply<I: Instance<Loc<F, N>>>(&self, x: I) -> Self::Codomain { 418 fn apply<I: Instance<Loc<N, F>>>(&self, x: I) -> Self::Codomain {
419 let xc = x.cow(); 419 let xc = x.cow();
420 self.bt 420 self.bt
421 .iter_at(&*xc) 421 .iter_at(&*xc)
422 .map(|&d| self.generator.support_for(d).apply(&*xc)) 422 .map(|&d| self.generator.support_for(d).apply(&*xc))
423 .sum() 423 .sum()
424 } 424 }
425 } 425 }
426 426
427 impl<F: Float, G, BT, V, const N: usize> DifferentiableImpl<Loc<F, N>> for BTFN<F, G, BT, N> 427 impl<F: Float, G, BT, V, const N: usize> DifferentiableImpl<Loc<N, F>> for BTFN<F, G, BT, N>
428 where 428 where
429 BT: BTImpl<F, N>, 429 BT: BTImpl<N, F>,
430 G: SupportGenerator<F, N, Id = BT::Data>, 430 G: SupportGenerator<N, F, Id = BT::Data>,
431 G::SupportType: 431 G::SupportType:
432 LocalAnalysis<F, BT::Agg, N> + DifferentiableMapping<Loc<F, N>, DerivativeDomain = V>, 432 LocalAnalysis<F, BT::Agg, N> + DifferentiableMapping<Loc<N, F>, DerivativeDomain = V>,
433 V: Sum + Space, 433 V: Sum + Space,
434 { 434 {
435 type Derivative = V; 435 type Derivative = V;
436 436
437 fn differential_impl<I: Instance<Loc<F, N>>>(&self, x: I) -> Self::Derivative { 437 fn differential_impl<I: Instance<Loc<N, F>>>(&self, x: I) -> Self::Derivative {
438 let xc = x.cow(); 438 let xc = x.cow();
439 self.bt 439 self.bt
440 .iter_at(&*xc) 440 .iter_at(&*xc)
441 .map(|&d| self.generator.support_for(d).differential(&*xc)) 441 .map(|&d| self.generator.support_for(d).differential(&*xc))
442 .sum() 442 .sum()
447 // GlobalAnalysis 447 // GlobalAnalysis
448 // 448 //
449 449
450 impl<F: Float, G, BT, const N: usize> GlobalAnalysis<F, BT::Agg> for BTFN<F, G, BT, N> 450 impl<F: Float, G, BT, const N: usize> GlobalAnalysis<F, BT::Agg> for BTFN<F, G, BT, N>
451 where 451 where
452 BT: BTImpl<F, N>, 452 BT: BTImpl<N, F>,
453 G: SupportGenerator<F, N, Id = BT::Data>, 453 G: SupportGenerator<N, F, Id = BT::Data>,
454 G::SupportType: LocalAnalysis<F, BT::Agg, N>, 454 G::SupportType: LocalAnalysis<F, BT::Agg, N>,
455 { 455 {
456 #[inline] 456 #[inline]
457 fn global_analysis(&self) -> BT::Agg { 457 fn global_analysis(&self) -> BT::Agg {
458 self.bt.global_analysis() 458 self.bt.global_analysis()
465 // 465 //
466 466
467 /* 467 /*
468 impl<'b, X, F : Float, G, BT, const N : usize> Apply<&'b X, F> 468 impl<'b, X, F : Float, G, BT, const N : usize> Apply<&'b X, F>
469 for BTFN<F, G, BT, N> 469 for BTFN<F, G, BT, N>
470 where BT : BTImpl<F, N>, 470 where BT : BTImpl< N, F>,
471 G : SupportGenerator<F, N, Id=BT::Data>, 471 G : SupportGenerator< N, F, Id=BT::Data>,
472 G::SupportType : LocalAnalysis<F, BT::Agg, N>, 472 G::SupportType : LocalAnalysis<F, BT::Agg, N>,
473 X : for<'a> Apply<&'a BTFN<F, G, BT, N>, F> { 473 X : for<'a> Apply<&'a BTFN<F, G, BT, N>, F> {
474 474
475 #[inline] 475 #[inline]
476 fn apply(&self, x : &'b X) -> F { 476 fn apply(&self, x : &'b X) -> F {
478 } 478 }
479 } 479 }
480 480
481 impl<X, F : Float, G, BT, const N : usize> Apply<X, F> 481 impl<X, F : Float, G, BT, const N : usize> Apply<X, F>
482 for BTFN<F, G, BT, N> 482 for BTFN<F, G, BT, N>
483 where BT : BTImpl<F, N>, 483 where BT : BTImpl< N, F>,
484 G : SupportGenerator<F, N, Id=BT::Data>, 484 G : SupportGenerator< N, F, Id=BT::Data>,
485 G::SupportType : LocalAnalysis<F, BT::Agg, N>, 485 G::SupportType : LocalAnalysis<F, BT::Agg, N>,
486 X : for<'a> Apply<&'a BTFN<F, G, BT, N>, F> { 486 X : for<'a> Apply<&'a BTFN<F, G, BT, N>, F> {
487 487
488 #[inline] 488 #[inline]
489 fn apply(&self, x : X) -> F { 489 fn apply(&self, x : X) -> F {
491 } 491 }
492 } 492 }
493 493
494 impl<X, F : Float, G, BT, const N : usize> Linear<X> 494 impl<X, F : Float, G, BT, const N : usize> Linear<X>
495 for BTFN<F, G, BT, N> 495 for BTFN<F, G, BT, N>
496 where BT : BTImpl<F, N>, 496 where BT : BTImpl< N, F>,
497 G : SupportGenerator<F, N, Id=BT::Data>, 497 G : SupportGenerator< N, F, Id=BT::Data>,
498 G::SupportType : LocalAnalysis<F, BT::Agg, N>, 498 G::SupportType : LocalAnalysis<F, BT::Agg, N>,
499 X : for<'a> Apply<&'a BTFN<F, G, BT, N>, F> { 499 X : for<'a> Apply<&'a BTFN<F, G, BT, N>, F> {
500 type Codomain = F; 500 type Codomain = F;
501 } 501 }
502 */ 502 */
510 /// 510 ///
511 /// The function returns `(x, v)` where `x` is the minimiser `v` an approximation of `g(x)`. 511 /// The function returns `(x, v)` where `x` is the minimiser `v` an approximation of `g(x)`.
512 fn p2_minimise<G: Fn(&U) -> F>(&self, g: G) -> (U, F); 512 fn p2_minimise<G: Fn(&U) -> F>(&self, g: G) -> (U, F);
513 } 513 }
514 514
515 impl<F: Float> P2Minimise<Loc<F, 1>, F> for Cube<F, 1> { 515 impl<F: Float> P2Minimise<Loc<1, F>, F> for Cube<1, F> {
516 fn p2_minimise<G: Fn(&Loc<F, 1>) -> F>(&self, g: G) -> (Loc<F, 1>, F) { 516 fn p2_minimise<G: Fn(&Loc<1, F>) -> F>(&self, g: G) -> (Loc<1, F>, F) {
517 let interval = Simplex(self.corners()); 517 let interval = Simplex(self.corners());
518 interval.p2_model(&g).minimise(&interval) 518 interval.p2_model(&g).minimise(&interval)
519 } 519 }
520 } 520 }
521 521
522 #[replace_float_literals(F::cast_from(literal))] 522 #[replace_float_literals(F::cast_from(literal))]
523 impl<F: Float> P2Minimise<Loc<F, 2>, F> for Cube<F, 2> { 523 impl<F: Float> P2Minimise<Loc<2, F>, F> for Cube<2, F> {
524 fn p2_minimise<G: Fn(&Loc<F, 2>) -> F>(&self, g: G) -> (Loc<F, 2>, F) { 524 fn p2_minimise<G: Fn(&Loc<2, F>) -> F>(&self, g: G) -> (Loc<2, F>, F) {
525 if false { 525 if false {
526 // Split into two triangle (simplex) with separate P2 model in each. 526 // Split into two triangle (simplex) with separate P2 model in each.
527 // The six nodes of each triangle are the corners and the edges. 527 // The six nodes of each triangle are the corners and the edges.
528 let [a, b, c, d] = self.corners(); 528 let [a, b, c, d] = self.corners();
529 let [va, vb, vc, vd] = [g(&a), g(&b), g(&c), g(&d)]; 529 let [va, vb, vc, vd] = [g(&a), g(&b), g(&c), g(&d)];
604 how: T, 604 how: T,
605 } 605 }
606 606
607 impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for P2Refiner<F, RefineMax> 607 impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for P2Refiner<F, RefineMax>
608 where 608 where
609 Cube<F, N>: P2Minimise<Loc<F, N>, F>, 609 Cube<N, F>: P2Minimise<Loc<N, F>, F>,
610 G: SupportGenerator<F, N>, 610 G: SupportGenerator<N, F>,
611 G::SupportType: Mapping<Loc<F, N>, Codomain = F> + LocalAnalysis<F, Bounds<F>, N>, 611 G::SupportType: Mapping<Loc<N, F>, Codomain = F> + LocalAnalysis<F, Bounds<F>, N>,
612 { 612 {
613 type Result = Option<(Loc<F, N>, F)>; 613 type Result = Option<(Loc<N, F>, F)>;
614 type Sorting = UpperBoundSorting<F>; 614 type Sorting = UpperBoundSorting<F>;
615 615
616 fn refine( 616 fn refine(
617 &self, 617 &self,
618 aggregator: &Bounds<F>, 618 aggregator: &Bounds<F>,
619 cube: &Cube<F, N>, 619 cube: &Cube<N, F>,
620 data: &[G::Id], 620 data: &[G::Id],
621 generator: &G, 621 generator: &G,
622 step: usize, 622 step: usize,
623 ) -> RefinerResult<Bounds<F>, Self::Result> { 623 ) -> RefinerResult<Bounds<F>, Self::Result> {
624 if self 624 if self
628 // The upper bound is below the maximisation threshold. Don't bother with this cube. 628 // The upper bound is below the maximisation threshold. Don't bother with this cube.
629 return RefinerResult::Uncertain(*aggregator, None); 629 return RefinerResult::Uncertain(*aggregator, None);
630 } 630 }
631 631
632 // g gives the negative of the value of the function presented by `data` and `generator`. 632 // g gives the negative of the value of the function presented by `data` and `generator`.
633 let g = move |x: &Loc<F, N>| { 633 let g = move |x: &Loc<N, F>| {
634 let f = move |&d| generator.support_for(d).apply(x); 634 let f = move |&d| generator.support_for(d).apply(x);
635 -data.iter().map(f).sum::<F>() 635 -data.iter().map(f).sum::<F>()
636 }; 636 };
637 // … so the negative of the minimum is the maximm we want. 637 // … so the negative of the minimum is the maximm we want.
638 let (x, _neg_v) = cube.p2_minimise(g); 638 let (x, _neg_v) = cube.p2_minimise(g);
667 } 667 }
668 } 668 }
669 669
670 impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for P2Refiner<F, RefineMin> 670 impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for P2Refiner<F, RefineMin>
671 where 671 where
672 Cube<F, N>: P2Minimise<Loc<F, N>, F>, 672 Cube<N, F>: P2Minimise<Loc<N, F>, F>,
673 G: SupportGenerator<F, N>, 673 G: SupportGenerator<N, F>,
674 G::SupportType: Mapping<Loc<F, N>, Codomain = F> + LocalAnalysis<F, Bounds<F>, N>, 674 G::SupportType: Mapping<Loc<N, F>, Codomain = F> + LocalAnalysis<F, Bounds<F>, N>,
675 { 675 {
676 type Result = Option<(Loc<F, N>, F)>; 676 type Result = Option<(Loc<N, F>, F)>;
677 type Sorting = LowerBoundSorting<F>; 677 type Sorting = LowerBoundSorting<F>;
678 678
679 fn refine( 679 fn refine(
680 &self, 680 &self,
681 aggregator: &Bounds<F>, 681 aggregator: &Bounds<F>,
682 cube: &Cube<F, N>, 682 cube: &Cube<N, F>,
683 data: &[G::Id], 683 data: &[G::Id],
684 generator: &G, 684 generator: &G,
685 step: usize, 685 step: usize,
686 ) -> RefinerResult<Bounds<F>, Self::Result> { 686 ) -> RefinerResult<Bounds<F>, Self::Result> {
687 if self 687 if self
691 // The lower bound is above the minimisation threshold. Don't bother with this cube. 691 // The lower bound is above the minimisation threshold. Don't bother with this cube.
692 return RefinerResult::Uncertain(*aggregator, None); 692 return RefinerResult::Uncertain(*aggregator, None);
693 } 693 }
694 694
695 // g gives the value of the function presented by `data` and `generator`. 695 // g gives the value of the function presented by `data` and `generator`.
696 let g = move |x: &Loc<F, N>| { 696 let g = move |x: &Loc<N, F>| {
697 let f = move |&d| generator.support_for(d).apply(x); 697 let f = move |&d| generator.support_for(d).apply(x);
698 data.iter().map(f).sum::<F>() 698 data.iter().map(f).sum::<F>()
699 }; 699 };
700 // Minimise it. 700 // Minimise it.
701 let (x, _v) = cube.p2_minimise(g); 701 let (x, _v) = cube.p2_minimise(g);
753 how: T, 753 how: T,
754 } 754 }
755 755
756 impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for BoundRefiner<F, RefineMax> 756 impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for BoundRefiner<F, RefineMax>
757 where 757 where
758 G: SupportGenerator<F, N>, 758 G: SupportGenerator<N, F>,
759 { 759 {
760 type Result = bool; 760 type Result = bool;
761 type Sorting = UpperBoundSorting<F>; 761 type Sorting = UpperBoundSorting<F>;
762 762
763 fn refine( 763 fn refine(
764 &self, 764 &self,
765 aggregator: &Bounds<F>, 765 aggregator: &Bounds<F>,
766 _cube: &Cube<F, N>, 766 _cube: &Cube<N, F>,
767 _data: &[G::Id], 767 _data: &[G::Id],
768 _generator: &G, 768 _generator: &G,
769 step: usize, 769 step: usize,
770 ) -> RefinerResult<Bounds<F>, Self::Result> { 770 ) -> RefinerResult<Bounds<F>, Self::Result> {
771 if aggregator.upper() <= self.bound + self.tolerance { 771 if aggregator.upper() <= self.bound + self.tolerance {
788 } 788 }
789 } 789 }
790 790
791 impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for BoundRefiner<F, RefineMin> 791 impl<F: Float, G, const N: usize> Refiner<F, Bounds<F>, G, N> for BoundRefiner<F, RefineMin>
792 where 792 where
793 G: SupportGenerator<F, N>, 793 G: SupportGenerator<N, F>,
794 { 794 {
795 type Result = bool; 795 type Result = bool;
796 type Sorting = UpperBoundSorting<F>; 796 type Sorting = UpperBoundSorting<F>;
797 797
798 fn refine( 798 fn refine(
799 &self, 799 &self,
800 aggregator: &Bounds<F>, 800 aggregator: &Bounds<F>,
801 _cube: &Cube<F, N>, 801 _cube: &Cube<N, F>,
802 _data: &[G::Id], 802 _data: &[G::Id],
803 _generator: &G, 803 _generator: &G,
804 step: usize, 804 step: usize,
805 ) -> RefinerResult<Bounds<F>, Self::Result> { 805 ) -> RefinerResult<Bounds<F>, Self::Result> {
806 if aggregator.lower() >= self.bound - self.tolerance { 806 if aggregator.lower() >= self.bound - self.tolerance {
836 // the queue. If the queue empties as a result of that, the thread goes to wait for other threads 836 // the queue. If the queue empties as a result of that, the thread goes to wait for other threads
837 // to produce results. Since some node had a node whose lower bound was above the `glb`, eventually 837 // to produce results. Since some node had a node whose lower bound was above the `glb`, eventually
838 // there should be a result, or new nodes above the `glb` inserted into the queue. Then the waiting 838 // there should be a result, or new nodes above the `glb` inserted into the queue. Then the waiting
839 // threads can also continue processing. If, however, numerical inaccuracy destroyes the `glb`, 839 // threads can also continue processing. If, however, numerical inaccuracy destroyes the `glb`,
840 // the queue may run out, and we get “Refiner failure”. 840 // the queue may run out, and we get “Refiner failure”.
841 impl<F: Float, G, BT, const N: usize> MinMaxMapping<F, N> for BTFN<F, G, BT, N> 841 impl<F: Float, G, BT, const N: usize> MinMaxMapping<N, F> for BTFN<F, G, BT, N>
842 where 842 where
843 BT: BTSearch<F, N, Agg = Bounds<F>>, 843 BT: BTSearch<N, F, Agg = Bounds<F>>,
844 G: SupportGenerator<F, N, Id = BT::Data>, 844 G: SupportGenerator<N, F, Id = BT::Data>,
845 G::SupportType: Mapping<Loc<F, N>, Codomain = F> + LocalAnalysis<F, Bounds<F>, N>, 845 G::SupportType: Mapping<Loc<N, F>, Codomain = F> + LocalAnalysis<F, Bounds<F>, N>,
846 Cube<F, N>: P2Minimise<Loc<F, N>, F>, 846 Cube<N, F>: P2Minimise<Loc<N, F>, F>,
847 { 847 {
848 fn maximise(&mut self, tolerance: F, max_steps: usize) -> (Loc<F, N>, F) { 848 fn maximise(&mut self, tolerance: F, max_steps: usize) -> (Loc<N, F>, F) {
849 let refiner = P2Refiner { 849 let refiner = P2Refiner {
850 tolerance, 850 tolerance,
851 max_steps, 851 max_steps,
852 how: RefineMax, 852 how: RefineMax,
853 bound: None, 853 bound: None,
861 fn maximise_above( 861 fn maximise_above(
862 &mut self, 862 &mut self,
863 bound: F, 863 bound: F,
864 tolerance: F, 864 tolerance: F,
865 max_steps: usize, 865 max_steps: usize,
866 ) -> Option<(Loc<F, N>, F)> { 866 ) -> Option<(Loc<N, F>, F)> {
867 let refiner = P2Refiner { 867 let refiner = P2Refiner {
868 tolerance, 868 tolerance,
869 max_steps, 869 max_steps,
870 how: RefineMax, 870 how: RefineMax,
871 bound: Some(bound), 871 bound: Some(bound),
873 self.bt 873 self.bt
874 .search_and_refine(refiner, &self.generator) 874 .search_and_refine(refiner, &self.generator)
875 .expect("Refiner failure.") 875 .expect("Refiner failure.")
876 } 876 }
877 877
878 fn minimise(&mut self, tolerance: F, max_steps: usize) -> (Loc<F, N>, F) { 878 fn minimise(&mut self, tolerance: F, max_steps: usize) -> (Loc<N, F>, F) {
879 let refiner = P2Refiner { 879 let refiner = P2Refiner {
880 tolerance, 880 tolerance,
881 max_steps, 881 max_steps,
882 how: RefineMin, 882 how: RefineMin,
883 bound: None, 883 bound: None,
891 fn minimise_below( 891 fn minimise_below(
892 &mut self, 892 &mut self,
893 bound: F, 893 bound: F,
894 tolerance: F, 894 tolerance: F,
895 max_steps: usize, 895 max_steps: usize,
896 ) -> Option<(Loc<F, N>, F)> { 896 ) -> Option<(Loc<N, F>, F)> {
897 let refiner = P2Refiner { 897 let refiner = P2Refiner {
898 tolerance, 898 tolerance,
899 max_steps, 899 max_steps,
900 how: RefineMin, 900 how: RefineMin,
901 bound: Some(bound), 901 bound: Some(bound),

Mercurial Repository: alg_tools

mercurial