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

pub(super) type Rect = (UVec2, UVec2);

pub(super) trait RectItem: Copy + Eq {
	const EMPTY: Self;
}

pub(super) trait RectOutput: Default {
	type Item: RectItem;

	fn push(&mut self, rect: Rect, item: Self::Item);
}

impl RectItem for bool {
	const EMPTY: bool = false;
}

impl RectOutput for Vec<Rect> {
	type Item = bool;

	fn push(&mut self, rect: Rect, _item: bool) {
		self.push(rect);
	}
}

impl RectItem for u8 {
	const EMPTY: u8 = 0;
}

impl RectOutput for Vec<(u8, Rect)> {
	type Item = u8;

	fn push(&mut self, rect: Rect, item: u8) {
		self.push((item, rect));
	}
}

/**
 * Extracts some rectangles from a section.
 *
 * To minimise the number of vertices in each section, this function is called
 * to group some of these blocks together into larger rectangles.
 *
 * This algorithm doesn't find the minimum number of rectangles needed to
 * represent the blocks, as I'm too lazy to do it, and the complexity isn't
 * nice. However, this algorithm is much better than doing nothing at all.
 *
 * Sources about this "minimum rectilinear partitioning":
 * 	https://web.archive.org/web/20100605183205/http://www.math.unl.edu/~s-dstolee1/Presentations/Sto08-MinRectPart.pdf
 * 	https://doi.org/10.1016/0734-189X(84)90139-7
 */
pub(super) fn section_to_rects<O: RectOutput>(size: UVec2, mut section: Box<[O::Item]>) -> O {
	let mut i = 0usize;
	let mut rects = O::default();
	for y in 0..size.y {
		let mut x = 0;
		while x < size.x {
			let item = section[i];
			if item != O::Item::EMPTY {
				let pos = UVec2::new(x, y);
				let rect = find_max_rect(i, pos, size, &section, item);

				// Clears the rectangle that was just found
				let mut j = i;
				for _ in 0..rect.y {
					section[j..j + rect.x as usize].fill(O::Item::EMPTY);
					j += size.x as usize;
				}

				// Can skip ahead a bit, knowing that no rectangle will be found
				i += rect.x as usize;
				x += rect.x;

				rects.push((pos, pos + rect), item);
			} else {
				x += 1;
				i += 1;
			}
		}
	}
	rects
}

// Note: i = pos.x + pos.y * size.x must hold
// Also the section and size must be consistent
fn find_max_rect<I: RectItem>(mut i: usize, pos: UVec2, size: UVec2, section: &[I], item: I) -> UVec2 {
	let mut rect = { // Finds the first n×1 rectangle
		let mut j = i + 1;
		let row_end = ((pos.y + 1) * size.x) as usize;
		while j < row_end && section[j] == item { j += 1; }
		UVec2::new((j - i) as u32, 1)
	};
	let mut max_area = rect.x;
	let mut max_x = rect.x;

	// Searches down and tries to find a larger rectangle
	for y in 2..=size.y - pos.y {
		i += size.x as usize;
		if section[i] != item { break; } // Past the last rectangle so stop searching, cannot go down any further

		let end = i + max_x as usize;

		// Finds the largest rectangle of height `y`
		let mut j = i + 1;
		while j < end && section[j] == item { j += 1; }

		// Updates the largest rectangle if the area is greater
		let x = (j - i) as u32;
		max_x = x; // max_x can only decrease
		let area = x * y;
		if area > max_area {
			rect = UVec2::new(x, y);
			max_area = area;
		}
	}

	rect
}

#[cfg(test)]
mod tests {
	use super::*;
	use super::super::SECTION_SIZE;

	const SIZE: UVec2 = UVec2::splat(SECTION_SIZE);

	/*
	 * A function used for all these property tests that checks that:
	 * 	1. Rectangles do not overlap.
	 * 	2. All blocks are covered by a rectangle.
	 * 	3. No rectangle covers an area that isn't a block.
	 * 	4. p0 < p1, where p0 and p1 are the two points defining the rectangle.
	 */
	fn properties_hold(size: UVec2, mut section: Box<[bool]>) {
		let rects: Vec<Rect> = section_to_rects(size, section.clone());
		assert!(rects.iter().all(|rect| rect.0.cmplt(rect.1).all())); // p0 < p1

		for rect in rects {
			for y in rect.0.y..rect.1.y {
				for x in rect.0.x..rect.1.x {
					let i = (x + y * size.x) as usize;
					assert!(section[i]); // Rectangle cannot cover any non-blocks
					section[i] = false; // Resets it to detect overlapping rectangles as the above assertion will panic
				}
			}
		}

		assert!(section.iter().all(|&b| !b)); // Must all be non-blocks, checking that all blocks are covered
	}

	#[test]
	fn random() {
		for _ in 0..500 {
			let r = rand::random::<f32>();
			let section = (0..SECTION_SIZE * SECTION_SIZE).map(|_| rand::random::<f32>() < r).collect::<Box<[bool]>>();
			properties_hold(SIZE, section);
		}
	}

	#[test]
	fn empty() {
		let section = vec![false; (SECTION_SIZE * SECTION_SIZE) as usize].into_boxed_slice();
		properties_hold(SIZE, section.clone());
		assert!(section_to_rects::<Vec<Rect>>(SIZE, section).is_empty());
	}

	#[test]
	fn full() {
		let section = vec![true; (SECTION_SIZE * SECTION_SIZE) as usize].into_boxed_slice();
		properties_hold(SIZE, section.clone());
		assert!(section_to_rects::<Vec<Rect>>(SIZE, section).len() == 1);
	}

	#[test]
	fn half() {
		let section = (0..SECTION_SIZE * SECTION_SIZE).map(|i| i < SECTION_SIZE * SECTION_SIZE / 2).collect::<Box<[bool]>>();
		properties_hold(SIZE, section.clone());
		assert!(section_to_rects::<Vec<Rect>>(SIZE, section).len() == 1);
	}

	#[test]
	fn vertical_stripes() {
		let section = (0..SECTION_SIZE * SECTION_SIZE).map(|i| i % 2 == 0).collect::<Box<[bool]>>();
		properties_hold(SIZE, section.clone());
		assert!(section_to_rects::<Vec<Rect>>(SIZE, section).len() == (SECTION_SIZE / 2) as usize);
	}

	#[test]
	fn horizontal() {
		let section = (0..SECTION_SIZE * SECTION_SIZE).map(|i| (i / SECTION_SIZE).is_multiple_of(2)).collect::<Box<[bool]>>();
		properties_hold(SIZE, section.clone());
		assert!(section_to_rects::<Vec<Rect>>(SIZE, section).len() == (SECTION_SIZE / 2) as usize);
	}
}
