#######################
# Constraint Networks #
#######################

################
# SICP Version #
################

class Connector:
    """A connector between constraints.

    >>> celsius = Connector('Celsius')
    >>> fahrenheit = Connector('Fahrenheit')
    >>> converter(celsius, fahrenheit)

    >>> celsius.set('user', 25)
    Celsius = 25
    Fahrenheit = 77.0

    >>> fahrenheit.set('user', 212)
    Contradiction detected: 77.0 vs 212

    >>> celsius.forget('user')
    Celsius is forgotten
    Fahrenheit is forgotten

    >>> fahrenheit.set('user', 212)
    Fahrenheit = 212
    Celsius = 100.0
    """

    def __init__(self, name=None):
        self._name = name
        self._informant = None   # The source of the current val
        self._constraints = []   # A list of connected constraints
        self.val = None

    def set(self, source, value):
        if self.val is None:
            self._informant, self.val = source, value
            if self._name is not None:
                print(self._name, '=', value)
            self.inform_all_except(source, lambda x: x.new_val())
        else:
            if self.val != value:
                print('Contradiction detected:', self.val, 'vs', value)

    def forget(self, source):
        if self._informant == source:
            self._informant, self.val = None, None
            if self._name is not None:
                print(self._name, 'is forgotten')                
            self.inform_all_except(source, lambda x: x.forget())

    def has_val(self):
        return self.val is not None

    def connect(self, source):
        self._constraints.append(source)

    def inform_all_except(self, source, action):
        """Apply ACTION to all constraints, except SOURCE."""
        for c in self._constraints:
            if c != source:
                action(c)

class TernaryConstraint:
    """Represents a constraint on the values three connectors."""

    def __init__(self, a, b, c, ab, ca, cb):
        """The constraint that AB(A, B) = C, CA(C, A) = B, and CB(C, B) = A."""
        self._connectors = a, b, c
        self._funcs = ab, ca, cb

    def new_val(self):
        a, b, c = self._connectors
        ab, ca, cb = self._funcs
        av, bv, cv = [connector.has_val() for connector in self._connectors]
        if av and bv:
            c.set(self, ab(a.val, b.val))
        elif av and cv:
            b.set(self, ca(c.val, a.val))
        elif bv and cv:
            a.set(self, cb(c.val, b.val))
        
    def forget(self):
        for c in self._connectors:
            c.forget(self)
        
    def connect(self):
        for c in self._connectors:
            c.connect(self);

class ConstantConstraint:
    """Represents a constraint that a connector has a specific constant value."""
    def __init__(self, connector, v):
        self._connector, self._val = connector, v
        
    def new_val(self):
        pass

    def forget(self):
        pass

    def connect(self):
        self._connector.set(self, self._val)
        return self

from operator import add, sub, mul, truediv

def adder(a, b, c):
    """The constraint that a + b = c."""
    return TernaryConstraint(a, b, c, add, sub, sub).connect()

def multiplier(a, b, c):
    """The constraint that a * b = c."""
    return TernaryConstraint(a, b, c, mul, truediv, truediv).connect()

def constant(connector, value):
    """The constraint that connector = value."""
    return ConstantConstraint(connector, value).connect()

def converter(c, f):
    """Connect c to f to convert from Celsius to Fahrenheit."""
    u, v, w, x, y = [Connector() for _ in range(5)]
    multiplier(c, w, u)
    multiplier(v, x, u)
    adder(v, y, f)
    constant(w, 9)
    constant(x, 5)
    constant(y, 32)

###################
# Arc Constraints #
###################

class Var:
    """A constrained variable."""

    def __init__(self, name, domain):
        """A variable whose domain of possible values is initially DOMAIN."""
        self._dom = domain
        self._name = name
        self.entering_constraints = []
        self.exiting_constraints = []

    def values(self):
        return self._dom

    def constrain_entering(self, constraint):
        """Add CONSTRAINT to my entering constraints."""
        self.entering_constraints.append(constraint)

    def constrain_exiting(self, constraint):
        """Add CONSTRAINT to my exiting constraints."""
        self.exiting_constraints.append(constraint)

    def remove(self, v, constraint, todo):
        self._dom.remove(v)
        if not self._dom:
            raise ConstraintError("variable {} has no possible value".format(self._name)
        todo.update(self.entering_constraints)
        for c in self.exiting_constraints:
            if c is not constraint:
                todo.add(c)

def ArcConstraint:
    """A constraint between two Vars."""

    def __init__(self, v1, v2, pred):
        """The constraint that for each value x1 in the possible values of
        V!, there must be a value x2 in the values of V2 such that
        PRED(x1, x2)."""
        self._v1, self._v2, self._pred = v1, v2, pred

    def add(self):
        self._v1.constrain_exiting(self)
        self._v2.constrain_entering(self)

    def check(self, todo):
        remove = []
        for x1 in self._v1.values():
            for x2 in self._v2.values():
                if self._pred(x1, x2):
                    break
            else:
                remove.append(x1)
        for x1 in remove:
            self._v1.remove(x1, self, todo)

def solve(vars):
    todo = {}
    for v in vars:
        todo.update(v.entering_constraints, v.exiting_constraints)

    while todo:
        todo.pop().check(todo)