extends Node2D

const GRID_WIDTH: int = 10
const GRID_HEIGHT: int = 10
const ITEM_SIZE: int = 2
const GRID_SIZE: int = GRID_WIDTH * GRID_HEIGHT

var inventory: PackedInt32Array = PackedInt32Array()
var availability_mask: PackedInt64Array = PackedInt64Array()
var item_positions: Dictionary = {}

func _ready() -> void:
	initialize_worst_case_inventory()
	print_grid()

func initialize_worst_case_inventory() -> void:
	inventory.resize(GRID_SIZE)
	inventory.fill(1)
	availability_mask.resize((GRID_HEIGHT - ITEM_SIZE + 1) * (GRID_WIDTH - ITEM_SIZE + 1) / 64 + 1)
	availability_mask.fill(0)

	var empty_x: int = GRID_WIDTH - ITEM_SIZE
	var empty_y: int = GRID_HEIGHT - ITEM_SIZE
	var start_index: int = calculate_index(empty_x, empty_y)
	for dy in range(ITEM_SIZE):
		var row_start: int = start_index + dy * GRID_WIDTH
		for dx in range(ITEM_SIZE):
			inventory[row_start + dx] = 0
	update_availability_mask(empty_x, empty_y, true)

func benchmark_find_space(iterations: int) -> float:
	var start_time: float = Time.get_ticks_usec()

	for _i in range(iterations):
		find_next_available_space()

	var elapsed_time: float = (Time.get_ticks_usec() - start_time) / 1_000_000.0
	print("GDScript: Find space benchmark (%d iterations) took %.6f seconds" % [iterations, elapsed_time])
	return elapsed_time

func find_next_available_space() -> Vector2i:
	for i in range(availability_mask.size()):
		var mask: int = availability_mask[i]
		if mask != 0:
			var bit: int = 0
			while (mask & (1 << bit)) == 0:
				bit += 1
			var position: int = i * 64 + bit
			var y: int = position / (GRID_WIDTH - ITEM_SIZE + 1)
			var x: int = position % (GRID_WIDTH - ITEM_SIZE + 1)
			return Vector2i(x, y)
	return Vector2i(-1, -1)

func update_availability_mask(x: int, y: int, available: bool) -> void:
	var index: int = y * (GRID_WIDTH - ITEM_SIZE + 1) + x
	var mask_index: int = index >> 6
	var bit_index: int = index & 63
	if available:
		availability_mask[mask_index] |= (1 << bit_index)
	else:
		availability_mask[mask_index] &= ~(1 << bit_index)

func calculate_index(x: int, y: int) -> int:
	return y * GRID_WIDTH + x

func print_grid() -> void:
	print("GDScript Grid:")
	for y in range(GRID_HEIGHT):
		var row: String = ""
		var start_index: int = y * GRID_WIDTH
		for x in range(GRID_WIDTH):
			row += "□ " if inventory[start_index + x] == 0 else "■ "
		print(row)
	print("")

func initialize_inventory_for_sorting() -> void:
	inventory.fill(0)
	availability_mask.fill(~0)
	item_positions.clear()

	var items: PackedInt32Array = PackedInt32Array([1, 2, 3, 4, 5])
	var positions: PackedVector2Array = PackedVector2Array([Vector2i(2, 2), Vector2i(5, 1), Vector2i(1, 5), Vector2i(7, 6), Vector2i(4, 8)])

	for i in range(items.size()):
		place_item(items[i], positions[i].x, positions[i].y)

func place_item(item: int, x: int, y: int) -> void:
	var start: int = calculate_index(x, y)
	for dy in range(ITEM_SIZE):
		var row_start: int = start + dy * GRID_WIDTH
		for dx in range(ITEM_SIZE):
			inventory[row_start + dx] = item
	update_availability_mask(x, y, false)
	item_positions[item] = Vector2i(x, y)

func benchmark_sort_inventory(iterations: int) -> float:
	var start_time: float = Time.get_ticks_usec()

	for _i in range(iterations):
		sort_inventory()

	var elapsed_time: float = (Time.get_ticks_usec() - start_time) / 1_000_000.0
	print("GDScript: Sort inventory benchmark (%d iterations) took %.6f seconds" % [iterations, elapsed_time])
	return elapsed_time

func sort_inventory() -> void:
	var items: Array = item_positions.keys()
	items.sort()

	inventory.fill(0)
	availability_mask.fill(~0)

	for item in items:
		var new_pos: Vector2i = find_next_available_space()
		if new_pos.x != -1 and new_pos.y != -1:
			place_item(item, new_pos.x, new_pos.y)

func print_inventory_for_sorting() -> void:
	print("GDScript Inventory Before Sorting:")
	print_grid()
	sort_inventory()
	print("GDScript Inventory After Sorting:")
	print_grid()