Mercurial > repos > alg_tools / file comparison

comparison: src/bisection_tree/aggregator.rs

src/bisection_tree/aggregator.rs

branch
dev
changeset 96
962c8e346ab9
parent 63
f7b87d84864d
child 97
4e80fb049dca
equal deleted inserted replaced
95:9cb8225a3a41 96:962c8e346ab9
1 /*! 1 /*!
2 Aggregation / summarisation of information in branches of bisection trees. 2 Aggregation / summarisation of information in branches of bisection trees.
3 */ 3 */
4 4
5 use crate::instance::Instance;
6 use crate::sets::Set;
5 use crate::types::*; 7 use crate::types::*;
6 use crate::sets::Set;
7 use crate::instance::Instance;
8 8
9 /// Trait for aggregating information about a branch of a [bisection tree][super::BT]. 9 /// Trait for aggregating information about a branch of a [bisection tree][super::BT].
10 /// 10 ///
11 /// Currently [`Bounds`] is the only provided aggregator. 11 /// Currently [`Bounds`] is the only provided aggregator.
12 /// It keeps track of upper and lower bounds of a function representeed by the `BT` by 12 /// It keeps track of upper and lower bounds of a function representeed by the `BT` by
17 /// estimate of the upper and lower bounds of a sum of functions. 17 /// estimate of the upper and lower bounds of a sum of functions.
18 /// * [`Self::summarise`] takes the maximum of the input bounds. This calculates the bounds 18 /// * [`Self::summarise`] takes the maximum of the input bounds. This calculates the bounds
19 /// of a function on a greater domain from bounds on subdomains 19 /// of a function on a greater domain from bounds on subdomains
20 /// (in practise [`Cube`][crate::sets::Cube]s). 20 /// (in practise [`Cube`][crate::sets::Cube]s).
21 /// 21 ///
22 pub trait Aggregator : Clone + Sync + Send + 'static + std::fmt::Debug { 22 pub trait Aggregator: Clone + Sync + Send + 'static + std::fmt::Debug {
23 /// Aggregate a new data to current state. 23 /// Aggregate a new data to current state.
24 fn aggregate<I>(&mut self, aggregates : I) 24 fn aggregate<I>(&mut self, aggregates: I)
25 where I : Iterator<Item=Self>; 25 where
26 I: Iterator<Item = Self>;
26 27
27 /// Summarise several other aggregators, resetting current state. 28 /// Summarise several other aggregators, resetting current state.
28 fn summarise<'a, I>(&'a mut self, aggregates : I) 29 fn summarise<'a, I>(&'a mut self, aggregates: I)
29 where I : Iterator<Item=&'a Self>; 30 where
31 I: Iterator<Item = &'a Self>;
30 32
31 /// Create a new “empty” aggregate data. 33 /// Create a new “empty” aggregate data.
32 fn new() -> Self; 34 fn new() -> Self;
33 } 35 }
34 36
35 /// An [`Aggregator`] that doesn't aggregate anything. 37 /// An [`Aggregator`] that doesn't aggregate anything.
36 #[derive(Clone,Debug)] 38 #[derive(Clone, Debug)]
37 pub struct NullAggregator; 39 pub struct NullAggregator;
38 40
39 impl Aggregator for NullAggregator { 41 impl Aggregator for NullAggregator {
40 fn aggregate<I>(&mut self, _aggregates : I) 42 fn aggregate<I>(&mut self, _aggregates: I)
41 where I : Iterator<Item=Self> {} 43 where
42 44 I: Iterator<Item = Self>,
43 fn summarise<'a, I>(&'a mut self, _aggregates : I) 45 {
44 where I : Iterator<Item=&'a Self> {} 46 }
45 47
46 fn new() -> Self { NullAggregator } 48 fn summarise<'a, I>(&'a mut self, _aggregates: I)
49 where
50 I: Iterator<Item = &'a Self>,
51 {
52 }
53
54 fn new() -> Self {
55 NullAggregator
56 }
47 } 57 }
48 58
49 /// Upper and lower bounds on an `F`-valued function. 59 /// Upper and lower bounds on an `F`-valued function.
50 #[derive(Copy,Clone,Debug)] 60 #[derive(Copy, Clone, Debug)]
51 pub struct Bounds<F>( 61 pub struct Bounds<F>(
52 /// Lower bound 62 /// Lower bound
53 pub F, 63 pub F,
54 /// Upper bound 64 /// Upper bound
55 pub F 65 pub F,
56 ); 66 );
57 67
58 impl<F : Copy> Bounds<F> { 68 impl<F: Copy> Bounds<F> {
59 /// Returns the lower bound 69 /// Returns the lower bound
60 #[inline] 70 #[inline]
61 pub fn lower(&self) -> F { self.0 } 71 pub fn lower(&self) -> F {
72 self.0
73 }
62 74
63 /// Returns the upper bound 75 /// Returns the upper bound
64 #[inline] 76 #[inline]
65 pub fn upper(&self) -> F { self.1 } 77 pub fn upper(&self) -> F {
66 } 78 self.1
67 79 }
68 impl<F : Float> Bounds<F> { 80 }
81
82 impl<F: Float> Bounds<F> {
69 /// Returns a uniform bound. 83 /// Returns a uniform bound.
70 /// 84 ///
71 /// This is maximum over the absolute values of the upper and lower bound. 85 /// This is maximum over the absolute values of the upper and lower bound.
72 #[inline] 86 #[inline]
73 pub fn uniform(&self) -> F { 87 pub fn uniform(&self) -> F {
75 lower.abs().max(upper.abs()) 89 lower.abs().max(upper.abs())
76 } 90 }
77 91
78 /// Construct a bounds, making sure `lower` bound is less than `upper` 92 /// Construct a bounds, making sure `lower` bound is less than `upper`
79 #[inline] 93 #[inline]
80 pub fn corrected(lower : F, upper : F) -> Self { 94 pub fn corrected(lower: F, upper: F) -> Self {
81 if lower <= upper { 95 if lower <= upper {
82 Bounds(lower, upper) 96 Bounds(lower, upper)
83 } else { 97 } else {
84 Bounds(upper, lower) 98 Bounds(upper, lower)
85 } 99 }
86 } 100 }
87 101
88 /// Refine the lower bound 102 /// Refine the lower bound
89 #[inline] 103 #[inline]
90 pub fn refine_lower(&self, lower : F) -> Self { 104 pub fn refine_lower(&self, lower: F) -> Self {
91 let &Bounds(l, u) = self; 105 let &Bounds(l, u) = self;
92 debug_assert!(l <= u); 106 debug_assert!(l <= u);
93 Bounds(l.max(lower), u.max(lower)) 107 Bounds(l.max(lower), u.max(lower))
94 } 108 }
95 109
96 /// Refine the lower bound 110 /// Refine the lower bound
97 #[inline] 111 #[inline]
98 pub fn refine_upper(&self, upper : F) -> Self { 112 pub fn refine_upper(&self, upper: F) -> Self {
99 let &Bounds(l, u) = self; 113 let &Bounds(l, u) = self;
100 debug_assert!(l <= u); 114 debug_assert!(l <= u);
101 Bounds(l.min(upper), u.min(upper)) 115 Bounds(l.min(upper), u.min(upper))
102 } 116 }
103 } 117 }
104 118
105 impl<'a, F : Float> std::ops::Add<Self> for Bounds<F> { 119 impl<'a, F: Float> std::ops::Add<Self> for Bounds<F> {
106 type Output = Self; 120 type Output = Self;
107 #[inline] 121 #[inline]
108 fn add(self, Bounds(l2, u2) : Self) -> Self::Output { 122 fn add(self, Bounds(l2, u2): Self) -> Self::Output {
109 let Bounds(l1, u1) = self; 123 let Bounds(l1, u1) = self;
110 debug_assert!(l1 <= u1 && l2 <= u2); 124 debug_assert!(l1 <= u1 && l2 <= u2);
111 Bounds(l1 + l2, u1 + u2) 125 Bounds(l1 + l2, u1 + u2)
112 } 126 }
113 } 127 }
114 128
115 impl<'a, F : Float> std::ops::Mul<Self> for Bounds<F> { 129 impl<'a, F: Float> std::ops::Mul<Self> for Bounds<F> {
116 type Output = Self; 130 type Output = Self;
117 #[inline] 131 #[inline]
118 fn mul(self, Bounds(l2, u2) : Self) -> Self::Output { 132 fn mul(self, Bounds(l2, u2): Self) -> Self::Output {
119 let Bounds(l1, u1) = self; 133 let Bounds(l1, u1) = self;
120 debug_assert!(l1 <= u1 && l2 <= u2); 134 debug_assert!(l1 <= u1 && l2 <= u2);
121 let a = l1 * l2; 135 let a = l1 * l2;
122 let b = u1 * u2; 136 let b = u1 * u2;
123 // The order may flip when negative numbers are involved, so need min/max 137 // The order may flip when negative numbers are involved, so need min/max
124 Bounds(a.min(b), a.max(b)) 138 Bounds(a.min(b), a.max(b))
125 } 139 }
126 } 140 }
127 141
128 impl<F : Float> std::iter::Product for Bounds<F> { 142 impl<F: Float> std::iter::Product for Bounds<F> {
129 #[inline] 143 #[inline]
130 fn product<I>(mut iter: I) -> Self 144 fn product<I>(mut iter: I) -> Self
131 where I: Iterator<Item = Self> { 145 where
146 I: Iterator<Item = Self>,
147 {
132 match iter.next() { 148 match iter.next() {
133 None => Bounds(F::ZERO, F::ZERO), 149 None => Bounds(F::ZERO, F::ZERO),
134 Some(init) => iter.fold(init, |a, b| a*b) 150 Some(init) => iter.fold(init, |a, b| a * b),
135 } 151 }
136 } 152 }
137 } 153 }
138 154
139 impl<F : Float> Set<F> for Bounds<F> { 155 impl<F: Float> Set<F> for Bounds<F> {
140 fn contains<I : Instance<F>>(&self, item : I) -> bool { 156 fn contains<I: Instance<F>>(&self, item: I) -> bool {
141 let v = item.own(); 157 let v = item.own();
142 let &Bounds(l, u) = self; 158 let &Bounds(l, u) = self;
143 debug_assert!(l <= u); 159 debug_assert!(l <= u);
144 l <= v && v <= u 160 l <= v && v <= u
145 } 161 }
146 } 162 }
147 163
148 impl<F : Float> Bounds<F> { 164 impl<F: Float> Bounds<F> {
149 /// Calculate a common bound (glb, lub) for two bounds. 165 /// Calculate a common bound (glb, lub) for two bounds.
150 #[inline] 166 #[inline]
151 pub fn common(&self, &Bounds(l2, u2) : &Self) -> Self { 167 pub fn common(&self, &Bounds(l2, u2): &Self) -> Self {
152 let &Bounds(l1, u1) = self; 168 let &Bounds(l1, u1) = self;
153 debug_assert!(l1 <= u1 && l2 <= u2); 169 debug_assert!(l1 <= u1 && l2 <= u2);
154 Bounds(l1.min(l2), u1.max(u2)) 170 Bounds(l1.min(l2), u1.max(u2))
155 } 171 }
156 172
157 /// Indicates whether `Self` is a superset of the argument bound. 173 /// Indicates whether `Self` is a superset of the argument bound.
158 #[inline] 174 #[inline]
159 pub fn superset(&self, &Bounds(l2, u2) : &Self) -> bool { 175 pub fn superset(&self, &Bounds(l2, u2): &Self) -> bool {
160 let &Bounds(l1, u1) = self; 176 let &Bounds(l1, u1) = self;
161 debug_assert!(l1 <= u1 && l2 <= u2); 177 debug_assert!(l1 <= u1 && l2 <= u2);
162 l1 <= l2 && u2 <= u1 178 l1 <= l2 && u2 <= u1
163 } 179 }
164 180
165 /// Returns the greatest bound contained by both argument bounds, if one exists. 181 /// Returns the greatest bound contained by both argument bounds, if one exists.
166 #[inline] 182 #[inline]
167 pub fn glb(&self, &Bounds(l2, u2) : &Self) -> Option<Self> { 183 pub fn glb(&self, &Bounds(l2, u2): &Self) -> Option<Self> {
168 let &Bounds(l1, u1) = self; 184 let &Bounds(l1, u1) = self;
169 debug_assert!(l1 <= u1 && l2 <= u2); 185 debug_assert!(l1 <= u1 && l2 <= u2);
170 let l = l1.max(l2); 186 let l = l1.max(l2);
171 let u = u1.min(u2); 187 let u = u1.min(u2);
172 debug_assert!(l <= u); 188 debug_assert!(l <= u);
176 None 192 None
177 } 193 }
178 } 194 }
179 } 195 }
180 196
181 impl<F : Float> Aggregator for Bounds<F> { 197 impl<F: Float> Aggregator for Bounds<F> {
182 #[inline] 198 #[inline]
183 fn aggregate<I>(&mut self, aggregates : I) 199 fn aggregate<I>(&mut self, aggregates: I)
184 where I : Iterator<Item=Self> { 200 where
201 I: Iterator<Item = Self>,
202 {
185 *self = aggregates.fold(*self, |a, b| a + b); 203 *self = aggregates.fold(*self, |a, b| a + b);
186 } 204 }
187 205
188 #[inline] 206 #[inline]
189 fn summarise<'a, I>(&'a mut self, mut aggregates : I) 207 fn summarise<'a, I>(&'a mut self, mut aggregates: I)
190 where I : Iterator<Item=&'a Self> { 208 where
209 I: Iterator<Item = &'a Self>,
210 {
191 *self = match aggregates.next() { 211 *self = match aggregates.next() {
192 None => Bounds(F::ZERO, F::ZERO), // No parts in this cube; the function is zero 212 None => Bounds(F::ZERO, F::ZERO), // No parts in this cube; the function is zero
193 Some(&bounds) => { 213 Some(&bounds) => aggregates.fold(bounds, |a, b| a.common(b)),
194 aggregates.fold(bounds, |a, b| a.common(b))
195 }
196 } 214 }
197 } 215 }
198 216
199 #[inline] 217 #[inline]
200 fn new() -> Self { 218 fn new() -> Self {

Mercurial Repository: alg_tools

mercurial