gpf.rs

use std::collections::HashMap;

use crate::model::Problem;

/// A piece type: all pieces with same (width, height) grouped together.
#[derive(Debug, Clone)]
pub struct PieceType {
    pub width: u32,
    pub height: u32,
    pub count: u32,
}

/// Step function f(x; D): sorted by x ascending, heights strictly descending.
/// Semantics: f(x) = h_i for x ∈ [x_i, x_{i+1}), ∞ for x < x_1.
/// Empty vec = identically ∞ (infeasible).
pub type StepFn = Vec<(u32, u32)>;

/// Evaluate f(x): return height at given width, None if infeasible.
fn eval_f(f: &StepFn, x: u32) -> Option<u32> {
    // Find last breakpoint with x_i <= x (f is non-increasing step function).
    // Breakpoints sorted ascending, so find the last one where x_i <= x.
    let pos = f.partition_point(|&(xi, _)| xi <= x);
    if pos == 0 {
        None
    } else {
        Some(f[pos - 1].1)
    }
}

/// Evaluate f⁻¹(h): return minimum x such that f(x) <= h, None if no such x.
/// Heights in f are strictly decreasing left-to-right, so scan from left
/// for the first h_i <= h.
fn eval_inv(f: &StepFn, h: u32) -> Option<u32> {
    // Heights decrease: f[0].1 >= f[1].1 >= ...
    // Want first i, where f[i].1 <= h → that gives minimum x = f[i].0
    for &(xi, hi) in f {
        if hi <= h {
            return Some(xi);
        }
    }
    None
}

/// Remove points that do not strictly decrease in height (dominated or flat segments).
/// Input must be sorted by x ascending.
fn simplify(pts: &mut StepFn) {
    if pts.len() <= 1 {
        return;
    }
    let mut write = 1;
    for read in 1..pts.len() {
        if pts[read].1 < pts[write - 1].1 {
            pts[write] = pts[read];
            write += 1;
        }
        // If height == previous or x is duplicate: drop
    }
    pts.truncate(write);
}

/// H-cut: stack D1 on top of D2 (same width, add heights + kerf).
pub fn h_cut(f1: &StepFn, f2: &StepFn, kerf: u32) -> StepFn {
    if f1.is_empty() || f2.is_empty() {
        return vec![];
    }
    // Merge x-breakpoints
    let mut xs: Vec<u32> = f1.iter().map(|&(x, _)| x).chain(f2.iter().map(|&(x, _)| x)).collect();
    xs.sort_unstable();
    xs.dedup();

    let mut result = Vec::with_capacity(xs.len());
    for x in xs {
        if let (Some(h1), Some(h2)) = (eval_f(f1, x), eval_f(f2, x)) {
            result.push((x, h1 + h2 + kerf));
        }
    }
    simplify(&mut result);
    result
}

/// V-cut: place D1 and D2 side by side (same height, add widths + kerf).
pub fn v_cut(f1: &StepFn, f2: &StepFn, kerf: u32) -> StepFn {
    if f1.is_empty() || f2.is_empty() {
        return vec![];
    }
    // Collect candidate heights from both functions, sorted descending
    let mut hs: Vec<u32> = f1.iter().map(|&(_, h)| h).chain(f2.iter().map(|&(_, h)| h)).collect();
    hs.sort_unstable_by(|a, b| b.cmp(a));
    hs.dedup();

    let mut result = Vec::with_capacity(hs.len());
    for h in hs {
        if let (Some(w1), Some(w2)) = (eval_inv(f1, h), eval_inv(f2, h)) {
            result.push((w1 + w2 + kerf, h));
        }
    }
    // result is in order of decreasing h → need to re-sort by x ascending
    // (w values may not be monotone before simplification)
    result.sort_unstable_by_key(|&(x, _)| x);
    simplify(&mut result);
    result
}

/// Pointwise minimum of two step functions.
pub fn min_fn(f1: &StepFn, f2: &StepFn) -> StepFn {
    if f1.is_empty() {
        return f2.clone();
    }
    if f2.is_empty() {
        return f1.clone();
    }
    let mut xs: Vec<u32> = f1.iter().map(|&(x, _)| x).chain(f2.iter().map(|&(x, _)| x)).collect();
    xs.sort_unstable();
    xs.dedup();

    let mut result = Vec::with_capacity(xs.len());
    for x in xs {
        match (eval_f(f1, x), eval_f(f2, x)) {
            (Some(h1), Some(h2)) => result.push((x, h1.min(h2))),
            (Some(h), None) | (None, Some(h)) => result.push((x, h)),
            (None, None) => {}
        }
    }
    simplify(&mut result);
    result
}

/// The complete GPF DP table.
pub struct GpfTable {
    pub types: Vec<PieceType>,
    strides: Vec<usize>,
    cells: Vec<StepFn>,
    pub kerf: u32,
}

impl GpfTable {
    fn flat_index(&self, counts: &[u32]) -> usize {
        counts.iter().zip(&self.strides).map(|(&k, &s)| k as usize * s).sum()
    }

    fn total_subsets(&self) -> usize {
        self.types.iter().map(|t| (t.count + 1) as usize).product::<usize>()
    }

    /// Decode flat index back to per-type counts.
    fn decode_index(&self, mut idx: usize) -> Vec<u32> {
        let t = self.types.len();
        let mut counts = vec![0u32; t];
        // Type 0 is least significant digit (stride=1), so extract left-to-right.
        for (count, pt) in counts.iter_mut().zip(&self.types) {
            let modulus = (pt.count + 1) as usize;
            *count = (idx % modulus) as u32;
            idx /= modulus;
        }
        counts
    }

    /// Evaluate f(width; full set).
    pub fn eval_full_set(&self, width: u32) -> Option<u32> {
        let full: Vec<u32> = self.types.iter().map(|t| t.count).collect();
        let idx = self.flat_index(&full);
        eval_f(&self.cells[idx], width)
    }

    /// Evaluate f(width; subset specified by per-type counts).
    pub fn eval_subset(&self, counts: &[u32], width: u32) -> Option<u32> {
        let idx = self.flat_index(counts);
        eval_f(&self.cells[idx], width)
    }

    /// Print the full DP table: each non-empty subset, its step function, and f(width).
    pub fn display_table(&self, width: u32) -> String {
        let total = self.total_subsets();
        // Collect all non-empty subsets, sort by total piece count
        let mut rows: Vec<(usize, Vec<u32>)> = (1..total)
            .map(|idx| {
                let counts = self.decode_index(idx);
                let total_pieces: u32 = counts.iter().sum();
                (idx, counts, total_pieces)
            })
            .filter(|(idx, _, _)| !self.cells[*idx].is_empty())
            .map(|(idx, counts, total_pieces)| (total_pieces as usize, idx, counts))
            .collect::<Vec<_>>()
            .into_iter()
            .map(|(tp, idx, counts)| (idx, counts, tp))
            .collect::<Vec<_>>()
            .into_iter()
            .map(|(idx, counts, tp)| (tp, counts, idx))
            .collect::<Vec<_>>()
            .into_iter()
            .map(|(tp, counts, _idx)| (tp, counts))
            .collect();
        rows.sort_by_key(|(tp, _)| *tp);

        // Type labels: A, B, C, ...
        let labels: Vec<String> = (0..self.types.len())
            .map(|i| {
                if i < 26 {
                    format!("{}", (b'A' + i as u8) as char)
                } else {
                    format!("T{i}")
                }
            })
            .collect();

        let mut lines = Vec::new();
        lines.push(format!("{:<20}  {:<40}  f({})", "Subset", "Step function", width));
        lines.push("-".repeat(70));

        for (_, counts) in &rows {
            let label = subset_label(&labels, counts);
            let idx = self.flat_index(counts);
            let f = &self.cells[idx];
            let step_str = format_step_fn(f);
            let fval = eval_f(f, width)
                .map(|h| h.to_string())
                .unwrap_or_else(|| "∞".to_string());
            lines.push(format!("{:<20}  {:<40}  {}", label, step_str, fval));
        }
        lines.join("\n")
    }
}

fn subset_label(labels: &[String], counts: &[u32]) -> String {
    let parts: Vec<String> = counts
        .iter()
        .enumerate()
        .filter(|(_, k)| **k > 0)
        .map(|(i, &k)| if k == 1 { labels[i].clone() } else { format!("{}·{}", k, labels[i]) })
        .collect();
    format!("{{{}}}", parts.join(","))
}

fn format_step_fn(f: &StepFn) -> String {
    if f.is_empty() {
        return "∞".to_string();
    }
    let parts: Vec<String> = f.iter().map(|&(x, h)| format!("({x},{h})")).collect();
    format!("[{}]", parts.join(", "))
}

/// Build the GPF table for a problem (fixed pieces only; can_rotate ignored).
pub fn build_gpf(problem: &Problem) -> GpfTable {
    // 1. Group pieces by (width, height) preserving order of first appearance
    let mut type_map: HashMap<(u32, u32), usize> = HashMap::new();
    let mut types: Vec<PieceType> = Vec::new();
    for piece in &problem.pieces {
        let key = (piece.width, piece.height);
        if let Some(&ti) = type_map.get(&key) {
            types[ti].count += 1;
        } else {
            let ti = types.len();
            type_map.insert(key, ti);
            types.push(PieceType { width: piece.width, height: piece.height, count: 1 });
        }
    }
    let t = types.len();

    // 2. Compute strides: strides[i] = ∏_{j<i} (types[j].count + 1)
    let mut strides = vec![1usize; t];
    for i in 1..t {
        strides[i] = strides[i - 1] * (types[i - 1].count + 1) as usize;
    }
    let total: usize = if t == 0 { 1 } else { strides[t - 1] * (types[t - 1].count + 1) as usize };

    let mut cells: Vec<StepFn> = vec![vec![]; total];

    // 3. Collect all non-empty subsets sorted by total piece count (BFS order)
    let mut subsets: Vec<(u32, usize, Vec<u32>)> = Vec::with_capacity(total - 1);
    for flat in 1..total {
        let counts = decode_index_with(&types, flat);
        let total_pieces: u32 = counts.iter().sum();
        subsets.push((total_pieces, flat, counts));
    }
    subsets.sort_unstable_by_key(|&(tp, _, _)| tp);

    let kerf = problem.kerf;

    // 4. Fill DP table
    for (total_pieces, flat, counts) in &subsets {
        if *total_pieces == 1 {
            // Base case: find which type has exactly 1 piece
            for (i, &k) in counts.iter().enumerate() {
                if k == 1 {
                    cells[*flat] = vec![(types[i].width, types[i].height)];
                    break;
                }
            }
        } else {
            // Enumerate all splits D = D1 ∪ D2
            // D1 = a[i] pieces of type i, D2 = counts[i] - a[i]
            let mut best: StepFn = vec![];
            let ranges = counts.to_vec();
            let split_count: usize = ranges.iter().map(|&k| (k + 1) as usize).product();

            for split_flat in 0..split_count {
                // Decode split_flat into per-type split (a[i] for D1)
                let d1_counts = decode_split(&ranges, split_flat);
                let d1_total: u32 = d1_counts.iter().sum();
                if d1_total == 0 || d1_total == *total_pieces {
                    continue; // skip empty splits
                }
                let d2_counts: Vec<u32> = counts.iter().zip(&d1_counts).map(|(&k, &a)| k - a).collect();

                let d1_flat = flat_index_with(&strides, &d1_counts);
                let d2_flat = flat_index_with(&strides, &d2_counts);

                // Avoid processing (D1, D2) and (D2, D1) twice
                if d1_flat > d2_flat {
                    continue;
                }

                let f1 = &cells[d1_flat];
                let f2 = &cells[d2_flat];
                if f1.is_empty() || f2.is_empty() {
                    continue;
                }

                let fh = h_cut(f1, f2, kerf);
                let fv = v_cut(f1, f2, kerf);
                let candidate = min_fn(&fh, &fv);
                best = min_fn(&best, &candidate);
            }
            cells[*flat] = best;
        }
    }

    GpfTable { types, strides, cells, kerf }
}

fn decode_index_with(types: &[PieceType], mut idx: usize) -> Vec<u32> {
    let mut counts = vec![0u32; types.len()];
    for (count, pt) in counts.iter_mut().zip(types) {
        let modulus = (pt.count + 1) as usize;
        *count = (idx % modulus) as u32;
        idx /= modulus;
    }
    counts
}

fn flat_index_with(strides: &[usize], counts: &[u32]) -> usize {
    counts.iter().zip(strides).map(|(&k, &s)| k as usize * s).sum()
}

fn decode_split(ranges: &[u32], mut idx: usize) -> Vec<u32> {
    let mut result = vec![0u32; ranges.len()];
    for (out, &range) in result.iter_mut().zip(ranges) {
        let modulus = (range + 1) as usize;
        *out = (idx % modulus) as u32;
        idx /= modulus;
    }
    result
}

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

    #[test]
    fn eval_f_basic() {
        let f: StepFn = vec![(2, 3), (4, 2)];
        assert_eq!(eval_f(&f, 1), None);
        assert_eq!(eval_f(&f, 2), Some(3));
        assert_eq!(eval_f(&f, 3), Some(3));
        assert_eq!(eval_f(&f, 4), Some(2));
        assert_eq!(eval_f(&f, 10), Some(2));
    }

    #[test]
    fn eval_inv_basic() {
        // f = [(8,6),(10,3)]: f(x)=6 for x∈[8,10), f(x)=3 for x≥10
        // f⁻¹(h) = min x such that f(x) ≤ h
        let f: StepFn = vec![(8, 6), (10, 3)];
        assert_eq!(eval_inv(&f, 2), None);    // h=2 < 3 = min height → impossible
        assert_eq!(eval_inv(&f, 3), Some(10)); // f(10)=3 ≤ 3, first such x
        assert_eq!(eval_inv(&f, 5), Some(10)); // f(8)=6 > 5, f(10)=3 ≤ 5
        assert_eq!(eval_inv(&f, 6), Some(8));  // f(8)=6 ≤ 6 → x=8
        assert_eq!(eval_inv(&f, 7), Some(8));  // f(8)=6 ≤ 7 → x=8
    }

    #[test]
    fn h_cut_basic() {
        // f({C}) = [(8,3)], f({A}) = [(2,3)]
        let fc: StepFn = vec![(8, 3)];
        let fa: StepFn = vec![(2, 3)];
        let fh = h_cut(&fc, &fa, 0);
        assert_eq!(fh, vec![(8, 6)]);
    }

    #[test]
    fn v_cut_basic() {
        // f({C}) = [(8,3)], f({A}) = [(2,3)]
        let fc: StepFn = vec![(8, 3)];
        let fa: StepFn = vec![(2, 3)];
        let fv = v_cut(&fc, &fa, 0);
        assert_eq!(fv, vec![(10, 3)]);
    }

    #[test]
    fn combined_ca() {
        let fc: StepFn = vec![(8, 3)];
        let fa: StepFn = vec![(2, 3)];
        let fh = h_cut(&fc, &fa, 0);
        let fv = v_cut(&fc, &fa, 0);
        let combined = min_fn(&fh, &fv);
        // x ∈ [8,10): H wins → 6; x ≥ 10: V wins → 3
        assert_eq!(combined, vec![(8, 6), (10, 3)]);
    }

    #[test]
    fn tutorial_example() {
        // "10x8F:0:2x3/4,4x3,8x3,5x2/2" — all fixed, kerf=0
        let p = parse_problem("10x8F:0:2x3/4,4x3,8x3,5x2/2").unwrap();
        let table = build_gpf(&p);
        // Full set at width=10 must equal 8
        assert_eq!(table.eval_full_set(10), Some(8));
        // Base cases
        assert_eq!(table.eval_subset(&[1, 0, 0, 0], 2), Some(3)); // {A} at x=2
        assert_eq!(table.eval_subset(&[0, 1, 0, 0], 4), Some(3)); // {B} at x=4
        assert_eq!(table.eval_subset(&[0, 0, 1, 0], 8), Some(3)); // {C} at x=8
        assert_eq!(table.eval_subset(&[0, 0, 0, 1], 5), Some(2)); // {D} at x=5
    }
}