monolith

use crate::geom::{Change, Rect};

use crate::strategy::plan_group;

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

pub enum Style {

    /// Every window moves or resizes along one axis per phase.

    Orthogonal,

    /// Windows may change both axes in one phase when no pair loses its separation.

    Direct,

}

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

pub struct Config {

    pub style: Style,

    /// Gap between tiled windows. Neighbours closer than this are adjacent.

    pub gap: f64,

    /// Tolerance for separation and adjacency tests.

    pub eps: f64,

    /// Lanes thinner than this are not used.

    pub min_lane: f64,

}

impl Default for Config {

    fn default() -> Self {

        Self {

            style: Style::Orthogonal,

            gap: 10.0,

            eps: 0.5,

            min_lane: 6.0,

        }

    }

}

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

pub enum Strategy {

    Unchanged,

    Direct,

    AxisOrder,

    Lanes { lanes: usize },

    Grid { cells: usize },

    Pinch,

}

/// Windows that plan together. Groups never touch each other while moving.

#[derive(Clone, Debug, PartialEq)]

pub struct Group {

    pub members: Vec<usize>,

    pub strategy: Strategy,

    pub phases: usize,

    /// Whether the plan briefly separates two neighbours that touch at both ends.

    pub opens_hole: bool,

}

/// Keyframe layouts indexed like the input. Every phase lasts the same time

/// and every window in a group moves on that group's curve.

#[derive(Clone, Debug, PartialEq)]

pub struct Plan {

    pub keyframes: Vec<Vec<Rect>>,

    pub groups: Vec<Group>,

}

impl Plan {

    pub fn phases(&self) -> usize {

        self.keyframes.len().saturating_sub(1)

    }

    /// Window positions at `phase` with eased progress `s`.

    pub fn sample(&self, phase: usize, s: f64) -> Vec<Rect> {

        match (self.keyframes.get(phase), self.keyframes.get(phase + 1)) {

            (Some(a), Some(b)) => a.iter().zip(b).map(|(a, b)| a.lerp(b, s)).collect(),

            _ => self.keyframes.last().cloned().unwrap_or_default(),

        }

    }

}

pub(crate) struct GroupPlan {

    pub keys: Vec<Vec<Rect>>,

    pub strategy: Strategy,

    pub opens_hole: bool,

}

impl GroupPlan {

    pub fn reversed(mut self) -> Self {

        self.keys.reverse();

        self

    }

}

/// Plans the transition from `from` to `to`. Both slices index the same windows.

/// When some windows appear while others vanish in the same place, no single

/// set of phases keeps them apart, so the vanishing ones finish first.

pub fn plan(from: &[Rect], to: &[Rect], cfg: &Config) -> Plan {

    let direct = plan_once(from, to, cfg);

    if !direct.groups.iter().any(|g| g.strategy == Strategy::Pinch) {

        return direct;

    }

    staged(from, to, cfg).unwrap_or(direct)

}

/// Plans everything but the windows that appear, then lets those grow.

/// A window that appears from a seed sits inside the space a vanishing one

/// still fills, and the exact overlap check rejects growing into it.

fn staged(from: &[Rect], to: &[Rect], cfg: &Config) -> Option<Plan> {

    let appears = |i: usize| is_empty(&from[i], cfg) && !is_empty(&to[i], cfg);

    if !(0..from.len()).any(appears) {

        return None;

    }

    let mid: Vec<Rect> = (0..from.len())

        .map(|i| if appears(i) { from[i] } else { to[i] })

        .collect();

    let (first, second) = (plan_once(from, &mid, cfg), plan_once(&mid, to, cfg));

    let groups: Vec<Group> = first.groups.into_iter().chain(second.groups).collect();

    if groups.iter().any(|g| g.strategy == Strategy::Pinch) {

        return None;

    }

    let mut keyframes = first.keyframes;

    keyframes.extend(second.keyframes.into_iter().skip(1));

    Some(Plan { keyframes, groups })

}

fn is_empty(r: &Rect, cfg: &Config) -> bool {

    r.w <= cfg.eps || r.h <= cfg.eps

}

/// Windows with no area at either end, like hidden ones held at their seed,

/// jump straight to `to`. Planning them would let an invisible point inside

/// a visible window join its group, or block every strategy and pinch.

fn plan_once(from: &[Rect], to: &[Rect], cfg: &Config) -> Plan {

    assert_eq!(

        from.len(),

        to.len(),

        "layouts must describe the same windows"

    );

    let live: Vec<usize> = (0..from.len())

        .filter(|&i| !(is_empty(&from[i], cfg) && is_empty(&to[i], cfg)))

        .collect();

    if live.len() == from.len() {

        return plan_live(from, to, cfg);

    }

    let pick = |rects: &[Rect]| live.iter().map(|&i| rects[i]).collect::<Vec<_>>();

    let inner = plan_live(&pick(from), &pick(to), cfg);

    let keyframes = inner

        .keyframes

        .iter()

        .map(|key| {

            let mut frame = to.to_vec();

            for (k, &i) in live.iter().enumerate() {

                frame[i] = key[k];

            }

            frame

        })

        .collect();

    let groups = inner

        .groups

        .into_iter()

        .map(|g| Group {

            members: g.members.iter().map(|&k| live[k]).collect(),

            ..g

        })

        .collect();

    Plan { keyframes, groups }

}

fn plan_live(from: &[Rect], to: &[Rect], cfg: &Config) -> Plan {

    let mut groups = Vec::new();

    let mut plans = Vec::new();

    for members in motion_groups(from, to, cfg) {

        let f: Vec<Rect> = members.iter().map(|&i| from[i]).collect();

        let t: Vec<Rect> = members.iter().map(|&i| to[i]).collect();

        let gp = plan_canonical(&f, &t, cfg);

        groups.push(Group {

            members: members.clone(),

            strategy: gp.strategy,

            phases: gp.keys.len() - 1,

            opens_hole: gp.opens_hole,

        });

        plans.push((members, gp));

    }

    let phases = groups.iter().map(|g| g.phases).max().unwrap_or(0);

    let mut keyframes = vec![to.to_vec(); phases + 1];

    for (members, gp) in &plans {

        for (k, frame) in keyframes.iter_mut().enumerate() {

            let key = &gp.keys[k.min(gp.keys.len() - 1)];

            for (local, &i) in members.iter().enumerate() {

                frame[i] = key[local];

            }

        }

    }

    Plan { keyframes, groups }

}

/// Plans in one fixed direction per pair of layouts, so planning back plays

/// the same plan in reverse.

pub(crate) fn plan_canonical(from: &[Rect], to: &[Rect], cfg: &Config) -> GroupPlan {

    if canonical_order(from, to).is_le() {

        plan_group(from, to, cfg)

    } else {

        plan_group(to, from, cfg).reversed()

    }

}

fn canonical_order(a: &[Rect], b: &[Rect]) -> std::cmp::Ordering {

    let q = |v: f64| (v * 10.0).round() as i64;

    let key = |r: &Rect| [q(r.x), q(r.y), q(r.w), q(r.h)];

    a.iter().map(key).cmp(b.iter().map(key))

}

/// Partitions windows so that windows in different groups can never meet.

/// A moving window joins every window its swept area comes within a gap of.

fn motion_groups(from: &[Rect], to: &[Rect], cfg: &Config) -> Vec<Vec<usize>> {

    let n = from.len();

    let swept: Vec<Rect> = (0..n)

        .map(|i| Rect::bounding([&from[i], &to[i]]).expanded(cfg.gap / 2.0 + cfg.eps))

        .collect();

    let moves: Vec<bool> = (0..n)

        .map(|i| Change::between(&from[i], &to[i]).moves())

        .collect();

    let mut parent: Vec<usize> = (0..n).collect();

    fn find(parent: &mut [usize], mut i: usize) -> usize {

        while parent[i] != i {

            parent[i] = parent[parent[i]];

            i = parent[i];

        }

        i

    }

    for i in 0..n {

        for j in i + 1..n {

            if (moves[i] || moves[j]) && swept[i].intersects(&swept[j]) {

                let (a, b) = (find(&mut parent, i), find(&mut parent, j));

                parent[a] = b;

            }

        }

    }

    let mut groups: Vec<Vec<usize>> = Vec::new();

    let mut slot = vec![usize::MAX; n];

    for i in 0..n {

        let root = find(&mut parent, i);

        if slot[root] == usize::MAX {

            slot[root] = groups.len();

            groups.push(Vec::new());

        }

        groups[slot[root]].push(i);

    }

    groups

}