comparison: src/bisection_tree/aggregator.rs
src/bisection_tree/aggregator.rs
- branch
- dev
- changeset 97
- 4e80fb049dca
- parent 96
- 962c8e346ab9
equal
deleted
inserted
replaced
| 96:962c8e346ab9 | 97:4e80fb049dca |
|---|---|
| 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; | 5 pub use crate::bounds::Bounds; |
| 6 use crate::sets::Set; | |
| 7 use crate::types::*; | 6 use crate::types::*; |
| 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. |
| 54 fn new() -> Self { | 53 fn new() -> Self { |
| 55 NullAggregator | 54 NullAggregator |
| 56 } | 55 } |
| 57 } | 56 } |
| 58 | 57 |
| 59 /// Upper and lower bounds on an `F`-valued function. | |
| 60 #[derive(Copy, Clone, Debug)] | |
| 61 pub struct Bounds<F>( | |
| 62 /// Lower bound | |
| 63 pub F, | |
| 64 /// Upper bound | |
| 65 pub F, | |
| 66 ); | |
| 67 | |
| 68 impl<F: Copy> Bounds<F> { | |
| 69 /// Returns the lower bound | |
| 70 #[inline] | |
| 71 pub fn lower(&self) -> F { | |
| 72 self.0 | |
| 73 } | |
| 74 | |
| 75 /// Returns the upper bound | |
| 76 #[inline] | |
| 77 pub fn upper(&self) -> F { | |
| 78 self.1 | |
| 79 } | |
| 80 } | |
| 81 | |
| 82 impl<F: Float> Bounds<F> { | |
| 83 /// Returns a uniform bound. | |
| 84 /// | |
| 85 /// This is maximum over the absolute values of the upper and lower bound. | |
| 86 #[inline] | |
| 87 pub fn uniform(&self) -> F { | |
| 88 let &Bounds(lower, upper) = self; | |
| 89 lower.abs().max(upper.abs()) | |
| 90 } | |
| 91 | |
| 92 /// Construct a bounds, making sure `lower` bound is less than `upper` | |
| 93 #[inline] | |
| 94 pub fn corrected(lower: F, upper: F) -> Self { | |
| 95 if lower <= upper { | |
| 96 Bounds(lower, upper) | |
| 97 } else { | |
| 98 Bounds(upper, lower) | |
| 99 } | |
| 100 } | |
| 101 | |
| 102 /// Refine the lower bound | |
| 103 #[inline] | |
| 104 pub fn refine_lower(&self, lower: F) -> Self { | |
| 105 let &Bounds(l, u) = self; | |
| 106 debug_assert!(l <= u); | |
| 107 Bounds(l.max(lower), u.max(lower)) | |
| 108 } | |
| 109 | |
| 110 /// Refine the lower bound | |
| 111 #[inline] | |
| 112 pub fn refine_upper(&self, upper: F) -> Self { | |
| 113 let &Bounds(l, u) = self; | |
| 114 debug_assert!(l <= u); | |
| 115 Bounds(l.min(upper), u.min(upper)) | |
| 116 } | |
| 117 } | |
| 118 | |
| 119 impl<'a, F: Float> std::ops::Add<Self> for Bounds<F> { | |
| 120 type Output = Self; | |
| 121 #[inline] | |
| 122 fn add(self, Bounds(l2, u2): Self) -> Self::Output { | |
| 123 let Bounds(l1, u1) = self; | |
| 124 debug_assert!(l1 <= u1 && l2 <= u2); | |
| 125 Bounds(l1 + l2, u1 + u2) | |
| 126 } | |
| 127 } | |
| 128 | |
| 129 impl<'a, F: Float> std::ops::Mul<Self> for Bounds<F> { | |
| 130 type Output = Self; | |
| 131 #[inline] | |
| 132 fn mul(self, Bounds(l2, u2): Self) -> Self::Output { | |
| 133 let Bounds(l1, u1) = self; | |
| 134 debug_assert!(l1 <= u1 && l2 <= u2); | |
| 135 let a = l1 * l2; | |
| 136 let b = u1 * u2; | |
| 137 // The order may flip when negative numbers are involved, so need min/max | |
| 138 Bounds(a.min(b), a.max(b)) | |
| 139 } | |
| 140 } | |
| 141 | |
| 142 impl<F: Float> std::iter::Product for Bounds<F> { | |
| 143 #[inline] | |
| 144 fn product<I>(mut iter: I) -> Self | |
| 145 where | |
| 146 I: Iterator<Item = Self>, | |
| 147 { | |
| 148 match iter.next() { | |
| 149 None => Bounds(F::ZERO, F::ZERO), | |
| 150 Some(init) => iter.fold(init, |a, b| a * b), | |
| 151 } | |
| 152 } | |
| 153 } | |
| 154 | |
| 155 impl<F: Float> Set<F> for Bounds<F> { | |
| 156 fn contains<I: Instance<F>>(&self, item: I) -> bool { | |
| 157 let v = item.own(); | |
| 158 let &Bounds(l, u) = self; | |
| 159 debug_assert!(l <= u); | |
| 160 l <= v && v <= u | |
| 161 } | |
| 162 } | |
| 163 | |
| 164 impl<F: Float> Bounds<F> { | |
| 165 /// Calculate a common bound (glb, lub) for two bounds. | |
| 166 #[inline] | |
| 167 pub fn common(&self, &Bounds(l2, u2): &Self) -> Self { | |
| 168 let &Bounds(l1, u1) = self; | |
| 169 debug_assert!(l1 <= u1 && l2 <= u2); | |
| 170 Bounds(l1.min(l2), u1.max(u2)) | |
| 171 } | |
| 172 | |
| 173 /// Indicates whether `Self` is a superset of the argument bound. | |
| 174 #[inline] | |
| 175 pub fn superset(&self, &Bounds(l2, u2): &Self) -> bool { | |
| 176 let &Bounds(l1, u1) = self; | |
| 177 debug_assert!(l1 <= u1 && l2 <= u2); | |
| 178 l1 <= l2 && u2 <= u1 | |
| 179 } | |
| 180 | |
| 181 /// Returns the greatest bound contained by both argument bounds, if one exists. | |
| 182 #[inline] | |
| 183 pub fn glb(&self, &Bounds(l2, u2): &Self) -> Option<Self> { | |
| 184 let &Bounds(l1, u1) = self; | |
| 185 debug_assert!(l1 <= u1 && l2 <= u2); | |
| 186 let l = l1.max(l2); | |
| 187 let u = u1.min(u2); | |
| 188 debug_assert!(l <= u); | |
| 189 if l < u { | |
| 190 Some(Bounds(l, u)) | |
| 191 } else { | |
| 192 None | |
| 193 } | |
| 194 } | |
| 195 } | |
| 196 | |
| 197 impl<F: Float> Aggregator for Bounds<F> { | 58 impl<F: Float> Aggregator for Bounds<F> { |
| 198 #[inline] | 59 #[inline] |
| 199 fn aggregate<I>(&mut self, aggregates: I) | 60 fn aggregate<I>(&mut self, aggregates: I) |
| 200 where | 61 where |
| 201 I: Iterator<Item = Self>, | 62 I: Iterator<Item = Self>, |
