//! The `bsp` module implements a Binary-Space Partitioning based dungeon generator.
//! Produces a tile array and a player start position for a given seed.

use core::panic;
use rand::Rng;
use rand::prelude::IndexedRandom;
use std::cmp::{self, Ordering}; // for min/max

use crate::{
	const_pos,
	map::{Floor, MAP_SIZE, TILE_COUNT, Tile},
	pos::Pos,
	rng::DungeonRng,
};

/// `MIN_LEAF_SIZE` is the minimum width/height for a leaf to be considered "splittable".
const MIN_LEAF_SIZE: u16 = 8;
/// `MIN_ROOM_SIZE` is the minimum room size (w/h).
const MIN_ROOM_SIZE: u16 = 3;
/// `MAX_ROOM_SIZE` is the maximum room size (w/h).
const MAX_ROOM_SIZE: u16 = 12;

/// The `Rect` type represents a rectangle inside the map (x,y,width,height).
/// (x,y) is the top-left corner.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Rect {
	x: u16,
	y: u16,
	w: u16,
	h: u16,
}
// since this is all "internal", you likely have to use unit tests and not doctests
impl Rect {
	const fn new(x: u16, y: u16, w: u16, h: u16) -> Self {
		Self { x, y, w, h }
	}

	/// Returns the center point (cx, cy) of the rectangle as a Pos.
	fn center(self) -> Pos {
		let cx = self.x + self.w / 2;
		let cy = self.y + self.h / 2;
		Pos::new(cx, cy).unwrap_or(const_pos!(1, 1))
	}

	/// Returns a random point in this rectangle.
	fn random_point(self, rng: &mut DungeonRng) -> Pos {
		let rx = rng.random_range(self.x..(self.x + self.w));
		let ry = rng.random_range(self.y..(self.y + self.h));
		Pos::new(rx, ry).unwrap_or(self.center())
	}
}

/// The `Node` type represents a node in the BSP tree.
/// Has optional left and right children, and an optional room rectangle.
#[derive(Debug, Clone, PartialEq, Eq)]
struct Node {
	rect: Rect,               // Area this node covers
	left: Option<Box<Self>>,  // Left child (if not leaf)
	right: Option<Box<Self>>, // Right child (if not leaf)
	room: Option<Rect>,       // Room created in this node (if leaf)
}

impl Node {
	const fn new(rect: Rect) -> Self {
		Self {
			rect,
			left: None,
			right: None,
			room: None,
		}
	}

	/// Try to split the node. Returns true if split happened.
	/// Splitting is done either horizontally or vertically,
	/// depending on the dimensions of the node.
	fn split(&mut self, rng: &mut DungeonRng) -> bool {
		// Already split
		if self.left.is_some() || self.right.is_some() {
			return false;
		}

		// Determine if we can split
		let can_split_h = self.rect.h >= (MIN_LEAF_SIZE * 2);
		let can_split_v = self.rect.w >= (MIN_LEAF_SIZE * 2);

		if !can_split_h && !can_split_v {
			return false;
		}

		// Choose orientation: prefer the longer side
		let split_h = match self.rect.w.cmp(&self.rect.h) {
			Ordering::Greater => false,
			Ordering::Less => true,
			Ordering::Equal => rng.random(),
		};

		// Choose split coordinate with margin so each side can contain a room
		if split_h {
			// horizontal split => choose y
			// avoid too close to borders of rect
			let min = cmp::max(
				self.rect.y + MIN_ROOM_SIZE + 1,
				self.rect.y + MIN_LEAF_SIZE + 1,
			);
			let max = cmp::min(
				self.rect.y + self.rect.h - MIN_ROOM_SIZE - 1,
				self.rect.y + self.rect.h - MIN_LEAF_SIZE - 1,
			);
			if max <= min {
				return false;
			}
			// Add some heterogeneity: choose random position between min..max
			let split_y = rng.random_range(min..=max);
			let top_h = split_y - self.rect.y;
			let bottom_h = self.rect.h - top_h;
			if top_h < MIN_LEAF_SIZE || bottom_h < MIN_LEAF_SIZE {
				return false;
			}

			let top = Rect::new(self.rect.x, self.rect.y, self.rect.w, top_h);
			let bottom = Rect::new(self.rect.x, split_y, self.rect.w, bottom_h);
			self.left = Some(Box::new(Self::new(top)));
			self.right = Some(Box::new(Self::new(bottom)));
		} else {
			// vertical split => choose x
			let min = cmp::max(
				self.rect.x + MIN_ROOM_SIZE + 1,
				self.rect.x + MIN_LEAF_SIZE + 1,
			);
			let max = cmp::min(
				self.rect.x + self.rect.w - MIN_ROOM_SIZE - 1,
				self.rect.x + self.rect.w - MIN_LEAF_SIZE - 1,
			);
			if max <= min {
				return false;
			}
			let split_x = rng.random_range(min..=max);
			let left_w = split_x - self.rect.x;
			let right_w = self.rect.w - left_w;
			if left_w < MIN_LEAF_SIZE || right_w < MIN_LEAF_SIZE {
				return false;
			}

			let left_rect = Rect::new(self.rect.x, self.rect.y, left_w, self.rect.h);
			let right_rect = Rect::new(split_x, self.rect.y, right_w, self.rect.h);
			self.left = Some(Box::new(Self::new(left_rect)));
			self.right = Some(Box::new(Self::new(right_rect)));
		}
		true
	}

	/// Create a room inside this node (called for leaves).
	/// Room size and position chosen randomly.
	fn create_room(&mut self, rng: &mut DungeonRng) {
		if self.left.is_some() || self.right.is_some() {
			// This is not a leaf
			if let Some(left) = &mut self.left {
				left.create_room(rng);
			}
			if let Some(right) = &mut self.right {
				right.create_room(rng);
			}
			return;
		}

		// Leaf: choose room size
		// Ensure room fits inside rect with at least 1 tile border to walls
		let max_w = (self.rect.w - 2).max(MIN_ROOM_SIZE);
		let max_h = (self.rect.h - 2).max(MIN_ROOM_SIZE);
		let room_w = rng.random_range(MIN_ROOM_SIZE..=max_w.min(MAX_ROOM_SIZE));
		let room_h = rng.random_range(MIN_ROOM_SIZE..=max_h.min(MAX_ROOM_SIZE));

		// Define a valid range for room position, leaving at least 1 tile border
		let x_range = (self.rect.x + 1)..=(self.rect.x + self.rect.w - 1 - room_w);
		let y_range = (self.rect.y + 1)..=(self.rect.y + self.rect.h - 1 - room_h);

		// Choose room position randomly within valid range
		let rx = rng.random_range(x_range);
		let ry = rng.random_range(y_range);

		self.room = Some(Rect::new(rx, ry, room_w, room_h));
	}

	/// Return a vector of references to all leaf nodes (in-order).
	fn collect_leaves<'a>(&'a self, out: &mut Vec<&'a Self>) {
		if self.left.is_none() && self.right.is_none() {
			out.push(self);
			return;
		}
		if let Some(left) = &self.left {
			left.collect_leaves(out);
		}
		if let Some(right) = &self.right {
			right.collect_leaves(out);
		}
	}

	/// Return the "room center" for this subtree: if node has a room, return its center,
	/// else try left then right.
	fn room_center(&self) -> Pos {
		// Base case: if this node has a room, return its center
		if let Some(room) = &self.room {
			return room.center();
		}
		if let Some(left) = &self.left {
			return left.room_center();
		}
		if let Some(right) = &self.right {
			return right.room_center();
		}
		// Fallback (should not happen)
		panic!("No room found in subtree");
	}

	/// Return a random point for a room in this subtree:
	/// if node has a room, return a randiom point in it, else try left then right.
	fn random_point_in_room(&self, rng: &mut DungeonRng) -> Pos {
		// Base case: if this node has a room, return a random point in it
		if let Some(room) = &self.room {
			return room.random_point(rng);
		}
		if let Some(left) = &self.left {
			return left.random_point_in_room(rng);
		}
		if let Some(right) = &self.right {
			return right.random_point_in_room(rng);
		}
		// Fallback (should not happen)
		panic!("No room found in subtree");
	}

	/// Connect rooms of child nodes recursively and collect corridors to carve.
	/// returns corridors: output vector of (Pos, Pos) pairs to connect
	fn connect_children(&self, rng: &mut DungeonRng) -> Vec<(Pos, Pos)> {
		let mut corridors = Vec::new();

		if let (Some(left), Some(right)) = (&self.left, &self.right) {
			// Get a random point in each child's room
			let left_point = left.random_point_in_room(rng);
			let right_point = right.random_point_in_room(rng);
			corridors.push((left_point, right_point));

			// Recursively connect children
			let mut left_corridors = left.connect_children(rng);
			let mut right_corridors = right.connect_children(rng);
			corridors.append(&mut left_corridors);
			corridors.append(&mut right_corridors);
		}

		corridors
	}
}

/// Carve a room rectangle into the map (tile array) by setting tiles inside to Room.
fn carve_room(tiles: &mut [Tile; TILE_COUNT], room: Rect) {
	for y in room.y..(room.y + room.h) {
		for x in room.x..(room.x + room.w) {
			let idx = x + y * MAP_SIZE;
			tiles[idx as usize] = Tile::Room;
		}
	}
}

/// Carve a horizontal corridor from x1..=x2 at y (inclusive)
fn carve_h_corridor(tiles: &mut [Tile; TILE_COUNT], x1: u16, x2: u16, y: u16) {
	let (sx, ex) = if x1 <= x2 { (x1, x2) } else { (x2, x1) };
	for x in sx..=ex {
		let idx = x + y * MAP_SIZE;
		// Don't carve if it's already a room
		if tiles[idx as usize] == Tile::Room {
			continue;
		}
		tiles[idx as usize] = Tile::Hallway;
	}
}

/// Carve a vertical corridor from y1..=y2 at x (inclusive)
fn carve_v_corridor(tiles: &mut [Tile; TILE_COUNT], y1: u16, y2: u16, x: u16) {
	let (sy, ey) = if y1 <= y2 { (y1, y2) } else { (y2, y1) };
	for y in sy..=ey {
		let idx = x + y * MAP_SIZE;
		// Don't carve if it's already a room
		if tiles[idx as usize] == Tile::Room {
			continue;
		}
		tiles[idx as usize] = Tile::Hallway;
	}
}

/// Top-level generator function for the dungeon using BSP.
/// Returns a `Floor`
pub fn generate(rng: &mut DungeonRng) -> Floor {
	// Initialize all tiles to walls
	let mut tiles_box: Box<[Tile; TILE_COUNT]> = Box::new([Tile::Wall; TILE_COUNT]);

	// Rooms and coorridors will be carved as `Air` into the tile array.
	// Build root rect (whole map)
	let root_rect = Rect::new(0, 0, MAP_SIZE, MAP_SIZE);
	let mut root = Node::new(root_rect);

	// Repeatedly try splitting nodes to produce the tree.
	// Collect leaves and try to split them until no splits happen or we reach a cap.
	// Number of splits proportional to map size to avoid infinite loops.
	let max_attempts = 2000usize;
	let mut attempts = 0usize;
	while attempts < max_attempts {
		attempts += 1;

		// Collect mutable references to current leaves
		let mut leaves = vec![];
		{
			// Collect leaves with a stack
			let mut stack = vec![&mut root];
			while let Some(node) = stack.pop() {
				if node.left.is_none() && node.right.is_none() {
					leaves.push(node);
				} else {
					if let Some(left) = &mut node.left {
						stack.push(left);
					}
					if let Some(right) = &mut node.right {
						stack.push(right);
					}
				}
			}
		}

		let mut splitted_any = false;

		// Try splitting each leaf in order
		for node_ptr in &mut leaves {
			// Attempt to split if possible
			if node_ptr.split(rng) {
				splitted_any = true;
			}
		}

		// If no splits happened, we're done
		if !splitted_any {
			break;
		}
	}

	// Create rooms in all leaves
	root.create_room(rng);

	// Carve all rooms into the tile array
	let mut leaves = vec![];
	root.collect_leaves(&mut leaves);
	for leaf in &leaves {
		if let Some(room) = leaf.room {
			carve_room(&mut tiles_box, room);
		}
	}

	// Collect corridors (pairs of centers) by connecting children bottom-up
	let corridors = root.connect_children(rng);

	// Carve corridors. For each corridor (x1,y1,x2,y2), carve straight or L-shape.
	for (left_point, right_point) in corridors {
		let (x1, y1) = (left_point.xy().0, left_point.xy().1);
		let (x2, y2) = (right_point.xy().0, right_point.xy().1);
		// If aligned horizontally or vertically, carve straight
		if x1 == x2 {
			carve_v_corridor(&mut tiles_box, y1, y2, x1);
		} else if y1 == y2 {
			carve_h_corridor(&mut tiles_box, x1, x2, y1);
		} else {
			// Choose whether to go horizontal then vertical or vertical then horizontal
			if rng.random_bool(0.5) {
				carve_h_corridor(&mut tiles_box, x1, x2, y1);
				carve_v_corridor(&mut tiles_box, y1, y2, x2);
			} else {
				carve_v_corridor(&mut tiles_box, y1, y2, x1);
				carve_h_corridor(&mut tiles_box, x1, x2, y2);
			}
		}
	}

	// Choose player start randomly in the center of one of the rooms (leaf nodes)
	let mut leaves = vec![];
	root.collect_leaves(&mut leaves);
	let player_room = leaves.choose(rng).unwrap_or(&leaves[0]);
	let player_start = player_room.room_center();

	// Set one tile to Stairs (exit) in a random room different from player start
	let mut exit_room = player_room;
	while exit_room == player_room {
		exit_room = leaves.choose(rng).unwrap_or(&leaves[0]);
	}
	let exit_pos = exit_room.room_center();
	let exit_idx = exit_pos.xy().0 + exit_pos.xy().1 * MAP_SIZE;
	tiles_box[exit_idx as usize] = Tile::Stairs;

	// Return components turned into a `Floor`
	Floor::new(tiles_box, player_start)
}

/// BSP Unit Tests
#[cfg(test)]
mod tests {
	use rand::SeedableRng;

	use super::*;
	use crate::map::MAP_SIZE;

	#[test]
	fn test_rect_center() {
		let rect = Rect::new(2, 2, 4, 4);
		let center = rect.center();
		assert_eq!(center.xy().0, 4);
		assert_eq!(center.xy().1, 4);
	}

	#[test]
	fn test_node_split() {
		let rect = Rect::new(0, 0, 20, 20);
		let mut node = Node::new(rect);
		let mut rng = DungeonRng::seed_from_u64(12345);
		let splitted = node.split(&mut rng);
		assert!(splitted);
		assert!(node.left.is_some());
		assert!(node.right.is_some());
	}

	#[test]
	fn test_node_create_room() {
		let rect = Rect::new(0, 0, 20, 20);
		let mut node = Node::new(rect);
		let mut rng = DungeonRng::seed_from_u64(12345);
		node.create_room(&mut rng);
		assert!(node.room.is_some());
		match &node.room {
			Some(room) => {
				assert!(room.w >= MIN_ROOM_SIZE && room.h >= MIN_ROOM_SIZE);
				assert!(room.x >= 1 && room.y >= 1);
				assert!(room.x + room.w < MAP_SIZE);
				assert!(room.y + room.h < MAP_SIZE);
			}
			None => self::panic!("Room should exist"),
		}
	}

	#[test]
	fn test_node_collect_leaves() {
		let rect = Rect::new(0, 0, 20, 20);
		let mut node = Node::new(rect);
		let mut rng = DungeonRng::seed_from_u64(12345);
		node.split(&mut rng);
		let mut leaves = Vec::new();
		node.collect_leaves(&mut leaves);
		assert!(!leaves.is_empty());
	}

	#[test]
	fn test_node_connect_children() {
		let rect = Rect::new(0, 0, 20, 20);
		let mut node = Node::new(rect);
		let mut rng = DungeonRng::seed_from_u64(12345);
		node.split(&mut rng);
		node.create_room(&mut rng);
		let corridors = node.connect_children(&mut rng);
		assert!(!corridors.is_empty());
	}

	#[test]
	fn test_generate() {
		let seed = 12345u64;
		let mut rng = DungeonRng::seed_from_u64(seed);
		let floor = generate(&mut rng);
		// Check that tiles contain some Room tiles
		let room_count = floor.tiles().iter().filter(|&&t| t == Tile::Room).count();
		assert!(room_count > 0);
		// Check that player_start is within bounds
		assert!(floor.player_start().xy().0 < MAP_SIZE);
		assert!(floor.player_start().xy().1 < MAP_SIZE);
	}
}