monolith

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

use crate::plan::{Config, GroupPlan, Strategy, Style};

use crate::relation::{ABOVE, LEFT, X_BITS, Y_BITS, adjacency, separation};

use crate::sat::{Lit, TwoSat};

/// Upper bound on lane-assignment search steps before giving up on a lane count.

const LANE_SEARCH_BUDGET: usize = 20_000;

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

enum Axis {

    X,

    Y,

}

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

    let done = |keys: Vec<Vec<Rect>>, strategy| GroupPlan {

        keys,

        strategy,

        opens_hole: false,

    };

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

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

        .collect();

    if movers.is_empty() {

        return done(vec![from.to_vec()], Strategy::Unchanged);

    }

    let pure = movers

        .iter()

        .all(|&i| !Change::between(&from[i], &to[i]).both());

    if phase_ok(from, to, cfg) && (cfg.style == Style::Direct || pure) {

        return done(vec![from.to_vec(), to.to_vec()], Strategy::Direct);

    }

    if let Some((k1, opens_hole)) = axis_order(from, to, &movers, cfg) {

        return GroupPlan {

            keys: vec![from.to_vec(), k1, to.to_vec()],

            strategy: Strategy::AxisOrder,

            opens_hole,

        };

    }

    for axis in [Axis::Y, Axis::X] {

        if let Some((k1, k2, lanes)) = lanes(from, to, &movers, axis, cfg) {

            return done(

                vec![from.to_vec(), k1, k2, to.to_vec()],

                Strategy::Lanes { lanes },

            );

        }

    }

    if let Some((keys, cells)) = grid(from, to, &movers, cfg) {

        return done(keys, Strategy::Grid { cells });

    }

    done(pinch(from, to, &movers), Strategy::Pinch)

}

/// Every pair shares a separating relation at both ends of the phase.

pub(crate) fn phase_ok(a: &[Rect], b: &[Rect], cfg: &Config) -> bool {

    (0..a.len()).all(|i| {

        (i + 1..a.len())

            .all(|j| separation(&a[i], &a[j], cfg.eps) & separation(&b[i], &b[j], cfg.eps) != 0)

    })

}

fn pure_ok(keys: &[&[Rect]], cfg: &Config) -> bool {

    cfg.style == Style::Direct

        || keys.windows(2).all(|w| {

            w[0].iter()

                .zip(w[1])

                .all(|(a, b)| !Change::between(a, b).both())

        })

}

fn valid(keys: &[&[Rect]], cfg: &Config) -> bool {

    keys.windows(2).all(|w| phase_ok(w[0], w[1], cfg)) && pure_ok(keys, cfg)

}

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

    let n = from.len();

    let mut hit = vec![false; n];

    for i in 0..n {

        for j in i + 1..n {

            if separation(&from[i], &from[j], cfg.eps) & separation(&to[i], &to[j], cfg.eps) == 0 {

                hit[i] = true;

                hit[j] = true;

            }

        }

    }

    (0..n).filter(|&i| hit[i]).collect()

}

/// Two phases. Each moving window takes one axis of its target in phase 1 and

/// the other in phase 2. The choice per window is a boolean, every pair forbids

/// some combinations, and the result is a 2-SAT instance. Neighbours that touch

/// at both ends must also touch in the middle keyframe when that is possible.

fn axis_order(

    from: &[Rect],

    to: &[Rect],

    movers: &[usize],

    cfg: &Config,

) -> Option<(Vec<Rect>, bool)> {

    let n = from.len();

    let mut var = vec![None; n];

    for (v, &i) in movers.iter().enumerate() {

        var[i] = Some(v);

    }

    let options = |i: usize| -> Vec<(Option<bool>, Rect)> {

        if var[i].is_some() {

            vec![

                (Some(false), Rect::mixed(&from[i], &to[i])),

                (Some(true), Rect::mixed(&to[i], &from[i])),

            ]

        } else {

            vec![(None, from[i])]

        }

    };

    let preferred: Vec<bool> = movers

        .iter()

        .map(|&i| {

            let c = Change::between(&from[i], &to[i]);

            c.x && !c.y

        })

        .collect();

    for keep_edges in [true, false] {

        let mut sat = TwoSat::new(movers.len());

        let mut impossible = false;

        for i in 0..n {

            for j in i + 1..n {

                if var[i].is_none() && var[j].is_none() {

                    continue;

                }

                let sf = separation(&from[i], &from[j], cfg.eps);

                let st = separation(&to[i], &to[j], cfg.eps);

                let coupled = adjacency(&from[i], &from[j], cfg.gap, cfg.eps)

                    & adjacency(&to[i], &to[j], cfg.gap, cfg.eps);

                for (ci, ri) in options(i) {

                    for (cj, rj) in options(j) {

                        let s = separation(&ri, &rj, cfg.eps);

                        let held = !keep_edges

                            || adjacency(&ri, &rj, cfg.gap, cfg.eps) & coupled == coupled;

                        if sf & s != 0 && s & st != 0 && held {

                            continue;

                        }

                        match (ci, cj) {

                            (Some(a), Some(b)) => {

                                sat.either(Lit::new(var[i]?, !a), Lit::new(var[j]?, !b))

                            }

                            (Some(a), None) => sat.require(Lit::new(var[i]?, !a)),

                            (None, Some(b)) => sat.require(Lit::new(var[j]?, !b)),

                            (None, None) => impossible = true,

                        }

                    }

                }

            }

        }

        if impossible {

            continue;

        }

        if let Some(choice) = sat.solve_preferring(&preferred) {

            let mut k1 = from.to_vec();

            for (v, &i) in movers.iter().enumerate() {

                k1[i] = if choice[v] {

                    Rect::mixed(&to[i], &from[i])

                } else {

                    Rect::mixed(&from[i], &to[i])

                };

            }

            let hole = opens_hole(from, to, &k1, cfg);

            return Some((k1, hole));

        }

    }

    None

}

fn opens_hole(from: &[Rect], to: &[Rect], mid: &[Rect], cfg: &Config) -> bool {

    let n = from.len();

    (0..n).any(|i| {

        (i + 1..n).any(|j| {

            let coupled = adjacency(&from[i], &from[j], cfg.gap, cfg.eps)

                & adjacency(&to[i], &to[j], cfg.gap, cfg.eps);

            adjacency(&mid[i], &mid[j], cfg.gap, cfg.eps) & coupled != coupled

        })

    })

}

/// Three phases. Windows that pass each other shrink across the axis of travel

/// into separate lanes, slide, then expand. Lanes span only the band the

/// involved windows occupy.

fn lanes(

    from: &[Rect],

    to: &[Rect],

    movers: &[usize],

    axis: Axis,

    cfg: &Config,

) -> Option<(Vec<Rect>, Vec<Rect>, usize)> {

    let n = from.len();

    let (travel, before) = match axis {

        Axis::Y => (X_BITS, ABOVE),

        Axis::X => (Y_BITS, LEFT),

    };

    let span = |r: &Rect| match axis {

        Axis::Y => (r.y, r.bottom()),

        Axis::X => (r.x, r.right()),

    };

    for set in [

        conflict_set(from, to, cfg),

        movers.to_vec(),

        (0..n).collect(),

    ] {

        let m = set.len();

        if m < 2 {

            continue;

        }

        let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);

        for &i in &set {

            for r in [&from[i], &to[i]] {

                let (a, b) = span(r);

                lo = lo.min(a);

                hi = hi.max(b);

            }

        }

        let mut diff = vec![vec![false; m]; m];

        let mut lt = vec![vec![false; m]; m];

        for a in 0..m {

            for b in 0..m {

                if a == b {

                    continue;

                }

                let f = separation(&from[set[a]], &from[set[b]], cfg.eps);

                let t = separation(&to[set[a]], &to[set[b]], cfg.eps);

                diff[a][b] = f & t & travel == 0;

                lt[a][b] = [f, t].iter().any(|r| r & travel == 0 && r & before != 0);

            }

        }

        let in_set: Vec<Option<usize>> = (0..n).map(|i| set.iter().position(|&s| s == i)).collect();

        for k in 2..=m {

            let size = (hi - lo - (k - 1) as f64 * cfg.gap) / k as f64;

            if size < cfg.min_lane {

                break;

            }

            let mut lane = vec![usize::MAX; m];

            let mut budget = LANE_SEARCH_BUDGET;

            if !assign_lanes(0, k, &mut lane, &diff, &lt, &mut budget) {

                continue;

            }

            let strip = |l: usize| lo + l as f64 * (size + cfg.gap);

            let in_lane = |r: &Rect, l: usize| match axis {

                Axis::Y => Rect::new(r.x, strip(l), r.w, size),

                Axis::X => Rect::new(strip(l), r.y, size, r.h),

            };

            for phase in [2, 1, 3] {

                let mut k1 = Vec::with_capacity(n);

                let mut k2 = Vec::with_capacity(n);

                for i in 0..n {

                    let (f, t) = (from[i], to[i]);

                    let (a, b) = match (in_set[i], phase) {

                        (Some(s), _) => (in_lane(&f, lane[s]), in_lane(&t, lane[s])),

                        (None, 1) => (t, t),

                        (None, 2) => (f, t),

                        (None, _) => (f, f),

                    };

                    k1.push(a);

                    k2.push(b);

                }

                if valid(&[from, &k1, &k2, to], cfg) {

                    return Some((k1, k2, k));

                }

            }

        }

    }

    None

}

fn assign_lanes(

    i: usize,

    k: usize,

    lane: &mut [usize],

    diff: &[Vec<bool>],

    lt: &[Vec<bool>],

    budget: &mut usize,

) -> bool {

    if i == lane.len() {

        return true;

    }

    for l in 0..k {

        if *budget == 0 {

            return false;

        }

        *budget -= 1;

        let fits = (0..i).all(|j| {

            !(diff[i][j] && lane[j] == l)

                && !(lt[i][j] && l >= lane[j])

                && !(lt[j][i] && lane[j] >= l)

        });

        if fits {

            lane[i] = l;

            if assign_lanes(i + 1, k, lane, diff, lt, budget) {

                return true;

            }

            lane[i] = usize::MAX;

        }

    }

    false

}

/// Four phases that work for any input. Involved windows shrink into rows

/// ordered by where they start, then into columns ordered by where they end,

/// then move vertically to their target, then horizontally.

fn grid(

    from: &[Rect],

    to: &[Rect],

    movers: &[usize],

    cfg: &Config,

) -> Option<(Vec<Vec<Rect>>, usize)> {

    let n = from.len();

    for set in [

        conflict_set(from, to, cfg),

        movers.to_vec(),

        (0..n).collect(),

    ] {

        let m = set.len();

        if m < 2 {

            continue;

        }

        let area = Rect::bounding(set.iter().flat_map(|&i| [&from[i], &to[i]]));

        let gap = |len: f64| {

            if len - (m - 1) as f64 * cfg.gap > m as f64 {

                cfg.gap

            } else {

                0.0

            }

        };

        let (gh, gw) = (gap(area.h), gap(area.w));

        let sh = (area.h - (m - 1) as f64 * gh) / m as f64;

        let sw = (area.w - (m - 1) as f64 * gw) / m as f64;

        let mut by_row = set.clone();

        by_row.sort_by(|&a, &b| {

            from[a]

                .center_y()

                .total_cmp(&from[b].center_y())

                .then(from[a].center_x().total_cmp(&from[b].center_x()))

        });

        let mut by_col = set.clone();

        by_col.sort_by(|&a, &b| {

            to[a]

                .center_x()

                .total_cmp(&to[b].center_x())

                .then(to[a].center_y().total_cmp(&to[b].center_y()))

        });

        let mut row = vec![0.0; n];

        let mut col = vec![0.0; n];

        for (r, &i) in by_row.iter().enumerate() {

            row[i] = area.y + r as f64 * (sh + gh);

        }

        for (c, &i) in by_col.iter().enumerate() {

            col[i] = area.x + c as f64 * (sw + gw);

        }

        let in_set: Vec<bool> = (0..n).map(|i| set.contains(&i)).collect();

        for phase in [3, 2, 4, 1] {

            let mut keys = vec![

                from.to_vec(),

                Vec::new(),

                Vec::new(),

                Vec::new(),

                to.to_vec(),

            ];

            for i in 0..n {

                let (f, t) = (from[i], to[i]);

                let mid = if in_set[i] {

                    [

                        Rect::new(f.x, row[i], f.w, sh),

                        Rect::new(col[i], row[i], sw, sh),

                        Rect::new(col[i], t.y, sw, t.h),

                    ]

                } else {

                    [1, 2, 3].map(|k| if k >= phase { t } else { f })

                };

                for (k, r) in mid.into_iter().enumerate() {

                    keys[k + 1].push(r);

                }

            }

            let refs: Vec<&[Rect]> = keys.iter().map(|k| k.as_slice()).collect();

            if valid(&refs, cfg) {

                return Some((keys, m));

            }

        }

    }

    None

}

/// Safety net. Movers shrink to a point, travel invisibly, and regrow.

fn pinch(from: &[Rect], to: &[Rect], movers: &[usize]) -> Vec<Vec<Rect>> {

    let mut k1 = from.to_vec();

    let mut k2 = to.to_vec();

    for &i in movers {

        k1[i] = Rect::new(from[i].center_x(), from[i].center_y(), 0.0, 0.0);

        k2[i] = Rect::new(to[i].center_x(), to[i].center_y(), 0.0, 0.0);

    }

    vec![from.to_vec(), k1, k2, to.to_vec()]

}