src/bisection_tree/refine.rs

Sat, 10 Dec 2022 16:23:58 +0200

author
Tuomo Valkonen <tuomov@iki.fi>
date
Sat, 10 Dec 2022 16:23:58 +0200
changeset 21
62bdbff9a288
parent 9
f40dfaf2166d
permissions
-rw-r--r--

Add rust-version specification to Cargo.toml

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

mercurial