Sat, 22 Oct 2022 18:12:49 +0300
Fix some unit tests after fundamental changes that made them invalid
0 | 1 | use crate::types::*; |
2 | use crate::sets::Set; | |
3 | ||
4 | /// Trait for aggregating information about a branch of a [`super::BT`] bisection tree. | |
5 | pub trait Aggregator : Clone + std::fmt::Debug { | |
6 | // Aggregate a new leaf data point to current state. | |
7 | fn aggregate<I>(&mut self, aggregates : I) | |
8 | where I : Iterator<Item=Self>; | |
9 | ||
10 | // Summarise several other aggregators, resetting current state. | |
11 | fn summarise<'a, I>(&'a mut self, aggregates : I) | |
12 | where I : Iterator<Item=&'a Self>; | |
13 | ||
14 | /// Initialisation of aggregate data for an empty lower node. | |
15 | fn new() -> Self; | |
16 | } | |
17 | ||
18 | /// An [`Aggregator`] that doesn't aggregate anything. | |
19 | #[derive(Clone,Debug)] | |
20 | pub struct NullAggregator; | |
21 | ||
22 | impl Aggregator for NullAggregator { | |
23 | // TODO: these should probabably also take a Cube as argument to | |
24 | // allow integrating etc. | |
25 | fn aggregate<I>(&mut self, _aggregates : I) | |
26 | where I : Iterator<Item=Self> {} | |
27 | ||
28 | fn summarise<'a, I>(&'a mut self, _aggregates : I) | |
29 | where I : Iterator<Item=&'a Self> {} | |
30 | ||
31 | fn new() -> Self { NullAggregator } | |
32 | } | |
33 | ||
34 | /// Upper and lower bounds on an `F`-valued function. | |
35 | /// Returned by [`super::support::Bounded::bounds`]. | |
36 | #[derive(Copy,Clone,Debug)] | |
37 | pub struct Bounds<F>(pub F, pub F); | |
38 | ||
39 | impl<F : Num> Bounds<F> { | |
40 | /// Returns the lower bound | |
41 | #[inline] | |
42 | pub fn lower(&self) -> F { self.0 } | |
43 | ||
44 | /// Returns the upper bound | |
45 | #[inline] | |
46 | pub fn upper(&self) -> F { self.1 } | |
47 | } | |
48 | ||
49 | impl<F : Float> Bounds<F> { | |
50 | /// Returns a uniform bound on the function (maximum over the absolute values of the | |
51 | /// upper and lower bound). | |
52 | #[inline] | |
53 | pub fn uniform(&self) -> F { | |
54 | let &Bounds(lower, upper) = self; | |
55 | lower.abs().max(upper.abs()) | |
56 | } | |
57 | } | |
58 | ||
59 | impl<'a, F : Float> std::ops::Add<Self> for Bounds<F> { | |
60 | type Output = Self; | |
61 | #[inline] | |
62 | fn add(self, Bounds(l2, u2) : Self) -> Self::Output { | |
63 | let Bounds(l1, u1) = self; | |
64 | debug_assert!(l1 <= u1 && l2 <= u2); | |
65 | Bounds(l1 + l2, u1 + u2) | |
66 | } | |
67 | } | |
68 | ||
69 | impl<'a, F : Float> std::ops::Mul<Self> for Bounds<F> { | |
70 | type Output = Self; | |
71 | #[inline] | |
72 | fn mul(self, Bounds(l2, u2) : Self) -> Self::Output { | |
73 | let Bounds(l1, u1) = self; | |
74 | debug_assert!(l1 <= u1 && l2 <= u2); | |
75 | let a = l1 * l2; | |
76 | let b = u1 * u2; | |
77 | // The order may flip when negative numbers are involved, so need min/max | |
78 | Bounds(a.min(b), a.max(b)) | |
79 | } | |
80 | } | |
81 | ||
82 | impl<F : Float> std::iter::Product for Bounds<F> { | |
83 | #[inline] | |
84 | fn product<I>(mut iter: I) -> Self | |
85 | where I: Iterator<Item = Self> { | |
86 | match iter.next() { | |
87 | None => Bounds(F::ZERO, F::ZERO), | |
88 | Some(init) => iter.fold(init, |a, b| a*b) | |
89 | } | |
90 | } | |
91 | } | |
92 | ||
93 | impl<F : Float> Set<F> for Bounds<F> { | |
94 | fn contains(&self, item : &F) -> bool { | |
95 | let &Bounds(l, u) = self; | |
96 | debug_assert!(l <= u); | |
97 | l <= *item && *item <= u | |
98 | } | |
99 | } | |
100 | ||
101 | impl<F : Float> Bounds<F> { | |
102 | /// Calculate a common bound (glb, lub) for two bounds. | |
103 | #[inline] | |
104 | pub fn common(&self, &Bounds(l2, u2) : &Self) -> Self { | |
105 | let &Bounds(l1, u1) = self; | |
106 | debug_assert!(l1 <= u1 && l2 <= u2); | |
107 | Bounds(l1.min(l2), u1.max(u2)) | |
108 | } | |
109 | ||
110 | #[inline] | |
111 | pub fn superset(&self, &Bounds(l2, u2) : &Self) -> bool { | |
112 | let &Bounds(l1, u1) = self; | |
113 | debug_assert!(l1 <= u1 && l2 <= u2); | |
114 | l1 <= l2 && u2 <= u1 | |
115 | } | |
116 | ||
117 | // Return the greatest bound contained by both argument bounds, if one exists. | |
118 | #[inline] | |
119 | pub fn glb(&self, &Bounds(l2, u2) : &Self) -> Option<Self> { | |
120 | let &Bounds(l1, u1) = self; | |
121 | debug_assert!(l1 <= u1 && l2 <= u2); | |
122 | let l = l1.max(l2); | |
123 | let u = u1.min(u2); | |
124 | if l < u { | |
125 | Some(Bounds(l, u)) | |
126 | } else { | |
127 | None | |
128 | } | |
129 | } | |
130 | } | |
131 | ||
132 | impl<F : Float> Aggregator for Bounds<F> { | |
133 | #[inline] | |
134 | fn aggregate<I>(&mut self, aggregates : I) | |
135 | where I : Iterator<Item=Self> { | |
136 | *self = aggregates.fold(*self, |a, b| a + b); | |
137 | } | |
138 | ||
139 | #[inline] | |
140 | fn summarise<'a, I>(&'a mut self, mut aggregates : I) | |
141 | where I : Iterator<Item=&'a Self> { | |
142 | *self = match aggregates.next() { | |
143 | None => Bounds(F::ZERO, F::ZERO), // No parts in this cube; the function is zero | |
144 | Some(&bounds) => { | |
145 | aggregates.fold(bounds, |a, b| a.common(b)) | |
146 | } | |
147 | } | |
148 | } | |
149 | ||
150 | #[inline] | |
151 | fn new() -> Self { | |
152 | Bounds(F::ZERO, F::ZERO) | |
153 | } | |
154 | } |