class Node(object):
    def __init__(self, parent, symbol, weight):
        self.parent = parent
        self.symbol = symbol
        self.weight = weight
        self.id = None
        self.nodes = {}

    def __str__(self):
        if self.is_root_node:
            return "Root"

        label = "Leaf" if self.is_leaf_node else "Node"

        return "%s(input='%s',P=%0.4f,id=%s)" % (label, self.matching_string, self.cumulative_weight, self.id)

    def dump(self, depth = 0):
        print "%s %s" % ("*" * (depth + 1), self)
        for _,node in sorted(self.nodes.iteritems()):
            node.dump(depth + 1)

    def add_children(self, symbols_with_weights):
        for symbol, weight in symbols_with_weights:
            self.nodes[symbol] = Node(self, symbol, weight)

    @property
    def is_root_node(self):
        return self.parent is None

    @property
    def is_leaf_node(self):
        return not self.nodes

    @property
    def leaf_count(self):
        if self.is_leaf_node:
            return 1
        else:
            return sum((node.leaf_count for node in self.nodes.itervalues()))

    @property
    def cumulative_weight(self):
        if self.is_root_node:
            return self.weight
        return self.parent.cumulative_weight * self.weight

    @property
    def matching_string(self):
        if self.is_root_node:
            return ""
        return self.parent.matching_string + self.symbol


class RootNode(Node):
    def __init__(self):
        super(RootNode, self).__init__(None, None, 1.0)


def node_list(tree):
    result = [tree]
    for node in tree.nodes.itervalues():
        result += node_list(node)
    return result


def highest_probability_leaf(tree):
    if tree.is_leaf_node:
        return tree

    candidates = [highest_probability_leaf(node) for node in tree.nodes.itervalues()]
    sorted_candidates = sorted(candidates, key=lambda v:v.cumulative_weight)
    return sorted_candidates[-1]


def build_tree(input_symbols, alphabet_size):
    tree = RootNode()

    while (tree.leaf_count < alphabet_size - 1):
        print "Leaf count:", tree.leaf_count
        print "Candidates:"
        for node in node_list(tree):
            if node.is_leaf_node:
                print str(node)

        new_node = highest_probability_leaf(tree)
        print "Choice: ", new_node, "\n"

        new_node.add_children(input_symbols)

    node_id = 0
    leaf_id = 0
    for node in node_list(tree):
        if node.is_leaf_node:
            node.id = leaf_id
            leaf_id += 1
        elif not node.is_root_node:
            node.id = node_id
            node_id += 1

    return tree


def make_symbols(prob_of_0):
    return [('0', prob_of_0), ('1', 1 - prob_of_0)]


input_symbols = make_symbols(0.8)

tree = build_tree(input_symbols, 36)

print "\nTree:"
tree.dump()

print "\nNodes:"
for node in node_list(tree):
    print str(node)