//! 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");

    }

}