Mercurial > repos > alg_tools / file comparison

comparison: src/bisection_tree/aggregator.rs

src/bisection_tree/aggregator.rs

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

Mercurial Repository: alg_tools

mercurial