Computer Science 210
Data Structures

Fall 2016, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

For this lab, you will be implementing an interesting ordered structure and using it in a number of contexts.

You may work alone or in a group of 2 or 3 on this lab. Only one submission per group is needed.

While this lab is not due until right before you leave for Thanksgiving break, you should try to get as much as possible done this coming week.

Getting Set Up

To get your BlueJ environment set up for this week's lab assignment, start BlueJ and choose "New Project" from the "Project" menu. Navigate to your folder for this course and choose the name "Lab9" (no spaces) for the project.

Create a document where you will record your answers to the lab questions. If you use plain text, call it "lab9.txt". If it's a Word document, you can call it whatever you'd like, but when you submit, be sure you convert it to a PDF document "lab9.pdf" before you submit it.

Practice Program

Finding the "Best Of"

The remaining tasks will be graded as a programming assignment.

The first part of your programming assignment is to complete the laboratory in Section 11.4 of Bailey - computing the "Best Of" a collection of values by some metric. Initially, the metric will be determined by the compareTo method of the Comparable objects we we place into the BestOf data structure.

First, carefully read the lab description in the text. Before you start coding, think carefully about the BestOf class. What does it extend and/or implement? What will you use for your BestOf's internal data representation? Based on that data representation, what instance variables are needed? Do you plan to store the contents of your BestOf in order at all times or sort them as needed? Why or why not? Do not start coding until you are confident in your answers to these questions.

Your BestOf's main method should run one or more simple test cases for your structure. You may use the one described at the top of p. 276 or devise your own test cases.

Rather than answering thought question 3 as written, we will extend it a bit.

Write a program as a main method in a class Syracuse in a file Syracuse.java that generates the Syracuse sequences for all starting values from 1 up to n, given as a command-line parameter. Your program should track and report the following:

1. The top k (a second command-line parameter) intermediate values encountered at any point in the sequences. At the end it should report the k values, and for each, print out the value, the n that generated it, and the position in the sequence for n where the large value occurred.
2. Find the top k longest sequences. At the end it should report the length of the k longest sequences and the n that generated each.

You should maintain two BestOfs for this program, one responsible for each above the parts above. Should you wish to use an extra class to keep track of information for the Syracuse sequence generation (and that's a Good Idea), you might want to declare a non-public class inside of Syracuse.java that can be used only within that Java file. Class examples SimpleLinkedList and MazeRunner have examples of non-public classes.

The intermediate values you will generate can get quite large, so you should store numbers in variables of type long and Long instead of int and Integer as you generate your sequences.

Working with Travel Mapping Data

Next, you will begin working with some real world data derived from highway systems. You will likely use this same data in other assignments later this semester.

A big advantage of working with this kind of data is that it has a connection to reality, and that we can visualize the data and the results of our manipulations of that data with the Google Maps API. This data is collected by the Travel Mapping (TM) Project (http://tm.teresco.org/). The METAL project has taken the highway data from TM and converted into a format that is more convenient for us to load into a data structure and use. Much more about the project is available at (/metal/, but everything you need to know should be on this sheet.

The Data

The data is in plain text ".tmg" ("Travel Mapping Graph") files which have the following format:

• The first line identifies the file type (always should be "TMG"), file format version (always should be "1.0"), and graph format (either "simple" or "collapsed") of the file. For this week, you can safely ignore the contents of this line in your programs.
• The next line consists of two numbers: the number of vertices, |V|, (we'll call them "waypoints") and the number of edges, |E|, (road segments that connect adjacent waypoints).
• The next |V| lines describe the waypoints. Each line consists of a string describing a waypoint (its "label"), followed by its latitude and longitude as floating-point numbers.
• For this assignment, you can safely ignore the remainder of the file. But if you are interested, these last |E| lines describe the road segments. Each line consists of two numbers specifying the waypoint numbers (0-based and in the order read in from this file) connected by this road segment, followed by a string with the name of the road or roads that form this segment. For collapsed format files, each line also optionally includes a list of coordinate pairs that help to give a more accurate shape to the segment.

These graph files are linked from http://tm.teresco.org/graphs/. For example, usai.tmg describes the entire U.S. Interstate Highway system. YT-all.tmg describes a much smaller set of roads: the routes in the Yukon. You can download a few individual files, or download a zip file of the entire collection.

If you'd like to see what this data looks like in map form, you can load it into the METAL project's Highway Data Examiner, at /metal/hdx/.

Initially, you will work only with waypoint data and ignore the road segments. Your tasks:

1. Develop a class Waypoint that represents that data for a single waypoint. It should include fields for the waypoint name and its latitude and longitude values, a constructor, accessors for the three components, and appropriate equals and toString methods.
2. Develop a class WaypointLoader that has a main method that takes the name of a .tmg file to be loaded as a command-line parameter, and reads all of the waypoints from that file into a Vector or ArrayList of Waypoint objects. It should then enter an input loop where the user is repeatedly prompted for a string, and the program prints out all waypoints in the Vector or ArrayList whose labels contain the entered string as a substring, ignoring case.

Expanding and Using BestOf

Now let's take your working BestOf structure, enhance it a bit, then use it to compute some information about this mapping data.

What you need to do:

1. Enhance your Waypoint implementation to implement the Comparable interface. There is no obvious "natural" ordering here, so just have your compareTo method order Waypoints in alphabetical order by waypoint name.
2. Enhance your BestOf implementation as indicated in thought question 4 to use a Comparator to compare objects for inclusion in the structure.
3. Write a Comparator class or classes that compare Waypoint objects in the following ways: increasing latitude (northernmost), decreasing latitude (southernmost), increasing longitude (easternmost), decreasing longitude (westernmost), alphabetical order by waypoint name, order by length of waypoint name.
4. Write a program WaypointBest that has a main method that takes 2 command-line parameters: a .tmg file name, and a number n, and reports the best n waypoints in the file using each of the 6 criteria from the previous item.

A point of emphasis in this lab is on error checking: if your program expects a command-line parameter that is not provided, your program should not crash with an exception. It should print a meaningful error message.

Submitting

Before 11:30 AM, Friday, December 2, 2016, submit your lab for grading. There are two things to do to complete the submission: (i) Copy your file with the answers to the lab questions into your project directory. Be sure to use the correct file name. If you prepared your answers in Word, export to a PDF file and submit that. and (ii) upload a copy of your lab (a .7z or .zip file containing your project directory) to Blackboard under "Lab9". Don't forget to check your programming assignment programs for compliance with the Style Guide for CSIS 210 Programs

Grading

This assignment is worth 125 points, which are distributed as follows: