import os

class PoliceNode:
    """docstring for PoliceNode"""
    def __init__(self, policeId, fineAmt):

        self.policeId = policeId
        self.fineAmt = fineAmt
        self.left = None
        self.right = None


class DriverHash:
    """docstring for DriverHash"""
    def __init__(self, max_size):
        self._map = None
        self.max_size = max_size

    def initializeHash(self):
        self._map = [None for i in range(0, self.max_size)]

    def get(self, hash):
         return self._map[hash]

    def put(self, hash_index, value):
        self._map[hash_index] = value


def insertHash(driverhash, lic):
    """
    Inserts/increments the counter for given licence number
    Note: considering licence number as Integer
    """
    hash = lic%driverhash.max_size
    bucket = driverhash.get(hash)
    if bucket is not None:
        hasLicence=False
        for index, (licence, violation_cnt) in enumerate(bucket):
            if licence==lic:
                hasLicence = True
                bucket[index] = (lic, violation_cnt+1)
        if not hasLicence:
            bucket.append((lic, 1))
    else:
        driverhash.put(hash,[(lic, 1)])


def printViolators(driverhash):

    with open("violators.txt", "w") as f:
        for hash_index in range(0, driverhash.max_size):
            if driverhash.get(hash_index):
                for licence, violation_cnt in driverhash.get(hash_index):

                    if violation_cnt>3:
                        # given more than 3 in qn
                        f.write("{},{}\n".format(licence, violation_cnt))


def destroyHash(driverhash):
    driverhash.hashmap = None

def insertByPoliceId(policeRoot, policeId, amount):

    if policeRoot is None:
        policeRoot = PoliceNode(policeId, amount)
        return policeRoot
    elif policeId == policeRoot.policeId:
        policeRoot.fineAmt = policeRoot.fineAmt + amount
        return policeRoot
    elif policeId<policeRoot.policeId:
        policeRoot.left = insertByPoliceId(policeRoot.left, policeId, amount)
        return policeRoot
    else:
        policeRoot.right = insertByPoliceId(policeRoot.right, policeId, amount)
        return policeRoot

def insertByAmount(root, current):

    if root is None:
        root = current
        return root
    elif current.fineAmt>root.fineAmt:
        root.right = insertByAmount(root.right, current)
        return root
    else:
        root.left = insertByAmount(root.left, current)
        return root


def reorderByFineAmount(policeRoot):
    if policeRoot is None:
        return
    queue = []
    newRoot = None
    queue.append(policeRoot)
    while(len(queue) > 0):
        node = queue.pop(0)
        print(node.policeId)

        if node.left is not None :
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)
        node.left=None
        node.right=None
        newRoot = insertByAmount(newRoot, node)
    return newRoot


def max_fine_amount(policeRoot):
    if policeRoot is not None:
        max_fine_amt = policeRoot.fineAmt
        lmax = max_fine_amount(policeRoot.left) or 0
        rmax = max_fine_amount(policeRoot.right) or 0
        if (lmax>max_fine_amt):
            max_fine_amt = lmax
        if (rmax>max_fine_amt):
            max_fine_amt = rmax
        return max_fine_amt

def printBonusPolicemen(policeRoot):
    if policeRoot is not None:
        print(policeRoot.fineAmt)
        max_fine_90p = max_fine_amount(policeRoot) * 0.9
        queue = []
        queue.append(policeRoot)
        with open("bonus.txt", "w") as f:
            while(len(queue) > 0):

                node = queue.pop(0)
                if node.fineAmt>=max_fine_90p:
                    f.write("{},{}\n".format(node.policeId, node.fineAmt))
                if node.left is not None :
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)

def printPoliceTree(policeRoot):

    if policeRoot is not None:
        printPoliceTree(policeRoot.left)
        print("{},{}".format(policeRoot.policeId, policeRoot.fineAmt))
        printPoliceTree(policeRoot.right)


def destroyPoliceTree (policeRoot):
    policeRoot=None
if __name__ == '__main__':
    import sys
    driverhash= DriverHash(16)
    driverhash.initializeHash()
    policeRoot = None
    with open("inputPS3.txt","r") as fp:
        for line in fp :
            try:
                if line.strip()!="":
                    police_id = int(line.split("/")[0])
                    licence = int(line.split("/")[1])
                    amount = int(line.split("/")[2])
                    insertHash(driverhash, licence)
                    policeRoot = insertByPoliceId(policeRoot, police_id, amount)
            except Exception as e:
                print(e)

    printViolators(driverhash)
    printPoliceTree(policeRoot)
    newPoliceRoot = reorderByFineAmount(policeRoot)
    printPoliceTree(newPoliceRoot)
    printBonusPolicemen(newPoliceRoot)
    destroyHash(driverhash)
    destroyPoliceTree(policeRoot)