backend/app/services/parser.py

"""Parser service for initial state and traffic strings."""
from typing import Tuple, List
from ..models.grid import Grid
from ..models.entities import Store, Destination, Tunnel
from ..models.state import SearchState


def parse_initial_state(initial_state: str) -> Tuple[int, int, List[Store], List[Destination], List[Tunnel]]:
    """
    Parse the initial state string.

    Format:
    m;n;P;S;CustomerX_1,CustomerY_1,CustomerX_2,CustomerY_2,...;
    TunnelX_1,TunnelY_1,TunnelX_1',TunnelY_1',TunnelX_2,TunnelY_2,TunnelX_2',TunnelY_2',...

    Args:
        initial_state: The initial state string

    Returns:
        Tuple of (width, height, stores, destinations, tunnels)
    """
    parts = initial_state.strip().split(';')

    # Grid dimensions
    width = int(parts[0])  # m
    height = int(parts[1])  # n

    # Number of packages/customers and stores
    num_packages = int(parts[2])  # P
    num_stores = int(parts[3])  # S

    # Parse customer locations
    destinations: List[Destination] = []
    if len(parts) > 4 and parts[4]:
        customer_coords = parts[4].split(',')
        for i in range(0, len(customer_coords), 2):
            if i + 1 < len(customer_coords):
                x = int(customer_coords[i])
                y = int(customer_coords[i + 1])
                dest_id = len(destinations) + 1
                destinations.append(Destination(id=dest_id, position=(x, y)))

    # Parse tunnel locations
    tunnels: List[Tunnel] = []
    if len(parts) > 5 and parts[5]:
        tunnel_coords = parts[5].split(',')
        for i in range(0, len(tunnel_coords), 4):
            if i + 3 < len(tunnel_coords):
                x1 = int(tunnel_coords[i])
                y1 = int(tunnel_coords[i + 1])
                x2 = int(tunnel_coords[i + 2])
                y2 = int(tunnel_coords[i + 3])
                tunnels.append(Tunnel(entrance1=(x1, y1), entrance2=(x2, y2)))

    # Generate stores (positions need to be provided or generated)
    # For now, place stores at corners/edges
    stores: List[Store] = []
    store_positions = _generate_store_positions(width, height, num_stores, destinations, tunnels)
    for i, pos in enumerate(store_positions):
        stores.append(Store(id=i + 1, position=pos))

    return width, height, stores, destinations, tunnels


def _generate_store_positions(
    width: int,
    height: int,
    num_stores: int,
    destinations: List[Destination],
    tunnels: List[Tunnel]
) -> List[Tuple[int, int]]:
    """
    Generate store positions avoiding conflicts.

    Places stores at corners and edges of the grid.
    """
    occupied = set()
    for dest in destinations:
        occupied.add(dest.position)
    for tunnel in tunnels:
        occupied.add(tunnel.entrance1)
        occupied.add(tunnel.entrance2)

    # Preferred positions (corners first, then edges)
    preferred = [
        (0, 0),
        (width - 1, 0),
        (0, height - 1),
        (width - 1, height - 1),
        (width // 2, 0),
        (0, height // 2),
        (width - 1, height // 2),
        (width // 2, height - 1),
    ]

    positions = []
    for pos in preferred:
        if pos not in occupied and len(positions) < num_stores:
            positions.append(pos)
            occupied.add(pos)

    # If still need more positions, find any valid position
    if len(positions) < num_stores:
        for x in range(width):
            for y in range(height):
                if (x, y) not in occupied and len(positions) < num_stores:
                    positions.append((x, y))
                    occupied.add((x, y))

    return positions


def parse_traffic(traffic_str: str, width: int, height: int) -> Grid:
    """
    Parse the traffic string and create a Grid.

    Format:
    SrcX_1,SrcY_1,DstX_1,DstY_1,Traffic_1;SrcX_2,SrcY_2,DstX_2,DstY_2,Traffic_2;...

    Args:
        traffic_str: Traffic string
        width: Grid width
        height: Grid height

    Returns:
        Grid with traffic information
    """
    grid = Grid(width=width, height=height)

    if not traffic_str:
        # Initialize all segments with default traffic level 1
        _initialize_default_traffic(grid)
        return grid

    segments = traffic_str.strip().split(';')
    for segment in segments:
        if not segment:
            continue
        parts = segment.split(',')
        if len(parts) >= 5:
            src_x = int(parts[0])
            src_y = int(parts[1])
            dst_x = int(parts[2])
            dst_y = int(parts[3])
            traffic = int(parts[4])
            grid.add_segment((src_x, src_y), (dst_x, dst_y), traffic)

    return grid


def _initialize_default_traffic(grid: Grid, default_traffic: int = 1) -> None:
    """
    Initialize all grid segments with default traffic.

    Creates horizontal and vertical segments between adjacent cells.
    """
    for x in range(grid.width):
        for y in range(grid.height):
            # Horizontal segment (right)
            if x + 1 < grid.width:
                grid.add_segment((x, y), (x + 1, y), default_traffic)
            # Vertical segment (up)
            if y + 1 < grid.height:
                grid.add_segment((x, y), (x, y + 1), default_traffic)


def parse_full_state(initial_state: str, traffic_str: str) -> SearchState:
    """
    Parse both initial state and traffic into a complete SearchState.

    Args:
        initial_state: Initial state string
        traffic_str: Traffic string

    Returns:
        Complete SearchState object
    """
    width, height, stores, destinations, tunnels = parse_initial_state(initial_state)
    grid = parse_traffic(traffic_str, width, height)

    return SearchState(
        grid=grid,
        stores=stores,
        destinations=destinations,
        tunnels=tunnels
    )


def format_initial_state(
    width: int,
    height: int,
    stores: List[Store],
    destinations: List[Destination],
    tunnels: List[Tunnel]
) -> str:
    """
    Format state back into initial state string.

    Args:
        width: Grid width
        height: Grid height
        stores: List of stores
        destinations: List of destinations
        tunnels: List of tunnels

    Returns:
        Formatted initial state string
    """
    parts = [
        str(width),
        str(height),
        str(len(destinations)),
        str(len(stores)),
    ]

    # Customer coordinates
    customer_coords = []
    for dest in destinations:
        customer_coords.extend([str(dest.position[0]), str(dest.position[1])])
    parts.append(','.join(customer_coords))

    # Tunnel coordinates
    tunnel_coords = []
    for tunnel in tunnels:
        tunnel_coords.extend([
            str(tunnel.entrance1[0]), str(tunnel.entrance1[1]),
            str(tunnel.entrance2[0]), str(tunnel.entrance2[1])
        ])
    parts.append(','.join(tunnel_coords))

    return ';'.join(parts)


def format_traffic(grid: Grid) -> str:
    """
    Format grid traffic into traffic string.

    Args:
        grid: Grid with traffic information

    Returns:
        Formatted traffic string
    """
    segments = []
    for (src, dst), segment in grid.segments.items():
        segments.append(
            f"{src[0]},{src[1]},{dst[0]},{dst[1]},{segment.traffic}"
        )
    return ';'.join(segments)