from typing import Union, List, Optional, Dict, Tuple, Set
# from collections import ...  # use if necessary
import enum
# don't import anything else unless explicitly allowed in discussion forum and
# updated assignment text


class Operation(enum.Enum):
    Epsilon = enum.auto()    # reprezentuje typ listu, který je prázdné slovo
    Emptyset = enum.auto()   # list, který je prázdná množina
    Literal = enum.auto()    # list, který je znak
    Union = enum.auto()      # sjednocení (+)
    Concat = enum.auto()     # zřetězení (.)
    Iteration = enum.auto()  # iterace (*)


# Do not change this class!
class Regex:
    def __init__(self,
                 op_or_value: Union[str, Operation],
                 left: Optional["Regex"] = None,
                 right: Optional["Regex"] = None) -> None:
        if isinstance(op_or_value, str):
            # if the first arg is a string we have a literal
            self.op: Operation = Operation.Literal
            self.value: Optional[str] = op_or_value
            assert len(self.value) == 1
            assert left is None
            assert right is None
        else:
            # otherwise we have an operator
            self.op = op_or_value
            self.value = None
            assert ((op_or_value is Operation.Iteration
                     and left is not None and right is None)
                    or (op_or_value in [Operation.Epsilon, Operation.Emptyset]
                        and left is None and right is None)
                    or (left is not None and right is not None))
        self.left = left
        self.right = right

    def is_lit(self) -> bool:
        return self.op is Operation.Literal

    # for pretty-printing results in interpreter and for the sake of
    # print-debugging
    def __repr__(self) -> str:
        op_or_value = self.value if self.op is Operation.Literal else self.op
        base = f"Regex({op_or_value}"
        assert self.left is not None or self.right is None
        for arg in [self.left, self.right]:
            if arg is not None:
                base += f", {arg}"
        return base + ")"

    # equality of regexes
    def __eq__(self, other: object) -> bool:
        if isinstance(other, Regex):
            return self.op == other.op and self.value == other.value \
                and self.left == other.left and self.right == other.right
        return False

    # hashing to make set & dict work properly
    def __hash__(self) -> int:
        return hash((self.op, self.value, self.left, self.right))


# TODO: implement match, you can add any other members
class CompiledRegex:  # TODO
    def match(self, value: str) -> bool:
        ...


# TODO: implement this
def compile(regex: Regex) -> CompiledRegex:
    ...


re_a = Regex(Operation.Iteration, Regex("a"))
re_b = Regex(Operation.Union,
             Regex(Operation.Union,
                   Regex(Operation.Iteration, Regex("a")),
                   Regex(Operation.Iteration, Regex("b"))),
             Regex(Operation.Iteration, Regex("c")))
re_c = Regex(Operation.Iteration,
             Regex(Operation.Concat,
                   Regex(Operation.Union,
                         Regex("a"),
                         Regex(Operation.Union, Regex("b"), Regex("c"))),
                   Regex(Operation.Union,
                         Regex(Operation.Union, Regex("a"), Regex("b")),
                         Regex("c"))))
re_d = Regex(Operation.Union,
             Regex(Operation.Epsilon),
             Regex(Operation.Emptyset))


if __name__ == '__main__':
    cre_a = compile(re_a)
    assert isinstance(cre_a, CompiledRegex)
    assert cre_a.match("aaa")
    assert cre_a.match("")
    assert not cre_a.match("b")
    assert not cre_a.match("ab")

    cre_b = compile(re_b)
    assert isinstance(cre_b, CompiledRegex)
    assert cre_b.match("aaa")
    assert cre_b.match("bb")
    assert not cre_b.match("aabb")
    assert not cre_b.match("bca")

    cre_c = compile(re_c)
    assert isinstance(cre_c, CompiledRegex)
    assert cre_c.match("")
    assert not cre_c.match("a")
    assert cre_c.match("abca")
    assert not cre_c.match("abbba")

    cre_d = compile(re_d)
    assert isinstance(cre_d, CompiledRegex)
    assert cre_d.match("")
    assert not cre_d.match("a")
    assert not cre_d.match("abca")
    assert not cre_d.match("abbba")