"""
AutoPOE2 - Vertical Column-Major Inventory Packer & Auto-Sort Engine (Doc 63 SSoT)
===================================================================================
Thuật toán sắp xếp túi đồ và rương đồ thông minh theo Chiều Dọc (Column-Major Packing):
- Khắc phục triệt để hiện tượng phân mảnh không gian (Fragmentation) khi xếp đồ theo chiều ngang.
- Gom toàn bộ đồ nhỏ 1x1 (Currency, Gems, Waystones, Charms, Rings, Amulets) dồn về các cột bên phải (Cột 11 dồn sang 10...).
- Bảo toàn trọn vẹn các cột dọc bên trái (Cột 0..9) với chiều cao nguyên vẹn (5 hàng) để chứa các trang bị lớn:
  + Áo giáp (Body Armour: 2x3)
  + Vũ khí 2 tay (Quarterstaff, Bow, Crossbow: 2x4 hoặc 2x6)
  + Mũ, Giày, Găng tay, Khiên (2x2)
- Cung cấp kế hoạch di chuyển từng bước (MovePlan) tối thiểu hóa số lần click chuột.
"""

from dataclasses import dataclass, field
from enum import Enum
from typing import Any, Dict, List, Optional, Set, Tuple


class ItemDimension(Enum):
    SIZE_1X1 = (1, 1)  # Currency, Waystone, Gem, Ring, Amulet, Charm
    SIZE_1X2 = (1, 2)  # Belt, Wand
    SIZE_2X2 = (2, 2)  # Helmet, Boots, Gloves, Small Shield
    SIZE_2X3 = (2, 3)  # Body Armour, Shield, 1H Weapon
    SIZE_2X4 = (2, 4)  # 2H Quarterstaff, Bow, Crossbow, 2H Axe


@dataclass
class InventoryItemSlot:
    item_id: str
    name: str
    col: int
    row: int
    width: int = 1
    height: int = 1
    is_locked: bool = False  # True nếu người chơi khóa không cho di chuyển


@dataclass
class SlotMoveAction:
    item_id: str
    from_col: int
    from_row: int
    to_col: int
    to_row: int
    description: str = ""


class VerticalInventoryPacker:
    """
    Bộ sắp xếp túi đồ và rương đồ tối ưu hóa không gian dọc cho Path of Exile 2.
    """

    def __init__(self, cols: int = 12, rows: int = 5):
        self.cols = cols
        self.rows = rows

    def calculate_free_blocks(self, grid_occupancy: List[List[bool]]) -> List[Tuple[int, int, int, int]]:
        """
        Tìm kiếm các khối hình chữ nhật còn trống trong lưới.
        Trả về danh sách: [(col, row, width, height), ...]
        """
        blocks = []
        # Quét các khối có thể chứa đồ 2x4 và 2x3
        for c in range(self.cols - 1):
            for r in range(self.rows):
                # Kiểm tra khối 2x4
                if r + 4 <= self.rows:
                    if not any(grid_occupancy[r + dr][c + dc] for dr in range(4) for dc in range(2)):
                        blocks.append((c, r, 2, 4))
                # Kiểm tra khối 2x3
                if r + 3 <= self.rows:
                    if not any(grid_occupancy[r + dr][c + dc] for dr in range(3) for dc in range(2)):
                        blocks.append((c, r, 2, 3))
        return blocks

    def plan_vertical_sort(
        self, items: List[InventoryItemSlot]
    ) -> List[SlotMoveAction]:
        """
        Lập kế hoạch di chuyển item theo thuật toán Vertical Column-Major Packing:
        1. Phân loại item thành 2 nhóm:
           - Nhóm Small (1x1, 1x2): Dồn vào các cột ngoài cùng bên phải (Cột 11 -> 0, hàng 0 -> 4).
           - Nhóm Large (2x2, 2x3, 2x4): Dồn vào các cột bên trái (Cột 0 -> 11, hàng 0 -> 4).
        2. Sinh danh sách các thao tác di chuyển SlotMoveAction tránh đè lên nhau.
        """
        small_items = []
        large_items = []

        for it in items:
            if it.width == 1 and it.height == 1:
                small_items.append(it)
            else:
                large_items.append(it)

        # Lưới mô phỏng vị trí đích (Target Grid)
        target_grid = [[False for _ in range(self.cols)] for _ in range(self.rows)]
        actions: List[SlotMoveAction] = []

        # 1. Định vị các item lớn ở bên trái theo chiều dọc (Column-Major Left-to-Right)
        curr_large_col = 0
        curr_large_row = 0

        # Sắp xếp item lớn theo chiều cao giảm dần (2x4 trước, rồi 2x3, 2x2)
        large_items.sort(key=lambda x: (x.height, x.width), reverse=True)

        for it in large_items:
            placed = False
            for c in range(0, self.cols - it.width + 1):
                for r in range(0, self.rows - it.height + 1):
                    # Kiểm tra ô đích có trống không
                    if not any(target_grid[r + dr][c + dc] for dr in range(it.height) for dc in range(it.width)):
                        # Chiếm chỗ
                        for dr in range(it.height):
                            for dc in range(it.width):
                                target_grid[r + dr][c + dc] = True

                        if it.col != c or it.row != r:
                            actions.append(SlotMoveAction(
                                item_id=it.item_id,
                                from_col=it.col,
                                from_row=it.row,
                                to_col=c,
                                to_row=r,
                                description=f"Dồn item lớn {it.name} ({it.width}x{it.height}) sang cột dọc ({c}, {r})"
                            ))
                        placed = True
                        break
                if placed:
                    break

        # 2. Định vị các item 1x1 từ cột ngoài cùng bên phải dồn sang trái (Right-to-Left, Top-to-Bottom)
        small_col = self.cols - 1
        small_row = 0

        for it in small_items:
            # Tìm ô trống gần nhất từ bên phải
            found = False
            while small_col >= 0 and not found:
                while small_row < self.rows and not found:
                    if not target_grid[small_row][small_col]:
                        target_grid[small_row][small_col] = True
                        if it.col != small_col or it.row != small_row:
                            actions.append(SlotMoveAction(
                                item_id=it.item_id,
                                from_col=it.col,
                                from_row=it.row,
                                to_col=small_col,
                                to_row=small_row,
                                description=f"Gom đồ 1x1 {it.name} về cột phải ({small_col}, {small_row})"
                            ))
                        found = True
                    small_row += 1
                if not found:
                    small_row = 0
                    small_col -= 1

        return actions