Tue, 06 Dec 2022 08:58:49 +0200
README improvements
5 | 1 | |
2 | /*! | |
3 | Bisection tree basics, [`BT`] type and the [`BTImpl`] trait. | |
4 | */ | |
0 | 5 | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
6 | use std::slice::IterMut; |
0 | 7 | use std::iter::once; |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
8 | use std::sync::Arc; |
0 | 9 | use serde::{Serialize, Deserialize}; |
5 | 10 | pub(super) use nalgebra::Const; |
0 | 11 | use itertools::izip; |
12 | ||
13 | use crate::types::{Float, Num}; | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
14 | use crate::parallelism::{with_task_budget, TaskBudget}; |
0 | 15 | use crate::coefficients::pow; |
16 | use crate::maputil::{ | |
17 | array_init, | |
18 | map2, | |
19 | map2_indexed, | |
20 | collect_into_array_unchecked | |
21 | }; | |
5 | 22 | use crate::sets::Cube; |
23 | use crate::loc::Loc; | |
0 | 24 | use super::support::*; |
25 | use super::aggregator::*; | |
26 | ||
5 | 27 | /// An enum that indicates whether a [`Node`] of a [`BT`] is uninitialised, leaf, or branch. |
28 | /// | |
29 | /// For the type and const parametere, see the [module level documentation][super]. | |
0 | 30 | #[derive(Clone,Debug)] |
5 | 31 | pub(super) enum NodeOption<F : Num, D, A : Aggregator, const N : usize, const P : usize> { |
32 | /// Indicates an uninitilised node; may become a branch or a leaf. | |
0 | 33 | // TODO: Could optimise Uninitialised away by simply treat Leaf with an empty Vec as |
34 | // something that can be still replaced with Branches. | |
35 | Uninitialised, | |
5 | 36 | /// Indicates a leaf node containing a copy-on-write reference-counted vector |
37 | /// of data of type `D`. | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
38 | Leaf(Vec<D>), |
5 | 39 | /// Indicates a branch node, cotaning a copy-on-write reference to the [`Branches`]. |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
40 | Branches(Arc<Branches<F, D, A, N, P>>), |
0 | 41 | } |
42 | ||
43 | /// Node of a [`BT`] bisection tree. | |
5 | 44 | /// |
45 | /// For the type and const parameteres, see the [module level documentation][super]. | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
46 | #[derive(Clone, Debug)] |
0 | 47 | pub struct Node<F : Num, D, A : Aggregator, const N : usize, const P : usize> { |
5 | 48 | /// The data or branches under the node. |
0 | 49 | pub(super) data : NodeOption<F, D, A, N, P>, |
50 | /// Aggregator for `data`. | |
51 | pub(super) aggregator : A, | |
52 | } | |
53 | ||
5 | 54 | /// Branching information of a [`Node`] of a [`BT`] bisection tree into `P` subnodes. |
55 | /// | |
56 | /// For the type and const parameters, see the [module level documentation][super]. | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
57 | #[derive(Clone, Debug)] |
5 | 58 | pub(super) struct Branches<F : Num, D, A : Aggregator, const N : usize, const P : usize> { |
0 | 59 | /// Point for subdivision of the (unstored) [`Cube`] corresponding to the node. |
60 | pub(super) branch_at : Loc<F, N>, | |
61 | /// Subnodes | |
62 | pub(super) nodes : [Node<F, D, A, N, P>; P], | |
63 | } | |
64 | ||
65 | /// Dirty workaround to broken Rust drop, see [https://github.com/rust-lang/rust/issues/58068](). | |
66 | impl<F : Num, D, A : Aggregator, const N : usize, const P : usize> | |
67 | Drop for Node<F, D, A, N, P> { | |
68 | fn drop(&mut self) { | |
69 | use NodeOption as NO; | |
70 | ||
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
71 | let process = |brc : Arc<Branches<F, D, A, N, P>>, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
72 | to_drop : &mut Vec<Arc<Branches<F, D, A, N, P>>>| { |
0 | 73 | // We only drop Branches if we have the only strong reference. |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
74 | // FIXME: update the RwLocks on Nodes. |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
75 | Arc::try_unwrap(brc).ok().map(|branches| branches.nodes.map(|mut node| { |
0 | 76 | if let NO::Branches(brc2) = std::mem::replace(&mut node.data, NO::Uninitialised) { |
77 | to_drop.push(brc2) | |
78 | } | |
79 | })); | |
80 | }; | |
81 | ||
82 | // We mark Self as NodeOption::Uninitialised, extracting the real contents. | |
83 | // If we have subprocess, we need to process them. | |
84 | if let NO::Branches(brc1) = std::mem::replace(&mut self.data, NO::Uninitialised) { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
85 | // We store a queue of Arc<Branches> to drop into a vector |
0 | 86 | let mut to_drop = Vec::new(); |
87 | process(brc1, &mut to_drop); | |
88 | ||
89 | // While there are any Branches in the drop queue vector, we continue the process, | |
90 | // pushing all internal branching nodes into the queue. | |
91 | while let Some(brc) = to_drop.pop() { | |
92 | process(brc, &mut to_drop) | |
93 | } | |
94 | } | |
95 | } | |
96 | } | |
97 | ||
5 | 98 | /// Trait for the depth of a [`BT`]. |
99 | /// | |
100 | /// This will generally be either a runtime [`DynamicDepth`] or compile-time [`Const`] depth. | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
101 | pub trait Depth : 'static + Copy + Send + Sync + std::fmt::Debug { |
5 | 102 | /// Lower depth type. |
0 | 103 | type Lower : Depth; |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
104 | |
5 | 105 | /// Returns a lower depth, if there still is one. |
0 | 106 | fn lower(&self) -> Option<Self::Lower>; |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
107 | |
5 | 108 | /// Returns a lower depth or self if this is the lowest depth. |
0 | 109 | fn lower_or(&self) -> Self::Lower; |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
110 | |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
111 | /// Returns the numeric value of the depth |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
112 | fn value(&self) -> u32; |
0 | 113 | } |
114 | ||
5 | 115 | /// Dynamic (runtime) [`Depth`] for a [`BT`]. |
0 | 116 | #[derive(Copy,Clone,Debug,Serialize,Deserialize)] |
5 | 117 | pub struct DynamicDepth( |
118 | /// The depth | |
119 | pub u8 | |
120 | ); | |
121 | ||
0 | 122 | impl Depth for DynamicDepth { |
123 | type Lower = Self; | |
124 | #[inline] | |
125 | fn lower(&self) -> Option<Self> { | |
126 | if self.0>0 { | |
127 | Some(DynamicDepth(self.0-1)) | |
128 | } else { | |
129 | None | |
130 | } | |
131 | } | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
132 | |
0 | 133 | #[inline] |
134 | fn lower_or(&self) -> Self { | |
135 | DynamicDepth(if self.0>0 { self.0 - 1 } else { 0 }) | |
136 | } | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
137 | |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
138 | #[inline] |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
139 | fn value(&self) -> u32 { |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
140 | self.0 as u32 |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
141 | } |
0 | 142 | } |
143 | ||
144 | impl Depth for Const<0> { | |
145 | type Lower = Self; | |
146 | fn lower(&self) -> Option<Self::Lower> { None } | |
147 | fn lower_or(&self) -> Self::Lower { Const } | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
148 | fn value(&self) -> u32 { 0 } |
0 | 149 | } |
150 | ||
151 | macro_rules! impl_constdepth { | |
152 | ($($n:literal)*) => { $( | |
153 | impl Depth for Const<$n> { | |
154 | type Lower = Const<{$n-1}>; | |
155 | fn lower(&self) -> Option<Self::Lower> { Some(Const) } | |
156 | fn lower_or(&self) -> Self::Lower { Const } | |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
157 | fn value(&self) -> u32 { $n } |
0 | 158 | } |
159 | )* }; | |
160 | } | |
161 | impl_constdepth!(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32); | |
162 | ||
5 | 163 | /// Trait for counting the branching factor of a [`BT`] of dimension `N`. |
164 | /// | |
165 | /// The const parameter `P` from the [module level documentation][super] is required to satisfy | |
166 | /// `Const<P> : Branchcount<N>`. | |
167 | /// This trait is implemented for `P=pow(2, N)` for small `N`. | |
0 | 168 | pub trait BranchCount<const N : usize> {} |
169 | macro_rules! impl_branchcount { | |
170 | ($($n:literal)*) => { $( | |
171 | impl BranchCount<$n> for Const<{pow(2, $n)}>{} | |
172 | )* } | |
173 | } | |
174 | impl_branchcount!(1 2 3 4 5 6 7 8); | |
175 | ||
176 | impl<F : Float, D, A, const N : usize, const P : usize> Branches<F,D,A,N,P> | |
177 | where Const<P> : BranchCount<N>, | |
178 | A : Aggregator | |
179 | { | |
5 | 180 | /// Returns the index in {0, …, `P`-1} for the branch to which the point `x` corresponds. |
181 | /// | |
182 | /// This only takes the branch subdivision point $d$ into account, so is always succesfull. | |
183 | /// Thus, for this point, each branch corresponds to a quadrant of $ℝ^N$ relative to $d$. | |
0 | 184 | fn get_node_index(&self, x : &Loc<F, N>) -> usize { |
185 | izip!(0..P, x.iter(), self.branch_at.iter()).map(|(i, x_i, branch_i)| | |
186 | if x_i > branch_i { 1<<i } else { 0 } | |
187 | ).sum() | |
188 | } | |
189 | ||
5 | 190 | /// Returns the node within `Self` containing the point `x`. |
191 | /// | |
192 | /// This only takes the branch subdivision point $d$ into account, so is always succesfull. | |
193 | /// Thus, for this point, each branch corresponds to a quadrant of $ℝ^N$ relative to $d$. | |
0 | 194 | #[inline] |
5 | 195 | fn get_node(&self, x : &Loc<F,N>) -> &Node<F,D,A,N,P> { |
0 | 196 | &self.nodes[self.get_node_index(x)] |
197 | } | |
198 | } | |
199 | ||
5 | 200 | /// An iterator over the $P=2^N$ subcubes of a [`Cube`] subdivided at a point `d`. |
201 | pub(super) struct SubcubeIter<'b, F : Float, const N : usize, const P : usize> { | |
0 | 202 | domain : &'b Cube<F, N>, |
203 | branch_at : Loc<F, N>, | |
204 | index : usize, | |
205 | } | |
206 | ||
5 | 207 | /// Returns the `i`:th subcube of `domain` subdivided at `branch_at`. |
0 | 208 | #[inline] |
5 | 209 | fn get_subcube<F : Float, const N : usize>( |
210 | branch_at : &Loc<F, N>, | |
211 | domain : &Cube<F, N>, | |
212 | i : usize | |
213 | ) -> Cube<F, N> { | |
0 | 214 | map2_indexed(branch_at, domain, move |j, &branch, &[start, end]| { |
215 | if i & (1 << j) != 0 { | |
216 | [branch, end] | |
217 | } else { | |
218 | [start, branch] | |
219 | } | |
220 | }).into() | |
221 | } | |
222 | ||
223 | impl<'a, 'b, F : Float, const N : usize, const P : usize> Iterator | |
224 | for SubcubeIter<'b, F, N, P> { | |
225 | type Item = Cube<F, N>; | |
226 | #[inline] | |
227 | fn next(&mut self) -> Option<Self::Item> { | |
228 | if self.index < P { | |
229 | let i = self.index; | |
230 | self.index += 1; | |
231 | Some(get_subcube(&self.branch_at, self.domain, i)) | |
232 | } else { | |
233 | None | |
234 | } | |
235 | } | |
236 | } | |
237 | ||
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
238 | impl<F : Float, D, A, const N : usize, const P : usize> |
0 | 239 | Branches<F,D,A,N,P> |
240 | where Const<P> : BranchCount<N>, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
241 | A : Aggregator, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
242 | D : 'static + Copy + Send + Sync { |
0 | 243 | |
5 | 244 | /// Creates a new node branching structure, subdividing `domain` based on the |
245 | /// [hint][Support::support_hint] of `support`. | |
246 | pub(super) fn new_with<S : LocalAnalysis <F, A, N>>( | |
0 | 247 | domain : &Cube<F,N>, |
248 | support : &S | |
249 | ) -> Self { | |
250 | let hint = support.bisection_hint(domain); | |
251 | let branch_at = map2(&hint, domain, |h, r| { | |
252 | h.unwrap_or_else(|| (r[0]+r[1])/F::TWO).max(r[0]).min(r[1]) | |
253 | }).into(); | |
254 | Branches{ | |
255 | branch_at : branch_at, | |
256 | nodes : array_init(|| Node::new()), | |
257 | } | |
258 | } | |
259 | ||
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
260 | /// Summarises the aggregators of these branches into `agg` |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
261 | pub(super) fn summarise_into(&self, agg : &mut A) { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
262 | // We need to create an array of the aggregators clones due to the RwLock. |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
263 | agg.summarise(self.nodes.iter().map(Node::get_aggregator)); |
0 | 264 | } |
265 | ||
5 | 266 | /// Returns an iterator over the subcubes of `domain` subdivided at the branching point |
267 | /// of `self`. | |
0 | 268 | #[inline] |
5 | 269 | pub(super) fn iter_subcubes<'b>(&self, domain : &'b Cube<F, N>) |
0 | 270 | -> SubcubeIter<'b, F, N, P> { |
271 | SubcubeIter { | |
272 | domain : domain, | |
273 | branch_at : self.branch_at, | |
274 | index : 0, | |
275 | } | |
276 | } | |
277 | ||
5 | 278 | /* |
279 | /// Returns an iterator over all nodes and corresponding subcubes of `self`. | |
0 | 280 | #[inline] |
5 | 281 | pub(super) fn nodes_and_cubes<'a, 'b>(&'a self, domain : &'b Cube<F, N>) |
0 | 282 | -> std::iter::Zip<Iter<'a, Node<F,D,A,N,P>>, SubcubeIter<'b, F, N, P>> { |
283 | self.nodes.iter().zip(self.iter_subcubes(domain)) | |
284 | } | |
5 | 285 | */ |
0 | 286 | |
5 | 287 | /// Mutably iterate over all nodes and corresponding subcubes of `self`. |
0 | 288 | #[inline] |
5 | 289 | pub(super) fn nodes_and_cubes_mut<'a, 'b>(&'a mut self, domain : &'b Cube<F, N>) |
0 | 290 | -> std::iter::Zip<IterMut<'a, Node<F,D,A,N,P>>, SubcubeIter<'b, F, N, P>> { |
291 | let subcube_iter = self.iter_subcubes(domain); | |
292 | self.nodes.iter_mut().zip(subcube_iter) | |
293 | } | |
294 | ||
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
295 | /// Call `f` on all `(subnode, subcube)` pairs in multiple threads, if `guard` so deems. |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
296 | #[inline] |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
297 | fn recurse<'scope, 'smaller, 'refs>( |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
298 | &'smaller mut self, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
299 | domain : &'smaller Cube<F, N>, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
300 | task_budget : TaskBudget<'scope, 'refs>, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
301 | guard : impl Fn(&Node<F,D,A,N,P>, &Cube<F, N>) -> bool + Send + 'smaller, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
302 | mut f : impl for<'a> FnMut(&mut Node<F,D,A,N,P>, &Cube<F, N>, TaskBudget<'smaller, 'a>) |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
303 | + Send + Copy + 'smaller |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
304 | ) where 'scope : 'smaller { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
305 | let subs = self.nodes_and_cubes_mut(domain); |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
306 | task_budget.zoom(move |s| { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
307 | for (node, subcube) in subs { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
308 | if guard(node, &subcube) { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
309 | s.execute(move |new_budget| f(node, &subcube, new_budget)) |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
310 | } |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
311 | } |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
312 | }); |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
313 | } |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
314 | |
0 | 315 | /// Insert data into the branch. |
5 | 316 | /// |
317 | /// The parameters are as follows: | |
318 | /// * `domain` is the cube corresponding to this branch. | |
319 | /// * `d` is the data to be inserted | |
320 | /// * `new_leaf_depth` is the depth relative to `self` at which the data is to be inserted. | |
321 | /// * `support` is the [`Support`] that is used determine with which subcubes of `domain` | |
322 | /// (at subdivision depth `new_leaf_depth`) the data `d` is to be associated with. | |
323 | /// | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
324 | pub(super) fn insert<'refs, 'scope, M : Depth, S : LocalAnalysis<F, A, N>>( |
0 | 325 | &mut self, |
326 | domain : &Cube<F,N>, | |
327 | d : D, | |
328 | new_leaf_depth : M, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
329 | support : &S, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
330 | task_budget : TaskBudget<'scope, 'refs>, |
0 | 331 | ) { |
332 | let support_hint = support.support_hint(); | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
333 | self.recurse(domain, task_budget, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
334 | |_, subcube| support_hint.intersects(&subcube), |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
335 | move |node, subcube, new_budget| node.insert(subcube, d, new_leaf_depth, support, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
336 | new_budget)); |
0 | 337 | } |
338 | ||
5 | 339 | /// Construct a new instance of the branch for a different aggregator. |
340 | /// | |
341 | /// The `generator` is used to convert the data of type `D` of the branch into corresponding | |
342 | /// [`Support`]s. The `domain` is the cube corresponding to `self`. | |
343 | /// The type parameter `ANew´ is the new aggregator, and needs to be implemented for the | |
344 | /// generator's `SupportType`. | |
345 | pub(super) fn convert_aggregator<ANew, G>( | |
0 | 346 | self, |
347 | generator : &G, | |
348 | domain : &Cube<F, N> | |
349 | ) -> Branches<F,D,ANew,N,P> | |
350 | where ANew : Aggregator, | |
351 | G : SupportGenerator<F, N, Id=D>, | |
352 | G::SupportType : LocalAnalysis<F, ANew, N> { | |
353 | let branch_at = self.branch_at; | |
354 | let subcube_iter = self.iter_subcubes(domain); | |
355 | let new_nodes = self.nodes.into_iter().zip(subcube_iter).map(|(node, subcube)| { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
356 | Node::convert_aggregator(node, generator, &subcube) |
0 | 357 | }); |
358 | Branches { | |
359 | branch_at : branch_at, | |
360 | nodes : collect_into_array_unchecked(new_nodes), | |
361 | } | |
362 | } | |
363 | ||
5 | 364 | /// Recalculate aggregator after changes to generator. |
365 | /// | |
366 | /// The `generator` is used to convert the data of type `D` of the branch into corresponding | |
367 | /// [`Support`]s. The `domain` is the cube corresponding to `self`. | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
368 | pub(super) fn refresh_aggregator<'refs, 'scope, G>( |
0 | 369 | &mut self, |
370 | generator : &G, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
371 | domain : &Cube<F, N>, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
372 | task_budget : TaskBudget<'scope, 'refs>, |
0 | 373 | ) where G : SupportGenerator<F, N, Id=D>, |
374 | G::SupportType : LocalAnalysis<F, A, N> { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
375 | self.recurse(domain, task_budget, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
376 | |_, _| true, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
377 | move |node, subcube, new_budget| node.refresh_aggregator(generator, subcube, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
378 | new_budget)); |
0 | 379 | } |
380 | } | |
381 | ||
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
382 | impl<F : Float, D, A, const N : usize, const P : usize> |
0 | 383 | Node<F,D,A,N,P> |
384 | where Const<P> : BranchCount<N>, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
385 | A : Aggregator, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
386 | D : 'static + Copy + Send + Sync { |
0 | 387 | |
5 | 388 | /// Create a new node |
0 | 389 | #[inline] |
5 | 390 | pub(super) fn new() -> Self { |
0 | 391 | Node { |
392 | data : NodeOption::Uninitialised, | |
393 | aggregator : A::new(), | |
394 | } | |
395 | } | |
396 | ||
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
397 | /* |
0 | 398 | /// Get leaf data |
399 | #[inline] | |
5 | 400 | pub(super) fn get_leaf_data(&self, x : &Loc<F, N>) -> Option<&Vec<D>> { |
0 | 401 | match self.data { |
402 | NodeOption::Uninitialised => None, | |
403 | NodeOption::Leaf(ref data) => Some(data), | |
404 | NodeOption::Branches(ref b) => b.get_node(x).get_leaf_data(x), | |
405 | } | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
406 | }*/ |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
407 | |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
408 | /// Get leaf data iterator |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
409 | #[inline] |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
410 | pub(super) fn get_leaf_data_iter(&self, x : &Loc<F, N>) -> Option<std::slice::Iter<'_, D>> { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
411 | match self.data { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
412 | NodeOption::Uninitialised => None, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
413 | NodeOption::Leaf(ref data) => Some(data.iter()), |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
414 | NodeOption::Branches(ref b) => b.get_node(x).get_leaf_data_iter(x), |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
415 | } |
0 | 416 | } |
417 | ||
418 | /// Returns a reference to the aggregator of this node | |
419 | #[inline] | |
5 | 420 | pub(super) fn get_aggregator(&self) -> &A { |
0 | 421 | &self.aggregator |
422 | } | |
423 | ||
5 | 424 | /// Insert data under the node. |
425 | /// | |
426 | /// The parameters are as follows: | |
427 | /// * `domain` is the cube corresponding to this branch. | |
428 | /// * `d` is the data to be inserted | |
429 | /// * `new_leaf_depth` is the depth relative to `self` at which new leaves are created. | |
430 | /// * `support` is the [`Support`] that is used determine with which subcubes of `domain` | |
431 | /// (at subdivision depth `new_leaf_depth`) the data `d` is to be associated with. | |
432 | /// | |
433 | /// If `self` is already [`NodeOption::Leaf`], the data is inserted directly in this node. | |
434 | /// If `self` is a [`NodeOption::Branches`], the data is passed to branches whose subcubes | |
435 | /// `support` intersects. If an [`NodeOption::Uninitialised`] node is encountered, a new leaf is | |
436 | /// created at a minimum depth of `new_leaf_depth`. | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
437 | pub(super) fn insert<'refs, 'scope, M : Depth, S : LocalAnalysis <F, A, N>>( |
0 | 438 | &mut self, |
439 | domain : &Cube<F,N>, | |
440 | d : D, | |
441 | new_leaf_depth : M, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
442 | support : &S, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
443 | task_budget : TaskBudget<'scope, 'refs>, |
0 | 444 | ) { |
445 | match &mut self.data { | |
446 | NodeOption::Uninitialised => { | |
447 | // Replace uninitialised node with a leaf or a branch | |
448 | self.data = match new_leaf_depth.lower() { | |
449 | None => { | |
450 | let a = support.local_analysis(&domain); | |
451 | self.aggregator.aggregate(once(a)); | |
452 | // TODO: this is currently a dirty hard-coded heuristic; | |
453 | // should add capacity as a parameter | |
454 | let mut vec = Vec::with_capacity(2*P+1); | |
455 | vec.push(d); | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
456 | NodeOption::Leaf(vec) |
0 | 457 | }, |
458 | Some(lower) => { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
459 | let b = Arc::new({ |
0 | 460 | let mut b0 = Branches::new_with(domain, support); |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
461 | b0.insert(domain, d, lower, support, task_budget); |
0 | 462 | b0 |
463 | }); | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
464 | b.summarise_into(&mut self.aggregator); |
0 | 465 | NodeOption::Branches(b) |
466 | } | |
467 | } | |
468 | }, | |
469 | NodeOption::Leaf(leaf) => { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
470 | leaf.push(d); |
0 | 471 | let a = support.local_analysis(&domain); |
472 | self.aggregator.aggregate(once(a)); | |
473 | }, | |
474 | NodeOption::Branches(b) => { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
475 | // FIXME: recursion that may cause stack overflow if the tree becomes |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
476 | // very deep, e.g. due to [`BTSearch::search_and_refine`]. |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
477 | let bm = Arc::make_mut(b); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
478 | bm.insert(domain, d, new_leaf_depth.lower_or(), support, task_budget); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
479 | bm.summarise_into(&mut self.aggregator); |
0 | 480 | }, |
481 | } | |
482 | } | |
483 | ||
5 | 484 | /// Construct a new instance of the node for a different aggregator |
485 | /// | |
486 | /// The `generator` is used to convert the data of type `D` of the node into corresponding | |
487 | /// [`Support`]s. The `domain` is the cube corresponding to `self`. | |
488 | /// The type parameter `ANew´ is the new aggregator, and needs to be implemented for the | |
489 | /// generator's `SupportType`. | |
490 | pub(super) fn convert_aggregator<ANew, G>( | |
0 | 491 | mut self, |
492 | generator : &G, | |
493 | domain : &Cube<F, N> | |
494 | ) -> Node<F,D,ANew,N,P> | |
495 | where ANew : Aggregator, | |
496 | G : SupportGenerator<F, N, Id=D>, | |
497 | G::SupportType : LocalAnalysis<F, ANew, N> { | |
498 | ||
499 | // The mem::replace is needed due to the [`Drop`] implementation to extract self.data. | |
500 | match std::mem::replace(&mut self.data, NodeOption::Uninitialised) { | |
501 | NodeOption::Uninitialised => Node { | |
502 | data : NodeOption::Uninitialised, | |
503 | aggregator : ANew::new(), | |
504 | }, | |
505 | NodeOption::Leaf(v) => { | |
506 | let mut anew = ANew::new(); | |
507 | anew.aggregate(v.iter().map(|d| { | |
508 | let support = generator.support_for(*d); | |
509 | support.local_analysis(&domain) | |
510 | })); | |
511 | ||
512 | Node { | |
513 | data : NodeOption::Leaf(v), | |
514 | aggregator : anew, | |
515 | } | |
516 | }, | |
517 | NodeOption::Branches(b) => { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
518 | // FIXME: recursion that may cause stack overflow if the tree becomes |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
519 | // very deep, e.g. due to [`BTSearch::search_and_refine`]. |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
520 | let bnew = Arc::unwrap_or_clone(b).convert_aggregator(generator, domain); |
0 | 521 | let mut anew = ANew::new(); |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
522 | bnew.summarise_into(&mut anew); |
0 | 523 | Node { |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
524 | data : NodeOption::Branches(Arc::new(bnew)), |
0 | 525 | aggregator : anew, |
526 | } | |
527 | } | |
528 | } | |
529 | } | |
530 | ||
5 | 531 | /// Refresh aggregator after changes to generator. |
532 | /// | |
533 | /// The `generator` is used to convert the data of type `D` of the node into corresponding | |
534 | /// [`Support`]s. The `domain` is the cube corresponding to `self`. | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
535 | pub(super) fn refresh_aggregator<'refs, 'scope, G>( |
0 | 536 | &mut self, |
537 | generator : &G, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
538 | domain : &Cube<F, N>, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
539 | task_budget : TaskBudget<'scope, 'refs>, |
0 | 540 | ) where G : SupportGenerator<F, N, Id=D>, |
541 | G::SupportType : LocalAnalysis<F, A, N> { | |
542 | match &mut self.data { | |
543 | NodeOption::Uninitialised => { }, | |
544 | NodeOption::Leaf(v) => { | |
545 | self.aggregator = A::new(); | |
546 | self.aggregator.aggregate(v.iter().map(|d| { | |
547 | generator.support_for(*d) | |
548 | .local_analysis(&domain) | |
549 | })); | |
550 | }, | |
551 | NodeOption::Branches(ref mut b) => { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
552 | // FIXME: recursion that may cause stack overflow if the tree becomes |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
553 | // very deep, e.g. due to [`BTSearch::search_and_refine`]. |
9
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
554 | let bm = Arc::make_mut(b); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
555 | bm.refresh_aggregator(generator, domain, task_budget); |
f40dfaf2166d
Improvements and minor fixes to bisection tree refinement.
Tuomo Valkonen <tuomov@iki.fi>
parents:
8
diff
changeset
|
556 | bm.summarise_into(&mut self.aggregator); |
0 | 557 | } |
558 | } | |
559 | } | |
560 | } | |
561 | ||
5 | 562 | /// Helper trait for working with [`Node`]s without the knowledge of `P`. |
563 | /// | |
564 | /// This can be removed and the methods implemented directly on [`BT`] once Rust's const generics | |
565 | /// are flexible enough to allow fixing `P=pow(2, N)`. | |
0 | 566 | pub trait BTNode<F, D, A, const N : usize> |
567 | where F : Float, | |
568 | D : 'static + Copy, | |
569 | A : Aggregator { | |
570 | type Node : Clone + std::fmt::Debug; | |
571 | } | |
572 | ||
5 | 573 | /// Helper structure for looking up a [`Node`] without the knowledge of `P`. |
574 | /// | |
575 | /// This can be removed once Rust's const generics are flexible enough to allow fixing | |
576 | /// `P=pow(2, N)`. | |
0 | 577 | #[derive(Debug)] |
578 | pub struct BTNodeLookup; | |
579 | ||
5 | 580 | /// Basic interface to a [`BT`] bisection tree. |
581 | /// | |
582 | /// Further routines are provided by the [`BTSearch`][super::refine::BTSearch] trait. | |
0 | 583 | pub trait BTImpl<F : Float, const N : usize> : std::fmt::Debug + Clone + GlobalAnalysis<F, Self::Agg> { |
5 | 584 | /// The data type stored in the tree |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
585 | type Data : 'static + Copy + Send + Sync; |
5 | 586 | /// The depth type of the tree |
0 | 587 | type Depth : Depth; |
5 | 588 | /// The type for the [aggregate information][Aggregator] about the `Data` stored in each node |
589 | /// of the tree. | |
0 | 590 | type Agg : Aggregator; |
5 | 591 | /// The type of the tree with the aggregator converted to `ANew`. |
0 | 592 | type Converted<ANew> : BTImpl<F, N, Data=Self::Data, Agg=ANew> where ANew : Aggregator; |
593 | ||
5 | 594 | /// Insert the data `d` into the tree for `support`. |
595 | /// | |
596 | /// Every leaf node of the tree that intersects the `support` will contain a copy of | |
597 | /// `d`. | |
0 | 598 | fn insert<S : LocalAnalysis<F, Self::Agg, N>>( |
599 | &mut self, | |
600 | d : Self::Data, | |
601 | support : &S | |
602 | ); | |
603 | ||
5 | 604 | /// Construct a new instance of the tree for a different aggregator |
605 | /// | |
606 | /// The `generator` is used to convert the data of type [`Self::Data`] contained in the tree | |
607 | /// into corresponding [`Support`]s. | |
0 | 608 | fn convert_aggregator<ANew, G>(self, generator : &G) |
609 | -> Self::Converted<ANew> | |
610 | where ANew : Aggregator, | |
611 | G : SupportGenerator<F, N, Id=Self::Data>, | |
612 | G::SupportType : LocalAnalysis<F, ANew, N>; | |
613 | ||
614 | ||
5 | 615 | /// Refreshes the aggregator of the three after possible changes to the support generator. |
616 | /// | |
617 | /// The `generator` is used to convert the data of type [`Self::Data`] contained in the tree | |
618 | /// into corresponding [`Support`]s. | |
0 | 619 | fn refresh_aggregator<G>(&mut self, generator : &G) |
620 | where G : SupportGenerator<F, N, Id=Self::Data>, | |
621 | G::SupportType : LocalAnalysis<F, Self::Agg, N>; | |
622 | ||
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
623 | /// Returns an iterator over all [`Self::Data`] items at the point `x` of the domain. |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
624 | fn iter_at(&self, x : &Loc<F,N>) -> std::slice::Iter<'_, Self::Data>; |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
625 | |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
626 | /* |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
627 | /// Returns all [`Self::Data`] items at the point `x` of the domain. |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
628 | fn data_at(&self, x : &Loc<F,N>) -> Arc<Vec<Self::Data>>; |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
629 | */ |
0 | 630 | |
5 | 631 | /// Create a new tree on `domain` of indicated `depth`. |
0 | 632 | fn new(domain : Cube<F, N>, depth : Self::Depth) -> Self; |
633 | } | |
634 | ||
5 | 635 | /// The main bisection tree structure. |
636 | /// | |
637 | /// It should be accessed via the [`BTImpl`] trait to hide the `const P : usize` parameter until | |
638 | /// const generics are flexible enough to fix `P=pow(2, N)` and thus also get rid of | |
639 | /// the `BTNodeLookup : BTNode<F, D, A, N>` trait bound. | |
0 | 640 | #[derive(Clone,Debug)] |
641 | pub struct BT< | |
642 | M : Depth, | |
643 | F : Float, | |
644 | D : 'static + Copy, | |
645 | A : Aggregator, | |
646 | const N : usize, | |
647 | > where BTNodeLookup : BTNode<F, D, A, N> { | |
5 | 648 | /// The depth of the tree (initial, before refinement) |
0 | 649 | pub(super) depth : M, |
5 | 650 | /// The domain of the toplevel node |
0 | 651 | pub(super) domain : Cube<F, N>, |
5 | 652 | /// The toplevel node of the tree |
0 | 653 | pub(super) topnode : <BTNodeLookup as BTNode<F, D, A, N>>::Node, |
654 | } | |
655 | ||
656 | macro_rules! impl_bt { | |
657 | ($($n:literal)*) => { $( | |
658 | impl<F, D, A> BTNode<F, D, A, $n> for BTNodeLookup | |
659 | where F : Float, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
660 | D : 'static + Copy + Send + Sync + std::fmt::Debug, |
0 | 661 | A : Aggregator { |
662 | type Node = Node<F,D,A,$n,{pow(2, $n)}>; | |
663 | } | |
664 | ||
665 | impl<M,F,D,A> BTImpl<F,$n> for BT<M,F,D,A,$n> | |
666 | where M : Depth, | |
667 | F : Float, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
668 | D : 'static + Copy + Send + Sync + std::fmt::Debug, |
0 | 669 | A : Aggregator { |
670 | type Data = D; | |
671 | type Depth = M; | |
672 | type Agg = A; | |
673 | type Converted<ANew> = BT<M,F,D,ANew,$n> where ANew : Aggregator; | |
674 | ||
675 | fn insert<S: LocalAnalysis<F, A, $n>>( | |
676 | &mut self, | |
677 | d : D, | |
678 | support : &S | |
679 | ) { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
680 | with_task_budget(|task_budget| |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
681 | self.topnode.insert( |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
682 | &self.domain, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
683 | d, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
684 | self.depth, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
685 | support, |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
686 | task_budget |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
687 | ) |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
688 | ) |
0 | 689 | } |
690 | ||
691 | fn convert_aggregator<ANew, G>(self, generator : &G) -> Self::Converted<ANew> | |
692 | where ANew : Aggregator, | |
693 | G : SupportGenerator<F, $n, Id=D>, | |
694 | G::SupportType : LocalAnalysis<F, ANew, $n> { | |
695 | let topnode = self.topnode.convert_aggregator(generator, &self.domain); | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
696 | |
0 | 697 | BT { |
698 | depth : self.depth, | |
699 | domain : self.domain, | |
700 | topnode | |
701 | } | |
702 | } | |
703 | ||
704 | fn refresh_aggregator<G>(&mut self, generator : &G) | |
705 | where G : SupportGenerator<F, $n, Id=Self::Data>, | |
706 | G::SupportType : LocalAnalysis<F, Self::Agg, $n> { | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
707 | with_task_budget(|task_budget| |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
708 | self.topnode.refresh_aggregator(generator, &self.domain, task_budget) |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
709 | ) |
0 | 710 | } |
711 | ||
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
712 | /*fn data_at(&self, x : &Loc<F,$n>) -> Arc<Vec<D>> { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
713 | self.topnode.get_leaf_data(x).unwrap_or_else(|| Arc::new(Vec::new())) |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
714 | }*/ |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
715 | |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
716 | fn iter_at(&self, x : &Loc<F,$n>) -> std::slice::Iter<'_, D> { |
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
717 | self.topnode.get_leaf_data_iter(x).unwrap_or_else(|| [].iter()) |
0 | 718 | } |
719 | ||
720 | fn new(domain : Cube<F, $n>, depth : M) -> Self { | |
721 | BT { | |
722 | depth : depth, | |
723 | domain : domain, | |
724 | topnode : Node::new(), | |
725 | } | |
726 | } | |
727 | } | |
728 | ||
729 | impl<M,F,D,A> GlobalAnalysis<F,A> for BT<M,F,D,A,$n> | |
730 | where M : Depth, | |
731 | F : Float, | |
8
4e09b7829b51
Multithreaded bisection tree operations
Tuomo Valkonen <tuomov@iki.fi>
parents:
5
diff
changeset
|
732 | D : 'static + Copy + Send + Sync + std::fmt::Debug, |
0 | 733 | A : Aggregator { |
734 | fn global_analysis(&self) -> A { | |
735 | self.topnode.get_aggregator().clone() | |
736 | } | |
737 | } | |
738 | )* } | |
739 | } | |
740 | ||
741 | impl_bt!(1 2 3 4); | |
742 |