#!/usr/bin/env python
#
# Decision Tree
    
def filein():
    file = open("MakeATree","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:
                attributes = text[0]
                parsed[attributes[w]].append(z)
                w +=1
        i += 1
    return parsed
    print parsed

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
data = filein() #stores file dictionary in 'data'
print data
res1 = entropy(data['D1'])
print "The entropy of the vector 'D1' is: ", res1
res2 = entropy(data['D2'])
print "The entropy of the vector 'D2' is: ", res2
res3 = entropy(data['D3'])
print "The entropy of the vector 'D3' is: ", res3
res4 = entropy(data['D4'])
print "The entropy of the vector 'D4' is: ", res4
res5 = entropy(data['target'])
print "The entropy of the target vector is: ", res5
resA = condentropy(data['D1'], data['target'])
print "conditional entropy of the target vector knowing D1 is: ", resA
igA = entropy(data['target']) - condentropy(data['D1'],data['target'])
print "information gain D1 = ", igA
resB = condentropy(data['D2'], data['target'])
print "conditional entropy of the target vector knowing D2 is: ", resB
igB = entropy(data['target']) - condentropy(data['D2'],data['target'])
print "information gain D2 = ", igB
resC = condentropy(data['D3'], data['target'])
print "conditional entropy of the target vector knowing D3 is: ", resC
igC = entropy(data['target']) - condentropy(data['D3'],data['target'])
print "information gain D3 = ", igC
resD = condentropy(data['D4'], data['target'])
print "conditional entropy of the target vector knowing D4 is: ", resD
igD = entropy(data['target']) - condentropy(data['D4'],data['target'])
print "information gain D4 = ", igD

ig = [igA, igB, igC, igD]
ig.sort(reverse=True)
print ig

if ig[0] == igA:
    A = "D1", data['D1']
elif ig[0] == igB:
    A = "D2", data['D2']
elif ig[0] == igC:
    A = "D3", data['D3']
else:
    A = "D4", data['D4']
if ig[1] == igA:
    B = "D1", data['D1']
elif ig[1] == igB:
    B = "D2", data['D2']
elif ig[1] == igC:
    B = "D3", data['D3']
else:
    B = "D4", data['D4']
if ig[2] == igA:
    C = "D1", data['D1']
elif ig[2] == igB:
    C = "D2", data['D2']
elif ig[2] == igC:
    C = "D3", data['D3']
else:
    C = "D4", data['D4']
if ig[3] == igA:
    D = "D1", data['D1']
elif ig[3] == igB:
    D = "D2", data['D2']
elif ig[3] == igC:
    D = "D3", data['D3']
else:
    D = "D4", data['D4']

print A
print B
print C
print D

target = data['target']
attributes = [A, B, C, D, target]

