#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import deque
from src.augmenting_data import data
from src.graph import Graph
from src.testing import AD2TestCase, get_return_type, recursion_variant
from typing import *
import logging
import math
import unittest
'''
Assignment 1, Problem 2: Augmenting Path Detection in Network Graphs

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__ = ['augmenting', 'augmenting_extended']


def augmenting(G: Graph, s: str, t: str) -> bool:
    '''
    Pre:  G is a directed graph;
          nodes s and t are in G;
          node s is connected to all other nodes in G; and
          each edge (u, v) in G has a non-negative integer capacity c
          and a non-negative integer flow f with f <= c.
    Post: returns true if there exists an augmenting path from s to t in G.
    '''
    pass


def augmenting_extended(G: Graph,
                        s: str, t: str) -> Tuple[bool, List[Tuple[str, str]]]:
    '''
    Pre:  G is a directed graph;
          nodes s and t are in G;
          node s is connected to all other nodes in G; and
          each edge (u, v) in G has a non-negative integer capacity c
          and a non-negative integer flow f with f <= c.
    Post: returns an augmenting path from s to t in G if one exists, else
          returns an empty list.
    '''
    pass


class AugmentingTest(AD2TestCase):
    '''
    Test Suite for augmenting path dectection problem

    Any method named 'test_something' will be run when this file is executed.
    Use the sanity check as a template for adding your own test cases if you
    wish. (You may delete this class from your submitted solution.)
    '''
    logger = logging.getLogger('AugmentingTest')
    data = data
    augmenting = augmenting
    augmenting_ret_type = get_return_type(augmenting)
    augmenting_extended = augmenting_extended
    augmenting_extended_ret_type = get_return_type(augmenting_extended)
    src_code_path = __file__
    
    def source_code_path(self):
        return AugmentingTest.src_code_path

    def assertIsAugmentingPath(self, graph: Graph, s: str, t: str,
                               path: List[Tuple[str, str]]) -> None:
        if len(path) == 0:
            self.fail('The path should be non-empty.')

        self.assertEqual(path[0][0], s,
                         f'The path does not start at the source {s}.')
        self.assertEqual(path[-1][1], t,
                         f'The path does not end at the sink {t}.')
        for u, v in path:
            self.assertIn((u, v), graph,
                          f'The edge {(u, v)} of the path does not exist in '
                          'the graph.')

        for i in range(1, len(path)):
            self.assertEqual(path[i - 1][1], path[i][0],
                             f'The end of edge {path[i - 1]} does not match '
                             f'the start of the next edge {path[i]}.')

        self.assertEqual(len(path), len(set(path)),
                         'The path contains duplicates of one or more edges.')

        for u, v in path:
            self.assertLess(graph.flow(u, v), graph.capacity(u, v),
                            f'The flow is not less than the capacity for '
                            f'edge {(u, v)}.')

    def test_augmenting(self) -> None:
        for i, instance in enumerate(AugmentingTest.data):
            with self.subTest(instance=i):
                found = self.assertAlgorithm(
                    AugmentingTest.augmenting,
                    AugmentingTest.augmenting_ret_type,
                    instance['digraph'].copy(),
                    instance['source'],
                    instance['sink'])
                m = '' if instance['expected'] else ' not'
                self.assertEqual(found, instance['expected'],
                                 f'The network should{m} contain an '
                                 f'augmenting path.')

    def test_augmenting_extended(self) -> None:
        instance = AugmentingTest.data[0]
        if AugmentingTest.augmenting_extended(instance['digraph'].copy(),
                                              instance['source'],
                                              instance['sink']) is None:
            self.skipTest('augmenting_extended not implemented.')

        for i, instance in enumerate(AugmentingTest.data):
            with self.subTest(instance=i):
                t = self.assertAlgorithm(
                    AugmentingTest.augmenting_extended,
                    AugmentingTest.augmenting_extended_ret_type,
                    instance['digraph'].copy(),
                    instance['source'],
                    instance['sink'])
                found, path = t

                m = '' if instance['expected'] else ' not'
                self.assertEqual(found, instance['expected'],
                                 f'The network should{m} contain an '
                                 f'augmenting path.')
                if instance['expected']:
                    self.assertIsAugmentingPath(instance['digraph'].copy(),
                                                instance['source'],
                                                instance['sink'],
                                                path)
                else:
                    self.assertListEqual(path, [])


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)