Computer Science 210
Data Structures

Fall 2017, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

This programming project focuses on sorting. You will learn the power of Java's Comparator interface as it applies to writing a generalized sorting method. You will extend the functionality of an existing class using inheritance, you will implement a simple sorting procedure within this extension, and you will learn about Comparators, which provide a more flexible mechanism for ordering objects than the Comparables we have seen in class.

You may work alone or in a group of two or three on this project. Of course, collaboration with your partner(s) is unrestricted. You may discuss the assignment with your classmates and give and receive some help, but your submission must be your own work (or that of you and your teammates, if you choose to form a group).

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository sorting-project-yourgitname for this Programming Project. One member of the group should follow the link to set up the repository on GitHub, then that person should email the instructor with the other group members' GitHub usernames so they can be granted access. This will allow all members of the group to clone the repository and commit and push changes to the origin on GitHub. At least one group member should make a clone of the repository to begin work.

Please answer lab questions in the README.md file in your group's GitHub repository.

Command-line Parameters

We can provide information to a Java application through the args parameter to its main method. As you can see from the main method signature we have been using all semester, it is an array of Strings. These String values come from what the program's user types after its name on the command line when running the program. Different Java IDEs provide different mechanisms for specifying these Strings, known as command-line parameters. In BlueJ, these are specified in a dialog box that we have been ignoring each time we run a Java application - the one that comes up after you choose main from the right-click menu to run your application. To specify the command-line parameters, we specify them as an array of String with the same syntax as a statically initialized array in Java. For example, we could specify an array of 3 String values:

  { "Java", "is", "fun" }

The Java run-time system will construct and initialize an array with these values, and we can access "Java" as args[0], "is" as args[1], and "fun" as args[2] in our program's main method.

Note: you can convert a String whose contents can be interpreted as an integer value to an int by passing it to the Integer.parseInt method.

Programming Assignment

We will do the laboratory at the end of Chapter 6 in Bailey. You will need to read about the Comparator interface in Section 6.8.

Please note the following clarifications, modifications, and explanations relating to the lab procedure outlined in the text:

• In step 1, you are asked to create an extension of structure.Vector called MyVector. Since we are using the generic version of the structure package, you will extend structure5.Vector. Your class header for MyVector should look like this:

  public class MyVector<T> extends structure5.Vector<T>
  

  We have not yet discussed inheritance, which is what allows one class to extend another, but you don't need to know too much about it to do this. Basically, your MyVector class will be able to do everything a structure5.Vector can do, plus anything you add in your MyVector class definition. In particular, your extension of structure5.Vector, methods of MyVector will have access to instance variables and methods declared as protected in the structure5.Vector implementation. Make good use of this fact! It will make the code you need to write quite short.

  Important Note: The elementData array in structure5.Vector is declared as private rather than protected for type safety reasons. This means, unfortunately, that MyVector will not be able to access the array directly. Fortunately, Vector has mutator and accessor methods that are (almost) as good as direct access to the array.

  Another Important Note: You do not need to copy or rewrite Vector.java! When you extend the existing Vector code, it will inherit all of the constructors and methods. You're just adding one method.

• In step 2 of the lab procedure in Bailey, you are to write a sort method. The text says you may use any sort that you like, but keep it simple! Use an iterative selection sort or insertion sort.

  The structure of the code will be very similar to what you have seen in our class and text examples, but you will need to modify it to use Comparators (as opposed to primitive types or Comparable objects) and to operate on the internal array of your instance of MyVector (as opposed to an array or other structure you would pass in as a parameter).

• Be sure to test your sort method in MyVector thoroughly before going on to step 3 of the lab assignment procedure. A good way to do this is to create a MyVector of some Comparable class (like Integer or String) and use structure5.NaturalComparator for your Comparator. Include this test as part of your submission as a main method of your MyVector class.
• For part 3 of the lab procedure, write two applications (three if you are working in a group of three). They should each work on a different data file and each should perform more than one "interesting" sort process. Both/all three will use the same MyVector class, but each application will call its own class for encapsulating the data objects you are working with, and a number of Comparators to sort the data in different ways. You should have a total of at least five (seven, if working in a group of three) unique Comparators in your submission.

  You may choose from the data files I have provided in the starter repository in the examples directory. (see the README file there for more information) or you may use some other data that you find interesting. Please include all data files that you use in your submission.

  Whatever types of data you choose to use, you will need to implement a custom class that holds the details of each type of data, Comparators that can compare instances of that class by different criteria, and an Java application that uses those Comparators to sort a MyVector that holds instances of your custom class in multiple ways. The examples directory includes a data file movies.dat, whose entries are used to create instances of the provided MovieInfo class, three classes that implement Comparator and compare MovieInfo objects by different criteria, and an application MovieInfoSorter that uses a MyVector with the Comparators to sort the data in multiple ways. Please do not start implementing your own code for custom classes and comparators until you fully understand the ones provided!

Submitting

Your submission requires that all required deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.

Grading

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