#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import deque
from src.graph import Graph
from src.recompute_mst_data import data
from src.testing import AD2TestCase, get_return_type, recursion_variant
from typing import *
import logging
import math
import unittest
'''
Assignment 2, Problem 2: Recomputing a Minimum Spanning Tree

Student Name:
'''

'''
Copyright: justin.pearson@it.uu.se and his teaching assistants, 2024.

This file is part of course 1DL231 at Uppsala University, Sweden.

Permission is hereby granted only to the registered students of that
course to use this file, for a homework assignment.

The copyright notice and permission notice above shall be included in
all copies and extensions of this file, and those are not allowed to
appear publicly on the internet, both during a course instance and
forever after.
'''
# Note: you must give a recursion variant for each recursive function fun by
# wrapping fun with the '@recursion_variant(lambda a, b, ..., z): expr)'
# wrapper, where the set {a, b, ..., z} is a subset of the arguments to fun and
# expr is evaluated to an integer.

# If your solution needs a queue, then you can use deque.

# If you need to log information during tests, execution, or both,
# then you can use this library:
# Basic example:
#   logger = logging.getLogger('put name here')
#   a = 5
#   logger.debug(f'a = {a}')


__all__ = ['update_MST_1', 'update_MST_2', 'update_MST_3', 'update_MST_4']


def update_MST_1(G: Graph, T: Graph, e: Tuple[str, str],
                 w: int) -> Union[Tuple[None, None],
                                  Tuple[Tuple[str, str],
                                        Tuple[str, str]]]:
    '''
    Pre:  T is a minimum spanning tree of G.
          Edge e is in G.
          Edge e is not in T.
          Weight w is greater than the weight of edge e in G.
    Post: Edge e has weight w in G.
          T is a minimum spanning tree of G.
    '''
    (u, v) = e
    assert (e in G and e not in T and w > G.weight(u, v))


def update_MST_2(G: Graph, T: Graph, e: Tuple[str, str],
                 w: int) -> Union[Tuple[None, None],
                                  Tuple[Tuple[str, str],
                                        Tuple[str, str]]]:
    '''
    Pre:  T is a minimum spanning tree of G.
          Edge e is in G.
          Edge e is not in T.
          Weight w is smaller than the weight of edge e in G.
    Post: Edge e has weight w in G.
          T is a minimum spanning tree of G.
    '''
    (u, v) = e
    assert (e in G and e not in T and w < G.weight(u, v))


def update_MST_3(G: Graph, T: Graph, e: Tuple[str, str],
                 w: int) -> Union[Tuple[None, None],
                                  Tuple[Tuple[str, str],
                                        Tuple[str, str]]]:
    '''
    Pre:  T is a minimum spanning tree of G.
          Edge e is in G.
          Edge e is in T.
          Weight w is smaller than the weight of edge e in G.
    Post: Edge e has weight w in G.
          T is a minimum spanning tree of G.
    '''
    (u, v) = e
    assert (e in G and e in T and w < G.weight(u, v))


def update_MST_4(G: Graph, T: Graph, e: Tuple[str, str],
                 w: int) -> Union[Tuple[None, None],
                                  Tuple[Tuple[str, str],
                                        Tuple[str, str]]]:
    '''
    Pre:  T is a minimum spanning tree of G.
          Edge e is in G.
          Edge e is in T.
          Weight w is greater than the weight of edge e in G.
    Post: Edge e has weight w in G.
          T is a minimum spanning tree of G.
    '''
    (u, v) = e
    assert (e in G and e in T and w > G.weight(u, v))


class RecomputeMstTest(AD2TestCase):
    '''
    Test Suite for minimum spanning tree problem

    Any method named 'test_something' will be run when this file is
    executed. You may add your own test cases if you wish.
    (You may delete this class from your submitted solution.)
    '''
    logger = logging.getLogger('RecomputeMstTest')
    data = data
    update_MST = [update_MST_1, update_MST_2, update_MST_3, update_MST_4]
    update_MST_ret_type = [get_return_type(f) for f in update_MST]
    src_code_path = __file__

    def source_code_path(self):
        return RecomputeMstTest.src_code_path

    def assertReturnedValue(self, unmodified_g: Graph, modified_g: Graph,
                            unmodified_t: Graph, modified_t: Graph,
                            t: Union[Tuple[None, None],
                                     Tuple[Tuple[str, str],
                                           Tuple[str, str]]]) -> None:
        e_removed, e_added = t
        if e_removed is None or e_added is None:
            return
        if e_removed == e_added:
            return
        self.assertLessEqual(unmodified_g.weight(*e_removed),
                             unmodified_g.weight(*e_added),
                             'The weight of the added edge cannot be less '
                             'than the weight of the removed edge in the'
                             'unmodified graph.')
        self.assertGreaterEqual(modified_g.weight(*e_removed),
                                modified_g.weight(*e_added),
                                'The weight of the added edge cannot be '
                                'greater than the weight of the removed edge '
                                'in the modified graph.')
        self.assertIn(e_removed, unmodified_t,
                      'The removed edge is not in unmodified MST.')
        self.assertNotIn(e_removed, modified_t,
                         'The removed edge is in the modified MST.')
        self.assertNotIn(e_added, unmodified_t,
                         'The added edge is in the unmodified MST.')
        self.assertIn(e_added, modified_t,
                      'The added edge is not in the modified MST.')

    def assertUndirectedEdgesEqual(self, actual: List[Tuple[str, str]],
                                   expected: List[Tuple[str, str]]) -> None:
        self.assertListEqual(
            sorted(((min(u, v), max(u, v)) for u, v in actual)),
            sorted(((min(u, v), max(u, v)) for u, v in expected)),
            'The edges in the MST does not match the expected edges.')

    def assertEdgesInExpectedGraph(self, expected_graph: List[Tuple[str, str]],
                                   graph: Graph) -> None:
        for e in expected_graph:
            self.assertIn(e, graph,
                          f'The edge {e} is not in the expected graph.')

    def assertTreeIsConnected(self, tree: Graph) -> None:
        if len(tree.nodes) == 0:
            return
        visited = set()
        queue = deque([tree.nodes[0]])
        while len(queue) > 0:
            u = queue.popleft()
            visited.add(u)
            for v in tree.neighbors(u):
                if v not in visited:
                    queue.append(v)
        self.assertSetEqual(visited, set(tree.nodes),
                            'The tree is not connected.')

    def assertGraphsEqual(self, actual: Graph, expected: Graph) -> None:
        self.assertEqual(len(actual.edges), len(expected.edges),
                         'The graphs have different number of edges.')
        for u, v in actual.edges:
            self.assertEqual(actual.weight(u, v), expected.weight(u, v),
                             f'The weight of edge ({u}, {v}) is not equal in '
                             'the actual and expected graphs.')

    def test_mst(self) -> None:
        is_implemented = [True] * len(self.update_MST)

        for i, update_MST in enumerate(self.update_MST, start=1):
            instance = data[0]
            graph = instance['graph'].copy()
            tree = instance['mst'].copy()
            u, v = instance['solutions'][i - 1]['edge']
            weight = instance['solutions'][i - 1]['weight']
            if update_MST(graph, tree, (u, v), weight) is None:
                self.logger.warning(f'update_MST_{i} not implemented.')
                is_implemented[i - 1] = False
                continue

            # test update_MST_{i}:
            for j, instance in enumerate(self.data):
                # test update_MST_{i} using instance {j}:
                with self.subTest(case=i, instance=j):
                    graph: Graph = instance['graph'].copy()
                    tree: Graph = instance['mst'].copy()
                    u, v = instance['solutions'][i - 1]['edge']
                    weight = instance['solutions'][i - 1]['weight']
                    expected = instance['solutions'][i - 1]['expected']
                    expected_graph: Graph = instance['graph'].copy()
                    expected_graph.set_weight(u, v, weight)
                    t = self.assertAlgorithm(
                        update_MST,
                        self.update_MST_ret_type[i - 1],
                        graph, tree, (u, v), weight)
                    self.assertReturnedValue(instance['graph'], graph,
                                             instance['mst'], tree,
                                             t)
                    self.assertUndirectedEdgesEqual(tree.edges, expected)
                    self.assertEdgesInExpectedGraph(tree.edges, expected_graph)
                    self.assertTreeIsConnected(tree)
                    self.assertGraphsEqual(graph, expected_graph)

        num_implemented_funs = sum((1 if b else 0 for b in is_implemented))
        self.assertGreaterEqual(
          num_implemented_funs, 2,
          'At least two of the four update_MST functions must be implemented.')


if __name__ == '__main__':
    # Set logging config to show debug messages:
    logging.basicConfig(level=logging.DEBUG)
    # run unit tests (failfast=True stops testing after the first failed test):
    unittest.main(failfast=True)
