Mercurial > repos > alg_tools / file comparison

comparison: src/bisection_tree/refine.rs

src/bisection_tree/refine.rs

branch
dev
changeset 124
6aa955ad8122
parent 94
1f19c6bbf07b
equal deleted inserted replaced
122:495448cca603 124:6aa955ad8122
1 1 use super::aggregator::*;
2 use super::bt::*;
3 use super::support::*;
4 use crate::nanleast::NaNLeast;
5 use crate::parallelism::TaskBudget;
6 use crate::parallelism::{thread_pool, thread_pool_size};
7 use crate::sets::Cube;
8 use crate::types::*;
9 use std::cmp::{max, Ord, Ordering, Ordering::*, PartialOrd};
2 use std::collections::BinaryHeap; 10 use std::collections::BinaryHeap;
3 use std::cmp::{PartialOrd, Ord, Ordering, Ordering::*, max};
4 use std::marker::PhantomData; 11 use std::marker::PhantomData;
5 use std::sync::{Arc, Mutex, MutexGuard, Condvar}; 12 use std::sync::{Arc, Condvar, Mutex, MutexGuard};
6 use crate::types::*;
7 use crate::nanleast::NaNLeast;
8 use crate::sets::Cube;
9 use crate::parallelism::{thread_pool_size, thread_pool};
10 use super::support::*;
11 use super::bt::*;
12 use super::aggregator::*;
13 use crate::parallelism::TaskBudget;
14 13
15 /// Trait for sorting [`Aggregator`]s for [`BT`] refinement. 14 /// Trait for sorting [`Aggregator`]s for [`BT`] refinement.
16 /// 15 ///
17 /// The sorting involves two sorting keys, the “upper” and the “lower” key. Any [`BT`] nodes 16 /// The sorting involves two sorting keys, the “upper” and the “lower” key. Any [`BT`] nodes
18 /// with upper key less the lower key of another are discarded from the refinement process. 17 /// with upper key less the lower key of another are discarded from the refinement process.
19 /// Nodes with the highest upper sorting key are picked for refinement. 18 /// Nodes with the highest upper sorting key are picked for refinement.
20 pub trait AggregatorSorting : Sync + Send + 'static { 19 pub trait AggregatorSorting: Sync + Send + 'static {
21 // Priority 20 // Priority
22 type Agg : Aggregator; 21 type Agg: Aggregator;
23 type Sort : Ord + Copy + std::fmt::Debug + Sync + Send; 22 type Sort: Ord + Copy + std::fmt::Debug + Sync + Send;
24 23
25 /// Returns lower sorting key 24 /// Returns lower sorting key
26 fn sort_lower(aggregator : &Self::Agg) -> Self::Sort; 25 fn sort_lower(aggregator: &Self::Agg) -> Self::Sort;
27 26
28 /// Returns upper sorting key 27 /// Returns upper sorting key
29 fn sort_upper(aggregator : &Self::Agg) -> Self::Sort; 28 fn sort_upper(aggregator: &Self::Agg) -> Self::Sort;
30 29
31 /// Returns a sorting key that is less than any other sorting key. 30 /// Returns a sorting key that is less than any other sorting key.
32 fn bottom() -> Self::Sort; 31 fn bottom() -> Self::Sort;
33 } 32 }
34 33
35 /// An [`AggregatorSorting`] for [`Bounds`], using the upper/lower bound as the upper/lower key. 34 /// An [`AggregatorSorting`] for [`Bounds`], using the upper/lower bound as the upper/lower key.
36 /// 35 ///
37 /// See [`LowerBoundSorting`] for the opposite ordering. 36 /// See [`LowerBoundSorting`] for the opposite ordering.
38 pub struct UpperBoundSorting<F : Float>(PhantomData<F>); 37 pub struct UpperBoundSorting<F: Float>(PhantomData<F>);
39 38
40 /// An [`AggregatorSorting`] for [`Bounds`], using the upper/lower bound as the lower/upper key. 39 /// An [`AggregatorSorting`] for [`Bounds`], using the upper/lower bound as the lower/upper key.
41 /// 40 ///
42 /// See [`UpperBoundSorting`] for the opposite ordering. 41 /// See [`UpperBoundSorting`] for the opposite ordering.
43 pub struct LowerBoundSorting<F : Float>(PhantomData<F>); 42 pub struct LowerBoundSorting<F: Float>(PhantomData<F>);
44 43
45 impl<F : Float> AggregatorSorting for UpperBoundSorting<F> { 44 impl<F: Float> AggregatorSorting for UpperBoundSorting<F> {
46 type Agg = Bounds<F>; 45 type Agg = Bounds<F>;
47 type Sort = NaNLeast<F>; 46 type Sort = NaNLeast<F>;
48 47
49 #[inline] 48 #[inline]
50 fn sort_lower(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(aggregator.lower()) } 49 fn sort_lower(aggregator: &Bounds<F>) -> Self::Sort {
51 50 NaNLeast(aggregator.lower())
52 #[inline] 51 }
53 fn sort_upper(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(aggregator.upper()) } 52
54 53 #[inline]
55 #[inline] 54 fn sort_upper(aggregator: &Bounds<F>) -> Self::Sort {
56 fn bottom() -> Self::Sort { NaNLeast(F::NEG_INFINITY) } 55 NaNLeast(aggregator.upper())
57 } 56 }
58 57
59 58 #[inline]
60 impl<F : Float> AggregatorSorting for LowerBoundSorting<F> { 59 fn bottom() -> Self::Sort {
60 NaNLeast(F::NEG_INFINITY)
61 }
62 }
63
64 impl<F: Float> AggregatorSorting for LowerBoundSorting<F> {
61 type Agg = Bounds<F>; 65 type Agg = Bounds<F>;
62 type Sort = NaNLeast<F>; 66 type Sort = NaNLeast<F>;
63 67
64 #[inline] 68 #[inline]
65 fn sort_upper(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(-aggregator.lower()) } 69 fn sort_upper(aggregator: &Bounds<F>) -> Self::Sort {
66 70 NaNLeast(-aggregator.lower())
67 #[inline] 71 }
68 fn sort_lower(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(-aggregator.upper()) } 72
69 73 #[inline]
70 #[inline] 74 fn sort_lower(aggregator: &Bounds<F>) -> Self::Sort {
71 fn bottom() -> Self::Sort { NaNLeast(F::NEG_INFINITY) } 75 NaNLeast(-aggregator.upper())
76 }
77
78 #[inline]
79 fn bottom() -> Self::Sort {
80 NaNLeast(F::NEG_INFINITY)
81 }
72 } 82 }
73 83
74 /// Return type of [`Refiner::refine`]. 84 /// Return type of [`Refiner::refine`].
75 /// 85 ///
76 /// The parameter `R` is the result type of the refiner acting on an [`Aggregator`] of type `A`. 86 /// The parameter `R` is the result type of the refiner acting on an [`Aggregator`] of type `A`.
77 pub enum RefinerResult<A : Aggregator, R> { 87 pub enum RefinerResult<A: Aggregator, R> {
78 /// Indicates an insufficiently refined state: the [`BT`] needs to be further refined. 88 /// Indicates an insufficiently refined state: the [`BT`] needs to be further refined.
79 NeedRefinement, 89 NeedRefinement,
80 /// Indicates a certain result `R`, stop refinement immediately. 90 /// Indicates a certain result `R`, stop refinement immediately.
81 Certain(R), 91 Certain(R),
82 /// Indicates an uncertain result: continue refinement until candidates have been exhausted 92 /// Indicates an uncertain result: continue refinement until candidates have been exhausted
83 /// or a certain result found. 93 /// or a certain result found.
84 Uncertain(A, R) 94 Uncertain(A, R),
85 } 95 }
86 96
87 use RefinerResult::*; 97 use RefinerResult::*;
88 98
89 /// A `Refiner` is used to search a [`BT`], refining the subdivision when necessary. 99 /// A `Refiner` is used to search a [`BT`], refining the subdivision when necessary.
90 /// 100 ///
91 /// The search is performed by [`BTSearch::search_and_refine`]. 101 /// The search is performed by [`BTSearch::search_and_refine`].
92 /// The `Refiner` is used to determine whether an [`Aggregator`] `A` stored in the [`BT`] is 102 /// The `Refiner` is used to determine whether an [`Aggregator`] `A` stored in the [`BT`] is
93 /// sufficiently refined within a [`Cube`], and in such a case, produce a desired result (e.g. 103 /// sufficiently refined within a [`Cube`], and in such a case, produce a desired result (e.g.
94 /// a maximum value of a function). 104 /// a maximum value of a function).
95 pub trait Refiner<F : Float, A, G, const N : usize> : Sync + Send + 'static 105 pub trait Refiner<F: Float, A, G, const N: usize>: Sync + Send + 'static
96 where F : Num, 106 where
97 A : Aggregator, 107 F: Num,
98 G : SupportGenerator<F, N> { 108 A: Aggregator,
99 109 G: SupportGenerator<N, F>,
110 {
100 /// The result type of the refiner 111 /// The result type of the refiner
101 type Result : std::fmt::Debug + Sync + Send + 'static; 112 type Result: std::fmt::Debug + Sync + Send + 'static;
102 /// The sorting to be employed by [`BTSearch::search_and_refine`] on node aggregators 113 /// The sorting to be employed by [`BTSearch::search_and_refine`] on node aggregators
103 /// to detemrine node priority. 114 /// to detemrine node priority.
104 type Sorting : AggregatorSorting<Agg = A>; 115 type Sorting: AggregatorSorting<Agg = A>;
105 116
106 /// Determines whether `aggregator` is sufficiently refined within `domain`. 117 /// Determines whether `aggregator` is sufficiently refined within `domain`.
107 /// 118 ///
108 /// If the aggregator is sufficiently refined that the desired `Self::Result` can be produced, 119 /// If the aggregator is sufficiently refined that the desired `Self::Result` can be produced,
109 /// a [`RefinerResult`]`::Certain` or `Uncertain` should be returned, depending on 120 /// a [`RefinerResult`]`::Certain` or `Uncertain` should be returned, depending on
122 /// The `generator` can be used to convert `data` into [`Support`]s. The parameter `step` 133 /// The `generator` can be used to convert `data` into [`Support`]s. The parameter `step`
123 /// counts the calls to `refine`, and can be used to stop the refinement when a maximum 134 /// counts the calls to `refine`, and can be used to stop the refinement when a maximum
124 /// number of steps is reached. 135 /// number of steps is reached.
125 fn refine( 136 fn refine(
126 &self, 137 &self,
127 aggregator : &A, 138 aggregator: &A,
128 domain : &Cube<F, N>, 139 domain: &Cube<N, F>,
129 data : &[G::Id], 140 data: &[G::Id],
130 generator : &G, 141 generator: &G,
131 step : usize, 142 step: usize,
132 ) -> RefinerResult<A, Self::Result>; 143 ) -> RefinerResult<A, Self::Result>;
133 144
134 /// Fuse two [`Self::Result`]s (needed in threaded refinement). 145 /// Fuse two [`Self::Result`]s (needed in threaded refinement).
135 fn fuse_results(r1 : &mut Self::Result, r2 : Self::Result); 146 fn fuse_results(r1: &mut Self::Result, r2: Self::Result);
136 } 147 }
137 148
138 /// Structure for tracking the refinement process in a [`BinaryHeap`]. 149 /// Structure for tracking the refinement process in a [`BinaryHeap`].
139 struct RefinementInfo<'a, F, D, A, S, RResult, const N : usize, const P : usize> 150 struct RefinementInfo<'a, F, D, A, S, RResult, const N: usize, const P: usize>
140 where F : Float, 151 where
141 D : 'static, 152 F: Float,
142 A : Aggregator, 153 D: 'static,
143 S : AggregatorSorting<Agg = A> { 154 A: Aggregator,
155 S: AggregatorSorting<Agg = A>,
156 {
144 /// Domain of `node` 157 /// Domain of `node`
145 cube : Cube<F, N>, 158 cube: Cube<N, F>,
146 /// Node to be refined 159 /// Node to be refined
147 node : &'a mut Node<F, D, A, N, P>, 160 node: &'a mut Node<F, D, A, N, P>,
148 /// Result and improve aggregator for the [`Refiner`] 161 /// Result and improve aggregator for the [`Refiner`]
149 refiner_info : Option<(A, RResult)>, 162 refiner_info: Option<(A, RResult)>,
150 /// For [`AggregatorSorting`] being used for the type system 163 /// For [`AggregatorSorting`] being used for the type system
151 sorting : PhantomData<S>, 164 sorting: PhantomData<S>,
152 } 165 }
153 166
154 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> 167 impl<'a, F, D, A, S, RResult, const N: usize, const P: usize>
155 RefinementInfo<'a, F, D, A, S, RResult, N, P> 168 RefinementInfo<'a, F, D, A, S, RResult, N, P>
156 where F : Float, 169 where
157 D : 'static, 170 F: Float,
158 A : Aggregator, 171 D: 'static,
159 S : AggregatorSorting<Agg = A> { 172 A: Aggregator,
160 173 S: AggregatorSorting<Agg = A>,
161 #[inline] 174 {
162 fn with_aggregator<U>(&self, f : impl FnOnce(&A) -> U) -> U { 175 #[inline]
176 fn with_aggregator<U>(&self, f: impl FnOnce(&A) -> U) -> U {
163 match self.refiner_info { 177 match self.refiner_info {
164 Some((ref agg, _)) => f(agg), 178 Some((ref agg, _)) => f(agg),
165 None => f(&self.node.aggregator), 179 None => f(&self.node.aggregator),
166 } 180 }
167 } 181 }
175 fn sort_upper(&self) -> S::Sort { 189 fn sort_upper(&self) -> S::Sort {
176 self.with_aggregator(S::sort_upper) 190 self.with_aggregator(S::sort_upper)
177 } 191 }
178 } 192 }
179 193
180 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> PartialEq 194 impl<'a, F, D, A, S, RResult, const N: usize, const P: usize> PartialEq
181 for RefinementInfo<'a, F, D, A, S, RResult, N, P> 195 for RefinementInfo<'a, F, D, A, S, RResult, N, P>
182 where F : Float, 196 where
183 D : 'static, 197 F: Float,
184 A : Aggregator, 198 D: 'static,
185 S : AggregatorSorting<Agg = A> { 199 A: Aggregator,
186 200 S: AggregatorSorting<Agg = A>,
187 #[inline] 201 {
188 fn eq(&self, other : &Self) -> bool { self.cmp(other) == Equal } 202 #[inline]
189 } 203 fn eq(&self, other: &Self) -> bool {
190 204 self.cmp(other) == Equal
191 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> PartialOrd 205 }
192 for RefinementInfo<'a, F, D, A, S, RResult, N, P> 206 }
193 where F : Float, 207
194 D : 'static, 208 impl<'a, F, D, A, S, RResult, const N: usize, const P: usize> PartialOrd
195 A : Aggregator, 209 for RefinementInfo<'a, F, D, A, S, RResult, N, P>
196 S : AggregatorSorting<Agg = A> { 210 where
197 211 F: Float,
198 #[inline] 212 D: 'static,
199 fn partial_cmp(&self, other : &Self) -> Option<Ordering> { Some(self.cmp(other)) } 213 A: Aggregator,
200 } 214 S: AggregatorSorting<Agg = A>,
201 215 {
202 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> Eq 216 #[inline]
203 for RefinementInfo<'a, F, D, A, S, RResult, N, P> 217 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
204 where F : Float, 218 Some(self.cmp(other))
205 D : 'static, 219 }
206 A : Aggregator, 220 }
207 S : AggregatorSorting<Agg = A> { 221
208 } 222 impl<'a, F, D, A, S, RResult, const N: usize, const P: usize> Eq
209 223 for RefinementInfo<'a, F, D, A, S, RResult, N, P>
210 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> Ord 224 where
211 for RefinementInfo<'a, F, D, A, S, RResult, N, P> 225 F: Float,
212 where F : Float, 226 D: 'static,
213 D : 'static, 227 A: Aggregator,
214 A : Aggregator, 228 S: AggregatorSorting<Agg = A>,
215 S : AggregatorSorting<Agg = A> { 229 {
216 230 }
217 #[inline] 231
218 fn cmp(&self, other : &Self) -> Ordering { 232 impl<'a, F, D, A, S, RResult, const N: usize, const P: usize> Ord
219 self.with_aggregator(|agg1| other.with_aggregator(|agg2| { 233 for RefinementInfo<'a, F, D, A, S, RResult, N, P>
220 match S::sort_upper(agg1).cmp(&S::sort_upper(agg2)) { 234 where
235 F: Float,
236 D: 'static,
237 A: Aggregator,
238 S: AggregatorSorting<Agg = A>,
239 {
240 #[inline]
241 fn cmp(&self, other: &Self) -> Ordering {
242 self.with_aggregator(|agg1| {
243 other.with_aggregator(|agg2| match S::sort_upper(agg1).cmp(&S::sort_upper(agg2)) {
221 Equal => S::sort_lower(agg1).cmp(&S::sort_lower(agg2)), 244 Equal => S::sort_lower(agg1).cmp(&S::sort_lower(agg2)),
222 order => order, 245 order => order,
223 } 246 })
224 })) 247 })
225 } 248 }
226 } 249 }
227 250
228 /// This is a container for a [`BinaryHeap`] of [`RefinementInfo`]s together with tracking of 251 /// This is a container for a [`BinaryHeap`] of [`RefinementInfo`]s together with tracking of
229 /// the greatest lower bound of the [`Aggregator`]s of the [`Node`]s therein accroding to 252 /// the greatest lower bound of the [`Aggregator`]s of the [`Node`]s therein accroding to
230 /// chosen [`AggregatorSorting`]. 253 /// chosen [`AggregatorSorting`].
231 struct HeapContainer<'a, F, D, A, S, RResult, const N : usize, const P : usize> 254 struct HeapContainer<'a, F, D, A, S, RResult, const N: usize, const P: usize>
232 where F : Float, 255 where
233 D : 'static + Copy, 256 F: Float,
234 Const<P> : BranchCount<N>, 257 D: 'static + Copy,
235 A : Aggregator, 258 Const<P>: BranchCount<N>,
236 S : AggregatorSorting<Agg = A> { 259 A: Aggregator,
260 S: AggregatorSorting<Agg = A>,
261 {
237 /// Priority queue of nodes to be refined 262 /// Priority queue of nodes to be refined
238 heap : BinaryHeap<RefinementInfo<'a, F, D, A, S, RResult, N, P>>, 263 heap: BinaryHeap<RefinementInfo<'a, F, D, A, S, RResult, N, P>>,
239 /// Maximum of node sorting lower bounds seen in the heap 264 /// Maximum of node sorting lower bounds seen in the heap
240 glb : S::Sort, 265 glb: S::Sort,
241 /// Number of insertions in the heap since previous prune 266 /// Number of insertions in the heap since previous prune
242 insert_counter : usize, 267 insert_counter: usize,
243 /// If a result has been found by some refinment threat, it is stored here 268 /// If a result has been found by some refinment threat, it is stored here
244 result : Option<RResult>, 269 result: Option<RResult>,
245 /// Refinement step counter 270 /// Refinement step counter
246 step : usize, 271 step: usize,
247 /// Number of threads currently processing (not sleeping) 272 /// Number of threads currently processing (not sleeping)
248 n_processing : usize, 273 n_processing: usize,
249 /// Threshold for heap pruning 274 /// Threshold for heap pruning
250 heap_prune_threshold : usize, 275 heap_prune_threshold: usize,
251 } 276 }
252 277
253 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> 278 impl<'a, F, D, A, S, RResult, const N: usize, const P: usize>
254 HeapContainer<'a, F, D, A, S, RResult, N, P> 279 HeapContainer<'a, F, D, A, S, RResult, N, P>
255 where F : Float, 280 where
256 D : 'static + Copy, 281 F: Float,
257 Const<P> : BranchCount<N>, 282 D: 'static + Copy,
258 A : Aggregator, 283 Const<P>: BranchCount<N>,
259 S : AggregatorSorting<Agg = A> { 284 A: Aggregator,
260 285 S: AggregatorSorting<Agg = A>,
286 {
261 /// Push `ri` into the [`BinaryHeap`]. Do greatest lower bound maintenance. 287 /// Push `ri` into the [`BinaryHeap`]. Do greatest lower bound maintenance.
262 /// 288 ///
263 /// Returns a boolean indicating whether the push was actually performed due to glb 289 /// Returns a boolean indicating whether the push was actually performed due to glb
264 /// filtering or not. 290 /// filtering or not.
265 #[inline] 291 #[inline]
266 fn push(&mut self, ri : RefinementInfo<'a, F, D, A, S, RResult, N, P>) -> bool { 292 fn push(&mut self, ri: RefinementInfo<'a, F, D, A, S, RResult, N, P>) -> bool {
267 if ri.sort_upper() >= self.glb { 293 if ri.sort_upper() >= self.glb {
268 let l = ri.sort_lower(); 294 let l = ri.sort_lower();
269 self.heap.push(ri); 295 self.heap.push(ri);
270 self.glb = self.glb.max(l); 296 self.glb = self.glb.max(l);
271 self.insert_counter += 1; 297 self.insert_counter += 1;
274 false 300 false
275 } 301 }
276 } 302 }
277 } 303 }
278 304
279 impl<F : Float, D, A, const N : usize, const P : usize> 305 impl<F: Float, D, A, const N: usize, const P: usize> Branches<F, D, A, N, P>
280 Branches<F,D,A,N,P> 306 where
281 where Const<P> : BranchCount<N>, 307 Const<P>: BranchCount<N>,
282 A : Aggregator, 308 A: Aggregator,
283 D : 'static + Copy + Send + Sync { 309 D: 'static + Copy + Send + Sync,
284 310 {
285 /// Stage all subnodes of `self` into the refinement queue `container`. 311 /// Stage all subnodes of `self` into the refinement queue `container`.
286 fn stage_refine<'a, S, RResult>( 312 fn stage_refine<'a, S, RResult>(
287 &'a mut self, 313 &'a mut self,
288 domain : Cube<F,N>, 314 domain: Cube<N, F>,
289 container : &mut HeapContainer<'a, F, D, A, S, RResult, N, P>, 315 container: &mut HeapContainer<'a, F, D, A, S, RResult, N, P>,
290 ) where S : AggregatorSorting<Agg = A> { 316 ) where
317 S: AggregatorSorting<Agg = A>,
318 {
291 // Insert all subnodes into the refinement heap. 319 // Insert all subnodes into the refinement heap.
292 for (node, cube) in self.nodes_and_cubes_mut(&domain) { 320 for (node, cube) in self.nodes_and_cubes_mut(&domain) {
293 container.push(RefinementInfo { 321 container.push(RefinementInfo {
294 cube, 322 cube,
295 node, 323 node,
296 refiner_info : None, 324 refiner_info: None,
297 sorting : PhantomData, 325 sorting: PhantomData,
298 }); 326 });
299 } 327 }
300 } 328 }
301 } 329 }
302 330
303 331 impl<F: Float, D, A, const N: usize, const P: usize> Node<F, D, A, N, P>
304 impl<F : Float, D, A, const N : usize, const P : usize> 332 where
305 Node<F,D,A,N,P> 333 Const<P>: BranchCount<N>,
306 where Const<P> : BranchCount<N>, 334 A: Aggregator,
307 A : Aggregator, 335 D: 'static + Copy + Send + Sync,
308 D : 'static + Copy + Send + Sync { 336 {
309
310 /// If `self` is a leaf node, uses the `refiner` to determine whether further subdivision 337 /// If `self` is a leaf node, uses the `refiner` to determine whether further subdivision
311 /// is required to get a sufficiently refined solution for the problem the refiner is used 338 /// is required to get a sufficiently refined solution for the problem the refiner is used
312 /// to solve. If the refiner returns [`RefinerResult::Certain`] result, it is returned. 339 /// to solve. If the refiner returns [`RefinerResult::Certain`] result, it is returned.
313 /// If [`RefinerResult::Uncertain`] is returned, the leaf is inserted back into the refinement 340 /// If [`RefinerResult::Uncertain`] is returned, the leaf is inserted back into the refinement
314 /// queue `container`. If `self` is a branch, its subnodes are staged into `container` using 341 /// queue `container`. If `self` is a branch, its subnodes are staged into `container` using
315 /// [`Branches::stage_refine`]. 342 /// [`Branches::stage_refine`].
316 /// 343 ///
317 /// `domain`, as usual, indicates the spatial area corresponding to `self`. 344 /// `domain`, as usual, indicates the spatial area corresponding to `self`.
318 fn search_and_refine<'a, 'b, 'c, R, G>( 345 fn search_and_refine<'a, 'b, 'c, R, G>(
319 self : &'a mut Self, 346 self: &'a mut Self,
320 domain : Cube<F,N>, 347 domain: Cube<N, F>,
321 refiner : &R, 348 refiner: &R,
322 generator : &G, 349 generator: &G,
323 container_arc : &'c Arc<Mutex<HeapContainer<'a, F, D, A, R::Sorting, R::Result, N, P>>>, 350 container_arc: &'c Arc<Mutex<HeapContainer<'a, F, D, A, R::Sorting, R::Result, N, P>>>,
324 step : usize 351 step: usize,
325 ) -> Result<R::Result, MutexGuard<'c, HeapContainer<'a, F, D, A, R::Sorting, R::Result, N, P>>> 352 ) -> Result<R::Result, MutexGuard<'c, HeapContainer<'a, F, D, A, R::Sorting, R::Result, N, P>>>
326 where R : Refiner<F, A, G, N>, 353 where
327 G : SupportGenerator<F, N, Id=D>, 354 R: Refiner<F, A, G, N>,
328 G::SupportType : LocalAnalysis<F, A, N> { 355 G: SupportGenerator<N, F, Id = D>,
329 356 G::SupportType: LocalAnalysis<F, A, N>,
357 {
330 //drop(container); 358 //drop(container);
331 359
332 // Refine a leaf. 360 // Refine a leaf.
333 let res = match self.data { 361 let res = match self.data {
334 NodeOption::Leaf(ref mut v) => { 362 NodeOption::Leaf(ref mut v) => {
366 // reference to self containing it. 394 // reference to self containing it.
367 #[cfg(nightly)] 395 #[cfg(nightly)]
368 unsafe { Arc::get_mut_unchecked(arc_b) } 396 unsafe { Arc::get_mut_unchecked(arc_b) }
369 .stage_refine(domain, &mut *container); 397 .stage_refine(domain, &mut *container);
370 #[cfg(not(nightly))] 398 #[cfg(not(nightly))]
371 Arc::get_mut(arc_b).unwrap() 399 Arc::get_mut(arc_b)
400 .unwrap()
372 .stage_refine(domain, &mut *container); 401 .stage_refine(domain, &mut *container);
373 402
374 return Err(container) 403 return Err(container);
375 }, 404 }
376 _ => unreachable!("This cannot happen"), 405 _ => unreachable!("This cannot happen"),
377 } 406 }
378 } 407 }
379 } 408 }
380 res 409 res
381 }, 410 }
382 NodeOption::Branches(ref mut b) => { 411 NodeOption::Branches(ref mut b) => {
383 // Insert branches into refinement priority queue. 412 // Insert branches into refinement priority queue.
384 let mut container = container_arc.lock().unwrap(); 413 let mut container = container_arc.lock().unwrap();
385 Arc::make_mut(b).stage_refine(domain, &mut *container); 414 Arc::make_mut(b).stage_refine(domain, &mut *container);
386 return Err(container) 415 return Err(container);
387 }, 416 }
388 NodeOption::Uninitialised => { 417 NodeOption::Uninitialised => {
389 refiner.refine(&self.aggregator, &domain, &[], generator, step) 418 refiner.refine(&self.aggregator, &domain, &[], generator, step)
390 }, 419 }
391 }; 420 };
392 421
393 match res { 422 match res {
394 Uncertain(agg, val) => { 423 Uncertain(agg, val) => {
395 // The refiner gave an undertain result. Push a leaf back into the refinement queue 424 // The refiner gave an undertain result. Push a leaf back into the refinement queue
397 // returned in the loop of [`BTSearch::search_and_refine`] when there are no 426 // returned in the loop of [`BTSearch::search_and_refine`] when there are no
398 // unrefined candidates that could potentially be better according to their basic 427 // unrefined candidates that could potentially be better according to their basic
399 // aggregator. 428 // aggregator.
400 let mut container = container_arc.lock().unwrap(); 429 let mut container = container_arc.lock().unwrap();
401 container.push(RefinementInfo { 430 container.push(RefinementInfo {
402 cube : domain, 431 cube: domain,
403 node : self, 432 node: self,
404 refiner_info : Some((agg, val)), 433 refiner_info: Some((agg, val)),
405 sorting : PhantomData, 434 sorting: PhantomData,
406 }); 435 });
407 Err(container) 436 Err(container)
408 }, 437 }
409 Certain(val) => { 438 Certain(val) => {
410 // The refiner gave a certain result so return it to allow early termination 439 // The refiner gave a certain result so return it to allow early termination
411 Ok(val) 440 Ok(val)
412 }, 441 }
413 NeedRefinement => { 442 NeedRefinement => {
414 // This should only happen when we run into NodeOption::Uninitialised above. 443 // This should only happen when we run into NodeOption::Uninitialised above.
415 // There's really nothing to do. 444 // There's really nothing to do.
416 panic!("Do not know whow to refine uninitialised nodes"); 445 panic!("Do not know whow to refine uninitialised nodes");
417 } 446 }
421 450
422 /// Interface trait to a refining search on a [`BT`]. 451 /// Interface trait to a refining search on a [`BT`].
423 /// 452 ///
424 /// This can be removed and the methods implemented directly on [`BT`] once Rust's const generics 453 /// This can be removed and the methods implemented directly on [`BT`] once Rust's const generics
425 /// are flexible enough to allow fixing `P=pow(2, N)`. 454 /// are flexible enough to allow fixing `P=pow(2, N)`.
426 pub trait BTSearch<F, const N : usize> : BTImpl<F, N> 455 pub trait BTSearch<const N: usize, F = f64>: BTImpl<N, F>
427 where F : Float { 456 where
428 457 F: Float,
458 {
429 /// Perform a search on on `Self`, as determined by `refiner`. 459 /// Perform a search on on `Self`, as determined by `refiner`.
430 /// 460 ///
431 /// Nodes are inserted in a priority queue and processed in the order determined by the 461 /// Nodes are inserted in a priority queue and processed in the order determined by the
432 /// [`AggregatorSorting`] [`Refiner::Sorting`]. Leaf nodes are subdivided until the refiner 462 /// [`AggregatorSorting`] [`Refiner::Sorting`]. Leaf nodes are subdivided until the refiner
433 /// decides that a sufficiently refined leaf node has been found, as determined by either the 463 /// decides that a sufficiently refined leaf node has been found, as determined by either the
435 /// [`RefinerResult::Uncertain`] result is found again at the top of the priority queue. 465 /// [`RefinerResult::Uncertain`] result is found again at the top of the priority queue.
436 /// 466 ///
437 /// The `generator` converts [`BTImpl::Data`] stored in the bisection tree into a [`Support`]. 467 /// The `generator` converts [`BTImpl::Data`] stored in the bisection tree into a [`Support`].
438 fn search_and_refine<'b, R, G>( 468 fn search_and_refine<'b, R, G>(
439 &'b mut self, 469 &'b mut self,
440 refiner : R, 470 refiner: R,
441 generator : &Arc<G>, 471 generator: &Arc<G>,
442 ) -> Option<R::Result> 472 ) -> Option<R::Result>
443 where R : Refiner<F, Self::Agg, G, N> + Sync + Send + 'static, 473 where
444 G : SupportGenerator<F, N, Id=Self::Data> + Sync + Send + 'static, 474 R: Refiner<F, Self::Agg, G, N> + Sync + Send + 'static,
445 G::SupportType : LocalAnalysis<F, Self::Agg, N>; 475 G: SupportGenerator<N, F, Id = Self::Data> + Sync + Send + 'static,
446 } 476 G::SupportType: LocalAnalysis<F, Self::Agg, N>;
447 477 }
448 fn refinement_loop<F : Float, D, A, R, G, const N : usize, const P : usize> ( 478
449 wakeup : Option<Arc<Condvar>>, 479 fn refinement_loop<F: Float, D, A, R, G, const N: usize, const P: usize>(
450 refiner : &R, 480 wakeup: Option<Arc<Condvar>>,
451 generator_arc : &Arc<G>, 481 refiner: &R,
452 container_arc : &Arc<Mutex<HeapContainer<F, D, A, R::Sorting, R::Result, N, P>>>, 482 generator_arc: &Arc<G>,
453 ) where A : Aggregator, 483 container_arc: &Arc<Mutex<HeapContainer<F, D, A, R::Sorting, R::Result, N, P>>>,
454 R : Refiner<F, A, G, N>, 484 ) where
455 G : SupportGenerator<F, N, Id=D>, 485 A: Aggregator,
456 G::SupportType : LocalAnalysis<F, A, N>, 486 R: Refiner<F, A, G, N>,
457 Const<P> : BranchCount<N>, 487 G: SupportGenerator<N, F, Id = D>,
458 D : 'static + Copy + Sync + Send + std::fmt::Debug { 488 G::SupportType: LocalAnalysis<F, A, N>,
459 489 Const<P>: BranchCount<N>,
490 D: 'static + Copy + Sync + Send + std::fmt::Debug,
491 {
460 let mut did_park = true; 492 let mut did_park = true;
461 let mut container = container_arc.lock().unwrap(); 493 let mut container = container_arc.lock().unwrap();
462 494
463 'main: loop { 495 'main: loop {
464 // Find a node to process 496 // Find a node to process
469 } 501 }
470 502
471 // Some refinement task/thread has found a result, return 503 // Some refinement task/thread has found a result, return
472 if container.result.is_some() { 504 if container.result.is_some() {
473 container.n_processing -= 1; 505 container.n_processing -= 1;
474 break 'main 506 break 'main;
475 } 507 }
476 508
477 match container.heap.pop() { 509 match container.heap.pop() {
478 // There's work to be done. 510 // There's work to be done.
479 Some(ri) => break 'get_next ri, 511 Some(ri) => break 'get_next ri,
487 } else if let Some(ref c) = wakeup { 519 } else if let Some(ref c) = wakeup {
488 did_park = true; 520 did_park = true;
489 container = c.wait(container).unwrap(); 521 container = c.wait(container).unwrap();
490 continue 'get_next; 522 continue 'get_next;
491 } else { 523 } else {
492 break 'main 524 break 'main;
493 } 525 }
494 } 526 }
495 }; 527 };
496 }; 528 };
497 529
500 532
501 if let Some((_, result)) = ri.refiner_info { 533 if let Some((_, result)) = ri.refiner_info {
502 // Terminate based on a “best possible” result. 534 // Terminate based on a “best possible” result.
503 container.result = Some(result); 535 container.result = Some(result);
504 container.n_processing -= 1; 536 container.n_processing -= 1;
505 break 'main 537 break 'main;
506 } 538 }
507 539
508 // Do priority queue maintenance 540 // Do priority queue maintenance
509 if container.insert_counter > container.heap_prune_threshold { 541 if container.insert_counter > container.heap_prune_threshold {
510 // Make sure glb is good. 542 // Make sure glb is good.
511 match container.heap.iter().map(|ri| ri.sort_lower()).reduce(max) { 543 match container.heap.iter().map(|ri| ri.sort_lower()).reduce(max) {
512 Some(glb) => { 544 Some(glb) => {
513 container.glb = glb; 545 container.glb = glb;
514 // Prune 546 // Prune
515 container.heap.retain(|ri| ri.sort_upper() >= glb); 547 container.heap.retain(|ri| ri.sort_upper() >= glb);
516 },
517 None => {
518 container.glb = R::Sorting::bottom()
519 } 548 }
549 None => container.glb = R::Sorting::bottom(),
520 } 550 }
521 container.insert_counter = 0; 551 container.insert_counter = 0;
522 } 552 }
523 553
524 // Unlock the mutex… 554 // Unlock the mutex…
525 drop(container); 555 drop(container);
526 556
527 // … and process the node. We may get returned an already unlocked mutex. 557 // … and process the node. We may get returned an already unlocked mutex.
528 match Node::search_and_refine(ri.node, ri.cube, refiner, &**generator_arc, 558 match Node::search_and_refine(
529 &container_arc, step) { 559 ri.node,
560 ri.cube,
561 refiner,
562 &**generator_arc,
563 &container_arc,
564 step,
565 ) {
530 Ok(r) => { 566 Ok(r) => {
531 let mut container = container_arc.lock().unwrap(); 567 let mut container = container_arc.lock().unwrap();
532 // Terminate based on a certain result from the refiner 568 // Terminate based on a certain result from the refiner
533 match container.result { 569 match container.result {
534 Some(ref mut r_prev) => R::fuse_results(r_prev, r), 570 Some(ref mut r_prev) => R::fuse_results(r_prev, r),
535 None => container.result = Some(r), 571 None => container.result = Some(r),
536 } 572 }
537 break 'main 573 break 'main;
538 }, 574 }
539 Err(cnt) => { 575 Err(cnt) => {
540 container = cnt; 576 container = cnt;
541 // Wake up another thread if one is sleeping; there should be now work in the 577 // Wake up another thread if one is sleeping; there should be now work in the
542 // queue. 578 // queue.
543 if let Some(ref c) = wakeup { 579 if let Some(ref c) = wakeup {
544 c.notify_one(); 580 c.notify_one();
545 } 581 }
546 } 582 }
547 } 583 }
548
549 } 584 }
550 585
551 // Make sure no task is sleeping 586 // Make sure no task is sleeping
552 if let Some(ref c) = wakeup { 587 if let Some(ref c) = wakeup {
553 c.notify_all(); 588 c.notify_all();
556 591
557 // Needed to get access to a Node without a trait interface. 592 // Needed to get access to a Node without a trait interface.
558 macro_rules! impl_btsearch { 593 macro_rules! impl_btsearch {
559 ($($n:literal)*) => { $( 594 ($($n:literal)*) => { $(
560 impl<'a, M, F, D, A> 595 impl<'a, M, F, D, A>
561 BTSearch<F, $n> 596 BTSearch<$n, F>
562 for BT<M,F,D,A,$n> 597 for BT<M,F,D,A,$n>
563 where //Self : BTImpl<F,$n,Data=D,Agg=A, Depth=M>, // <== automatically deduced 598 where //Self : BTImpl<$n, F, Data=D,Agg=A, Depth=M>, // <== automatically deduced
564 M : Depth, 599 M : Depth,
565 F : Float + Send, 600 F : Float + Send,
566 A : Aggregator, 601 A : Aggregator,
567 D : 'static + Copy + Sync + Send + std::fmt::Debug { 602 D : 'static + Copy + Sync + Send + std::fmt::Debug {
568 fn search_and_refine<'b, R, G>( 603 fn search_and_refine<'b, R, G>(
569 &'b mut self, 604 &'b mut self,
570 refiner : R, 605 refiner : R,
571 generator : &Arc<G>, 606 generator : &Arc<G>,
572 ) -> Option<R::Result> 607 ) -> Option<R::Result>
573 where R : Refiner<F, A, G, $n>, 608 where R : Refiner<F, A, G, $n>,
574 G : SupportGenerator<F, $n, Id=D>, 609 G : SupportGenerator< $n, F, Id=D>,
575 G::SupportType : LocalAnalysis<F, A, $n> { 610 G::SupportType : LocalAnalysis<F, A, $n> {
576 let mut init_container = HeapContainer { 611 let mut init_container = HeapContainer {
577 heap : BinaryHeap::new(), 612 heap : BinaryHeap::new(),
578 glb : R::Sorting::bottom(), 613 glb : R::Sorting::bottom(),
579 insert_counter : 0, 614 insert_counter : 0,
618 } 653 }
619 )* } 654 )* }
620 } 655 }
621 656
622 impl_btsearch!(1 2 3 4); 657 impl_btsearch!(1 2 3 4);
623

Mercurial Repository: alg_tools

mercurial