from __future__ import annotations
from typing import Any


class _Vertex:
    item: Any
    neighbours: set[_Vertex]

    def __init__(self, item: Any, neighbours: set[_Vertex]):
        self.item = item
        self.neighbours = neighbours

    # RE
    def check_conncected(self, target_item: Any, visited: set[_Vertex]) -> bool:
        if self.item == target_item:
            return True
        else:
            visited.add(self)
            for u in self.neighbours:
                if u not in visited:
                    if u.check_conncected(target_item, visited):
                        return True
        return False

    # RE
    def get_spanning_tree(self, visited: set[_Vertex]) -> list[set]:
        edges_so_far = []
        visited.add(self)
        for u in self.neighbours:
            if u not in visited:
                edges_so_far.append({self.item, u.item})
                edges_so_far.extend(u.get_spanning_tree(visited))
        return edges_so_far


class Graph:
    _vertices: dict[Any, _Vertex]

    def __init__(self) -> None:
        self._vertices = {}

    def add_vertex(self, item: Any) -> None:
        vertex = _Vertex(item, set())
        self._vertices[item] = vertex

    def add_edge(self, item1: Any, item2: Any) -> None:
        if item1 in self._vertices and item2 in self._vertices:
            vertex1 = self._vertices[item1]
            vertex2 = self._vertices[item2]
            vertex1.neighbours.add(vertex2)
            vertex2.neighbours.add(vertex1)
        else:
            raise ValueError

    def adjacent(self, item1: Any, item2: Any) -> bool:
        if item1 in self._vertices and item2 in self._vertices:
            vertex1 = self._vertices[item1]
            return any(v2.item == item2 for v2 in vertex1.neighbours)
        else:
            return False

    def get_neighbours(self, item: Any) -> set:
        if item in self._vertices:
            return {u.item for u in self._vertices[item].neighbours}
        else:
            raise ValueError

    # RE
    def num_edges(self) -> int:
        so_far = 0
        for u in self._vertices:
            so_far += len(self._vertices[u].neighbours)
        return so_far // 2

    def connected(self, item1: Any, item2: Any) -> bool:
        vertex1 = self._vertices[item1]
        if vertex1.check_conncected(item2, set()):
            return True
        return False

    def spanning_tree(self) -> list[set]:
        values = list(self._vertices.values())
        return values[0].get_spanning_tree(set())


# RE
def complete_graph(n: int) -> Graph:
    g = Graph()
    for i in range(n):
        g.add_vertex(i)
        for j in range(0, i):
            g.add_edge(j, i)
    return g


def selection_sort_simple(lst: list) -> list:
    sorted_lst = []
    copy = lst.copy()
    while copy != []:
        min_lst = min(copy)
        copy.remove(min_lst)
        sorted_lst.append(min_lst)
    return sorted_lst


def selection_sort(lst: list) -> None:
    for i in range(len(lst)):
        min_index = _helper(lst, i)
        lst[i], lst[min_index] = lst[min_index], lst[i]


def _helper(lst, i) -> int:
    min_index = i
    for j in range(i + 1, len(lst)):
        if lst[i] > lst[j]:
            min_index = j
    return min_index


def insertion_sort(lst: list) -> None:
    for i in range(len(lst)):
        _insert(lst, i)


# RE
def _insert(lst, i) -> None:
    for j in range(i, 0, -1):
        # RETURN EARLY TO REDUCE RUN TIME
        if lst[j] <= lst[j - 1]:
            return
        else:
            lst[j], lst[j - 1] = lst[j - 1], lst[j]


def sort_by_len(lst: list[str]) -> None:
    insertion_sort_by_len(lst)


def insertion_sort_by_len(lst: list[str], i) -> None:
    for j in range(i, 0, -1):
        if len(lst[j]) >= len(lst[j-1]):
            return
        else:
            ...  # switch...


from typing import Callable, Optional


def insertion_sort_by_key(lst: list, key: Optional[Callable] = None) \
        -> None:
    for i in range(0, len(lst)):
        _insert_by_key(lst, i, key)


def _insert_by_key(lst, i, key) -> None:
    for j in range(i, 0, -1):
        if key is None:
            ...
        else:
            if key(lst[j]) >= key(lst[j - 1]):
                ...


def count(s: str) -> int:
    return s.count('a')
    # lambda s: s.count('a')


def mergesort(lst: list) -> list:
    if len(lst) < 2:
        return lst.copy()
    else:
        midpoint = len(lst) // 2
        left = mergesort(lst[:midpoint])
        right = mergesort(lst[midpoint:])
        return _merge(left, right)

# RE
def _merge(lst1, lst2) -> list:
    i1 = 0
    i2 = 0
    sorted_lst = []
    while i1 < len(lst1) and i2 < len(lst2):
        assert sorted_lst == sorted(lst1[:i1] + lst2[:i2])
        if i1 <= i2:
            sorted_lst.append(lst1[i1])
            i1 += 1
        else:
            sorted_lst.append(lst2[i2])
            i1 += 1
    assert len(lst1) == i1 or len(lst2) == i2
    if len(lst1) == i1:
        return sorted_lst + lst2[i2:]
    else:
        return sorted_lst + lst1[i1:]


# RE
def quicksort(lst) -> list:
    if len(lst) < 2:
        return lst.copy()
    else:
        pivot = lst[0]
        rest = lst[1:]
        small, big = _partition(rest, pivot)
        small_lst = quicksort(small)
        big_lst = quicksort(big)
        return small_lst + [pivot] + big_lst


# RE
def _partition(lst, pivot) -> tuple[list, list]:
    small = []
    big = []
    for item in lst:
        # NOT LENGTH
        if item <= pivot:
            small.append(item)
        else:
            big.append(item)
    return (small, big)


# RE THIS IS EARLY VERSION OF INDEX VERSION
def _in_place_partition_draft(lst: list) -> None:
    pivot = lst[0]
    small = 1
    big = len(lst)
    while small < big:
        # Use big only to swap
        if lst[small] <= pivot:
            small += 1
        else:
            # Minus 1
            lst[small], lst[big - 1] = lst[big - 1], lst[small]
            big -= 1
    lst[0], lst[small - 1] = lst[0], lst[small - 1]


# CALLS _in_place_partition
def in_place_quicksort(lst: list) -> None:
    _in_place_partition(lst, 0, len(lst))


# RE CALLS _in_place_partition_indexed based on pivot
def _in_place_partition(lst, b, e) -> None:
    if e - b < 2:
        pass
    else:
        pivot_index = _in_place_partition_indexed(lst, b, e)
        _in_place_partition_indexed(lst, b, pivot_index)
        _in_place_partition_indexed(lst, pivot_index + 1, e)


# RE
def _in_place_partition_indexed(lst, b, e) -> int:
    pivot = lst[b]
    small = b + 1
    big = e
    while small < big:
        if lst[small] <= pivot:
            small += 1
        else:
            lst[small], lst[big - 1] = lst[big - 1], lst[small]
            big -= 1
    lst[b], lst[small - 1] = lst[b], lst[small - 1]
    return small - 1


class BinOp(Expr):
    left: Expr
    op: str
    right: Expr

    def __init__(self, left: Expr, op: str, right: Expr) -> None:
        self.left = left
        self.op = op
        self.right = right

    def evaluate(self, env: dict[str, Any]) -> Any:
        l_value = self.left.evaluate(env)
        r_value = self.right.evaluate(env)
        if self.op == '+':
            return l_value + r_value
        else:
            raise ValueError(f"{self.op} DNE")


# RE RAISE VALUE ERROR
class Compare(Expr):
    left: Expr
    comparisons: list[tuple[str, Expr]]
    def __init__(self, left: Expr,
                 comparisons: list[tuple[str, Expr]]) -> None:
        self.left = left
        self.comparisons = comparisons

    def evaluate(self) -> Any:
        left = self.left.evaluate()
        for ex in self.comparisons:
            right = ex[1].evaluate()
            if ex[0] == '<':
                if not left < right:
                    return False
            # ...
            else:
                raise ValueError
            left = right
        return False


# RE
class Name(Expr):
    id: str
    def __init__(self, id) -> None:
        self.id = id
    def evaluate(self, env: dict[str, Any]) -> Any:
        return env[self.id]


# RE
class Assign(Statement):
    target: str
    value: Expr

    def __init__(self, target: str, value: Expr) -> None:
        self.target = target
        self.value = value

    def evaluate(self, env: dict[str, Any]) -> None:
        # MAKE SURE TO USE ENV WHEN EVALUATE
        env[self.target] = self.value.evaluate(env)


# RE
class Module:
    body: list[Statement]

    def __init__(self, body: list[Statement]) -> None:
        self.body = body

    def evaluate(self) -> None:
        env = {}
        # MAKE EMPTY ENV
        for statement in self.body:
            statement.evaluate(env)

# RE EVALUATE THEN PRINT
class Print(Statement):
    argument: str
    def evaluate(self, env: dict[str, Any]) -> None:
        print(self.argument.evaluate(env))

# RE
class If(Statement):
    test: Expr
    body: list[Statement]
    orelse: list[Statement]
    def __init__(self, test: Expr, body: list[Statement],
                 orelse: list[Statement]) -> None:
        ...
    def evaluate(self, env: dict[str, Any]) -> None:
        if self.test.evaluate(env):
            for statement in self.body:
                statement.evaluate(env)
        else:
            for statement in self.orelse:
                statement.evaluate(env)

# RE
class ForRange(Statement):
    target: str
    start: Expr
    stop: Expr
    body: list[Statement]

    def __init__(self, target: str, start: Expr, stop: Expr,
                 body: list[Statement]) -> None:
        self.target = target
        self.start = start
        self.stop = stop
        self.body = body

    def evaluate(self, env: dict[str, Any]) -> None:
        for i in range(self.start.evaluate(env), self.stop.evaluate(env)):
            # Assign first
            env[self.target] = i
            Assign(self.target, Num(i))
            # Then run the statement
            for statement in self.body:
                statement.evaluate(env)