//! A board's charts and forecasts from its own history (oxygenhub#357):
//! cumulative flow, cycle time, throughput and a Monte Carlo of when the
//! remaining cards will be done, with no estimates to keep. Everything here
//! is a pure function of the board's card moves (`project_card_moves`), so
//! the series and the forecast's percentiles are testable from a fixture
//! board and a fixed seed.

use std::collections::{BTreeMap, HashMap};

pub const DAY_MS: i64 = 86_400_000;
pub const WEEK_MS: i64 = 7 * DAY_MS;

/// A card's move: to a column, or off the board (`None`), at a time.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Move {
    pub card: i64,
    pub column: Option<i64>,
    pub at: i64,
}

/// Cards per column at the end of each day from `first_day` (midnight UTC,
/// ms) for `days` days: one row a day, one count per column of `columns`
/// (in board order). Moves must be oldest first.
pub fn cumulative_flow(moves: &[Move], columns: &[i64], first_day: i64, days: usize) -> Vec<Vec<usize>> {
    let mut at: HashMap<i64, Option<i64>> = HashMap::new();
    let mut i = 0;
    let mut out = Vec::with_capacity(days);
    for d in 0..days {
        let end = first_day + (d as i64 + 1) * DAY_MS;
        while i < moves.len() && moves[i].at < end {
            at.insert(moves[i].card, moves[i].column);
            i += 1;
        }
        let mut counts = vec![0; columns.len()];
        for col in at.values().flatten() {
            if let Some(k) = columns.iter().position(|c| c == col) {
                counts[k] += 1;
            }
        }
        out.push(counts);
    }
    out
}

/// Each finished card's cycle time in ms: from when it first left the
/// board's first column (work started) to when it first reached `done`
/// after that. A card added straight into a later column starts there.
pub fn cycle_times(moves: &[Move], first_column: i64, done: i64) -> Vec<i64> {
    let mut started: HashMap<i64, i64> = HashMap::new();
    let mut finished: BTreeMap<i64, i64> = BTreeMap::new();
    for m in moves {
        let Some(col) = m.column else { continue };
        if col != first_column && !started.contains_key(&m.card) {
            started.insert(m.card, m.at);
        }
        if col == done && !finished.contains_key(&m.card) {
            if let Some(s) = started.get(&m.card) {
                finished.insert(m.card, m.at - s);
            }
        }
    }
    finished.into_values().collect()
}

/// The `p`th percentile (0 to 100) of `values`, nearest rank; `None` for none.
pub fn percentile(values: &[i64], p: u32) -> Option<i64> {
    if values.is_empty() {
        return None;
    }
    let mut v = values.to_vec();
    v.sort_unstable();
    let rank = ((p as f64 / 100.0) * v.len() as f64).ceil().max(1.0) as usize;
    Some(v[rank.min(v.len()) - 1])
}

/// Cards that first reached `done` in each of the `weeks` whole weeks
/// before `now`, oldest first.
pub fn weekly_throughput(moves: &[Move], done: i64, now: i64, weeks: usize) -> Vec<usize> {
    let mut first: HashMap<i64, i64> = HashMap::new();
    for m in moves {
        if m.column == Some(done) {
            first.entry(m.card).or_insert(m.at);
        }
    }
    let start = now - weeks as i64 * WEEK_MS;
    let mut out = vec![0; weeks];
    for at in first.values() {
        if *at >= start && *at < now {
            out[((at - start) / WEEK_MS) as usize] += 1;
        }
    }
    out
}

/// A forecast: in how many weeks the remaining cards are done at 50% and
/// 85% confidence, from how many weeks of history, and `None` when the
/// history holds no finished card to go on.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Forecast {
    pub remaining: usize,
    pub weeks_of_history: usize,
    pub p50_weeks: Option<usize>,
    pub p85_weeks: Option<usize>,
}

/// A small, seeded generator (xorshift64*): the forecast is the same for
/// the same history and seed, so it is testable and does not flicker
/// between page loads.
struct Rng(u64);

impl Rng {
    fn next(&mut self) -> u64 {
        let mut x = self.0;
        x ^= x >> 12;
        x ^= x << 25;
        x ^= x >> 27;
        self.0 = x;
        x.wrapping_mul(0x2545_F491_4F6C_DD1D)
    }
    fn below(&mut self, n: usize) -> usize {
        (self.next() % n as u64) as usize
    }
}

/// Weeks a run of trials can take at most before it is counted as never.
const HORIZON_WEEKS: usize = 520;

/// A Monte Carlo of when `remaining` cards are done: each trial draws
/// weeks from `throughput` (cards finished in each past week) until the
/// remaining cards are used up, `trials` times, seeded with `seed`.
pub fn forecast(throughput: &[usize], remaining: usize, trials: usize, seed: u64) -> Forecast {
    let weeks_of_history = throughput.len();
    if remaining == 0 {
        return Forecast { remaining, weeks_of_history, p50_weeks: Some(0), p85_weeks: Some(0) };
    }
    if throughput.iter().all(|t| *t == 0) || trials == 0 {
        return Forecast { remaining, weeks_of_history, p50_weeks: None, p85_weeks: None };
    }
    let mut rng = Rng(seed | 1);
    let mut taken: Vec<i64> = Vec::with_capacity(trials);
    for _ in 0..trials {
        let (mut left, mut weeks) = (remaining as i64, 0usize);
        while left > 0 && weeks < HORIZON_WEEKS {
            left -= throughput[rng.below(throughput.len())] as i64;
            weeks += 1;
        }
        taken.push(weeks as i64);
    }
    let at = |p| percentile(&taken, p).map(|w| w as usize).filter(|w| *w < HORIZON_WEEKS);
    Forecast { remaining, weeks_of_history, p50_weeks: at(50), p85_weeks: at(85) }
}

/// The open iteration's burn-down and scope: at the end of each day so
/// far, cards on the board not in `done` (left) and those plus the ones
/// that reached `done` since the iteration began (scope).
pub fn burn_down(moves: &[Move], done: i64, start: i64, days: usize) -> Vec<(usize, usize)> {
    let mut at: HashMap<i64, Option<i64>> = HashMap::new();
    let mut done_since: std::collections::HashSet<i64> = Default::default();
    let mut i = 0;
    let mut out = Vec::with_capacity(days);
    for d in 0..days {
        let end = start + (d as i64 + 1) * DAY_MS;
        while i < moves.len() && moves[i].at < end {
            let m = moves[i];
            at.insert(m.card, m.column);
            if m.column == Some(done) && m.at >= start {
                done_since.insert(m.card);
            }
            i += 1;
        }
        let left = at.values().filter(|c| c.is_some() && **c != Some(done)).count();
        // Done stays done when it leaves the board (an iteration closing).
        out.push((left, left + done_since.len()));
    }
    out
}

/// Points for an SVG polyline of `values` in a `w` × `h` box scaled to
/// `max` (at least 1), one step per value.
pub fn polyline(values: &[usize], max: usize, w: i64, h: i64) -> String {
    let max = max.max(1) as f64;
    let n = values.len().max(2) - 1;
    values
        .iter()
        .enumerate()
        .map(|(i, v)| format!("{},{}", (i as i64 * w) / n as i64, h - ((*v as f64 / max) * h as f64).round() as i64))
        .collect::<Vec<_>>()
        .join(" ")
}

/// The bands of a cumulative flow chart as SVG polygon points, one per
/// column (bottom band last in board order, Done at the bottom): each band
/// spans from the sum of the columns after it to that sum plus its own.
pub fn flow_bands(rows: &[Vec<usize>], w: i64, h: i64) -> Vec<String> {
    let cols = rows.first().map(|r| r.len()).unwrap_or(0);
    let max = rows.iter().map(|r| r.iter().sum::<usize>()).max().unwrap_or(0).max(1) as f64;
    let n = rows.len().max(2) - 1;
    let x = |i: usize| (i as i64 * w) / n as i64;
    let y = |v: usize| h - ((v as f64 / max) * h as f64).round() as i64;
    (0..cols)
        .map(|k| {
            let below = |r: &Vec<usize>| r[k + 1..].iter().sum::<usize>();
            let top: Vec<String> = rows.iter().enumerate().map(|(i, r)| format!("{},{}", x(i), y(below(r) + r[k]))).collect();
            let bottom: Vec<String> = rows.iter().enumerate().rev().map(|(i, r)| format!("{},{}", x(i), y(below(r)))).collect();
            [top, bottom].concat().join(" ")
        })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    const T0: i64 = 1_000 * DAY_MS;

    fn m(card: i64, column: Option<i64>, day: i64) -> Move {
        Move { card, column, at: T0 + day * DAY_MS + 3_600_000 }
    }

    /// Backlog 1, Doing 2, Done 3: card 1 goes the whole way in four days,
    /// card 2 reaches Doing on day 2 and stays, card 3 is added straight
    /// into Doing on day 3 and done on day 5, card 4 is archived on day 4.
    fn board() -> Vec<Move> {
        vec![
            m(1, Some(1), 0),
            m(2, Some(1), 0),
            m(4, Some(1), 0),
            m(1, Some(2), 1),
            m(2, Some(2), 2),
            m(3, Some(2), 3),
            m(4, None, 4),
            m(1, Some(3), 5),
            m(3, Some(3), 5),
        ]
    }

    #[test]
    fn cumulative_flow_replays_the_moves() {
        let rows = cumulative_flow(&board(), &[1, 2, 3], T0, 6);
        assert_eq!(rows, vec![vec![3, 0, 0], vec![2, 1, 0], vec![1, 2, 0], vec![1, 3, 0], vec![0, 3, 0], vec![0, 1, 2]]);
        let bands = flow_bands(&rows, 100, 30);
        assert_eq!(bands.len(), 3);
        assert!(bands[2].starts_with("0,30"), "Done is the bottom band: {}", bands[2]);
    }

    #[test]
    fn cycle_time_and_throughput() {
        let mut times = cycle_times(&board(), 1, 3);
        times.sort();
        assert_eq!(times, vec![2 * DAY_MS, 4 * DAY_MS], "card 3: day 3 to 5; card 1: day 1 to 5");
        assert_eq!(percentile(&times, 50), Some(2 * DAY_MS));
        assert_eq!(percentile(&times, 85), Some(4 * DAY_MS));
        assert_eq!(percentile(&[], 50), None);
        let now = T0 + 7 * DAY_MS;
        assert_eq!(weekly_throughput(&board(), 3, now, 2), vec![0, 2]);
    }

    #[test]
    fn the_forecast_is_seeded_and_honest() {
        // Two cards a week, every week: ten cards take five weeks, always.
        let f = forecast(&[2, 2, 2, 2], 10, 1000, 7);
        assert_eq!((f.p50_weeks, f.p85_weeks, f.weeks_of_history), (Some(5), Some(5), 4));
        // Uneven weeks: the 85% date is no earlier than the 50% one, and the
        // same seed gives the same answer.
        let a = forecast(&[0, 1, 4, 2, 3], 12, 2000, 42);
        assert_eq!(a, forecast(&[0, 1, 4, 2, 3], 12, 2000, 42));
        let (p50, p85) = (a.p50_weeks.unwrap(), a.p85_weeks.unwrap());
        assert!((4..=7).contains(&p50) && p85 >= p50, "{a:?}");
        // Nothing finished yet: no forecast, said plainly.
        assert_eq!(forecast(&[0, 0], 5, 100, 1).p50_weeks, None);
        assert_eq!(forecast(&[], 5, 100, 1).p50_weeks, None);
        assert_eq!(forecast(&[1], 0, 100, 1).p85_weeks, Some(0));
    }

    #[test]
    fn burn_down_counts_left_and_scope() {
        let bd = burn_down(&board(), 3, T0, 6);
        assert_eq!(bd[0], (3, 3));
        assert_eq!(bd[3], (4, 4), "card 3 added on day 3 grows the scope");
        assert_eq!(bd[4], (3, 3), "card 4 archived on day 4 leaves it");
        assert_eq!(bd[5], (1, 3), "two done");
        assert_eq!(polyline(&[0, 2, 4], 4, 10, 10), "0,10 5,5 10,0");
    }
}