"""Tests for search algorithms (BFS, DFS, UCS, A*, Greedy, IDS)."""

import pytest
from app.algorithms.bfs import bfs_search
from app.algorithms.dfs import dfs_search
from app.algorithms.ucs import ucs_search
from app.algorithms.astar import astar_search
from app.algorithms.greedy import greedy_search
from app.algorithms.ids import ids_search
from app.heuristics import manhattan_heuristic, euclidean_heuristic
from app.core.delivery_search import DeliverySearch
from app.models.grid import Grid


class TestBFS:
    """Tests for Breadth-First Search."""

    def test_bfs_finds_path(self, simple_grid):
        """Test BFS finds a path."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])
        result, steps = bfs_search(search, visualize=False)

        assert result.plan != ""
        assert result.cost < float("inf")
        assert len(result.path) > 0
        assert result.path[0] == (0, 0)
        assert result.path[-1] == (2, 2)

    def test_bfs_shortest_path(self, simple_grid):
        """Test BFS finds shortest path by steps."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])
        result, _ = bfs_search(search, visualize=False)

        # BFS should find path with minimum steps
        # From (0,0) to (2,2) needs at least 4 steps
        assert len(result.path) == 5  # 5 nodes including start and end

    def test_bfs_no_path(self):
        """Test BFS when no path exists."""
        grid = Grid(width=3, height=3)
        # Create disconnected grid - only add vertical segment
        grid.add_segment((0, 0), (0, 1), 1)

        search = DeliverySearch(grid, (0, 0), (2, 2), [])
        result, _ = bfs_search(search, visualize=False)

        assert result.plan == ""
        assert result.cost == float("inf")
        assert len(result.path) == 0

    def test_bfs_same_start_goal(self, simple_grid):
        """Test BFS when start equals goal."""
        search = DeliverySearch(simple_grid, (1, 1), (1, 1), [])
        result, _ = bfs_search(search, visualize=False)

        assert result.cost == 0
        assert len(result.path) == 1
        assert result.path[0] == (1, 1)

    def test_bfs_visualization(self, simple_grid):
        """Test BFS with visualization enabled."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])
        result, steps = bfs_search(search, visualize=True)

        assert steps is not None
        assert len(steps) > 0
        # First step should have start node
        assert steps[0].current_node == (0, 0)


class TestDFS:
    """Tests for Depth-First Search."""

    def test_dfs_finds_path(self, simple_grid):
        """Test DFS finds a path."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])
        result, steps = dfs_search(search, visualize=False)

        assert result.plan != ""
        assert result.cost < float("inf")
        assert len(result.path) > 0
        assert result.path[0] == (0, 0)
        assert result.path[-1] == (2, 2)

    def test_dfs_no_path(self):
        """Test DFS when no path exists."""
        grid = Grid(width=3, height=3)
        grid.add_segment((0, 0), (0, 1), 1)

        search = DeliverySearch(grid, (0, 0), (2, 2), [])
        result, _ = dfs_search(search, visualize=False)

        assert result.plan == ""
        assert result.cost == float("inf")

    def test_dfs_same_start_goal(self, simple_grid):
        """Test DFS when start equals goal."""
        search = DeliverySearch(simple_grid, (1, 1), (1, 1), [])
        result, _ = dfs_search(search, visualize=False)

        assert result.cost == 0
        assert len(result.path) == 1


class TestUCS:
    """Tests for Uniform Cost Search."""

    def test_ucs_finds_optimal_path(self, grid_with_varied_traffic):
        """Test UCS finds optimal (minimum cost) path."""
        search = DeliverySearch(grid_with_varied_traffic, (0, 0), (2, 2), [])
        result, _ = ucs_search(search, visualize=False)

        assert result.plan != ""
        assert result.cost < float("inf")

    def test_ucs_prefers_low_traffic(self, grid_with_varied_traffic):
        """Test UCS prefers lower traffic segments."""
        search = DeliverySearch(grid_with_varied_traffic, (0, 0), (2, 2), [])
        ucs_result, _ = ucs_search(search, visualize=False)
        bfs_result, _ = bfs_search(search, visualize=False)

        # UCS should find equal or better cost than BFS
        assert ucs_result.cost <= bfs_result.cost

    def test_ucs_no_path(self):
        """Test UCS when no path exists."""
        grid = Grid(width=3, height=3)
        grid.add_segment((0, 0), (0, 1), 1)

        search = DeliverySearch(grid, (0, 0), (2, 2), [])
        result, _ = ucs_search(search, visualize=False)

        assert result.cost == float("inf")

    def test_ucs_same_start_goal(self, simple_grid):
        """Test UCS when start equals goal."""
        search = DeliverySearch(simple_grid, (1, 1), (1, 1), [])
        result, _ = ucs_search(search, visualize=False)

        assert result.cost == 0


class TestAStar:
    """Tests for A* Search."""

    def test_astar_manhattan_finds_path(self, simple_grid):
        """Test A* with Manhattan heuristic finds a path."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])
        result, _ = astar_search(search, manhattan_heuristic, visualize=False)

        assert result.plan != ""
        assert result.cost < float("inf")
        assert result.path[0] == (0, 0)
        assert result.path[-1] == (2, 2)

    def test_astar_euclidean_finds_path(self, simple_grid):
        """Test A* with Euclidean heuristic finds a path."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])
        result, _ = astar_search(search, euclidean_heuristic, visualize=False)

        assert result.plan != ""
        assert result.cost < float("inf")

    def test_astar_optimal(self, grid_with_varied_traffic):
        """Test A* finds optimal path (same as UCS with admissible heuristic)."""
        search = DeliverySearch(grid_with_varied_traffic, (0, 0), (2, 2), [])
        astar_result, _ = astar_search(search, manhattan_heuristic, visualize=False)
        ucs_result, _ = ucs_search(search, visualize=False)

        # A* with admissible heuristic should find same cost as UCS
        assert astar_result.cost == ucs_result.cost

    def test_astar_fewer_nodes_than_ucs(self, larger_grid):
        """Test A* expands fewer nodes than UCS."""
        search = DeliverySearch(larger_grid, (0, 0), (4, 4), [])
        astar_result, _ = astar_search(search, manhattan_heuristic, visualize=False)
        ucs_result, _ = ucs_search(search, visualize=False)

        # A* should expand fewer or equal nodes
        assert astar_result.nodes_expanded <= ucs_result.nodes_expanded

    def test_astar_no_path(self):
        """Test A* when no path exists."""
        grid = Grid(width=3, height=3)
        grid.add_segment((0, 0), (0, 1), 1)

        search = DeliverySearch(grid, (0, 0), (2, 2), [])
        result, _ = astar_search(search, manhattan_heuristic, visualize=False)

        assert result.cost == float("inf")


class TestGreedy:
    """Tests for Greedy Best-First Search."""

    def test_greedy_manhattan_finds_path(self, simple_grid):
        """Test Greedy with Manhattan heuristic finds a path."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])
        result, _ = greedy_search(search, manhattan_heuristic, visualize=False)

        assert result.plan != ""
        assert result.cost < float("inf")

    def test_greedy_euclidean_finds_path(self, simple_grid):
        """Test Greedy with Euclidean heuristic finds a path."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])
        result, _ = greedy_search(search, euclidean_heuristic, visualize=False)

        assert result.plan != ""
        assert result.cost < float("inf")

    def test_greedy_fast_but_suboptimal(self, grid_with_varied_traffic):
        """Test Greedy is fast but may not find optimal path."""
        search = DeliverySearch(grid_with_varied_traffic, (0, 0), (2, 2), [])
        greedy_result, _ = greedy_search(search, manhattan_heuristic, visualize=False)
        ucs_result, _ = ucs_search(search, visualize=False)

        # Greedy may find suboptimal path
        assert greedy_result.cost >= ucs_result.cost

    def test_greedy_no_path(self):
        """Test Greedy when no path exists."""
        grid = Grid(width=3, height=3)
        grid.add_segment((0, 0), (0, 1), 1)

        search = DeliverySearch(grid, (0, 0), (2, 2), [])
        result, _ = greedy_search(search, manhattan_heuristic, visualize=False)

        assert result.cost == float("inf")


class TestIDS:
    """Tests for Iterative Deepening Search."""

    def test_ids_finds_path(self, simple_grid):
        """Test IDS finds a path."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])
        result, _ = ids_search(search, visualize=False)

        assert result.plan != ""
        assert result.cost < float("inf")
        assert result.path[0] == (0, 0)
        assert result.path[-1] == (2, 2)

    def test_ids_optimal_steps(self, simple_grid):
        """Test IDS finds path with optimal number of steps."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])
        ids_result, _ = ids_search(search, visualize=False)
        bfs_result, _ = bfs_search(search, visualize=False)

        # IDS should find same path length as BFS
        assert len(ids_result.path) == len(bfs_result.path)

    def test_ids_no_path(self):
        """Test IDS when no path exists."""
        grid = Grid(width=3, height=3)
        grid.add_segment((0, 0), (0, 1), 1)

        search = DeliverySearch(grid, (0, 0), (2, 2), [])
        result, _ = ids_search(search, visualize=False)

        assert result.cost == float("inf")

    def test_ids_same_start_goal(self, simple_grid):
        """Test IDS when start equals goal."""
        search = DeliverySearch(simple_grid, (1, 1), (1, 1), [])
        result, _ = ids_search(search, visualize=False)

        assert result.cost == 0
        assert len(result.path) == 1


class TestAlgorithmComparison:
    """Tests comparing different algorithms."""

    def test_all_algorithms_find_same_goal(self, simple_grid):
        """Test all algorithms reach the same goal."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])

        bfs_result, _ = bfs_search(search, visualize=False)
        dfs_result, _ = dfs_search(search, visualize=False)
        ucs_result, _ = ucs_search(search, visualize=False)
        astar_result, _ = astar_search(search, manhattan_heuristic, visualize=False)
        greedy_result, _ = greedy_search(search, manhattan_heuristic, visualize=False)
        ids_result, _ = ids_search(search, visualize=False)

        # All should find a path ending at goal
        assert bfs_result.path[-1] == (2, 2)
        assert dfs_result.path[-1] == (2, 2)
        assert ucs_result.path[-1] == (2, 2)
        assert astar_result.path[-1] == (2, 2)
        assert greedy_result.path[-1] == (2, 2)
        assert ids_result.path[-1] == (2, 2)

    def test_optimal_algorithms_same_cost(self, grid_with_varied_traffic):
        """Test UCS and A* find same optimal cost."""
        search = DeliverySearch(grid_with_varied_traffic, (0, 0), (2, 2), [])

        ucs_result, _ = ucs_search(search, visualize=False)
        astar_result, _ = astar_search(search, manhattan_heuristic, visualize=False)

        assert ucs_result.cost == astar_result.cost

    def test_visualization_consistency(self, simple_grid):
        """Test visualization steps are consistent across algorithms."""
        search = DeliverySearch(simple_grid, (0, 0), (2, 2), [])

        _, bfs_steps = bfs_search(search, visualize=True)
        _, ucs_steps = ucs_search(search, visualize=True)

        # Both should have visualization steps
        assert bfs_steps is not None
        assert ucs_steps is not None
        assert len(bfs_steps) > 0
        assert len(ucs_steps) > 0