// Copyright Marcus Del Favero 2025
// Licensed under the GNU AGPLv3 with an exception, see `README.md` for details
use glam::UVec2;

pub const BLOCK: u32 = u32::MAX;
pub const UNASSIGNED: u32 = u32::MAX - 1;

/**
 * Takes as input a grid of blocks, `data` and its size `grid_size` and updates
 * the grid with the connected components.
 *
 * The input grid must consist of only `BLOCK` and `UNASSIGNED`.
 *
 * Returns a list of the amount of empty cells in each component.
 */
pub fn find(grid_size: UVec2, data: &mut [u32]) -> Vec<usize> {
	let mut stack = Vec::new();
	let mut i = 0;
	let mut component = 0;
	let mut cells_per_component = Vec::new();

	assert!(data.len() == (grid_size.x * grid_size.y) as usize);

	for y in 0..grid_size.y {
		for x in 0..grid_size.x {
			if data[i] == UNASSIGNED {
				// Performs flood fill for the current component
				stack.push(UVec2::new(x, y));

				let mut cells_in_component = 0;
				while let Some(pos) = stack.pop() {
					if pos.x >= grid_size.x || pos.y >= grid_size.y { continue; }
					let i = (pos.x + pos.y * grid_size.x) as usize;
					if data[i] == UNASSIGNED {
						data[i] = component;
						cells_in_component += 1;
						stack.push(UVec2::new(pos.x.wrapping_sub(1), pos.y));
						stack.push(UVec2::new(pos.x + 1, pos.y));
						stack.push(UVec2::new(pos.x, pos.y.wrapping_sub(1)));
						stack.push(UVec2::new(pos.x, pos.y + 1));
					}
				}

				cells_per_component.push(cells_in_component);
				component += 1;
			}

			i += 1;
		}
	}

	cells_per_component
}
