use crate::coordinate::{CellRef, Col, Range, Row};
use crate::error::{Error, Result};
use crate::formula::eval::{Engine, recalculate_from_with};
use crate::formula::{Origin, Value};
use crate::model::scenario::{Scenario, ScenarioInput};
use crate::model::{CellValue, Spreadsheet};
use crate::progress::Options;
const DEFAULT_ITERATIONS: u32 = 100;
const DEFAULT_TOLERANCE: f64 = 0.001;
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Sought {
pub value: f64,
pub result: f64,
pub iterations: u32,
pub converged: bool,
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct SeekLimits {
pub max_iterations: u32,
pub tolerance: f64,
}
impl Default for SeekLimits {
fn default() -> Self {
Self {
max_iterations: DEFAULT_ITERATIONS,
tolerance: DEFAULT_TOLERANCE,
}
}
}
impl SeekLimits {
#[must_use]
pub fn of(book: &Spreadsheet) -> Self {
let read = |key: &str| {
book.calculation_properties
.iter()
.find(|(k, _)| k == key)
.map(|(_, v)| v.as_str())
};
Self {
max_iterations: read("iterateCount")
.and_then(|v| v.parse().ok())
.filter(|&n| n > 0)
.unwrap_or(DEFAULT_ITERATIONS),
tolerance: read("iterateDelta")
.and_then(|v| v.parse().ok())
.filter(|&t: &f64| t.is_finite() && t > 0.0)
.unwrap_or(DEFAULT_TOLERANCE),
}
}
}
pub fn goal_seek(
book: &mut Spreadsheet,
set: (usize, CellRef),
target: f64,
changing: (usize, CellRef),
) -> Result<Sought> {
let limits = SeekLimits::of(book);
goal_seek_with(book, set, target, changing, limits, &Options::default())
}
pub fn goal_seek_with(
book: &mut Spreadsheet,
set: (usize, CellRef),
target: f64,
changing: (usize, CellRef),
limits: SeekLimits,
options: &Options<'_>,
) -> Result<Sought> {
if !target.is_finite() {
return Err(Error::GoalSeek("the target must be a finite number".into()));
}
let value_at = |book: &Spreadsheet, (sheet, at): (usize, CellRef)| {
book.sheet(sheet)
.map(|ws| ws.get(at).map(|c| c.value.clone()).unwrap_or_default())
.ok_or(Error::SheetIndexOutOfRange(sheet))
};
let CellValue::Formula { formula, .. } = value_at(book, set)? else {
return Err(Error::GoalSeek(format!("{} must contain a formula", set.1)));
};
let start = match value_at(book, changing)? {
CellValue::Formula { .. } => {
return Err(Error::GoalSeek(format!(
"{} must contain a value, not a formula",
changing.1
)));
}
other => other.as_number().unwrap_or(0.0),
};
let formula = crate::formula::parse(&formula)
.map_err(|e| Error::InvalidFormula(format!("{}: {e}", set.1)))?;
let mut trial = |x: f64| -> f64 {
if let Some(ws) = book.sheet_mut(changing.0) {
ws.set(changing.1, x);
}
let mut engine = match options.functions() {
Some(custom) => Engine::with_functions(book, custom),
None => Engine::new(book),
};
match engine
.eval_tree(Origin::new(set.0, set.1), &formula)
.scalar()
{
Value::Number(n) => n - target,
_ => f64::NAN,
}
};
let found = seek(start, &mut trial, limits.max_iterations, limits.tolerance);
if let Some(ws) = book.sheet_mut(changing.0) {
ws.set(changing.1, found.x);
}
recalculate_from_with(book, &[changing], options);
Ok(Sought {
value: found.x,
result: found.fx + target,
iterations: found.iterations,
converged: found.converged,
})
}
#[derive(Debug, Clone, Copy, PartialEq)]
struct Seek {
x: f64,
fx: f64,
iterations: u32,
converged: bool,
}
fn seek(x0: f64, f: &mut dyn FnMut(f64) -> f64, max_iter: u32, tol: f64) -> Seek {
let tol = if tol.is_finite() && tol > 0.0 {
tol
} else {
DEFAULT_TOLERANCE
};
let max_iter = max_iter.clamp(1, 32_767);
let x0 = if x0.is_finite() { x0 } else { 0.0 };
let f0 = f(x0);
let mut best = (x0, f0);
let consider = |best: &mut (f64, f64), x: f64, fx: f64| {
if fx.is_finite() && (!best.1.is_finite() || fx.abs() < best.1.abs()) {
*best = (x, fx);
}
};
let done = |best: (f64, f64), iterations: u32| Seek {
x: best.0,
fx: best.1,
iterations,
converged: best.1.is_finite() && best.1.abs() <= tol,
};
if f0.is_finite() && f0.abs() <= tol {
return done(best, 1);
}
let step0 = if x0 == 0.0 { 0.01 } else { x0.abs() * 0.01 };
let (mut xa, mut fa) = (x0, f0);
let mut xb = x0 + step0;
let mut fb = f(xb);
let mut it = 2u32;
consider(&mut best, xb, fb);
let mut bracket: Option<(f64, f64, f64, f64)> = None;
let mut slow = 0u32;
while it < max_iter {
if fb.is_finite() && fb.abs() <= tol {
break;
}
if bracket.is_none() && fa.is_finite() && fb.is_finite() && (fa < 0.0) != (fb < 0.0) {
bracket = Some((xa, fa, xb, fb));
}
#[allow(clippy::float_cmp, reason = "a flat secant is exactly equal ends")]
let secant = if fa.is_finite() && fb.is_finite() && fb != fa {
xb - fb * (xb - xa) / (fb - fa)
} else {
f64::NAN
};
let next = if let Some((lo, _, hi, _)) = bracket {
let (a, b) = (lo.min(hi), lo.max(hi));
if slow >= 2 || !(secant > a && secant < b) {
f64::midpoint(lo, hi)
} else {
secant
}
} else {
let span = (xb - xa).abs().max(f64::MIN_POSITIVE);
if !fb.is_finite() {
f64::midpoint(xa, xb)
} else if !secant.is_finite() {
2.0f64.mul_add(xb - xa, xb)
} else if (secant - xb).abs() > 100.0f64.mul_add(span, 1.0) {
(secant - xb)
.signum()
.mul_add(100.0f64.mul_add(span, 1.0), xb)
} else {
secant
}
};
if !next.is_finite() {
break;
}
let fnext = f(next);
it += 1;
consider(&mut best, next, fnext);
if let Some((lo, flo, hi, fhi)) = bracket {
let width = (hi - lo).abs();
let narrowed = if fnext.is_finite() {
if (fnext < 0.0) == (flo < 0.0) {
(next, fnext, hi, fhi)
} else {
(lo, flo, next, fnext)
}
} else if flo.abs() < fhi.abs() {
(lo, flo, next, fhi)
} else {
(next, flo, hi, fhi)
};
bracket = Some(narrowed);
let (l, _, h, _) = narrowed;
let new_width = (h - l).abs();
slow = if new_width > width * 0.5 { slow + 1 } else { 0 };
if new_width <= f64::EPSILON * (1.0 + l.abs().max(h.abs())) {
break;
}
}
xa = xb;
fa = fb;
xb = next;
fb = fnext;
}
done(best, it)
}
fn scenario_text(value: &CellValue) -> String {
match value.result() {
CellValue::Number(n) => n.to_string(),
CellValue::Bool(b) => if *b { "TRUE" } else { "FALSE" }.to_owned(),
other => other.display(
crate::style::format::GENERAL,
crate::shared::date::Epoch::default(),
),
}
}
fn sheet_of(book: &Spreadsheet, sheet: usize) -> Result<&crate::model::Worksheet> {
book.sheet(sheet).ok_or(Error::SheetIndexOutOfRange(sheet))
}
pub fn add_scenario(
book: &mut Spreadsheet,
sheet: usize,
name: &str,
inputs: &[CellRef],
) -> Result<usize> {
let ws = sheet_of(book, sheet)?;
if inputs.is_empty() || inputs.len() > 32 {
return Err(Error::GoalSeek("a scenario changes 1 to 32 cells".into()));
}
let mut cells = Vec::new();
for &cell in inputs {
let value = ws.get(cell).map(|c| c.value.clone()).unwrap_or_default();
if matches!(value, CellValue::Formula { .. }) {
return Err(Error::GoalSeek(format!(
"{cell} holds a formula; a scenario changes values"
)));
}
cells.push(ScenarioInput {
cell,
value: scenario_text(&value),
..ScenarioInput::default()
});
}
let scenario = Scenario {
name: name.to_owned(),
inputs: cells,
..Scenario::default()
};
let list = &mut book
.sheet_mut(sheet)
.ok_or(Error::SheetIndexOutOfRange(sheet))?
.scenarios
.list;
if let Some(at) = list.iter().position(|s| s.name.eq_ignore_ascii_case(name)) {
list[at] = scenario;
Ok(at)
} else {
list.push(scenario);
Ok(list.len() - 1)
}
}
pub fn show_scenario(book: &mut Spreadsheet, sheet: usize, name: &str) -> Result<usize> {
let ws = sheet_of(book, sheet)?;
let (index, scenario) = ws
.scenarios
.list
.iter()
.enumerate()
.find(|(_, s)| s.name.eq_ignore_ascii_case(name))
.ok_or_else(|| Error::GoalSeek(format!("the sheet has no scenario {name:?}")))?;
let inputs: Vec<(CellRef, String)> = scenario
.inputs
.iter()
.filter(|i| !i.deleted)
.map(|i| (i.cell, i.value.clone()))
.collect();
let ws = book
.sheet_mut(sheet)
.ok_or(Error::SheetIndexOutOfRange(sheet))?;
for (cell, value) in &inputs {
ws.set(*cell, crate::reader::csv::value_of(value));
}
ws.scenarios.current = u32::try_from(index).ok();
let changed: Vec<(usize, CellRef)> = inputs.iter().map(|(c, _)| (sheet, *c)).collect();
recalculate_from_with(book, &changed, &Options::default());
Ok(inputs.len())
}
pub fn scenario_summary(
book: &mut Spreadsheet,
sheet: usize,
results: &[CellRef],
) -> Result<usize> {
let ws = sheet_of(book, sheet)?;
if ws.scenarios.list.is_empty() {
return Err(Error::GoalSeek(
"the sheet has no scenario to summarise".into(),
));
}
let scenarios = ws.scenarios.list.clone();
let mut changing: Vec<CellRef> = Vec::new();
for input in scenarios.iter().flat_map(|s| &s.inputs) {
if !changing.contains(&input.cell) {
changing.push(input.cell);
}
}
let read = |book: &Spreadsheet, cell: CellRef| {
book.sheet(sheet)
.and_then(|ws| ws.get(cell))
.map(|c| c.value.result().clone())
.unwrap_or_default()
};
let mut columns: Vec<(String, Vec<CellValue>)> = Vec::new();
let current: Vec<CellValue> = changing
.iter()
.chain(results)
.map(|&c| read(book, c))
.collect();
columns.push(("Current Values:".into(), current));
for scenario in &scenarios {
let mut copy = book.clone();
show_scenario(&mut copy, sheet, &scenario.name)?;
let values = changing
.iter()
.chain(results)
.map(|&c| read(©, c))
.collect();
columns.push((scenario.name.clone(), values));
}
let title = {
let taken = |t: &str| {
book.sheets()
.iter()
.any(|s| s.title().eq_ignore_ascii_case(t))
};
let mut title = "Scenario Summary".to_owned();
let mut n = 2;
while taken(&title) {
title = format!("Scenario Summary {n}");
n += 1;
}
title
};
let mut report = crate::model::Worksheet::new(title)?;
let mut put = |row: u32, col: u32, value: CellValue| {
if let (Some(r), Some(c)) = (Row::new(row - 1), Col::new(col - 1)) {
report.set(CellRef::new(c, r), value);
}
};
put(1, 1, CellValue::text("Scenario Summary"));
for (i, (name, _)) in (3u32..).zip(&columns) {
put(2, i, CellValue::text(name.as_str()));
}
put(3, 1, CellValue::text("Changing Cells:"));
let mut row = 4;
let mut lines: Vec<(u32, CellRef)> = Vec::new();
for &cell in &changing {
lines.push((row, cell));
row += 1;
}
if !results.is_empty() {
put(row, 1, CellValue::text("Result Cells:"));
row += 1;
for &cell in results {
lines.push((row, cell));
row += 1;
}
}
for (i, &(r, cell)) in lines.iter().enumerate() {
put(r, 2, CellValue::text(cell.to_string().as_str()));
for (c, (_, values)) in (3u32..).zip(&columns) {
put(r, c, values[i].clone());
}
}
put(
row + 1,
1,
CellValue::text("Notes: Current Values column represents values of changing cells at"),
);
put(
row + 2,
1,
CellValue::text("time Scenario Summary Report was created."),
);
book.add_sheet(report)
}
pub fn data_table(
book: &mut Spreadsheet,
sheet: usize,
area: Range,
row_input: Option<CellRef>,
column_input: Option<CellRef>,
) -> Result<usize> {
sheet_of(book, sheet)?;
if row_input.is_none() && column_input.is_none() {
return Err(Error::GoalSeek(
"a data table needs a row or a column input cell".into(),
));
}
if area.width() < 2 || area.height() < 2 {
return Err(Error::GoalSeek(format!(
"{area} is too small for a data table"
)));
}
if [row_input, column_input]
.into_iter()
.flatten()
.any(|c| area.contains(c))
{
return Err(Error::GoalSeek(
"an input cell may not lie inside the table".into(),
));
}
let at = |dr: u32, dc: u32| {
CellRef::new(
Col::new(area.start.col.index() + dc).unwrap_or(area.start.col),
Row::new(area.start.row.index() + dr).unwrap_or(area.start.row),
)
};
let value = |book: &Spreadsheet, cell: CellRef| {
book.sheet(sheet)
.and_then(|ws| ws.get(cell))
.map(|c| c.value.result().clone())
.unwrap_or_default()
};
let formula_at = |book: &Spreadsheet, cell: CellRef| -> Result<crate::formula::Expr> {
match book
.sheet(sheet)
.and_then(|ws| ws.get(cell))
.map(|c| &c.value)
{
Some(CellValue::Formula { formula, .. }) => crate::formula::parse(formula)
.map_err(|e| Error::InvalidFormula(format!("{cell}: {e}"))),
_ => Err(Error::GoalSeek(format!(
"{cell} must hold the formula the table computes"
))),
}
};
let (rows, cols) = (area.height(), area.width());
let mut jobs: Vec<(CellRef, CellRef, Option<CellValue>, Option<CellValue>)> = Vec::new();
for r in 1..rows {
for c in 1..cols {
let formula_cell = match (row_input, column_input) {
(Some(_), Some(_)) => at(0, 0),
(None, Some(_)) => at(0, c),
_ => at(r, 0),
};
let row_value = row_input.map(|_| value(book, at(0, c)));
let col_value = column_input.map(|_| value(book, at(r, 0)));
jobs.push((at(r, c), formula_cell, row_value, col_value));
}
}
let mut work = book.clone();
let mut out = Vec::with_capacity(jobs.len());
for (body, formula_cell, row_value, col_value) in jobs {
let expr = formula_at(book, formula_cell)?;
if let Some(ws) = work.sheet_mut(sheet) {
if let (Some(cell), Some(v)) = (row_input, row_value) {
ws.set(cell, v);
}
if let (Some(cell), Some(v)) = (column_input, col_value) {
ws.set(cell, v);
}
}
let result = Engine::new(&work).eval_tree(Origin::new(sheet, formula_cell), &expr);
out.push((body, crate::formula::eval::stored(result.scalar())));
}
let count = out.len();
let ws = book
.sheet_mut(sheet)
.ok_or(Error::SheetIndexOutOfRange(sheet))?;
for (cell, value) in out {
ws.set(cell, value);
}
Ok(count)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn finds_a_square_root() {
let r = seek(1.0, &mut |x| x * x - 2.0, 100, 1e-9);
assert!(r.converged);
assert!((r.x - 2f64.sqrt()).abs() < 1e-6);
}
#[test]
fn steps_out_of_an_error() {
let r = seek(
5.0,
&mut |x| if x > 0.0 { x.ln() - 1.0 } else { f64::NAN },
100,
1e-9,
);
assert!(r.converged);
assert!((r.x - std::f64::consts::E).abs() < 1e-6);
}
#[test]
fn reports_the_best_point_when_there_is_no_root() {
let r = seek(3.0, &mut |x| x * x + 1.0, 50, 1e-9);
assert!(!r.converged);
assert!(r.fx >= 1.0);
}
}