# ML Program 2 - Decision Tree (ID3 / Gain Ratio)
import pandas as pd
import numpy as np
import math

def read_data(filename):
    data = pd.read_csv(filename)
    metadata = list(data.columns)
    traindata = data.values.tolist()
    return (metadata, traindata)

class Node:
    def __init__(self, attribute):
        self.attribute = attribute
        self.children = []
        self.answer = ""

    def __str__(self):
        return self.attribute

def subtables(data, col, delete):
    dic = {}
    items = np.unique(data[:, col])
    count = np.zeros(items.shape[0], dtype=np.int32)

    for x in range(items.shape[0]):
        for y in range(data.shape[0]):
            if data[y, col] == items[x]:
                count[x] += 1

    for x in range(items.shape[0]):
        dic[items[x]] = np.empty((count[x], data.shape[1]), dtype="|S32")
        pos = 0
        for y in range(data.shape[0]):
            if data[y, col] == items[x]:
                dic[items[x]][pos] = data[y]
                pos += 1

        if delete:
            dic[items[x]] = np.delete(dic[items[x]], col, 1)

    return items, dic

def entropy(S):
    items = np.unique(S)

    if items.size == 1:
        return 0

    counts = np.zeros(items.shape[0])
    sums = 0

    for x in range(items.shape[0]):
        counts[x] = sum(S == items[x]) / float(S.size)

    for count in counts:
        if count > 0:
            sums += -count * math.log(count, 2)

    return sums

def gain_ratio(data, col):
    items, tables = subtables(data, col, delete=False)

    total_size = data.shape[0]
    total_entropy = entropy(data[:, -1])
    weighted_entropy = 0
    intrinsic_value = 0

    for value in items:
        subset = tables[value]
        ratio = subset.shape[0] / total_size

        weighted_entropy += ratio * entropy(subset[:, -1])

        if ratio > 0:
            intrinsic_value -= ratio * math.log(ratio, 2)

    information_gain = total_entropy - weighted_entropy

    if intrinsic_value == 0:
        return 0

    return information_gain / intrinsic_value

def create_node(data, metadata):
    if (np.unique(data[:, -1]).shape[0] == 1):
        node = Node("")
        node.answer = np.unique(data[:, -1])[0]
        return node

    gains = np.zeros((data.shape[1] - 1, 1))

    for col in range(data.shape[1] - 1):
        gains[col] = gain_ratio(data, col)

    split = np.argmax(gains)

    node = Node(metadata[split])
    metadata = np.delete(metadata, split, 0)

    items, dic = subtables(data, split, delete=True)

    for value in items:
        child = create_node(dic[value], metadata)
        node.children.append((value, child))

    return node

def empty(size):
    s = ""
    for x in range(size):
        s += " "
    return s

def print_tree(node, level):
    if node.answer != "":
        print(empty(level), node.answer)
        return

    print(empty(level), node.attribute)

    for value, n in node.children:
        print(empty(level + 1), value)
        print_tree(n, level + 2)

metadata, traindata = read_data('ML2-Dataset.csv')
data = np.array(traindata)
data1 = np.array(metadata)

node = create_node(data, metadata)
print_tree(node, 0)
