Home

##Project Description This project is about implementing the event counter using AVL tree. Each event has two fields: ID and count, where count is the number of active events with the given ID. The event counter stores only those ID’s whose count is > 0. Once a count drops below 1, that ID is removed. Initially, your program must build AVL tree from a sorted list of n events (i.e., n pairs (ID, count) in ascending order of ID) in O(n) time. Your counter should support the following operations in the specified time complexity.

Command	Description	Time Complexity
Increase(ID, m)	Increase the count of the event ID by m. If ID is not present, insert it. Print the count of ID after the addition	O (log n)
Reduce(ID, m)	Decrease the count of ID by m. If ID’s count becomes less than or equal to 0, remove ID from the counter. Print the count of ID after the deletion, or 0 if ID is removed or not present.	O (log n)
Next(ID)	Print ID and count of the event with lowest ID that is greater than ID. Print “0 0” if there is no next ID.	O (log n)
Count(ID)	Print the count of ID. If not present print 0.	O (log n)
Previous(ID)	Print ID and count of the event with greatest ID that is less than ID. Print “0 0” if there is no previous ID.	O (log n)
InRange (ID1 ,ID2)	Print the total count for IDs between ID1 and ID2 inclusively. Note ID1 ≤ ID2 .	O(log n + s), where s is the number of ID in this range.

##Input/output Requirements Your program has to support redirected input from a file "file-name" which contains the initial sorted list. The command line for this mode is as follows :

$java bbst file-name 
Input format 
n
ID1 count1
ID2 count2
...
IDn countn

Assume that IDi < IDi+1 where IDi and counti are positive integers and the total count fits in 4-byte integer limits.

Interactive part:

Read the commands from the standard input stream and print the output to the standard output stream. Use the command specifications described in part 1 with all lower cases. The command and the arguments are separated by a space, not parenthesis or commas (i.e. “inrange 3 5” instead of “InRange(3, 5)”). At the end of each command, there will be an EOL character. For each command, print the specified output in the table. Use one space if more than one numbers are printed. Print an EOL character at the end of each command. To exit from the program, use “quit” command.