Mercurial > repos > alg_tools / file comparison

comparison: src/bisection_tree/bt.rs

src/bisection_tree/bt.rs

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

Mercurial Repository: alg_tools

mercurial