use glam::Vec2;

/**
0b(tl)(tr)(br)(bl), 0..=15

0 0000 - -

1 0001 BL S → W

2 0010 BR E → S

3 0011 BL BR E → W

4 0100 TR N → E

5 0101 TR BL saddle: N → W, S → E

6 0110 TR BR N → S

7 0111 TR BR BL N → W

8 1000 TL W → N

9 1001 TL BL S → N

10 1010 TL BR saddle: E → N, W → S

11 1011 TL BR BL E → N

12 1100 TL TR W → E

13 1101 TL TR BL S → E

14 1110 TL TR BR W → S

15 1111 - -
*/

#[inline]
fn derive_type(tl: bool, tr: bool, br: bool, bl: bool) -> usize {
    bl as usize | (br as usize) << 1 | (tr as usize) << 2 | (tl as usize) << 3
}

pub trait Marchable {
    fn occupied(&self, x: i32, y: i32) -> bool;
    fn size(&self) -> (i32, i32);
}

pub fn compute_types(marchable: &impl Marchable, w: i32, h: i32) -> Vec<u8> {
    // TODO could pre-allocate size
    let mut types = Vec::new();
    for y in -1..h {
        // TODO precompute per column
        for x in -1..w {
            let tl = marchable.occupied(x, y);
            let tr = marchable.occupied(x + 1, y);
            let br = marchable.occupied(x + 1, y + 1);
            let bl = marchable.occupied(x, y + 1);
            types.push(derive_type(tl, tr, br, bl) as u8);
        }
    }
    types
}

#[derive(PartialEq, Eq, Clone, Copy)]
enum Side {
    None,
    N,
    E,
    S,
    W,
}

const EDGE_COUNT_BY_TYPE: [usize; 16] = [0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0];
const EDGE_START_BY_TYPE_BY_IDX: [[Side; 2]; 16] = [
    [Side::None, Side::None],
    [Side::S, Side::None],
    [Side::E, Side::None],
    [Side::E, Side::None],
    [Side::N, Side::None],
    [Side::N, Side::S],
    [Side::N, Side::None],
    [Side::N, Side::None],
    [Side::W, Side::None],
    [Side::S, Side::None],
    [Side::E, Side::W],
    [Side::E, Side::None],
    [Side::W, Side::None],
    [Side::S, Side::None],
    [Side::W, Side::None],
    [Side::None, Side::None],
];

const EDGE_END_BY_TYPE: [[Side; 2]; 16] = [
    [Side::None, Side::None],
    [Side::W, Side::None],
    [Side::S, Side::None],
    [Side::W, Side::None],
    [Side::E, Side::None],
    [Side::W, Side::E],
    [Side::S, Side::None],
    [Side::W, Side::None],
    [Side::N, Side::None],
    [Side::N, Side::None],
    [Side::N, Side::S],
    [Side::N, Side::None],
    [Side::E, Side::None],
    [Side::E, Side::None],
    [Side::S, Side::None],
    [Side::None, Side::None],
];

fn side_centre(x: i32, y: i32, s: Side) -> Vec2 {
    let (x, y) = (x as f32, y as f32);
    match s {
        Side::N => Vec2::new(x + 0.5, y),
        Side::E => Vec2::new(x + 1.0, y + 0.5),
        Side::S => Vec2::new(x + 0.5, y + 1.0),
        Side::W => Vec2::new(x, y + 0.5),
        Side::None => panic!("Tried to access None side"),
    }
}

fn toward_side(x: i32, y: i32, exit: Side) -> (i32, i32, Side) {
    match exit {
        Side::N => (x, y - 1, Side::S),
        Side::E => (x + 1, y, Side::W),
        Side::S => (x, y + 1, Side::N),
        Side::W => (x - 1, y, Side::E),
        Side::None => panic!("Tried to access None side"),
    }
}

// outer is cw, inner ccw
pub fn marching_squares_vertex_trace(marchable: &impl Marchable, w: i32, h: i32) -> Vec<Vec<Vec2>> {
    let mut visited = vec![0u8; ((w + 1) * (h + 1)) as usize];
    let idx = |cx: i32, cy: i32| (((cy + 1) * (w + 1)) + (cx + 1)) as usize;

    let types = compute_types(marchable, w, h);
    let mut polys = Vec::new();

    for y in -1..h {
        for x in -1..w {
            let mut t = types[(x + 1 + (y + 1) * (w + 1)) as usize] as usize;
            // if there are multiple edges for this type (saddle), try to build a poly for each
            for e in 0..EDGE_COUNT_BY_TYPE[t] {
                // if we have already visited this cell FOR this edge, skip
                if visited[idx(x, y)] & (1 << e) != 0 {
                    continue;
                }

                let mut poly = Vec::new();
                let (mut xi, mut yi, mut ei) = (x, y, e);
                // keep collecting until we don't connect to an edge
                loop {
                    // if we have already visited this cell FOR this edge, skip
                    if visited[idx(xi, yi)] & (1 << ei) != 0 {
                        break;
                    }
                    // set this on the inner loop since every cell we take on the loop is claimed
                    visited[idx(xi, yi)] |= 1 << ei;

                    // this edge starts and ends against some side of our cell
                    let (start, end) = (EDGE_START_BY_TYPE_BY_IDX[t][ei], EDGE_END_BY_TYPE[t][ei]);
                    poly.push(side_centre(xi, yi, start));

                    // move ourselves into the cell that our edge ends in, unless it's out of the grid
                    let (nx, ny, entry) = toward_side(xi, yi, end);
                    // TODO is equality cheaper?
                    if nx < -1 || nx >= w || ny < -1 || ny >= h {
                        // exited the board
                        panic!(
                            "Expecting closed loop but it's not (off the board)! Came from ({xi}, {yi}, {ei}) to ({nx}, {ny})"
                        )
                    }

                    let nt = types[(nx + 1 + (ny + 1) * (w + 1)) as usize] as usize;

                    if EDGE_START_BY_TYPE_BY_IDX[nt][0] == entry {
                        // there's an edge starting where we entered
                        xi = nx;
                        yi = ny;
                        ei = 0;
                        t = nt;
                    } else if EDGE_START_BY_TYPE_BY_IDX[nt][1] == entry {
                        // entering the other side of the saddle
                        xi = nx;
                        yi = ny;
                        ei = 1;
                        t = nt;
                    } else {
                        panic!(
                            "Expecting closed loop but it's not! Came from ({xi}, {yi}, {ei}) to ({nx}, {ny})"
                        )
                    }
                }
                polys.push(poly);
            }
        }
    }
    polys
}