CSCI 2311 Lab 8

Computer Science 2311
Fall 2007
Laboratory Assignment 8

Handed out: 10/29/07

Note. Read this entire assignment before beginning to work on it.

The skyline problem

Imagine a collection of buildings in a two-dimensional city. Each building has a horizontal extent (from one integer to another) and a height. You would like to know what the skyline looks like, defined by the tallest building at each position.

The input for this problem is in a file called skyline.txt. Each line describes the two-dimensional profile of a building, giving three integers: the left end, the right end and the height. For example, line

  14 22 105

describes a building that goes from position 14 to position 22 and has height 105. The end of the input is marked by a line that contains

  0  0  0

The assignment

Write a Java program that reads the contents of file skyline.txt and prints the skyline profile. It should print a sequence of lines, each giving a left endpoint, a right endpoint, and a height, indicating a part of the skyline. Two lines in a row must have different heights. The sections must be in left-to-right order. Any place where there is not a building has height 0. The last line of the output must have height 0.

All of the integers in this assignment are greater than or equal to 0 and less than or equal to 10,000.

An algorithm

Create an array of all of the horizontal positions, holding the skyline height at each position. Initialize it to hold 0 in each position. Now read the buildings, one at a time. For each building, insert it into the skyline by looping through the array, possibly storing new heights. Be sure only to increase heights. A short building does not lower the skyline.

After filling the array, scan it, looking for places where the height changes. After you have found a section of constant height, print out information about that section, and then get the next section.

Reading a file

To read the file, create two objects, on a raw reader that just knows how to get characters from a file, and another a more pleasant thing that knows how to get integers, strings, etc.

  boolean success = false;
  FileReader reader = null;
  try 
  {
    reader = new FileReader("skyline.txt");
    success = true;
  } 
  catch(FileNotFoundException e) {
    System.out.println("Cannot read file skyline.txt");
  }

  if(success) 
  {
    Scanner scan = new Scanner(reader);
    ...
    int left = scan.nextInt();
    int right = scan.nextInt();
    int height = scan.nextInt();
    ...

    scan.close();
  }

In order to use the FileReader and Scanner classes, do the following imports.

  import java.io.*;
  import java.util.*;

The nextInt() method of a scanner gets the next integer, and moves the scanner ahead after that integer. When you are finished reading from the scanner, close it as shown. Do not close it before you have read everything.

The try part is needed to check for the case where the file does not exist.

Creating an array

You will need an array of integers, which has type int[]. Line

  int[] a;

makes a variable that can refer to an array. To make it refer to a newly created array, use

  a = new int[n];

where n is the number of slots in the array. Subscripts are written in square brackets after the array, and go from 0. So, to create a new array of 3 integers and fill it with the value 0, you can write

  int[] a = new int[3];
  a[0] = 0;
  a[1] = 0;
  a[2] = 0;

But you can also use a loop to do the same thing. Here it is with a for loop.

  int[] a = new int[3];
  for(int i = 0; i < 3; i++) a[i] = 0;