# Контрольная работа

В контрольной работе 4 задачи, за каждую задачу можно набрать максимум 1 балл.
Для сдачи контрольной работы необходимо по каждой задаче набрать +0.7 баллов.

Если суммарно за работу вы наберете 2 или более баллов, то на переписке вам автоматически зачтутся все задачи, за
которые вы на этой итерации набрали +0.7 баллов.

## Задачи

#### 1 Merge
Из модулей разрешается использовать только `itertools`, `random` и `collections`.

- Напишите генератор, который принимает на вход две неубывающие последовательности и выдает одну объединенную
неубывающую последовательность.
- Используя решение предыдущего пункта, напишите **нерекурсивный генератор**, который принимает на вход произвольную
  последовательность и, используя сортировку слиянием, возвращает элементы в отсортированном порядке.
  Сортировка всей последовательности должна использовать `O(n (log n))` операций.

Примечание:
* Последовательность -- любой объект, по которому можно проитерироваться.

#### 2. `FixedSizeQueue`
Данное задание - задание на реализацию структуры данных.

Вам предлагается реализовать очередь на массиве фиксированного размера.
В качестве состояния очереди разрешается использовать только преаллоцированный лист размера `maxlen` и два индекса.

* Очередь не должна оставлять висящие ссылки на объекты, после того как они были вынуты из очереди.
* Очередь должна инициализироваться своим максимальным размером -– `q = FixedSizeQueue(maxlen=10)`.
* Свойство `empty`, возвращающее `True/False`, в зависимости от того, пуста ли очередь. `O(1)`.
* Свойство `full`, возвращающее `True/False`, в зависимости от того, заполнена ли очередь. `O(1)`.
* Метод `len(q)`, возвращающий число элементов в очереди. `O(1)`.
* Метод `q.put(obj)`, добавляющий объект в начало очереди. В случае, если в очереди нет места, необходимо бросить `ValueError`. `O(1)`.
* Метод `q.get()`, достающий объект из конца очереди. В случае, если очередь пуста, необходимо бросить `ValueError`. `O(1)`.
* Оператор `q + obj` должно возвращать новую очередь, никак не связанную с предыдущей, в которую добавлен элемент `obj`. `O(n)`.
* Оператор `q += obj` должно добавлять в текущую очередь элемент `obj`. `O(1)`.
* На очереди должен работать оператор `in`, проверяющий вхождение элемента в очередь. `O(n)`.
* Должно работать итерирование при помощи`for`-синтаксиса `for x in q`. При этом состояние очереди не должно меняться.

p.s. `n` -- текущее количество элементов в очереди.

#### 3. `@types_tracker`

Напишите декоратор `@types_tracker` и функцию `types_info(func)`, которая является генератором и выдает кортежи из двух
элементов:
  1. Словарь, отображающий имена аргументов в их типы, с которыми была вызвана функция `func`
  2. Множество типов возвращаемых значений, которые возникали при вызове функции `func` с такими типами аргументов.

Для работы функции `types_info` необходимо, чтобы функция была продекорирована, если это не так, то должно быть
сгенерировано исключение.

    @types_tracker
    def foo(a, b=42):
        pass

    @types_tracker
    def bar(a, b=42):
        if a < 42:
            return 1
        else:
            return "qwe"

    @types_tracker
    def id(a):
        return a

    def pretty_print_types_info(func):
        for call_args_types, res_types in types_info(func):
            s = "{}({}) -> {}".format(
                func.__name__,
                ", ".join("{}={}".format(k, v.__name__)
                            for k, v in call_args_types.items()),
                " & ".join(type.__name__ for type in res_types)
            )
            print(s)

    >>> foo(1)
    >>> foo(2)
    >>> pretty_print_types_info(foo)
    foo(a=int, b=int) -> NoneType

    >>> bar(1)
    >>> bar(42)
    >>> pretty_print_types_info(bar)
    bar(a=int, b=int) -> int & str

    >>> id(1)
    >>> id(2.0)
    >>> id(None)
    >>> pretty_print_types_info(id)
    id(a=int) -> int
    id(a=float) -> float
    id(a=NoneType) -> NoneType

NB: по примерам несложно понять, что при реализации нужно учитывать типы аргументов по-умолчанию.

#### 4. `CallStackPrinter`

Ваша задача –- реализовать менеджер контектса, выводящий дерево вызовов функций в аргумент `output`.

Пример:

    def foo(a):
        bar(a)
        baz()

    def bar(b, c=42):
        baz()

    def baz():
        pass

    with CallStackPrinter(output=sys.stdout):
        foo(1)
        bar(2, c=3)

Вывод:

    foo(1)
        bar(1)
            baz()
        baz()
    bar(2, c=3)
        baz()

Примечания:

* Можно считать, что все функции объявлены в глобальной области видимости.
* Учитывать дефолтные значения аргументов не нужно.
* При отрисовке дерева ключевые аргументы нужно отсортировать в лексикографическом порядке.
* Значение `output` по-умолчанию -- `stdout` из модуля `sys`.
* Не забудьте про рекурсию!