#####################################################################################################################################################
######################################################################## INFO #######################################################################
#####################################################################################################################################################

"""
This program is provided during session 2 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session2/practical/

It is meant to be used to verify the correct implementation of the DFS player and all its components.
"""

#####################################################################################################################################################
###################################################################### IMPORTS ######################################################################
#####################################################################################################################################################

# External imports
import random
import unittest

# PyRat imports
from pyrat import BigHolesRandomMaze
from players.DFS import DFS

#####################################################################################################################################################
###################################################################### CLASSES ######################################################################
#####################################################################################################################################################

class DFS_Tests (unittest.TestCase):

    """
    *(This class inherits from* ``unittest.TestCase`` *).*

    This class tests the methods of the DFS class.
    For each method, we test it with a few different configurations.
    """

    #############################################################################################################################################
    #                                                                CONSTRUCTOR                                                                #
    #############################################################################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        Initializes a new instance of the class.
        
        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """

        # Inherit from parent class
        super().__init__(*args, **kwargs)

    #############################################################################################################################################
    #                                                                TEST METHODS                                                               #
    #############################################################################################################################################

    def test_traversal (self) -> None:

        """
        This method tests the ``traversal(...)`` method.

        We are going to check the following:
        - Outputs are of the expected types.
        - All vertices are visited.
        - The routing table is a tree, with root corresponding to the start of the traversal.
        - The found distances are correct, i.e., strictly positive and increasing, except for the start vertex which should be 0.

        Note that we cannot test that the output is unique, as there are multiple valid outputs, depending on how vertices are explored.
        We will test the method on several random graphs to make sure it is working properly.
        Random graphs will be generated using the PyRat class used to create mazes in games.
        There are several such classes, but we will use the BigHolesRandomMaze class.
        """

        # Constants
        NB_GRAPHS = 10
        WIDTHS = [2, 30]
        HEIGHTS = [2, 30]
        CELL_PERCENTAGES = [20.0, 100.0]
        WALL_PERCENTAGES = [20.0, 100.0]
        MUD_PERCENTAGE = 0.0

        # Test on several graphs
        for i in range(NB_GRAPHS):
            
            # Instantiate the player
            player = DFS()

            # Generate a random maze
            # We use a fixed random seed for reproducibility of tests
            rng = random.Random(i)
            maze = BigHolesRandomMaze(width = rng.randint(WIDTHS[0], WIDTHS[1]),
                                      height = rng.randint(HEIGHTS[0], HEIGHTS[1]),
                                      cell_percentage = rng.uniform(CELL_PERCENTAGES[0], CELL_PERCENTAGES[1]),
                                      wall_percentage = rng.uniform(WALL_PERCENTAGES[0], WALL_PERCENTAGES[1]),
                                      mud_percentage = MUD_PERCENTAGE,
                                      random_seed = i)

            # Choose a random starting vertex
            start_vertex = rng.choice(maze.get_vertices())

            # Perform the traversal
            distances, routing_table = player.traversal(maze, start_vertex)

            # Check the output type for distances
            # It should be a dictionary with integer keys and integer values
            self.assertTrue(isinstance(distances, dict))
            self.assertTrue(all(isinstance(k, int) for k in distances.keys()))
            self.assertTrue(all(isinstance(v, int) for v in distances.values()))
            
            # Check the output type for the routing table
            # It should be a dictionary with integer keys and integer or None values
            self.assertTrue(isinstance(routing_table, dict))
            self.assertTrue(all(isinstance(k, int) for k in routing_table.keys()))
            self.assertTrue(all(isinstance(v, (type(None), int)) for v in routing_table.values()))

            # All vertices should be visited
            # Equivalently, the distances should have the same keys as the maze vertices
            self.assertEqual(sorted(set(distances.keys())), sorted(maze.get_vertices()))

            # Check that the start vertex is the only tree root
            self.assertEqual(routing_table[start_vertex], None)
            self.assertTrue(all(routing_table[v] is not None for v in routing_table.keys() if v != start_vertex))
            self.assertEqual(distances[start_vertex], 0)
            self.assertTrue(all(distances[v] > 0 for v in distances.keys() if v != start_vertex))
            
            # We check that the routing table is a tree
            # Also we check that associated distances are decreasing as we go to the root
            for vertex in routing_table:

                # We check that the parent is closer to the root
                if routing_table[vertex] is not None:
                    self.assertTrue(distances[routing_table[vertex]] < distances[vertex])
                
                # We ckeck that we can reach the root from any vertex
                path = [vertex]
                while routing_table[path[-1]] is not None:
                    self.assertTrue(routing_table[path[-1]] not in path)
                    path.append(routing_table[path[-1]])

#####################################################################################################################################################
####################################################################### SCRIPT ######################################################################
#####################################################################################################################################################

if __name__ == "__main__":

    # Run all tests
    unittest.main(verbosity=2)

#####################################################################################################################################################
#####################################################################################################################################################