from flask import request, jsonify
import logging
from routes import app
import re
from collections import deque


logger = logging.getLogger(__name__)
from copy import deepcopy
import sys
import threading

# Set recursion limit higher to prevent maximum recursion depth exceeded error
sys.setrecursionlimit(100000)

from flask import Flask, request, jsonify
from copy import deepcopy

import sys
import threading
from collections import deque

# Set recursion limit higher to prevent maximum recursion depth exceeded error
sys.setrecursionlimit(100000)

@app.route('/parkinglot', methods=['POST'])

def parking_lot():
    test_cases = request.get_json()
    responses = []

    for test_case in test_cases:
        response = process_test_case(test_case)
        responses.append(response)

    return jsonify(responses)


def process_test_case(test_case):
    minimum_total_fare = test_case["minimumTotalFare"]
    vehicles_info = {v["plateNumber"]: v for v in test_case["vehicles"]}
    actions = test_case["actions"]
    parking_lot = test_case["parkingLot"]

    # Initialize parking lot state
    parking_lot_state = ParkingLot(parking_lot)

    # Keep track of parked vehicles and their positions
    parked_vehicles = {}
    total_fare_collected = 0

    # Prepare the response actions
    response_actions = []

    # Sort vehicles by parking fare descending to prioritize higher fares
    vehicles_by_fare = sorted(vehicles_info.values(), key=lambda v: -v["parkingFare"])
    vehicles_parked = set()

    for action in actions:
        plate_number = action["plateNumber"]
        vehicle_action = action["action"]

        vehicle_info = vehicles_info[plate_number]

        if vehicle_action == "park":
            # If we need more fare, try to park the vehicle
            if total_fare_collected < minimum_total_fare:
                if plate_number not in vehicles_parked:
                    # Try to find a parking position
                    position = parking_lot_state.find_parking_position(vehicle_info)
                    if position:
                        # Park the vehicle
                        parking_lot_state.place_vehicle(vehicle_info, position)
                        parked_vehicles[plate_number] = (vehicle_info, position)
                        vehicles_parked.add(plate_number)
                        response_actions.append({
                            "plateNumber": plate_number,
                            "action": "park",
                            "execute": True,
                            "position": {
                                "x": position.x,
                                "y": position.y,
                                "direction": position.direction
                            }
                        })
                    else:
                        # Cannot park the vehicle
                        response_actions.append({
                            "plateNumber": plate_number,
                            "action": "park",
                            "execute": False,
                            "position": None
                        })
                else:
                    # Vehicle already parked
                    response_actions.append({
                        "plateNumber": plate_number,
                        "action": "park",
                        "execute": False,
                        "position": None
                    })
            else:
                # Already met minimum fare, skip parking
                response_actions.append({
                    "plateNumber": plate_number,
                    "action": "park",
                    "execute": False,
                    "position": None
                })

        elif vehicle_action == "exit":
            if plate_number in parked_vehicles:
                vehicle_info, position = parked_vehicles[plate_number]
                # Try to find a path to exit
                can_exit = parking_lot_state.can_exit_vehicle(vehicle_info, position)
                if can_exit:
                    # Remove the vehicle
                    parking_lot_state.remove_vehicle(vehicle_info, position)
                    total_fare_collected += vehicle_info["parkingFare"]
                    del parked_vehicles[plate_number]
                    response_actions.append({
                        "plateNumber": plate_number,
                        "action": "exit",
                        "execute": True,
                        "position": {
                            "x": position.x,
                            "y": position.y,
                            "direction": position.direction
                        }
                    })
                else:
                    # Cannot exit the vehicle
                    response_actions.append({
                        "plateNumber": plate_number,
                        "action": "exit",
                        "execute": False,
                        "position": None
                    })
            else:
                # Vehicle is not parked
                response_actions.append({
                    "plateNumber": plate_number,
                    "action": "exit",
                    "execute": False,
                    "position": None
                })
        else:
            # Unknown action, skip
            response_actions.append({
                "plateNumber": plate_number,
                "action": vehicle_action,
                "execute": False,
                "position": None
            })

    return {
        "actions": response_actions
    }


class ParkingLot:
    def __init__(self, parking_lot_map):
        self.map = parking_lot_map
        self.height = len(parking_lot_map)
        self.width = len(parking_lot_map[0]) if self.height > 0 else 0

        self.walls = set()
        self.entrances = set()
        self.exits = set()
        self.occupied = set()

        # Parse the parking lot map
        for y in range(self.height):
            for x in range(self.width):
                cell = parking_lot_map[y][x]
                if cell == 'X':
                    self.walls.add((x, y))
                elif cell == 'I':
                    self.entrances.add((x, y))
                elif cell == 'O':
                    self.exits.add((x, y))
                # Initialize occupied cells (walls, entrances, exits)
                if cell != ' ':
                    self.occupied.add((x, y))

    def find_parking_position(self, vehicle_info):
        # Try to find a valid parking position adjacent to an entrance
        for entrance in self.entrances:
            ex, ey = entrance
            possible_directions = []
            if ex == 0:
                possible_directions.append('EAST')
            if ey == 0:
                possible_directions.append('SOUTH')

            for direction in possible_directions:
                dx, dy = self.direction_to_delta(direction)
                for step in range(1, max(self.width, self.height)):
                    nx, ny = ex + dx * step, ey + dy * step
                    position = Position(nx, ny, direction)
                    if self.is_valid_parking_position(vehicle_info, position):
                        return position
        return None

    def is_valid_parking_position(self, vehicle_info, position):
        occupied_cells = self.get_vehicle_cells(vehicle_info, position)
        # Cannot park on walls, entrances, exits, or occupied cells
        for cell in occupied_cells:
            if cell in self.walls or cell in self.occupied or cell in self.entrances or cell in self.exits:
                return False
        # Check boundaries
        for cell in occupied_cells:
            if not (0 <= cell[0] < self.width and 0 <= cell[1] < self.height):
                return False
        return True

    def get_vehicle_cells(self, vehicle_info, position):
        length = vehicle_info["length"]
        width = vehicle_info["width"]
        x = position.x
        y = position.y
        direction = position.direction

        cells = []
        if direction == 'NORTH':
            for dx in range(width):
                for dy in range(length):
                    cells.append((x + dx, y - dy))
        elif direction == 'SOUTH':
            for dx in range(width):
                for dy in range(length):
                    cells.append((x + dx, y + dy))
        elif direction == 'EAST':
            for dx in range(length):
                for dy in range(width):
                    cells.append((x + dx, y + dy))
        elif direction == 'WEST':
            for dx in range(length):
                for dy in range(width):
                    cells.append((x - dx, y + dy))
        return cells

    def place_vehicle(self, vehicle_info, position):
        occupied_cells = self.get_vehicle_cells(vehicle_info, position)
        for cell in occupied_cells:
            self.occupied.add(cell)

    def remove_vehicle(self, vehicle_info, position):
        occupied_cells = self.get_vehicle_cells(vehicle_info, position)
        for cell in occupied_cells:
            if cell in self.occupied:
                self.occupied.remove(cell)

    def can_exit_vehicle(self, vehicle_info, position):
        # Check if vehicle can exit directly from its position without collisions
        possible_directions = []
        if position.x + vehicle_info["length"] <= self.width - 1:
            possible_directions.append('EAST')
        if position.y + vehicle_info["length"] <= self.height - 1:
            possible_directions.append('SOUTH')

        for exit_point in self.exits:
            ex, ey = exit_point
            if position.direction == 'EAST' and ex == self.width - 1:
                return True
            if position.direction == 'SOUTH' and ey == self.height - 1:
                return True
        return False

    def direction_to_delta(self, direction):
        if direction == 'NORTH':
            return (0, -1)
        elif direction == 'SOUTH':
            return (0, 1)
        elif direction == 'EAST':
            return (1, 0)
        elif direction == 'WEST':
            return (-1, 0)

class Position:
    def __init__(self, x, y, direction):
        self.x = x
        self.y = y
        self.direction = direction