In this Problem, you have to 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 has been charged with greater than five violations, then he has to be booked for further legal action. Also, the police department wants to take strict action on policemen who are not performing their duties. All policemen will have to book at least 10 violators in a given period to avoid further action.

The program should help the police department generate reports on the below queries:

1. Generate a list of license numbers which are repeat offenders.

2. Generate a list of policemen who are not meeting the monthly targets.

3. Top 10 policemen that have made the most bookings and total fine amount they have collected.

Additionally,

4. Perform an analysis of questions 1, 2 and 3 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 . 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:

Operations:

1. def initializeHash (self): This function creates an empty hash table that points to null.

1. 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.

1. def printViolators (driverhash): This function prints the repeat violators by looking through all hash table entries and printing the license numbers of the drivers who have greater than and equal to 5 violations onto the file violators.txt. The output should be in the format

--------------Violators-------------

, no of violations

1. def destroyHash (driverhash): This function destroys all the entries inside the hash table. This is a clean-up code.

1. 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 and increments the bookingCount by 1. This function returns the updated tree.

1. def reorderPoliceTree (policeRoot): This function reorders the Binary Tree on the basis of total number of bookingCount. This function removes the nodes from the original PoliceTree, and puts it in a new tree ordered by bookingCount. Note that if the count in node i is equal to the count 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.
2. def printPolicemen (policeRoot): This function prints the list of police ids which have not met the target of at least 10 bookings. The output is pushed to a file called police.txt. The output will be in the format

-------------- Police list -------------

Police id, no of bookings

1. def printTopTen(policeRoot): This function prints the list of top 10 police ids based on total number of bookings. The output is pushed to a file called police.txt. The output will be in the format

-------------- Police Top 10 -------------

Police id, no of bookings, total fine amount

1. def destroyPoliceTree (policeRoot): This function is a clean-up function that destroys all the nodes in the police tree.

1. def printPoliceTree (policeRoot): This function is meant for debugging purposes. This function prints the contents of the PoliceTree in-order.

Sample file formats

Sample Input file

Every row of the input file should contain the / / in the

same sequence. Save the input file as inputPS2.txt

Sample inputPS2.txt

111 / 1231114 / 100

111 / 1214413 / 200

222 / 1231412 / 100

222 / 1231114 / 100

333 / 1231114 / 100

Sample violators.txt

--------------Violators-------------

1231114, 3

Sample police.txt

--------------Police list-------------

111, 2

222, 2

-------------- Police Top 10 -------------

555, 15, 2100

Note that the input/output data shown here is only for understanding and testing, the actual file used for evaluation will be different.

class PoliceNode: def init (self, policeID, fineAmt): self.policeID = policeID self.fineAmt = fineAmt self.bookingCount =1 self.left = None self.right = None