"""
This script is meant to help you identify gaps in your python knowledge.

Here is a minimal list of concepts that you should be familiar with in python:
- Inheritance
- Constructors, destructors, operators
- Type annotations
- Format strings
- Exceptions
- Decorators, class decorators
- Properties
- Lambdas
- Wildcard arguments (*args and **kwargs)

I recommend googling for resources that explain these concepts, especially in
the official python documentation (docs.python.org/3), and then playing around
with examples. Write some code, guess what it will do, then verify.

Be sure that resources you access are up-to-date. The latest python version is
3.13, and the language changes significantly even between minor versions. This
script will not work with python older than 3.11. You should disregard any
resource targeted at version 2: python 2 and python 3 are practically different
programming languages.
"""

from collections.abc import Callable
import math
import copy
import functools

class Functor:
    _f: Callable[[int], int]
    _n: int

    def __init__(self, f: Callable[[int], int] | None):
        self._f = f
        self._n = 0

    # We don't want to limit the number of arguments, but we will insist that
    # they are all integers
    def __call__(self, *f_args: int, **f_kwargs: int) -> int:
        if not self._f:
            raise RuntimeError("We don't have a callable!")

        self._n += 1

        return self._f(*f_args, **f_kwargs)

    @property
    def f(self) -> Callable[[int], int] | None:
        return self._f

    @f.setter
    def f(self, f: Callable[[int], int] | None):
        self._f = f

    @property
    def n(self) -> int:
        return self._n

class LoggedFunctor(Functor):
    _should_log: bool
    _name: str

    def __init__(self, f: Callable[[int], int] | None, should_log: bool = True):
        super().__init__(f)
        self._should_log = should_log
        self._name = type(f).__name__

    def __del__(self):
        if self._should_log:
            print(f"{self._name} was called {self.n} times")

    def set_name(self, name: str):
        self._name = name


if __name__ == '__main__':
    my_functor = LoggedFunctor(lambda x: x+1)
    print(f"5 + 1 is {my_functor(5)}")

    try:
        my_functor.n = 10
    except AttributeError as e:
        print(f"""Cannot modify property without a setter!
        Error message: "{e}" """)
    
    # f does have a setter, so we can modify it!
    my_functor.f = None
    try:
        # But this won't work if f is None
        print(my_functor(6))
    except RuntimeError as e:
        print(f'Uh oh! Failed with message "{e}"')
    
    # Notice once my_functor is deleted that only one call was registered: the
    # second call was interrupted by the exception.
    del my_functor



# Let's see a real-world usecase for something like LoggedFunctor: analyzing
# two different sort algorithms by logging the number of comparisons they make.

class InsertionSorter:
    """
    Requires O(n**2) comparisons
    """

    @LoggedFunctor
    def _cmp(a: int, b: int) -> bool:
        return a < b


    def __init__(self):
        self._cmp.set_name("InsertionSorter: '<'")
    
    def __call__(self, xs_orig: [int]) -> [int]:
        # Let's not modify the input, so we can reuse it for future tests
        xs = copy.deepcopy(xs_orig)
        for i in range(len(xs)):
            for j in range(i):
                if self._cmp(xs[i], xs[j]):
                    # This is how you swap in python
                    xs[j], xs[i] = xs[i], xs[j]
        return xs

class MergeSorter:
    """
    Requires O(nlogn) comparisons
    """

    @LoggedFunctor
    def _cmp(a: int, b: int) -> bool:
        return a < b

    def __init__(self):
        self._cmp.set_name("MergeSorter: '<'")

    def _merge(self, xs: [int], ys: [int]) -> [int]:
        result = []
        i = 0
        j = 0
        while i < len(xs) and j < len(ys):
            if self._cmp(xs[i], ys[j]):
                result.append(xs[i])
                i += 1
            else:
                result.append(ys[j])
                j += 1

        while i < len(xs):
            result.append(xs[i])
            i += 1

        while j < len(ys):
            result.append(ys[j])
            j += 1

        return result

    def _sort(self, xs: [int]):
        n = len(xs)
        if n <= 1:
            return xs
        elif n == 2:
            if not self._cmp(xs[0], xs[1]):
                xs[1], xs[0] = xs[0], xs[1]
            return xs
        
        left = self._sort(xs[:int(n/2)])
        right = self._sort(xs[int(n/2):])

        return self._merge(left, right)
    
    def __call__(self, xs_orig: [int]) -> [int]:
        # Let's not modify the input, so we can reuse it for future tests
        xs = copy.deepcopy(xs_orig)
        return self._sort(xs)


if __name__ == '__main__':
    arr = [i for i in range(1000, 0, -1)]
    
    insertion_sort = InsertionSorter()
    sorted_arr = insertion_sort(arr)
    # Ensure that this is actually a sort algorithm
    assert(all(sorted_arr[i] <= sorted_arr[i+1] for i in range(len(sorted_arr) - 1)))
    
    merge_sort = MergeSorter()
    sorted_arr = merge_sort(arr)
    # Ensure that this is actually a sort algorithm
    assert(all(sorted_arr[i] <= sorted_arr[i+1] for i in range(len(sorted_arr) - 1)))
    
    print("n**2: {}, nlogn: {}".format(pow(1000, 2), 1000*math.log(1000)))