Write an application in Python 3.7 that keeps track of traffic fines. All violations are noted by a traffic policeman in a file as a record . At the end of each day, files from all traffic policemen are collated. If a driver had been charged with more than three violations so far, then he has to be booked for further legal action. Also, the police department provides additional bonus to those policemen who have brought in large fine earnings. All policemen who have collected equal to or more than 90% of the highest total fine collected by an individual policeman, shall be awarded the bonus. The program should help the police department answer the below queries: 1. Find out the drivers who are booked for legal action: All such license numbers are to be output in a file called violators.txt. 2. Find out the policemen who are eligible for bonus: The list of policemen eligible for bonus must be output in a file called bonus.txt. Additionally, 3. Perform an analysis of questions 1 and 2 and give the running time in terms of input size, n. Use hash tables for keeping track of drivers (and their violations), and a binary tree for keeping track of policemen (and their bookings). Data structures to be used: DriverHash: A separately chained hash table indexed by license numbers where each entry is of the form < license number, number of violations>. A simple hash function h(x) = x mod M, where M is the size of hash table can be used for this. PoliceTree: This is a Binary Tree of entries of the form
The basic structure of the Police Node will be:
class PoliceNode:
def __init__(self, policeId, fineAmt):
self.policeId = PoliceId
self.fineAmt = fineAmt
self.left = null
self.right = null
Functions: 1. def initializeHash (self): This function creates an empty hash table that points to null. 2. def insertHash (driverhash, lic): This function inserts the licence number lic to the hash table. If a drivers license number is already present, only the number of violations need to be updated else a new entry has to be created. 3. def printViolators (driverhash): This function prints the serious violators by looking through all hash table entries and printing the license numbers of the drivers who have more than 3 violations onto the file violators.txt. The output should be in the format --------------Violators------------- , no of violations 4. def destroyHash (driverhash): This function destroys all the entries inside the hash table. This is a clean-up code. 5. def insertByPoliceId (policeRoot, policeId, amount): This function inserts an entry into the police tree ordered by police id. If the Police id is already found in the tree, then this function adds up to the existing amount to get the total amount collected by him. This function returns the updated tree. 6. def reorderByFineAmount (policeRoot): This function reorders the Binary Tree on the basis of total fine amount, instead of police id. This function removes the nodes from the original PoliceTree, and puts it in a new tree ordered by fine amount. Note that if the fine amount in node i is equal to the amount in node j, then the node i will be inserted to the left of the node j. This function returns the root node of the new tree. 7. def printBonusPolicemen (policeRoot): This function prints the list of police ids which have earned equal to or more than 90% of maximum total fine amount collected by an individual. The output is pushed to a file called bonus.txt. The output will be in the format -------------- Bonus ------------- , no of violations 8. def destroyPoliceTree (policeRoot): This function is a clean-up function that destroys all the nodes in the police tree. 9. def printPoliceTree (policeRoot): This function is meant for debugging purposes. This function prints the contents of the PoliceTree in-order.
2. Sample file formats Sample Input file Every row of the input file should contain the / / in the same sequence. Save the input file as inputPS3.txt Sample inputPS3.txt 111 / 1231114 / 100 111 / 1214413 / 200 222 / 1231412 / 100 222 / 1231114 / 100 333 / 1231114 / 100 Sample violators.txt --------------Violators------------- 1231114, 3 Sample bonus.txt --------------Violators------------- 111, 300 222, 100
