Algorithm Analysis with Advanced Data Structures, 

Your good friend, a Rock Star, asked you to create a Time Manager app for him

The Rock Star performs gigs at certain dates, all around the country - at most one gig per day

His memory is poor, though – he often forgets if (and where) he is supposed to play on a certain date

After confirming he has a gig at a certain night, the Rock Star often wants to know when and where the next performance will be 

Write a program cmsc401.java that

receives a sequence of commands (from 1 up to 10000 commands)

a command can be one of: 

1 - an insert – add the date and city to “gig plan”

2 - a ‘date’ query – check if there’s a gig planned at a certain 

date (and if yes, which city)

3 - a ‘next gig’ query – for the gig found using most recent 

“command 2”, check when and where the next performance is

4 – end of sequence of commands, quit the program the sequence of commands always ends with Command 4

Command 3 always is preceded immediately by Command 2

Command 3 is given only if Command 2 returned data & city (that is, there was a gig planed at a queried date)

the sequence of commands is presented at standard input,

each line is a new command

format of the commands and responses to them:

1 - insert a gig, 

input format is “1 YYYYMMDD STRING”, no output

YYYYMMDD represents the date – date can by anything in the 21st century

STRING represents the city and is up to 10 characters in length

2 – a ‘date’ query, 

input format is “2 YYYYMMDD”, 

output format is “YYYYMMDD STRING” if there is a gig on that date, or 

“YYYYMMDD NO GIG” if not3 – a ‘next gig’ query

input format is “3”

output format is data and place of next gig: “YYYYMMDD STRING”, 

or “NO NEXT GIG” if there’s no next gig in database

4 – quit

input format is “4”, no output, program exits

Use Standard I/O to read input and write the result

In Java, it’s System.in for input, System.out for output