src/bisection_tree/bt.rs

Mon, 24 Oct 2022 10:52:19 +0300

author
Tuomo Valkonen <tuomov@iki.fi>
date
Mon, 24 Oct 2022 10:52:19 +0300
changeset 4
61b068c50e25
parent 0
9f27689eb130
child 5
59dc4c5883f4
permissions
-rw-r--r--

Added type for numerical errors

0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
1
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
2 use std::slice::{Iter,IterMut};
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
3 use std::iter::once;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
4 use std::rc::Rc;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
5 use serde::{Serialize, Deserialize};
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
6 pub use nalgebra::Const;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
7 use itertools::izip;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
8
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
9 use crate::iter::{MapF,Mappable};
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
10 use crate::types::{Float, Num};
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
11 use crate::coefficients::pow;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
12 use crate::maputil::{
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
13 array_init,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
14 map2,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
15 map2_indexed,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
16 collect_into_array_unchecked
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
17 };
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
18 pub use crate::sets::Cube;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
19 pub use crate::loc::Loc;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
20 use super::support::*;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
21 use super::aggregator::*;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
22
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
23 #[derive(Clone,Debug)]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
24 pub enum NodeOption<F : Num, D, A : Aggregator, const N : usize, const P : usize> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
25 // 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
26 // something that can be still replaced with Branches.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
27 Uninitialised,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
28 // TODO: replace with QuickVec fast and w/o allocs on single elements.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
29 Leaf(Rc<Vec<D>>),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
30 Branches(Rc<Branches<F, D, A, N, P>>),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
31 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
32
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
33 /// Node of a [`BT`] bisection tree.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
34 #[derive(Clone,Debug)]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
35 pub struct Node<F : Num, D, A : Aggregator, const N : usize, const P : usize> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
36 pub(super) data : NodeOption<F, D, A, N, P>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
37 /// Aggregator for `data`.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
38 pub(super) aggregator : A,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
39 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
40
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
41 /// Branch information of a [`Node`] of a [`BT`] bisection tree.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
42 #[derive(Clone,Debug)]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
43 pub struct Branches<F : Num, D, A : Aggregator, const N : usize, const P : usize> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
44 /// Point for subdivision of the (unstored) [`Cube`] corresponding to the node.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
45 pub(super) branch_at : Loc<F, N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
46 /// Subnodes
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
47 pub(super) nodes : [Node<F, D, A, N, P>; P],
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
48 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
49
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
50 /// 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
51 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
52 Drop for Node<F, D, A, N, P> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
53 fn drop(&mut self) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
54 use NodeOption as NO;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
55
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
56 let process = |brc : Rc<Branches<F, D, A, N, P>>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
57 to_drop : &mut Vec<Rc<Branches<F, D, A, N, P>>>| {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
58 // We only drop Branches if we have the only strong reference.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
59 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
60 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
61 to_drop.push(brc2)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
62 }
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
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
66 // We mark Self as NodeOption::Uninitialised, extracting the real contents.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
67 // If we have subprocess, we need to process them.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
68 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
69 // 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
70 let mut to_drop = Vec::new();
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
71 process(brc1, &mut to_drop);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
72
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
73 // 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
74 // pushing all internal branching nodes into the queue.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
75 while let Some(brc) = to_drop.pop() {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
76 process(brc, &mut to_drop)
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
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
82 pub trait Depth : 'static + Copy + std::fmt::Debug {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
83 type Lower : Depth;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
84 fn lower(&self) -> Option<Self::Lower>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
85 fn lower_or(&self) -> Self::Lower;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
86 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
87
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
88 #[derive(Copy,Clone,Debug,Serialize,Deserialize)]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
89 pub struct DynamicDepth(pub u8);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
90 impl Depth for DynamicDepth {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
91 type Lower = Self;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
92 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
93 fn lower(&self) -> Option<Self> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
94 if self.0>0 {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
95 Some(DynamicDepth(self.0-1))
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
96 } else {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
97 None
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
98 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
99 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
100 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
101 fn lower_or(&self) -> Self {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
102 DynamicDepth(if self.0>0 { self.0 - 1 } else { 0 })
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
103 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
104 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
105
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
106 impl Depth for Const<0> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
107 type Lower = Self;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
108 fn lower(&self) -> Option<Self::Lower> { None }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
109 fn lower_or(&self) -> Self::Lower { Const }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
110 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
111
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
112 macro_rules! impl_constdepth {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
113 ($($n:literal)*) => { $(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
114 impl Depth for Const<$n> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
115 type Lower = Const<{$n-1}>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
116 fn lower(&self) -> Option<Self::Lower> { Some(Const) }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
117 fn lower_or(&self) -> Self::Lower { Const }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
118 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
119 )* };
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
120 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
121 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
122
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
123
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
124 pub trait BranchCount<const N : usize> {}
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
125 macro_rules! impl_branchcount {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
126 ($($n:literal)*) => { $(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
127 impl BranchCount<$n> for Const<{pow(2, $n)}>{}
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
128 )* }
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 impl_branchcount!(1 2 3 4 5 6 7 8);
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<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
133 where Const<P> : BranchCount<N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
134 A : Aggregator
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
135 {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
136 fn get_node_index(&self, x : &Loc<F, N>) -> usize {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
137 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
138 if x_i > branch_i { 1<<i } else { 0 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
139 ).sum()
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
140 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
141
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
142 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
143 pub fn get_node(&self, x : &Loc<F,N>) -> &Node<F,D,A,N,P> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
144 &self.nodes[self.get_node_index(x)]
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
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
148
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
149 pub struct BTIter<'a, D> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
150 iter : Iter<'a, D>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
151 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
152
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
153 pub struct SubcubeIter<'b, F : Float, const N : usize, const P : usize> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
154 domain : &'b Cube<F, N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
155 branch_at : Loc<F, N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
156 index : usize,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
157 }
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 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
160 fn get_subcube<F : Float, const N : usize>(branch_at : &Loc<F, N>, domain : &Cube<F, N>, i : usize) -> Cube<F, N> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
161 map2_indexed(branch_at, domain, move |j, &branch, &[start, end]| {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
162 if i & (1 << j) != 0 {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
163 [branch, end]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
164 } else {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
165 [start, branch]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
166 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
167 }).into()
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
168 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
169
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
170 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
171 for SubcubeIter<'b, F, N, P> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
172 type Item = Cube<F, N>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
173 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
174 fn next(&mut self) -> Option<Self::Item> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
175 if self.index < P {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
176 let i = self.index;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
177 self.index += 1;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
178 Some(get_subcube(&self.branch_at, self.domain, i))
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
179 } else {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
180 None
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
181 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
182 }
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 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
186 Branches<F,D,A,N,P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
187 where Const<P> : BranchCount<N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
188 A : Aggregator {
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 pub fn new_with<S : LocalAnalysis <F, A, N>>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
191 domain : &Cube<F,N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
192 support : &S
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
193 ) -> Self {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
194 let hint = support.bisection_hint(domain);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
195 let branch_at = map2(&hint, domain, |h, r| {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
196 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
197 }).into();
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
198 Branches{
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
199 branch_at : branch_at,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
200 nodes : array_init(|| Node::new()),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
201 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
202 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
203
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
204 /// Get an iterator over the aggregators of the nodes of this branch head.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
205 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
206 pub fn aggregators(&self) -> MapF<Iter<'_, Node<F,D,A,N,P>>, &'_ A> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
207 self.nodes.iter().mapF(Node::get_aggregator)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
208 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
209
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
210 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
211 pub fn iter_subcubes<'b>(&self, domain : &'b Cube<F, N>)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
212 -> SubcubeIter<'b, F, N, P> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
213 SubcubeIter {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
214 domain : domain,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
215 branch_at : self.branch_at,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
216 index : 0,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
217 }
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
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
220 /// Iterate over all nodes and corresponding subcubes of self.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
221 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
222 pub fn nodes_and_cubes<'a, 'b>(&'a self, domain : &'b Cube<F, N>)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
223 -> 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
224 self.nodes.iter().zip(self.iter_subcubes(domain))
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
225 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
226
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
227 /// Mutably iterate over all nodes and corresponding subcubes of self.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
228 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
229 pub fn nodes_and_cubes_mut<'a, 'b>(&'a mut self, domain : &'b Cube<F, N>)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
230 -> 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
231 let subcube_iter = self.iter_subcubes(domain);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
232 self.nodes.iter_mut().zip(subcube_iter)
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 /// Insert data into the branch.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
236 pub fn insert<M : Depth, S : LocalAnalysis<F, A, N>>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
237 &mut self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
238 domain : &Cube<F,N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
239 d : D,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
240 new_leaf_depth : M,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
241 support : &S
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
242 ) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
243 let support_hint = support.support_hint();
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
244 for (node, subcube) in self.nodes_and_cubes_mut(&domain) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
245 if support_hint.intersects(&subcube) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
246 node.insert(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
247 &subcube,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
248 d,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
249 new_leaf_depth,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
250 support
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
251 );
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
252 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
253 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
254 }
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 /// Construct a new instance for a different aggregator
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
257 pub fn convert_aggregator<ANew, G>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
258 self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
259 generator : &G,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
260 domain : &Cube<F, N>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
261 ) -> Branches<F,D,ANew,N,P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
262 where ANew : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
263 G : SupportGenerator<F, N, Id=D>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
264 G::SupportType : LocalAnalysis<F, ANew, N> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
265 let branch_at = self.branch_at;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
266 let subcube_iter = self.iter_subcubes(domain);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
267 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
268 // TODO: avoid clone
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
269 node.convert_aggregator(generator, &subcube)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
270 });
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
271 Branches {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
272 branch_at : branch_at,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
273 nodes : collect_into_array_unchecked(new_nodes),
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 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
276
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
277 /// Recalculate aggregator after changes to generator
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
278 pub fn refresh_aggregator<G>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
279 &mut self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
280 generator : &G,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
281 domain : &Cube<F, N>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
282 ) where G : SupportGenerator<F, N, Id=D>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
283 G::SupportType : LocalAnalysis<F, A, N> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
284 for (node, subcube) in self.nodes_and_cubes_mut(domain) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
285 node.refresh_aggregator(generator, &subcube)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
286 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
287 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
288 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
289
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
290 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
291 Node<F,D,A,N,P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
292 where Const<P> : BranchCount<N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
293 A : Aggregator {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
294
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
295 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
296 pub fn new() -> Self {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
297 Node {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
298 data : NodeOption::Uninitialised,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
299 aggregator : A::new(),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
300 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
301 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
302
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
303 /// Get leaf data
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
304 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
305 pub fn get_leaf_data(&self, x : &Loc<F, N>) -> Option<&Vec<D>> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
306 match self.data {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
307 NodeOption::Uninitialised => None,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
308 NodeOption::Leaf(ref data) => Some(data),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
309 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
310 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
311 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
312
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
313 /// Returns a reference to the aggregator of this node
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
314 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
315 pub fn get_aggregator(&self) -> &A {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
316 &self.aggregator
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 /// Insert `d` into the tree. If an `Incomplete` node is encountered, a new
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
320 /// leaf is created at a minimum depth of `new_leaf_depth`
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
321 pub fn insert<M : Depth, S : LocalAnalysis <F, A, N>>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
322 &mut self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
323 domain : &Cube<F,N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
324 d : D,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
325 new_leaf_depth : M,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
326 support : &S
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
327 ) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
328 match &mut self.data {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
329 NodeOption::Uninitialised => {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
330 // Replace uninitialised node with a leaf or a branch
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
331 self.data = match new_leaf_depth.lower() {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
332 None => {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
333 let a = support.local_analysis(&domain);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
334 self.aggregator.aggregate(once(a));
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
335 // TODO: this is currently a dirty hard-coded heuristic;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
336 // should add capacity as a parameter
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
337 let mut vec = Vec::with_capacity(2*P+1);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
338 vec.push(d);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
339 NodeOption::Leaf(Rc::new(vec))
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
340 },
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
341 Some(lower) => {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
342 let b = Rc::new({
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
343 let mut b0 = Branches::new_with(domain, support);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
344 b0.insert(domain, d, lower, support);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
345 b0
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 self.aggregator.summarise(b.aggregators());
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
348 NodeOption::Branches(b)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
349 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
350 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
351 },
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
352 NodeOption::Leaf(leaf) => {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
353 Rc::make_mut(leaf).push(d);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
354 let a = support.local_analysis(&domain);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
355 self.aggregator.aggregate(once(a));
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
356 },
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
357 NodeOption::Branches(b) => {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
358 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
359 self.aggregator.summarise(b.aggregators());
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 /// Construct a new instance for a different aggregator
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
365 pub fn convert_aggregator<ANew, G>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
366 mut self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
367 generator : &G,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
368 domain : &Cube<F, N>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
369 ) -> Node<F,D,ANew,N,P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
370 where ANew : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
371 G : SupportGenerator<F, N, Id=D>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
372 G::SupportType : LocalAnalysis<F, ANew, N> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
373
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
374 // 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
375 match std::mem::replace(&mut self.data, NodeOption::Uninitialised) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
376 NodeOption::Uninitialised => Node {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
377 data : NodeOption::Uninitialised,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
378 aggregator : ANew::new(),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
379 },
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
380 NodeOption::Leaf(v) => {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
381 let mut anew = ANew::new();
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
382 anew.aggregate(v.iter().map(|d| {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
383 let support = generator.support_for(*d);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
384 support.local_analysis(&domain)
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 Node {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
388 data : NodeOption::Leaf(v),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
389 aggregator : anew,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
390 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
391 },
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
392 NodeOption::Branches(b) => {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
393 // TODO: now with Rc, convert_aggregator should be reference-based.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
394 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
395 let mut anew = ANew::new();
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
396 anew.summarise(bnew.aggregators());
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
397 Node {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
398 data : NodeOption::Branches(bnew),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
399 aggregator : anew,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
400 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
401 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
402 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
403 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
404
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
405 /// Refresh aggregator after changes to generator
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
406 pub fn refresh_aggregator<G>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
407 &mut self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
408 generator : &G,
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 ) where G : SupportGenerator<F, N, Id=D>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
411 G::SupportType : LocalAnalysis<F, A, N> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
412 match &mut self.data {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
413 NodeOption::Uninitialised => { },
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
414 NodeOption::Leaf(v) => {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
415 self.aggregator = A::new();
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
416 self.aggregator.aggregate(v.iter().map(|d| {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
417 generator.support_for(*d)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
418 .local_analysis(&domain)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
419 }));
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
420 },
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
421 NodeOption::Branches(ref mut b) => {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
422 // TODO: now with Rc, convert_aggregator should be reference-based.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
423 Rc::make_mut(b).refresh_aggregator(generator, domain);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
424 self.aggregator.summarise(b.aggregators());
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
425 }
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 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
428 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
429
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
430 impl<'a, D> Iterator for BTIter<'a,D> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
431 type Item = &'a D;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
432 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
433 fn next(&mut self) -> Option<&'a D> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
434 self.iter.next()
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
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
439 //
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
440 // BT
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
441 //
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
442
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
443 /// Internal structure to hide the `const P : usize` parameter of [`Node`] until
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
444 /// const generics are flexible enough to fix `P=pow(2, N)`.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
445 pub trait BTNode<F, D, A, const N : usize>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
446 where F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
447 D : 'static + Copy,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
448 A : Aggregator {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
449 type Node : Clone + std::fmt::Debug;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
450 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
451
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
452 #[derive(Debug)]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
453 pub struct BTNodeLookup;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
454
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
455 /// Interface to a [`BT`] bisection tree.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
456 pub trait BTImpl<F : Float, const N : usize> : std::fmt::Debug + Clone + GlobalAnalysis<F, Self::Agg> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
457 type Data : 'static + Copy;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
458 type Depth : Depth;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
459 type Agg : Aggregator;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
460 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
461
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
462 /// Insert d into the `BisectionTree`.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
463 fn insert<S : LocalAnalysis<F, Self::Agg, N>>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
464 &mut self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
465 d : Self::Data,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
466 support : &S
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
467 );
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
468
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
469 /// Construct a new instance for a different aggregator
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
470 fn convert_aggregator<ANew, G>(self, generator : &G)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
471 -> Self::Converted<ANew>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
472 where ANew : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
473 G : SupportGenerator<F, N, Id=Self::Data>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
474 G::SupportType : LocalAnalysis<F, ANew, N>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
475
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 /// Refresh aggregator after changes to generator
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
478 fn refresh_aggregator<G>(&mut self, generator : &G)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
479 where G : SupportGenerator<F, N, Id=Self::Data>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
480 G::SupportType : LocalAnalysis<F, Self::Agg, N>;
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 /// Iterarate items at x
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
483 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
484
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
485 /// Create a new instance
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
486 fn new(domain : Cube<F, N>, depth : Self::Depth) -> Self;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
487 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
488
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
489 /// The main bisection tree structure. The interface operations are via [`BTImpl`]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
490 /// to hide the `const P : usize` parameter until const generics are flexible enough
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
491 /// to fix `P=pow(2, N)`.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
492 #[derive(Clone,Debug)]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
493 pub struct BT<
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
494 M : Depth,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
495 F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
496 D : 'static + Copy,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
497 A : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
498 const N : usize,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
499 > where BTNodeLookup : BTNode<F, D, A, N> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
500 pub(super) depth : M,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
501 pub(super) domain : Cube<F, N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
502 pub(super) topnode : <BTNodeLookup as BTNode<F, D, A, N>>::Node,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
503 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
504
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
505 macro_rules! impl_bt {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
506 ($($n:literal)*) => { $(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
507 impl<F, D, A> BTNode<F, D, A, $n> for BTNodeLookup
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
508 where F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
509 D : 'static + Copy + std::fmt::Debug,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
510 A : Aggregator {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
511 type Node = Node<F,D,A,$n,{pow(2, $n)}>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
512 }
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 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
515 where M : Depth,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
516 F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
517 D : 'static + Copy + std::fmt::Debug,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
518 A : Aggregator {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
519 type Data = D;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
520 type Depth = M;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
521 type Agg = A;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
522 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
523
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
524 /// Insert `d` into the tree.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
525 fn insert<S: LocalAnalysis<F, A, $n>>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
526 &mut self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
527 d : D,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
528 support : &S
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
529 ) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
530 self.topnode.insert(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
531 &self.domain,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
532 d,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
533 self.depth,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
534 support
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
535 );
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
536 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
537
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
538 /// Construct a new instance for a different aggregator
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
539 fn convert_aggregator<ANew, G>(self, generator : &G) -> Self::Converted<ANew>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
540 where ANew : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
541 G : SupportGenerator<F, $n, Id=D>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
542 G::SupportType : LocalAnalysis<F, ANew, $n> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
543 let topnode = self.topnode.convert_aggregator(generator, &self.domain);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
544 BT {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
545 depth : self.depth,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
546 domain : self.domain,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
547 topnode
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
548 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
549 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
550
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
551 /// Refresh aggregator after changes to generator
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
552 fn refresh_aggregator<G>(&mut self, generator : &G)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
553 where G : SupportGenerator<F, $n, Id=Self::Data>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
554 G::SupportType : LocalAnalysis<F, Self::Agg, $n> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
555 self.topnode.refresh_aggregator(generator, &self.domain);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
556 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
557
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
558 /// Iterate elements at `x`.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
559 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
560 match self.topnode.get_leaf_data(x) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
561 Some(data) => BTIter { iter : data.iter() },
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
562 None => BTIter { iter : [].iter() }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
563 }
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
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
566 fn new(domain : Cube<F, $n>, depth : M) -> Self {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
567 BT {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
568 depth : depth,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
569 domain : domain,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
570 topnode : Node::new(),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
571 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
572 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
573 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
574
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
575 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
576 where M : Depth,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
577 F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
578 D : 'static + Copy + std::fmt::Debug,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
579 A : Aggregator {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
580 fn global_analysis(&self) -> A {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
581 self.topnode.get_aggregator().clone()
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
582 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
583 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
584 )* }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
585 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
586
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
587 impl_bt!(1 2 3 4);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
588

mercurial