# -*- coding: cp936 -*-
#
#!/usr/bin/env python
# 
# This program computes entropy in a vector
import math

# computes the entropy of a single vector
def entropy(vec):
    answercount = {} # empty dictionary
    totlen = len(vec)
    for x in vec:
        if x in answercount:
            answercount[x] += 1.0
        else: 
            answercount[x] = 1.0
    ent = 0
    for x in answercount:
        prob = (answercount[x])/totlen
        ent += - prob * math.log(prob,2)
    return ent

# computes the entropy of vec2 depending on vec1
def condentropy(vec1, vec2):
    if len(vec1) != len(vec2): return -1 # error
    totlen = len(vec1)
    answervec = {}
    i = 0
    while i < totlen:
        x = vec1[i]
        if x in answervec:
            answervec[x].append(vec2[i])
        else:
            answervec[x] = []
            answervec[x].append(vec2[i])
        i+= 1
    # print "Debugging answervec: ", answervec
    condent = 0
    for x in answervec:
        weight = (0.0+ len(answervec[x])) / totlen 
                	# cond entropy weight of x
        	# print ("Debugging letter: "), x, (" has weight: "), weight
        condent += weight * entropy(answervec[x])
    return condent

# EXECUTION

###############################################################
file = open("MakeATree","r")
text = file.readlines()
file.close()
decider={"D1":[],"D2":[],"D3":[],"D4":[]}
target={"target":[]}
for line in text[1:]:
    line=line.split("  ")
    decider["D1"].append(line[0])
    decider["D2"].append(line[1])
    decider["D3"].append(line[2])
    decider["D4"].append(line[3])
    target["target"].append(line[4].replace("\n",""))
###############################################################
###############################################################
def sdc(decider,target,tree,n):
    sce=1#sub conditional entropy
    xx=""#name of the current decider
    dcurrent={}
    for t in target:
        for x in decider:#find the SMALLEST conditional entropy
            ce=condentropy(decider[x], target[t])
            
            #print x,":",decider[x],ce
            if ce < sce:
                sce = ce
                dcurrent={}
                dcurrent[x] = decider[x]
                xx=x
        if len(dcurrent)>0:#see if there is any dicider left
            #add the name of current decider
            tree+="%s:\n" %xx
            if n!=1:
                n+=(len(xx)+1)
            
            #in case there are two target in the same level
            tempdecider={}
            for x in decider:
                tempdecider[x]=decider[x]
            if xx in tempdecider:
                del tempdecider[xx]
            presubtarget = {}
            subtarget={}
            subdecider ={}
            
            for x in dcurrent[xx]:#initialize the presubtarget
                presubtarget [x]=[]

            for x in dcurrent[xx]:#see if everything is decided
                if len(target[t])>0:
                    presubtarget[x].append(target[t][0])
                    target[t]=target[t][1:]
            #print presubtarget

            for x in presubtarget:#test one of the base case
                if len(presubtarget[x])>0:
                    pe=entropy(presubtarget[x])#presubtarget entropy
                    if pe==0:
                        for i in range(0,n):
                            tree+=" "
                        tree+="¨Á%s (%s happens %s times)|\n" %(x,presubtarget[x][0],str(len(presubtarget[x])))
                    else:
                        subtarget[x]=presubtarget[x] 
            #print subtarget
            if len(subtarget)>0:#see if there are more targets pending
                for x in subtarget:
                    if tree[-1]=="-":
                        n-=1
                    while(tree[-1]!="|"  and tree[-1]!=":" ):
                        tree=tree[:-1]
                    tree+="\n"
                    for i in range(0,n):
                        tree+=" "
                    tree+="¨¹%s-" %x
                    n+=len(x)
                    if (len(tempdecider)>0):#test the other base case
                        for j in tempdecider:#j stands for d1 d2 d3 d4
                            tempdecider[j]=decider[j]
                            pdecider={}#processing decider:use ABCD to select d1-4
                            for k in dcurrent[xx]:#initialize the pdecider
                                pdecider[k]=[]
                            for k in dcurrent[xx]:#dcurrent contains A B C D
                                    if len(tempdecider[j])>0:
                                        pdecider[k].append(tempdecider[j][0])
                                    tempdecider[j]=tempdecider[j][1:]
                            subdecider[j]=pdecider[x]
                        #print x,":",subtarget[x]
                        #print "subdecider: ",subdecider
                        sdc(subdecider,{x:subtarget[x]},tree,n)
                    else:
                        
                        tree+="the end-->no more decider"#no more dicider can be applied
            else:
                for i in range(0,n):
                    tree+=" "
                tree+="¨¹the end-->a full branch"
                print tree

sdc(decider,target,"",1)
top=raw_input("the end")
