Ground-penetrating radar ("GPR") sends pulsed radio waves into the ground and receives them as they reflect back. As with radar in air or water (sonar), GPR waves are distorted when they hit various materials—water, stone, bone, wood, metals, etc.—resulting in reflected waves that differ in shape and intensity depending upon what they “hit.” The reflected wave data is (computer) processed and recorded. When combined with the location of the readings, a two-dimensional map of the area can be composed, kind of like an aerial photograph of what’s under the ground. GPR is used for several purposes, but is perhaps most noted for accessing an area's archeological significance much faster (and cheaper) than digging. (To learn more about GPR, check out, for example, the Ground-penetrating radar entry in Wikipedia).

In the context of this program, each surveyed site has a title. The surveyed area is always a grid, a two-dimensional, rectangular array of equal-sized square cells. For each cell that has been surveyed, we have its row number (starting at 0), column number (starting at 0), the intensity of the reading (from 1 to 600), and the time the reading was taken. Data for a cell in the gird area not (yet) surveyed is either not given, or it appears as special values indicating the cell’s intensity is not yet known and the time is not applicable.

In this assignment, you complete a program to convert the GPR data from a text file (created by a download from a GPR field unit) into memory structures so that (already written) graphics routines can use it to produce an on-screen false color-coded map of the area surveyed, along with a report of the collected data. You gain practice with two-dimensional arrays and linked-list-based priority queues, a review of several programming concepts and Java features covered in ICS 21 and ICS 22, and an opportunity to make heavy use of pre-existing classes for which you have no source code—one of the most valuable of real-world programming skills. (This program is less sophisticated than a typical real-world GPR program, as this assignment is not about writing a full-blown GPR app; it’s about applying data structure and alogrithm concepts to an actual programmming problem.)

To view a GPR survey’s map and report, the user runs the GPR Viewer program (java GPR); this screen appears:

The user enters the name of a file in the GPR File Name: text box and presses the View button. If the file does not exist, an error message prints and the screen is otherwise left unchanged. If the file does exist, a color-coded map of the surveyed area appears in the map area above the file name and a text report containing survey information appears in the right-side window.

The program maps each cell to a position in the map area, corresponding to the cell’s row and column position in the grid. For instance, if the cell is at position (1,4) in the gird, it is displayed at position (1,4) on the map. The cell's size is set so that the grid fills the map window in at least one dimension—so if the survey area has few cells, each cell will be quite large. (Typically, each cell is relatively small compared to the survery area, so more precise readings of the area can be obtained.) Each cell is displayed in a color determined by its intensity; an intensity of 0 indicates the cell has yet to be surveyed, so the program leaves its cell unfilled:

The report displays the site name, the number of rows and the number of columns. It then lists each cell’s information, one cell per line. When the report is first displayed, the cells are sorted by intensity (see below for details). The user can press any of the buttons Sort by Intensity, Sort by Time, Sort by Row and Sort by Column to place cell data in that so-named ordering. The sort orders are

• Sort by Intensity: in order of decreasing intensity and, within each intensity value, sorted in ascending row order and, for each row, in ascending column order; unsurveyed cells that appear in the file are at the bottom of the list (as they have intensity 0)

• Sort by Time: in order of decreasing time (that is, most recently surveyed items appear first) and, within each time, sorted in ascending row order and, for each row, in ascending column order; unsurveyed cells that appear in the file appear at the bottom of the list

• Sort by Row: in order of increasing row number and, within each row, in ascending column order

• Sort by Column: in order of increasing column number and, within each column, in ascending row order

We’ve provided the code that handles the graphic display of the map and report. Your task is to supply the code that reads the information from the GPR data file and prepares the grid; it contains the same information as the file, but in a form appropriate for use by the graphics routines the control the grid map. You also write the code that takes information from the grid and "massages it" into the GPR report; that report, as a (very long) string, is then “picked up” by the graphics routines when appropriate and displayed in the report window.

Except for the code you will write, all of the code that you’ll need to complete this project is included in the Unearthed Zip archive. Much of the provided code is compiled (i.e. in .class files). There are four provided Java files; they should be left unchanged:

• GPR.java: the main progam; it also gives a brief description of the program

• CellInfoInterface.java: an interface that describes (and enforces some requirements for) the cell class, which contains the information about one cell of the grid; you write the cell class

• GPRGridInterface.java: an interface that describes (and enforces some requirements for) the grid class; you write the grid class

• SurveyReportInterface.java: an interface that describes (and enforces some requirements for) the report; you write the report class

• The exact format of the report is up to you, but it must (1) contain all the data that is in the GPR data file (2) be formatted so the site name, and number of rows and columns, appear at the top of the report, followed by cell information, with each cell’s information on one (and its own) line, and (3) be formatted so it is easy to read and locate specfic information (e.g., a user should be able to find the information about a particular cell quickly). You will lose points if your report is hard to read or understand.

• To sort the cells into a given order for the report, you must use a priority queue based on an unordered linked list. You can use Java’s LinkedList collection class, write your own linked-list class, or adapt a linked-list class from a text, a web site that allows such adaptation of its code, or class notes from this or another course. If you adapt your list code from another source, be sure to cite your source in comments in your code.—not doing so is considered plagarism!

  You must write your own priority queue class (which, of course, uses linked list class objects as appropriate).

The ZIP file also contains some test files to help you debug your program; they (and only they) end in the txt extension. For example, here is what the file SimpleTest.txt produces:

The gird patterns these files produce should look what their names imply. The files ending in BIG can take several minutes to process, so, obviously, use them once after you have your prgoram working on the smaller files.

You will note the report generated from these files is very poorly formatted; we did this purposely, to give you an idea of what not to do for your report. Your report showing the data from the test files should be much nicer, as described above.

Obvously, the users of the this GPR progam do not want to wait more than necessary to see a map and report; one the View button his clicked, the results need to display as quickly as feasible.

The main determiner of the speed of this program is how long the data files, especially the big files, take to process, and that depends mainly upon the priority queue implementation and the Java string classes we use. You’ll learn about other, faster, implementations of priority queues later in the course. But, even with this exercise&$146;s priority queue structure, the program can be made several times faster by using the right Java string class.

It turns out that main activity that slows down the program is constructing the report, which requires concatenating many, many pieces of information into one very long string, as the graphics routine that prints the report can only handle a single string as its input. If you use the standard String class, these concatenations takes a very long time. Strings are immutable; that is, they cannot change once assigned a value. So each time a concatenation is done requires that a new target string be allocated to hold the result, and the (large) concatenated string be copied into that new String object, a very time-consuming task.

However, Java also provides a StringBuffer class that

is like a String, but can be modified. At any point in time it contains some particular sequence of characters, but the length and content of the sequence can be changed...

The principal operations on a StringBuffer are the append and insert methods, which are overloaded so as to accept data of any type. Each effectively converts a given datum to a string and then appends or inserts the characters of that string to the string buffer. The append method always adds these characters at the end of the buffer; the insert method adds the characters at a specified point.

For example, if z refers to a string buffer object whose current contents are "start", then the method call z.append("le") would cause the string buffer to contain "startle", whereas z.insert(4, "le") would alter the string buffer to contain "starlet". [Java StringBuffer API documentation, http://java.sun.com/javase/6/docs/api/]

Thus, append works like concatenation for Strings, except that the current string is extended instead of a new String being allocated; this is much, much faster.

Potentially even better is StringBuilder:

...This class is designed for use as a drop-in replacement for StringBuffer in places where the string buffer was being used by a single thread (as is generally the case). Where possible, it is recommended that this class be used in preference to StringBuffer as it will be faster under most implementations.[Java StringBuilder API documentation, http://java.sun.com/javase/6/docs/api/]

The constructors, append() and insert() for StringBuilder work the same way as the equivalent StringBuffer methods.

The GPR program only uses one explicit thread— so try StringBuilder and see how well it works. The graphic routines sometimes call their own threads, which might interfere with StringBuilder; if so, revert back to StringBuffer. In no event, though, should you need to use String objects to build the report—so don’t! Use StringBuilder if you can, StringBuffer if you must.

Documetation for StringBuffer and StringBuilder is on the Javaª Platform, Standard Edition 6 API Specification web page.

Zip up all your program’s source code, class and test files—including the ones we gave you that you used in your final program—into the file UnearthingThePast.zip, and turn it in via Checkmate. This approach will help ensure all the files needed for your system to work are present.