use std::collections::{HashMap, VecDeque};
use ordered_float::OrderedFloat;
use estimates::{some_or_error};
fn change(a: f64, b: f64, relative: bool) -> f64 {
match relative {
true => (a - b).abs() / b,
false => (a - b).abs(),
}
}
pub struct ForwardChecker {
estimates: VecDeque<f64>,
first_n: usize,
delta_converged: HashMap<OrderedFloat<f64>, Option<usize>>,
next_deltas: Vec<f64>,
q: usize,
relative: bool,
}
impl ForwardChecker {
pub fn new(deltas: &Vec<f64>, q: usize, relative: bool) -> ForwardChecker {
assert!(deltas.len() > 0);
let mut deltas = deltas.clone();
deltas.sort_by(|a, b| a.partial_cmp(b).unwrap());
assert!(*deltas.get(0).unwrap() > 0.);
ForwardChecker {
estimates: VecDeque::new(),
first_n: 0,
delta_converged: deltas.iter()
.map(|d| (OrderedFloat::from(*d), None))
.collect(),
next_deltas: deltas,
q: q,
relative: relative,
}
}
pub fn get_converged(&self) -> HashMap<OrderedFloat<f64>, Option<usize>> {
self.delta_converged.clone()
}
pub fn get_not_converged(&self) -> HashMap<OrderedFloat<f64>, Option<usize>> {
let mut converged = HashMap::new();
let last_e = match self.estimates.back() {
Some(est) => est,
None => return converged,
};
let mut next_deltas = self.next_deltas.clone();
let mut delta = match next_deltas.pop() {
Some(delta) => delta,
None => return converged,
};
'outer: for (i, est) in self.estimates.iter().enumerate() {
while change(*est, *last_e, self.relative) < delta {
converged.insert(OrderedFloat::from(delta), Some(self.first_n + i));
delta = match next_deltas.pop() {
Some(delta) => delta,
None => break 'outer,
};
}
}
converged
}
pub fn all_converged(&self) -> bool {
self.next_deltas.len() == 0
}
pub fn add_estimate(&mut self, e: f64) {
if self.next_deltas.len() == 0 {
return;
}
self.estimates.push_back(e);
while self.update_convergence() {};
}
pub fn get_last_change(&self) -> Result<f64, ()> {
let first_e = some_or_error(self.estimates.front())?;
let last_e = some_or_error(self.estimates.back())?;
Ok(change(*first_e, *last_e, self.relative))
}
fn update_convergence(&mut self) -> bool {
let delta = match self.next_deltas.last() {
Some(delta) => *delta,
None => return false,
};
let last_e = match self.estimates.back() {
Some(est) => *est,
None => return false,
};
while change(*self.estimates.front().unwrap(), last_e, self.relative) >= delta {
let _ = self.estimates.pop_front();
self.first_n += 1;
}
if self.estimates.len() >= self.q {
let c = self.delta_converged.get_mut(&OrderedFloat::from(delta)).unwrap();
*c = Some(self.first_n);
self.next_deltas.pop();
if self.next_deltas.len() == 0 {
self.estimates.clear();
}
return true;
}
false
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn forward_checker_init() {
let checker = ForwardChecker::new(&vec![0.1, 0.02, 0.4, 0.001], 1000,
false);
assert_eq!(checker.next_deltas, vec![0.001, 0.02, 0.1, 0.4]);
}
#[test]
fn forward_checker_convergence() {
let deltas = vec![0.11, 0.06, 0.02, 0.02, 0.019, 0.002, 0.0001];
let mut checker = ForwardChecker::new(&deltas, 4, false);
let estimates = vec![0.9, 0.9, 0.8, 0.7, 0.7, 0.7, 0.65, 0.64, 0.63,
0.63, 0.62, 0.62, 0.6, 0.6, 0.6, 0.599];
let expected_conv: Vec<Option<usize>> = vec![Some(2), Some(3), Some(8),
Some(8), Some(8),
Some(12), None];
for e in estimates {
checker.add_estimate(e);
}
let converged = checker.get_converged();
for (delta, n) in deltas.iter().zip(expected_conv) {
assert_eq!(converged.get(&OrderedFloat::from(*delta)).unwrap(), &n);
}
}
#[test]
fn absolute_convergence() {
let deltas = vec![0.15, 0.1, 0.02, 0.02, 0.019, 0.002, 0.0017];
let estimates = vec![0.9, 0.9, 0.8, 0.7, 0.7, 0.7, 0.65, 0.64, 0.63,
0.63, 0.62, 0.62, 0.6, 0.6, 0.6, 0.599];
let mut fwchecker = ForwardChecker::new(&deltas, 4, false);
let expected_conv: Vec<Option<usize>> = vec![Some(2), Some(3), Some(8),
Some(8), Some(8),
Some(12), Some(12)];
for e in estimates {
fwchecker.add_estimate(e);
}
assert!(fwchecker.all_converged());
let fwconverged = fwchecker.get_converged();
for (delta, n) in deltas.iter().zip(expected_conv) {
assert_eq!(fwconverged.get(&OrderedFloat::from(*delta)).unwrap(), &n);
}
}
}