Description

CS 300 Data Structures

PLEASE NOTE:
SOLUTIONS HAVE TO BE YOUR OWN. NO COLLABORATION OR COOPERATION AMONG STUDENTS IS PERMITTED.
10% PENALTY WILL BE INCURRED FOR EACH DAY OF OVERTIME. SUBMISSIONS THAT ARE LATE MORE THAN 3 DAYS WILL NOT GET ANY CREDITS.
SUBMISSIONS WILL BE MADE TO THE SUCOURSE SERVER. NO OTHER METHOD OF SUBMISSION WILL BE ACCEPTED.

1 Introduction
The İstanbul skyline problem, often mistakenly called the New York skyline problem, is the problem of drawing the skyline of a city given a set of buildings of that city. In this homework you will write a program whose input is a list of the locations and sizes of buildings, and whose output is a description of the visible skyline, that is, how the city looks as an outline, when viewed from a distance. For a real-life version of this problem, go to Vaniköy on the Asian side of the Bosphorus, and, as you sip your tea, contemplate on how the skyline will look as the sun sets over the European side.

To make things simple, the buildings will be given using just two dimensions, x and y, rather than three, ignoring the depth value. (Think of x as horizontal and y as vertical.) Each building will be a rectangle with its base on the x-axis. Thus, a building can be completely described by giving the x-coordinates of its left and right sides, and the y coordinate (or height) of its top side. The input will be read from standard input. The first line of the input indicates how many buildings there are in the city, and each succeeding line will indicate the x-coordinate of the left side of a building followed by the ycoordinate of the top side of the building, followed by the x-coordinate of the right side of the building. The following is an example of a valid input to the program:

4
2 50 10
35 20 55
30 60 45
5 75 25

The output of this program should be a description of the skyline of the city. The skyline is the upper outline of the buildings in the city. To be more precise, the skyline is a function that maps each x-coordinate to the y-coordinate of the tallest building that covers that x-coordinate. Since all of our buildings are rectangles, this function will be a curve consisting of horizontal and vertical line segments. Your program should describe the skyline function by listing each x coordinate at which the height of the skyline changes, along with the new coordinate of the skyline at that x. Your program should do this in the direction of increasing x coordinate (i.e., left to right). For example, the following output describes the skyline of the input above:

0 0
2 50
5 75
25 0
30 60
45 20
55 0

2 The Modified Priority Queue Class
The first part of this assignment is to implement a class that we will call a “Modified Priority Queue,” (MPQ) that will be useful in computing the skyline of a set of buildings. The MPQ is a simple variation on the priority queue class that we used heaps to implement. The only difference is that the items that are maintained by a MPQ object internally have two components (say value and label), as opposed to just a value that is used to compare the items in a priority queue. The first component is again a value with which the items can be compared to each other just as in a priority queue. The other, label, is an identifying number that identifies a specific item in the MPQ. Thus for instance you can insert an item and either access or delete an item with the maximum value component or with a specific identifying number.

Your class definition should at least have the following method that could be useful for the rest of the homework.

• Constructor
• Destructor
• void insert(Comparable value, int label): This method inserts an item with the given value and label into the MPQ.
• Comparable Remove(int label): This method removes the value with this label and returns it.
• Comparable GetMax( ): This method returns the maximum value that is currently stored. (Note that contrary to priority queues, we do not remove the value from the MPQ data structure!)
• Finally, our class must allow us to check if it is empty, using the function
Boolean IsEmpty( ).

3 The Skyline Program
Once you have implemented the MPQ Class, you will write the code that computes the skyline of a city. We suggest the following algorithm outline but certainly you are welcome to come up with your own, but you should employ the MPQ class.
1. Read in the descriptions of all of the buildings from a file called input.txt. The format will be as given earlier.
2. Once you have read all the data in, put all of the x-coordinates of the left and right sides in a separate array (of size twice the number of buildings) together, and sort them into ascending order of the x-coordinates using some fast sorting algorithm (you can use heapsort, but you will have to modify it a bit). With each xcoordinate, also keep the identity of the corresponding building in the same array (e.g., the sequence number of the building as you read them in), and which side (left or right) it belongs to.
3. Make a left-to-right sweep across the city by examining the x-coordinates in the sorted list in ascending order. During the course of the sweep, the MPQ is used to keep track of which buildings span the current x coordinate and which of the buildings has the maximum height. You will have to figure out how to use the MPQ class for this. After each insertion and deletion, check to see if the maximum height of the buildings in the MPQ has changed. If so, output the x- coordinate that has just been examined, followed by the new current maximum height to the standard output.

4 What you should turn in
You should turn in a fully documented source code listing for your MPQ class and your main application program source with any addition classes and procedures. Your programs will be tested with the sample data that we will provide using the format above. Make sure your programs accept input or produce outputs in the specified format and way. If they do not, then you will not get any credits.

You should follow the following steps:
• Name the folder containing your source files as XXXX-NameLastname where XXXX is your student number. Make sure you do NOT use any Turkish characters in the folder name. You should remove any folders containing executables (Debug or Release), since they take up too much space.

• Use the Winzip or an equivalent program to compress your folders to a compressed file named, for example, 5432-AliMehmetoglu.zip. After you compress, please make sure it uncompresses properly and reproduces your folder exactly. We will NOT accept any excuses for files not appearing in your submitted files.

• You then submit this compressed file in accordance with the deadlines above.

Your homework will be graded in the following way:

• If the source code does NOT compile you get 0 points and that is it.

• We will run your program with one or more different input.txt files that we will prepare. If your output is completely correct for all the tests you will get 90 points maximum.

• Note that your outputs should be in the exact same format we described above. If they are not, you will lose points.

• The style of your code will be graded on clarity, commenting, etc. This will cover 10 points. You will however NOT get this credit if your program totally fails in the test we perform. A nice looking but useless program is just a useless program no matter how nice it is.

Good luck!