src/bisection_tree/bt.rs

Wed, 26 Oct 2022 22:16:57 +0300

author
Tuomo Valkonen <tuomov@iki.fi>
date
Wed, 26 Oct 2022 22:16:57 +0300
changeset 7
860a54fca7bc
parent 5
59dc4c5883f4
child 8
4e09b7829b51
permissions
-rw-r--r--

Added tag unthreaded for changeset d80b87b8acd0

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

mercurial