import math
def entropy(vec):
    answercount = {} 
    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

def condentropy(vec1, vec2):
    if len(vec1) != len(vec2): return -1
    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
    condent = 0
    for x in answervec:
        weight = (0.0+ len(answervec[x])) / totlen
        condent += weight * entropy(answervec[x])
    return condent

def filein(name):
   file = open(name,"r")
   text = file.readlines()
   file.close()
   i = 0
   for x in text:
       if x[len(x)-1:] == "\n":
           text[i] = x[:len(x)-1]
       if i == 0:
           text[i] = text[i].split(" ")
       else:
           text[i] = text[i].split("  ")
       i += 1
   length = len(text)-1
   i = 0
   parsed = {}
   for x in text:
       w = 0
       for z in x:
           if i == 0:
               parsed[z]=[]
           else:
               topics = text[0]
               parsed[topics[w]].append(z)
               w +=1
       i += 1
   return parsed

def new(item,column):
    vec = filein('MakeATree')
    z = 0
    while len(vec[column]) > z:
        if vec[column][z] != item:
            for index in vec:
                vec[index].pop(z)
            z -= 1
        z += 1
    return vec

def mostinfo(idk):
    stuff = {}
    for column in idk:
        stuff[column] = condentropy(idk[column],idk['target'])
    stuff = sorted(stuff, key=stuff.__getitem__)
    if stuff[0] != 'target':
        return stuff[0]
    elif stuff[1] != 'target':
        return stuff[1]

def test(dic):
    most = mostinfo(dic)
    result = []
    test = {}
    for x in dic[most]:
        if x not in result:
            result.append(x)
    result.sort()
    for x in result:
        r = 0
        w = 0
        ones = 0
        for item in dic[most]:
            if item == x:
                ones = ones + int(dic['target'][r])
                w = w+1
            r = r + 1
        test[x] = "No"
        if ones == w:
            test[x] = 1
        elif ones == 0:
            test[x] = 0
    return test

def buildtree(vec):
    info = test(vec)
    for item in info:
        print "If "+mostinfo(vec)+" = "+item+":"
        if info[item] != "No":
            print "   Result =",info[item]
        else:
            vec2 = new(item,mostinfo(vec))
            info2 = test(vec2)
            for item2 in info2:
                print "   If "+mostinfo(vec2)+" = "+item2+":"
                print "     Result =",info2[item2]
                
                        
                
idk = filein('MakeATree')
buildtree(idk)

