//! Lane layout for drawing history as a graph: each change takes a lane,
//! its first dependency continues that lane, other dependencies take free
//! lanes, so edges flow from a change down to what it depends on. Shared
//! by `oxy log` and hosts, so every view draws the same picture.

use crate::hash::ChangeHash;
use std::collections::{HashMap, HashSet};

/// A row of the graph: the change's lane and the edges drawn from it.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Row {
    pub lane: usize,
    /// `(from_lane, to_lane)` for each dependency drawn from this row to
    /// the rows below.
    pub edges: Vec<(usize, usize)>,
    /// Lanes that pass through this row without touching it.
    pub through: Vec<usize>,
}

/// `changes` newest first as `(hash, deps)`. A dependency outside the
/// list ends its lane at the bottom.
pub fn layout(changes: &[(ChangeHash, Vec<ChangeHash>)]) -> Vec<Row> {
    let mut active: Vec<Option<ChangeHash>> = Vec::new();
    let mut rows = Vec::with_capacity(changes.len());
    let known: HashSet<&ChangeHash> = changes.iter().map(|(h, _)| h).collect();
    let mut lanes: HashMap<ChangeHash, usize> = HashMap::new();
    for (hash, deps) in changes {
        let lane = match active.iter().position(|a| a.as_ref() == Some(hash)) {
            Some(l) => l,
            None => match active.iter().position(|a| a.is_none()) {
                Some(l) => {
                    active[l] = Some(*hash);
                    l
                }
                None => {
                    active.push(Some(*hash));
                    active.len() - 1
                }
            },
        };
        lanes.insert(*hash, lane);
        let mut edges = Vec::new();
        let deps: Vec<&ChangeHash> = deps.iter().filter(|d| known.contains(d)).collect();
        active[lane] = None;
        for (i, d) in deps.iter().enumerate() {
            let target = match active.iter().position(|a| a.as_ref() == Some(*d)) {
                Some(l) => l,
                None => {
                    let l = if i == 0 && active[lane].is_none() {
                        lane
                    } else {
                        match active.iter().position(|a| a.is_none()) {
                            Some(l) => l,
                            None => {
                                active.push(None);
                                active.len() - 1
                            }
                        }
                    };
                    active[l] = Some(**d);
                    l
                }
            };
            edges.push((lane, target));
        }
        let through: Vec<usize> = active
            .iter()
            .enumerate()
            .filter(|(l, a)| a.is_some() && *l != lane && !edges.iter().any(|e| e.1 == *l))
            .map(|(l, _)| l)
            .collect();
        rows.push(Row {
            lane,
            edges,
            through,
        });
        while active.last().is_some_and(|a| a.is_none()) {
            active.pop();
        }
    }
    rows
}

/// The number of lanes the rows use.
pub fn width(rows: &[Row]) -> usize {
    rows.iter()
        .map(|r| {
            r.lane
                .max(r.edges.iter().map(|e| e.1).max().unwrap_or(0))
                .max(r.through.iter().copied().max().unwrap_or(0))
        })
        .max()
        .map(|m| m + 1)
        .unwrap_or(1)
}

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

    fn h(n: u8) -> ChangeHash {
        ObjectRef([n; 32])
    }

    #[test]
    fn linear_history_is_one_lane() {
        let rows = layout(&[(h(3), vec![h(2)]), (h(2), vec![h(1)]), (h(1), vec![])]);
        assert!(rows.iter().all(|r| r.lane == 0), "{rows:?}");
        assert_eq!(rows[0].edges, vec![(0, 0)]);
        assert_eq!(width(&rows), 1);
    }

    #[test]
    fn a_diamond_takes_two_lanes_and_rejoins() {
        let rows = layout(&[
            (h(4), vec![h(2), h(3)]),
            (h(2), vec![h(1)]),
            (h(3), vec![h(1)]),
            (h(1), vec![]),
        ]);
        assert_eq!(rows[0].edges, vec![(0, 0), (0, 1)]);
        assert_eq!(rows[2].lane, 1);
        assert_eq!(
            rows[2].edges,
            vec![(1, 0)],
            "the second branch joins the first lane"
        );
        assert_eq!(width(&rows), 2);
    }
}