def compprob(fr,e):
    return rc(fr,make_dtree(fr.factors(),frozenset()),e)

def rc(fr,t,e):

    if leaf(t):
        return lookup(t['value'],e)
    else:
        yvars = t['context']
        y = tuple([(var,e[var]) for var in yvars])
        if y in t['cache']:
            return t['cache'][y]
        else:
            p = 0
            cvars = tuple(t['cutset'])
            for cvals in fr.insts(cvars):
                if consistent(cvars,cvals,e):
                    ec = e.copy()
                    ec.update(dict(zip(cvars,cvals)))
                    p += rc(fr,t['left'],ec) * rc(fr,t['right'],ec)
            t['cache'][y] = p
            return p


def consistent(cvars,cvals,e):
    for i, v in enumerate(cvars):
        try:
            if e[v] != cvals[i]:
                return False
        except KeyError:
            pass
    return True

def leaf(t):
    return 'value' in t

def lookup(factor,e):
    vs = sorted(factor.variables())
    indices_to_check = []
    for i, v in enumerate(vs):
        if v in e:
            indices_to_check.append(i)
    result = 0
    for (inst,val) in factor.insts_data_tuple():
        for i in indices_to_check:
            if inst[i] != e[vs[i]]:
                break
        else:
            result += val
    return result

def make_dtree(factors,acutset):

    if len(factors) == 1:
        return {'value':factors[0]}
    
    remaining = set(factors)
    branches = [[],[]]
    vs = [set(),set()]
    # alternate between choosing a factor for
    # branches[0] and branches[1]
    # if, say, choosing for branches[0] find the
    # factor with least overlap with variables in factors in branches[1]
    this_side, other_side = 0, 1
    while remaining:
        best_so_far = len(vs[other_side])
        for factor in remaining:
            overlap_size = len((factor.variables() & vs[other_side]) - acutset)
            if overlap_size == 0:
                best_factor = factor
                break
            if overlap_size <= best_so_far:
                overlap_size = best_so_far
                best_factor = factor
        remaining.remove(best_factor)
        branches[this_side].append(best_factor)
        vs[this_side].update(best_factor.variables())
        this_side, other_side = other_side, this_side
    cutset = (vs[this_side] & vs[other_side]) - acutset
    context = sorted((vs[this_side] | vs[other_side]) & acutset)
    return {
        'left':make_dtree(branches[0],acutset|cutset),
        'right':make_dtree(branches[1],acutset|cutset),
        'cutset': cutset,
        'context': context,
        'cache': {}}
    

def print_dtree(suffix,dtree):
    if 'value' in dtree:
        print suffix, dtree['value'].variables()
    else:
        print_dtree(suffix+'l',dtree['left'])
        print_dtree(suffix+'r',dtree['right'])


#from gPy.Examples import asia
#print compprob(asia,{'VisitAsia':'no_visit','Smoking':'smoker'})
#print compprob(asia,{'VisitAsia':'no_visit'})
#print compprob(asia,{'Smoking':'smoker'})
#print compprob(asia,{'Dyspnea':'absent'})