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

}

/// One cell of a graph row's lower line, the line under the change.

#[derive(Clone, Copy, Debug, PartialEq, Eq)]

pub enum Cell {

    /// Nothing in this column.

    Blank,

    /// A lane carries on down.

    Line,

    /// The change's lane ends at a dependency not drawn (too far down, or

    /// not in the list): `~`.

    Elided,

    /// The left end of a join: this lane carries on, and the lane to its

    /// right turns into it (`├`).

    JoinLeft,

    /// A join passes a column with no lane (`─`).

    JoinPass,

    /// A join crosses a lane that carries on (`┼`).

    JoinCross,

    /// The right end of a join: this lane turns left and ends (`╯`).

    JoinRight,

}

/// A row of the drawn graph: the change's column, which other columns

/// carry a lane past it, and the line under it.

#[derive(Clone, Debug, PartialEq, Eq)]

pub struct GraphRow {

    pub column: usize,

    /// Columns with a lane on the change's own line, besides its own.

    pub passing: Vec<usize>,

    /// The line under the change, one cell per column.

    pub below: Vec<Cell>,

}

/// Lay out `changes` (newest first, as `(hash, deps)`) for a terminal

/// graph. A change's dependencies form a wide graph, since a change builds

/// on whatever last touched the lines it edits, so only one edge is drawn

/// per change: to its newest dependency, the change it most directly

/// builds on. An edge longer than `max_edge` rows, or to a change not in

/// the list, is elided (`~`), as are the other dependencies, so the

/// picture keeps to a few lanes. Two lanes heading for the same change

/// join into the left one.

pub fn graph(changes: &[(ChangeHash, Vec<ChangeHash>)], max_edge: usize) -> Vec<GraphRow> {

    let index: HashMap<&ChangeHash, usize> = changes

        .iter()

        .enumerate()

        .map(|(i, (h, _))| (h, i))

        .collect();

    let mut active: Vec<Option<ChangeHash>> = Vec::new();

    let mut rows = Vec::with_capacity(changes.len());

    for (i, (hash, deps)) in changes.iter().enumerate() {

        let column = match active.iter().position(|a| a.as_ref() == Some(hash)) {

            Some(c) => c,

            None => match active.iter().position(Option::is_none) {

                Some(c) => {

                    active[c] = Some(*hash);

                    c

                }

                None => {

                    active.push(Some(*hash));

                    active.len() - 1

                }

            },

        };

        let passing: Vec<usize> = active

            .iter()

            .enumerate()

            .filter(|(c, a)| *c != column && a.is_some())

            .map(|(c, _)| c)

            .collect();

        // The newest dependency below this row (the list is newest first).

        let nearest = deps

            .iter()

            .filter_map(|d| index.get(d).copied())

            .filter(|&j| j > i)

            .min();

        let parent = nearest.filter(|&j| j - i <= max_edge).map(|j| changes[j].0);

        active[column] = None;

        let mut join: Option<(usize, usize)> = None;

        if let Some(p) = parent {

            match active.iter().position(|a| a.as_ref() == Some(&p)) {

                // Another lane already heads there: join the two, leftwards.

                Some(other) => {

                    let (left, right) = (other.min(column), other.max(column));

                    active[right] = None;

                    active[left] = Some(p);

                    join = Some((left, right));

                }

                None => active[column] = Some(p),

            }

        }

        let width = active.len().max(column + 1);

        let mut below = vec![Cell::Blank; width];

        for (c, a) in active.iter().enumerate() {

            if a.is_some() {

                below[c] = Cell::Line;

            }

        }

        if let Some((left, right)) = join {

            below[left] = Cell::JoinLeft;

            for cell in below.iter_mut().take(right).skip(left + 1) {

                *cell = if *cell == Cell::Line {

                    Cell::JoinCross

                } else {

                    Cell::JoinPass

                };

            }

            below[right] = Cell::JoinRight;

        } else if parent.is_none() && !deps.is_empty() {

            below[column] = Cell::Elided;

        }

        while below.len() > 1 && below.last() == Some(&Cell::Blank) {

            below.pop();

        }

        rows.push(GraphRow {

            column,

            passing,

            below,

        });

        while active.last().is_some_and(Option::is_none) {

            active.pop();

        }

    }

    rows

}

#[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);

    }

    #[test]

    fn the_graph_draws_the_newest_dependency_and_joins_lanes_left() {

        // 4 and 3 both build on 2; 2 on 1; 3 also depends on 1 (not drawn).

        let rows = graph(

            &[

                (h(4), vec![h(2)]),

                (h(3), vec![h(1), h(2)]),

                (h(2), vec![h(1)]),

                (h(1), vec![]),

            ],

            12,

        );

        assert_eq!(rows[0].column, 0);

        assert_eq!(rows[0].below, vec![Cell::Line]);

        assert_eq!(rows[1].column, 1, "a second head takes a new lane");

        assert_eq!(rows[1].passing, vec![0]);

        assert_eq!(rows[1].below, vec![Cell::JoinLeft, Cell::JoinRight]);

        assert_eq!(rows[2].column, 0);

        assert_eq!(rows[3].below, vec![Cell::Blank], "a root ends its lane");

    }

    #[test]

    fn a_long_edge_is_elided() {

        let mut changes = vec![(h(100), vec![h(1)])];

        for n in (2..=20).rev() {

            changes.push((h(n), vec![]));

        }

        changes.push((h(1), vec![]));

        let rows = graph(&changes, 5);

        assert_eq!(rows[0].below, vec![Cell::Elided]);

        assert!(

            rows.iter().all(|r| r.below.len() == 1),

            "one lane all the way"

        );

        let rows = graph(&changes, 100);

        assert_eq!(rows[0].below, vec![Cell::Line], "drawn when short enough");

    }

}