#!/usr/bin/python
# -*- coding: utf-8 -*-
# From Darius Bacon’s article on the Language of Choice

class Node(object):
    "A decision-tree node."
    def evaluate(self, env):
        "My value when variables are set according to env, a dictionary."
        abstract
    def __call__(self, if0, if1):
        "Return an expression whose value is if0's or if1's, according to self's."
        return Choice(self, if0, if1)
    def visit(self, visitor, value):
        "Traverse this subtree with the given visitor."
        abstract

class ConstantNode(Node):
    def __init__(self, value): self.value = value
    def __repr__(self):        return repr(self.value)
    def evaluate(self, env):   return self.value
    def visit(self, v, u):     return v.visit_constant(self, self.value, u)

class VariableNode(Node):
    def __init__(self, name):  self.name = name
    def __repr__(self):        return self.name
    def evaluate(self, env):   return env[self]
    def visit(self, v, u):     return v.visit_variable(self, self.name, u)

class ChoiceNode(Node):
    def __init__(self, index, if0, if1):
        self.index, self.if0, self.if1 = index, if0, if1
    def __repr__(self):
        return '%r(%r, %r)' % (self.index, self.if0, self.if1)
    def evaluate(self, env):
        branch = (self.if0, self.if1)[self.index.evaluate(env)]
        return branch.evaluate(env)
    def visit(self, visitor, v):
        a = visitor.pre_visit(self, v)
        b = self.if0.visit(visitor, a)
        c = self.if1.visit(visitor, b)
        return visitor.post_visit(self, a, b, c)

def memoize(f):
    """Return a function like f but caching its results. Its arguments
    must be hashable."""
    def memoized(*args):
        try: return memoized._memos[args]
        except KeyError:
            result = memoized._memos[args] = f(*args)
            return result
    memoized._memos = {}
    return memoized

Variable = VariableNode

def Choice(index, if0, if1):
    if if0 == if1:                            # A(B, B) --> B
        return if0
    elif (if0, if1) == (const0, const1):      # A(0, 1) --> A
        return index
    else:
        return ChoiceNode(index, if0, if1)

Choice = ChoiceNode

Constant = memoize(ConstantNode)
const0, const1 = Constant(0), Constant(1)
A, B, C, D = map(Variable, 'ABCD')

def express(variables, table):
    """Return an expression e such that, for each key in table,
    e.evaluate(dict(variables, key)) == table[key]."""
    if not table:
        return const0      # Or 1, doesn't matter.
    elif len(table) == 1:
        return Constant(table.values()[0])
    else:
        first_var, rest_vars = variables[0], variables[1:]
        return first_var(express(rest_vars, subst_for_first_var(table, 0)),
                         express(rest_vars, subst_for_first_var(table, 1)))

def subst_for_first_var(table, first_var_value):
    """Return a subtable of table, eliminating the first variable and
    supposing it'll take the given value."""
    return {keys[1:]: output
            for keys, output in table.items() if keys[0] == first_var_value}

maj = express((A, B, C), {(0,0,0): 0,  (1,1,1): 1,
                          (0,0,1): 0,  (1,1,0): 1,
                          (0,1,0): 0,  (1,0,1): 1,
                          (0,1,1): 1,  (1,0,0): 0})

def graphvizify(node):
    return 'digraph bdd {\n\t' + '\n\t'.join(graphviz_visit(node)) + '\n}\n'

class GraphvizVisitor:
    def __init__(self):
        self.nodes = set()

    def visit_variable(self, variable, name, _):
        if variable in self.nodes:
            return []
        self.nodes.add(variable)
        return ['"%s" [label=%s, shape=box]' % (id(variable), name)]

    def visit_constant(self, constant, value, _):
        if constant in self.nodes:
            return []
        self.nodes.add(constant)
        return ['"%s" [label=%s, shape=circle]' % (id(constant), value)]

    def pre_visit(self, node, _):
        pass

    def post_visit(self, node, _, left, right):
        if node in self.nodes:
            return []
        self.nodes.add(node)
        return ['"%s" [label=%s, shape=diamond]' % (id(node), node.index),
                '"%s" -> "%s" [label=0]' % (id(node), id(node.if0)),
                '"%s" -> "%s" [label=1]' % (id(node), id(node.if1)),
                ] + left + right

def graphviz_visit(node):
    return node.visit(GraphvizVisitor(), None)

parity = {(0,0,0,0): 0,  (0,0,0,1): 1,  (1,0,0,1): 0,  (1,0,0,0): 1,
          (0,0,1,1): 0,  (0,0,1,0): 1,  (1,0,1,0): 0,  (1,0,1,1): 1,
          (0,1,0,1): 0,  (0,1,0,0): 1,  (1,1,0,0): 0,  (1,1,0,1): 1,
          (0,1,1,0): 0,  (0,1,1,1): 1,  (1,1,1,1): 0,  (1,1,1,0): 1}

#ChoiceNode = memoize(ChoiceNode)

print graphvizify(express((A,B,C,D), parity))