from graphviz import Digraph


class Node:

    def __init__(self, value, depth=0):
        self.value = value
        self.left = None
        self.right = None
        self.depth = depth

    #再帰的にすべての要素が返される。
    #if文はオブジェクトの中身が存在するならTrue,存在しないならFalseを返す
    #という仕組みがある
    def __iter__(self):
        if self.left:
            yield from self.left
        yield self
        if self.right:
            yield from self.right


class BinarySearchTree:

    def __init__(self, values):
        self.root = None
        for value in values:
            self.insert(value)

    def insert(self, value):
        parent_node = None
        #グラフ内を走査しているときの現在地を表すノード
        tmp_node = self.root
        depth = 0
        #ノードを追加する場所を探索
        while tmp_node:
            parent_node = tmp_node
            tmp_node = tmp_node.left if value < tmp_node.value else tmp_node.right
            depth += 1
        #「parent_nodeではないなら」
        #ではなく
        #「parent_nodeが存在しないなら」
        if not parent_node:
            self.root = Node(value, depth)
        else:
            if value < parent_node.value:
                parent_node.left = Node(value, depth)
            else:
                parent_node.right = Node(value, depth)

    def __iter__(self):
        #main関数の下三行でこれが呼び出されている。
        #self.rootはNodeであるので上のNodeクラスの__iter__()がこの後呼び出される
        if self.root:
            yield from self.root

    def print_text(self):
        depth = -1
        #in の後ではsortedにより第一位に深さ、第二位に値、の順に並べられたBinarySearchTreeオブジェクトを
        #リスト化している
        for node in sorted(self, key=lambda node: (node.depth, node.value)):
            if depth != node.depth:
                depth = node.depth
                #print("深さ＝{}".format{depth})と同じ。古いpythonのバージョンでは
                #以下の書き方ではエラーが出るので注意。
                print(f"深さ＝{depth}")
            print(f"\t\t{node.value}")

    def view_graph(self):
        graph = Digraph(format="png")
        #tree(BinSearchTreeクラス)がselfである。
        for node in self:
            #値が同じノードの判別のために深さを組み合わせてノードの名前を決定する
            name = f"{node.value} of {node.depth}"
             #Graphvizでノードを追加
            graph.node(name, str(node.value))
            if node.left:
                #値が同じノードの判別のために深さを組み合わせてノードの名前を決定する
                child = f"{node.left.value} of {node.left.depth}"
                #Graphvizで辺を追加
                graph.edge(name, child, label="left", color="blue")
            if node.right:
                child = f"{node.right.value} of {node.right.depth}"
                graph.edge(name, child, label="right", color="red")
        graph.view("bin_tree")


def main():
    A = [32, 75, 30, 31, 65, 5, 435, 4, 5, 43, 523, 5, 534, 5, 43, 534, 5, 43, 534, 5]
    tree = BinarySearchTree(A)
    tree.print_text()
    tree.view_graph()

if __name__ == "__main__":
    main()