--- a/src/bisection_tree/bt.rs Sun Apr 27 14:48:13 2025 -0500
+++ b/src/bisection_tree/bt.rs Sun Apr 27 15:45:40 2025 -0500
@@ -1,34 +1,28 @@
-
/*!
Bisection tree basics, [`BT`] type and the [`BTImpl`] trait.
*/
-use std::slice::IterMut;
-use std::iter::once;
-use std::sync::Arc;
-use serde::{Serialize, Deserialize};
+use itertools::izip;
pub(super) use nalgebra::Const;
-use itertools::izip;
+use serde::{Deserialize, Serialize};
+use std::iter::once;
+use std::slice::IterMut;
+use std::sync::Arc;
-use crate::types::{Float, Num};
-use crate::parallelism::{with_task_budget, TaskBudget};
+use super::aggregator::*;
+use super::support::*;
use crate::coefficients::pow;
-use crate::maputil::{
- array_init,
- map2,
- map2_indexed,
- collect_into_array_unchecked
-};
+use crate::loc::Loc;
+use crate::maputil::{array_init, collect_into_array_unchecked, map2, map2_indexed};
+use crate::parallelism::{with_task_budget, TaskBudget};
use crate::sets::Cube;
-use crate::loc::Loc;
-use super::support::*;
-use super::aggregator::*;
+use crate::types::{Float, Num};
/// An enum that indicates whether a [`Node`] of a [`BT`] is uninitialised, leaf, or branch.
///
/// For the type and const parametere, see the [module level documentation][super].
-#[derive(Clone,Debug)]
-pub(super) enum NodeOption<F : Num, D, A : Aggregator, const N : usize, const P : usize> {
+#[derive(Clone, Debug)]
+pub(super) enum NodeOption<F: Num, D, A: Aggregator, const N: usize, const P: usize> {
/// Indicates an uninitilised node; may become a branch or a leaf.
// TODO: Could optimise Uninitialised away by simply treat Leaf with an empty Vec as
// something that can be still replaced with Branches.
@@ -44,39 +38,41 @@
///
/// For the type and const parameteres, see the [module level documentation][super].
#[derive(Clone, Debug)]
-pub struct Node<F : Num, D, A : Aggregator, const N : usize, const P : usize> {
+pub struct Node<F: Num, D, A: Aggregator, const N: usize, const P: usize> {
/// The data or branches under the node.
- pub(super) data : NodeOption<F, D, A, N, P>,
+ pub(super) data: NodeOption<F, D, A, N, P>,
/// Aggregator for `data`.
- pub(super) aggregator : A,
+ pub(super) aggregator: A,
}
/// Branching information of a [`Node`] of a [`BT`] bisection tree into `P` subnodes.
///
/// For the type and const parameters, see the [module level documentation][super].
#[derive(Clone, Debug)]
-pub(super) struct Branches<F : Num, D, A : Aggregator, const N : usize, const P : usize> {
+pub(super) struct Branches<F: Num, D, A: Aggregator, const N: usize, const P: usize> {
/// Point for subdivision of the (unstored) [`Cube`] corresponding to the node.
- pub(super) branch_at : Loc<F, N>,
+ pub(super) branch_at: Loc<F, N>,
/// Subnodes
- pub(super) nodes : [Node<F, D, A, N, P>; P],
+ pub(super) nodes: [Node<F, D, A, N, P>; P],
}
/// Dirty workaround to broken Rust drop, see [https://github.com/rust-lang/rust/issues/58068]().
-impl<F : Num, D, A : Aggregator, const N : usize, const P : usize>
-Drop for Node<F, D, A, N, P> {
+impl<F: Num, D, A: Aggregator, const N: usize, const P: usize> Drop for Node<F, D, A, N, P> {
fn drop(&mut self) {
use NodeOption as NO;
- let process = |brc : Arc<Branches<F, D, A, N, P>>,
- to_drop : &mut Vec<Arc<Branches<F, D, A, N, P>>>| {
+ let process = |brc: Arc<Branches<F, D, A, N, P>>,
+ to_drop: &mut Vec<Arc<Branches<F, D, A, N, P>>>| {
// We only drop Branches if we have the only strong reference.
// FIXME: update the RwLocks on Nodes.
- Arc::try_unwrap(brc).ok().map(|branches| branches.nodes.map(|mut node| {
- if let NO::Branches(brc2) = std::mem::replace(&mut node.data, NO::Uninitialised) {
- to_drop.push(brc2)
- }
- }));
+ Arc::try_unwrap(brc).ok().map(|branches| {
+ branches.nodes.map(|mut node| {
+ if let NO::Branches(brc2) = std::mem::replace(&mut node.data, NO::Uninitialised)
+ {
+ to_drop.push(brc2)
+ }
+ })
+ });
};
// We mark Self as NodeOption::Uninitialised, extracting the real contents.
@@ -98,9 +94,9 @@
/// Trait for the depth of a [`BT`].
///
/// This will generally be either a runtime [`DynamicDepth`] or compile-time [`Const`] depth.
-pub trait Depth : 'static + Copy + Send + Sync + std::fmt::Debug {
+pub trait Depth: 'static + Copy + Send + Sync + std::fmt::Debug {
/// Lower depth type.
- type Lower : Depth;
+ type Lower: Depth;
/// Returns a lower depth, if there still is one.
fn lower(&self) -> Option<Self::Lower>;
@@ -113,26 +109,26 @@
}
/// Dynamic (runtime) [`Depth`] for a [`BT`].
-#[derive(Copy,Clone,Debug,Serialize,Deserialize)]
+#[derive(Copy, Clone, Debug, Serialize, Deserialize)]
pub struct DynamicDepth(
/// The depth
- pub u8
+ pub u8,
);
impl Depth for DynamicDepth {
type Lower = Self;
#[inline]
fn lower(&self) -> Option<Self> {
- if self.0>0 {
- Some(DynamicDepth(self.0-1))
- } else {
+ if self.0 > 0 {
+ Some(DynamicDepth(self.0 - 1))
+ } else {
None
}
}
#[inline]
fn lower_or(&self) -> Self {
- DynamicDepth(if self.0>0 { self.0 - 1 } else { 0 })
+ DynamicDepth(if self.0 > 0 { self.0 - 1 } else { 0 })
}
#[inline]
@@ -143,9 +139,15 @@
impl Depth for Const<0> {
type Lower = Self;
- fn lower(&self) -> Option<Self::Lower> { None }
- fn lower_or(&self) -> Self::Lower { Const }
- fn value(&self) -> u32 { 0 }
+ fn lower(&self) -> Option<Self::Lower> {
+ None
+ }
+ fn lower_or(&self) -> Self::Lower {
+ Const
+ }
+ fn value(&self) -> u32 {
+ 0
+ }
}
macro_rules! impl_constdepth {
@@ -165,7 +167,7 @@
/// The const parameter `P` from the [module level documentation][super] is required to satisfy
/// `Const<P> : Branchcount<N>`.
/// This trait is implemented for `P=pow(2, N)` for small `N`.
-pub trait BranchCount<const N : usize> {}
+pub trait BranchCount<const N: usize> {}
macro_rules! impl_branchcount {
($($n:literal)*) => { $(
impl BranchCount<$n> for Const<{pow(2, $n)}>{}
@@ -173,18 +175,19 @@
}
impl_branchcount!(1 2 3 4 5 6 7 8);
-impl<F : Float, D, A, const N : usize, const P : usize> Branches<F,D,A,N,P>
-where Const<P> : BranchCount<N>,
- A : Aggregator
+impl<F: Float, D, A, const N: usize, const P: usize> Branches<F, D, A, N, P>
+where
+ Const<P>: BranchCount<N>,
+ A: Aggregator,
{
/// Returns the index in {0, …, `P`-1} for the branch to which the point `x` corresponds.
///
/// This only takes the branch subdivision point $d$ into account, so is always succesfull.
/// Thus, for this point, each branch corresponds to a quadrant of $ℝ^N$ relative to $d$.
- fn get_node_index(&self, x : &Loc<F, N>) -> usize {
- izip!(0..P, x.iter(), self.branch_at.iter()).map(|(i, x_i, branch_i)|
- if x_i > branch_i { 1<<i } else { 0 }
- ).sum()
+ fn get_node_index(&self, x: &Loc<F, N>) -> usize {
+ izip!(0..P, x.iter(), self.branch_at.iter())
+ .map(|(i, x_i, branch_i)| if x_i > branch_i { 1 << i } else { 0 })
+ .sum()
}
/// Returns the node within `Self` containing the point `x`.
@@ -192,24 +195,24 @@
/// This only takes the branch subdivision point $d$ into account, so is always succesfull.
/// Thus, for this point, each branch corresponds to a quadrant of $ℝ^N$ relative to $d$.
#[inline]
- fn get_node(&self, x : &Loc<F,N>) -> &Node<F,D,A,N,P> {
- &self.nodes[self.get_node_index(x)]
+ fn get_node(&self, x: &Loc<F, N>) -> &Node<F, D, A, N, P> {
+ &self.nodes[self.get_node_index(x)]
}
}
/// An iterator over the $P=2^N$ subcubes of a [`Cube`] subdivided at a point `d`.
-pub(super) struct SubcubeIter<'b, F : Float, const N : usize, const P : usize> {
- domain : &'b Cube<F, N>,
- branch_at : Loc<F, N>,
- index : usize,
+pub(super) struct SubcubeIter<'b, F: Float, const N: usize, const P: usize> {
+ domain: &'b Cube<F, N>,
+ branch_at: Loc<F, N>,
+ index: usize,
}
/// Returns the `i`:th subcube of `domain` subdivided at `branch_at`.
#[inline]
-fn get_subcube<F : Float, const N : usize>(
- branch_at : &Loc<F, N>,
- domain : &Cube<F, N>,
- i : usize
+fn get_subcube<F: Float, const N: usize>(
+ branch_at: &Loc<F, N>,
+ domain: &Cube<F, N>,
+ i: usize,
) -> Cube<F, N> {
map2_indexed(branch_at, domain, move |j, &branch, &[start, end]| {
if i & (1 << j) != 0 {
@@ -217,11 +220,11 @@
} else {
[start, branch]
}
- }).into()
+ })
+ .into()
}
-impl<'a, 'b, F : Float, const N : usize, const P : usize> Iterator
-for SubcubeIter<'b, F, N, P> {
+impl<'a, 'b, F: Float, const N: usize, const P: usize> Iterator for SubcubeIter<'b, F, N, P> {
type Item = Cube<F, N>;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
@@ -235,30 +238,30 @@
}
}
-impl<F : Float, D, A, const N : usize, const P : usize>
-Branches<F,D,A,N,P>
-where Const<P> : BranchCount<N>,
- A : Aggregator,
- D : 'static + Copy + Send + Sync {
-
+impl<F: Float, D, A, const N: usize, const P: usize> Branches<F, D, A, N, P>
+where
+ Const<P>: BranchCount<N>,
+ A: Aggregator,
+ D: 'static + Copy + Send + Sync,
+{
/// Creates a new node branching structure, subdividing `domain` based on the
/// [hint][Support::support_hint] of `support`.
- pub(super) fn new_with<S : LocalAnalysis <F, A, N>>(
- domain : &Cube<F,N>,
- support : &S
- ) -> Self {
+ pub(super) fn new_with<S: LocalAnalysis<F, A, N>>(domain: &Cube<F, N>, support: &S) -> Self {
let hint = support.bisection_hint(domain);
let branch_at = map2(&hint, domain, |h, r| {
- h.unwrap_or_else(|| (r[0]+r[1])/F::TWO).max(r[0]).min(r[1])
- }).into();
- Branches{
- branch_at : branch_at,
- nodes : array_init(|| Node::new()),
+ h.unwrap_or_else(|| (r[0] + r[1]) / F::TWO)
+ .max(r[0])
+ .min(r[1])
+ })
+ .into();
+ Branches {
+ branch_at: branch_at,
+ nodes: array_init(|| Node::new()),
}
}
/// Summarises the aggregators of these branches into `agg`
- pub(super) fn summarise_into(&self, agg : &mut A) {
+ pub(super) fn summarise_into(&self, agg: &mut A) {
// We need to create an array of the aggregators clones due to the RwLock.
agg.summarise(self.nodes.iter().map(Node::get_aggregator));
}
@@ -266,12 +269,11 @@
/// Returns an iterator over the subcubes of `domain` subdivided at the branching point
/// of `self`.
#[inline]
- pub(super) fn iter_subcubes<'b>(&self, domain : &'b Cube<F, N>)
- -> SubcubeIter<'b, F, N, P> {
+ pub(super) fn iter_subcubes<'b>(&self, domain: &'b Cube<F, N>) -> SubcubeIter<'b, F, N, P> {
SubcubeIter {
- domain : domain,
- branch_at : self.branch_at,
- index : 0,
+ domain: domain,
+ branch_at: self.branch_at,
+ index: 0,
}
}
@@ -286,8 +288,10 @@
/// Mutably iterate over all nodes and corresponding subcubes of `self`.
#[inline]
- pub(super) fn nodes_and_cubes_mut<'a, 'b>(&'a mut self, domain : &'b Cube<F, N>)
- -> std::iter::Zip<IterMut<'a, Node<F,D,A,N,P>>, SubcubeIter<'b, F, N, P>> {
+ pub(super) fn nodes_and_cubes_mut<'a, 'b>(
+ &'a mut self,
+ domain: &'b Cube<F, N>,
+ ) -> std::iter::Zip<IterMut<'a, Node<F, D, A, N, P>>, SubcubeIter<'b, F, N, P>> {
let subcube_iter = self.iter_subcubes(domain);
self.nodes.iter_mut().zip(subcube_iter)
}
@@ -296,12 +300,16 @@
#[inline]
fn recurse<'scope, 'smaller, 'refs>(
&'smaller mut self,
- domain : &'smaller Cube<F, N>,
- task_budget : TaskBudget<'scope, 'refs>,
- guard : impl Fn(&Node<F,D,A,N,P>, &Cube<F, N>) -> bool + Send + 'smaller,
- mut f : impl for<'a> FnMut(&mut Node<F,D,A,N,P>, &Cube<F, N>, TaskBudget<'smaller, 'a>)
- + Send + Copy + 'smaller
- ) where 'scope : 'smaller {
+ domain: &'smaller Cube<F, N>,
+ task_budget: TaskBudget<'scope, 'refs>,
+ guard: impl Fn(&Node<F, D, A, N, P>, &Cube<F, N>) -> bool + Send + 'smaller,
+ mut f: impl for<'a> FnMut(&mut Node<F, D, A, N, P>, &Cube<F, N>, TaskBudget<'smaller, 'a>)
+ + Send
+ + Copy
+ + 'smaller,
+ ) where
+ 'scope: 'smaller,
+ {
let subs = self.nodes_and_cubes_mut(domain);
task_budget.zoom(move |s| {
for (node, subcube) in subs {
@@ -321,19 +329,23 @@
/// * `support` is the [`Support`] that is used determine with which subcubes of `domain`
/// (at subdivision depth `new_leaf_depth`) the data `d` is to be associated with.
///
- pub(super) fn insert<'refs, 'scope, M : Depth, S : LocalAnalysis<F, A, N>>(
+ pub(super) fn insert<'refs, 'scope, M: Depth, S: LocalAnalysis<F, A, N>>(
&mut self,
- domain : &Cube<F,N>,
- d : D,
- new_leaf_depth : M,
- support : &S,
- task_budget : TaskBudget<'scope, 'refs>,
+ domain: &Cube<F, N>,
+ d: D,
+ new_leaf_depth: M,
+ support: &S,
+ task_budget: TaskBudget<'scope, 'refs>,
) {
let support_hint = support.support_hint();
- self.recurse(domain, task_budget,
- |_, subcube| support_hint.intersects(&subcube),
- move |node, subcube, new_budget| node.insert(subcube, d, new_leaf_depth, support,
- new_budget));
+ self.recurse(
+ domain,
+ task_budget,
+ |_, subcube| support_hint.intersects(&subcube),
+ move |node, subcube, new_budget| {
+ node.insert(subcube, d, new_leaf_depth, support, new_budget)
+ },
+ );
}
/// Construct a new instance of the branch for a different aggregator.
@@ -344,20 +356,24 @@
/// generator's `SupportType`.
pub(super) fn convert_aggregator<ANew, G>(
self,
- generator : &G,
- domain : &Cube<F, N>
- ) -> Branches<F,D,ANew,N,P>
- where ANew : Aggregator,
- G : SupportGenerator<F, N, Id=D>,
- G::SupportType : LocalAnalysis<F, ANew, N> {
+ generator: &G,
+ domain: &Cube<F, N>,
+ ) -> Branches<F, D, ANew, N, P>
+ where
+ ANew: Aggregator,
+ G: SupportGenerator<F, N, Id = D>,
+ G::SupportType: LocalAnalysis<F, ANew, N>,
+ {
let branch_at = self.branch_at;
let subcube_iter = self.iter_subcubes(domain);
- let new_nodes = self.nodes.into_iter().zip(subcube_iter).map(|(node, subcube)| {
- Node::convert_aggregator(node, generator, &subcube)
- });
+ let new_nodes = self
+ .nodes
+ .into_iter()
+ .zip(subcube_iter)
+ .map(|(node, subcube)| Node::convert_aggregator(node, generator, &subcube));
Branches {
- branch_at : branch_at,
- nodes : collect_into_array_unchecked(new_nodes),
+ branch_at: branch_at,
+ nodes: collect_into_array_unchecked(new_nodes),
}
}
@@ -367,30 +383,36 @@
/// [`Support`]s. The `domain` is the cube corresponding to `self`.
pub(super) fn refresh_aggregator<'refs, 'scope, G>(
&mut self,
- generator : &G,
- domain : &Cube<F, N>,
- task_budget : TaskBudget<'scope, 'refs>,
- ) where G : SupportGenerator<F, N, Id=D>,
- G::SupportType : LocalAnalysis<F, A, N> {
- self.recurse(domain, task_budget,
- |_, _| true,
- move |node, subcube, new_budget| node.refresh_aggregator(generator, subcube,
- new_budget));
+ generator: &G,
+ domain: &Cube<F, N>,
+ task_budget: TaskBudget<'scope, 'refs>,
+ ) where
+ G: SupportGenerator<F, N, Id = D>,
+ G::SupportType: LocalAnalysis<F, A, N>,
+ {
+ self.recurse(
+ domain,
+ task_budget,
+ |_, _| true,
+ move |node, subcube, new_budget| {
+ node.refresh_aggregator(generator, subcube, new_budget)
+ },
+ );
}
}
-impl<F : Float, D, A, const N : usize, const P : usize>
-Node<F,D,A,N,P>
-where Const<P> : BranchCount<N>,
- A : Aggregator,
- D : 'static + Copy + Send + Sync {
-
+impl<F: Float, D, A, const N: usize, const P: usize> Node<F, D, A, N, P>
+where
+ Const<P>: BranchCount<N>,
+ A: Aggregator,
+ D: 'static + Copy + Send + Sync,
+{
/// Create a new node
#[inline]
pub(super) fn new() -> Self {
Node {
- data : NodeOption::Uninitialised,
- aggregator : A::new(),
+ data: NodeOption::Uninitialised,
+ aggregator: A::new(),
}
}
@@ -407,7 +429,7 @@
/// Get leaf data iterator
#[inline]
- pub(super) fn get_leaf_data_iter(&self, x : &Loc<F, N>) -> Option<std::slice::Iter<'_, D>> {
+ pub(super) fn get_leaf_data_iter(&self, x: &Loc<F, N>) -> Option<std::slice::Iter<'_, D>> {
match self.data {
NodeOption::Uninitialised => None,
NodeOption::Leaf(ref data) => Some(data.iter()),
@@ -434,13 +456,13 @@
/// If `self` is a [`NodeOption::Branches`], the data is passed to branches whose subcubes
/// `support` intersects. If an [`NodeOption::Uninitialised`] node is encountered, a new leaf is
/// created at a minimum depth of `new_leaf_depth`.
- pub(super) fn insert<'refs, 'scope, M : Depth, S : LocalAnalysis <F, A, N>>(
+ pub(super) fn insert<'refs, 'scope, M: Depth, S: LocalAnalysis<F, A, N>>(
&mut self,
- domain : &Cube<F,N>,
- d : D,
- new_leaf_depth : M,
- support : &S,
- task_budget : TaskBudget<'scope, 'refs>,
+ domain: &Cube<F, N>,
+ d: D,
+ new_leaf_depth: M,
+ support: &S,
+ task_budget: TaskBudget<'scope, 'refs>,
) {
match &mut self.data {
NodeOption::Uninitialised => {
@@ -451,10 +473,10 @@
self.aggregator.aggregate(once(a));
// TODO: this is currently a dirty hard-coded heuristic;
// should add capacity as a parameter
- let mut vec = Vec::with_capacity(2*P+1);
+ let mut vec = Vec::with_capacity(2 * P + 1);
vec.push(d);
NodeOption::Leaf(vec)
- },
+ }
Some(lower) => {
let b = Arc::new({
let mut b0 = Branches::new_with(domain, support);
@@ -465,19 +487,19 @@
NodeOption::Branches(b)
}
}
- },
+ }
NodeOption::Leaf(leaf) => {
leaf.push(d);
let a = support.local_analysis(&domain);
self.aggregator.aggregate(once(a));
- },
+ }
NodeOption::Branches(b) => {
// FIXME: recursion that may cause stack overflow if the tree becomes
// very deep, e.g. due to [`BTSearch::search_and_refine`].
let bm = Arc::make_mut(b);
bm.insert(domain, d, new_leaf_depth.lower_or(), support, task_budget);
bm.summarise_into(&mut self.aggregator);
- },
+ }
}
}
@@ -489,18 +511,19 @@
/// generator's `SupportType`.
pub(super) fn convert_aggregator<ANew, G>(
mut self,
- generator : &G,
- domain : &Cube<F, N>
- ) -> Node<F,D,ANew,N,P>
- where ANew : Aggregator,
- G : SupportGenerator<F, N, Id=D>,
- G::SupportType : LocalAnalysis<F, ANew, N> {
-
+ generator: &G,
+ domain: &Cube<F, N>,
+ ) -> Node<F, D, ANew, N, P>
+ where
+ ANew: Aggregator,
+ G: SupportGenerator<F, N, Id = D>,
+ G::SupportType: LocalAnalysis<F, ANew, N>,
+ {
// The mem::replace is needed due to the [`Drop`] implementation to extract self.data.
match std::mem::replace(&mut self.data, NodeOption::Uninitialised) {
NodeOption::Uninitialised => Node {
- data : NodeOption::Uninitialised,
- aggregator : ANew::new(),
+ data: NodeOption::Uninitialised,
+ aggregator: ANew::new(),
},
NodeOption::Leaf(v) => {
let mut anew = ANew::new();
@@ -510,10 +533,10 @@
}));
Node {
- data : NodeOption::Leaf(v),
- aggregator : anew,
+ data: NodeOption::Leaf(v),
+ aggregator: anew,
}
- },
+ }
NodeOption::Branches(b) => {
// FIXME: recursion that may cause stack overflow if the tree becomes
// very deep, e.g. due to [`BTSearch::search_and_refine`].
@@ -521,8 +544,8 @@
let mut anew = ANew::new();
bnew.summarise_into(&mut anew);
Node {
- data : NodeOption::Branches(Arc::new(bnew)),
- aggregator : anew,
+ data: NodeOption::Branches(Arc::new(bnew)),
+ aggregator: anew,
}
}
}
@@ -534,20 +557,22 @@
/// [`Support`]s. The `domain` is the cube corresponding to `self`.
pub(super) fn refresh_aggregator<'refs, 'scope, G>(
&mut self,
- generator : &G,
- domain : &Cube<F, N>,
- task_budget : TaskBudget<'scope, 'refs>,
- ) where G : SupportGenerator<F, N, Id=D>,
- G::SupportType : LocalAnalysis<F, A, N> {
+ generator: &G,
+ domain: &Cube<F, N>,
+ task_budget: TaskBudget<'scope, 'refs>,
+ ) where
+ G: SupportGenerator<F, N, Id = D>,
+ G::SupportType: LocalAnalysis<F, A, N>,
+ {
match &mut self.data {
- NodeOption::Uninitialised => { },
+ NodeOption::Uninitialised => {}
NodeOption::Leaf(v) => {
self.aggregator = A::new();
- self.aggregator.aggregate(v.iter().map(|d| {
- generator.support_for(*d)
- .local_analysis(&domain)
- }));
- },
+ self.aggregator.aggregate(
+ v.iter()
+ .map(|d| generator.support_for(*d).local_analysis(&domain)),
+ );
+ }
NodeOption::Branches(ref mut b) => {
// FIXME: recursion that may cause stack overflow if the tree becomes
// very deep, e.g. due to [`BTSearch::search_and_refine`].
@@ -563,11 +588,13 @@
///
/// This can be removed and the methods implemented directly on [`BT`] once Rust's const generics
/// are flexible enough to allow fixing `P=pow(2, N)`.
-pub trait BTNode<F, D, A, const N : usize>
-where F : Float,
- D : 'static + Copy,
- A : Aggregator {
- type Node : Clone + std::fmt::Debug;
+pub trait BTNode<F, D, A, const N: usize>
+where
+ F: Float,
+ D: 'static + Copy,
+ A: Aggregator,
+{
+ type Node: Clone + std::fmt::Debug;
}
/// Helper structure for looking up a [`Node`] without the knowledge of `P`.
@@ -580,48 +607,48 @@
/// Basic interface to a [`BT`] bisection tree.
///
/// Further routines are provided by the [`BTSearch`][super::refine::BTSearch] trait.
-pub trait BTImpl<F : Float, const N : usize> : std::fmt::Debug + Clone + GlobalAnalysis<F, Self::Agg> {
+pub trait BTImpl<F: Float, const N: usize>:
+ std::fmt::Debug + Clone + GlobalAnalysis<F, Self::Agg>
+{
/// The data type stored in the tree
- type Data : 'static + Copy + Send + Sync;
+ type Data: 'static + Copy + Send + Sync;
/// The depth type of the tree
- type Depth : Depth;
+ type Depth: Depth;
/// The type for the [aggregate information][Aggregator] about the `Data` stored in each node
/// of the tree.
- type Agg : Aggregator;
+ type Agg: Aggregator;
/// The type of the tree with the aggregator converted to `ANew`.
- type Converted<ANew> : BTImpl<F, N, Data=Self::Data, Agg=ANew> where ANew : Aggregator;
+ type Converted<ANew>: BTImpl<F, N, Data = Self::Data, Agg = ANew>
+ where
+ ANew: Aggregator;
/// Insert the data `d` into the tree for `support`.
///
/// Every leaf node of the tree that intersects the `support` will contain a copy of
/// `d`.
- fn insert<S : LocalAnalysis<F, Self::Agg, N>>(
- &mut self,
- d : Self::Data,
- support : &S
- );
+ fn insert<S: LocalAnalysis<F, Self::Agg, N>>(&mut self, d: Self::Data, support: &S);
/// Construct a new instance of the tree for a different aggregator
///
/// The `generator` is used to convert the data of type [`Self::Data`] contained in the tree
/// into corresponding [`Support`]s.
- fn convert_aggregator<ANew, G>(self, generator : &G)
- -> Self::Converted<ANew>
- where ANew : Aggregator,
- G : SupportGenerator<F, N, Id=Self::Data>,
- G::SupportType : LocalAnalysis<F, ANew, N>;
-
+ fn convert_aggregator<ANew, G>(self, generator: &G) -> Self::Converted<ANew>
+ where
+ ANew: Aggregator,
+ G: SupportGenerator<F, N, Id = Self::Data>,
+ G::SupportType: LocalAnalysis<F, ANew, N>;
/// Refreshes the aggregator of the three after possible changes to the support generator.
///
/// The `generator` is used to convert the data of type [`Self::Data`] contained in the tree
/// into corresponding [`Support`]s.
- fn refresh_aggregator<G>(&mut self, generator : &G)
- where G : SupportGenerator<F, N, Id=Self::Data>,
- G::SupportType : LocalAnalysis<F, Self::Agg, N>;
+ fn refresh_aggregator<G>(&mut self, generator: &G)
+ where
+ G: SupportGenerator<F, N, Id = Self::Data>,
+ G::SupportType: LocalAnalysis<F, Self::Agg, N>;
/// Returns an iterator over all [`Self::Data`] items at the point `x` of the domain.
- fn iter_at(&self, x : &Loc<F,N>) -> std::slice::Iter<'_, Self::Data>;
+ fn iter_at(&self, x: &Loc<F, N>) -> std::slice::Iter<'_, Self::Data>;
/*
/// Returns all [`Self::Data`] items at the point `x` of the domain.
@@ -629,7 +656,7 @@
*/
/// Create a new tree on `domain` of indicated `depth`.
- fn new(domain : Cube<F, N>, depth : Self::Depth) -> Self;
+ fn new(domain: Cube<F, N>, depth: Self::Depth) -> Self;
}
/// The main bisection tree structure.
@@ -637,20 +664,17 @@
/// It should be accessed via the [`BTImpl`] trait to hide the `const P : usize` parameter until
/// const generics are flexible enough to fix `P=pow(2, N)` and thus also get rid of
/// the `BTNodeLookup : BTNode<F, D, A, N>` trait bound.
-#[derive(Clone,Debug)]
-pub struct BT<
- M : Depth,
- F : Float,
- D : 'static + Copy,
- A : Aggregator,
- const N : usize,
-> where BTNodeLookup : BTNode<F, D, A, N> {
+#[derive(Clone, Debug)]
+pub struct BT<M: Depth, F: Float, D: 'static + Copy, A: Aggregator, const N: usize>
+where
+ BTNodeLookup: BTNode<F, D, A, N>,
+{
/// The depth of the tree (initial, before refinement)
- pub(super) depth : M,
+ pub(super) depth: M,
/// The domain of the toplevel node
- pub(super) domain : Cube<F, N>,
+ pub(super) domain: Cube<F, N>,
/// The toplevel node of the tree
- pub(super) topnode : <BTNodeLookup as BTNode<F, D, A, N>>::Node,
+ pub(super) topnode: <BTNodeLookup as BTNode<F, D, A, N>>::Node,
}
macro_rules! impl_bt {
@@ -739,4 +763,3 @@
}
impl_bt!(1 2 3 4);
-