CS 151 - Introduction to Data Structures

Homework 4

Sorted Array Lists and Zip Code lookup

Overview

As you work on this assignment, keep in mind that only a small portion of your grade will be based on the user interface. So, only fix errors in the interface for Homework 3 if they are egregious.

Data

The data for this assignment is available via scp from goldengate.cs.brynmawr.edu at /home/gtowell/Public/cs151/Data/Hw4/shuffzips.csv (If you are logged in on a lab machine, this file is freely available at that location as well.) The file is also on the web at

            https://cs.brynmawr.edu/cs151/Data/Hw4/shuffzips.csv
      

Class design

List151Impl

SortedArrayList

• Add a private method grow that increases the size of the array underlying the the data structure by a factor of 2. (The grow method was discussed in class.) In your grow method, include something to print an informative message every time growth occurs.
• Change the method add so that it uses the grow method appropriately. The add method should now never return false to indicate that there is no space to add a new item.
• Further change the method add so that items are added to the existing items in a fashion such that the items in the SortedArrayList are kept in sorted order. (You will need to use the compare method of the string class as described next.)
• Sorting should be based upon the string representation of the items being compared. For instance, you might have a code similar to the following

  Place placeOne; 
  Place placeTwo;
  // something to actually set values into placeOne and placeTwo
  int compareResult = placeOne.toString().compareTo(placeTwo.toString());
                    

  You can read a lot about the compareTo method of String in the java documentation. The short version is that compareResult will have a value less than 0 if placeOne is lexicographically less than placeTwo; greater than 0 in the opposite case; and equal to 0 is the two strings are equal.
• You may need to adjust your toString methods to ensure that the zip code is printed first so that your sorted array list is sorted by zip code.

Add items to the underlying data structure in an "insertion sort" manner. That is, suppose that the existing data items are ["A", "D", "M", "T"], and you want to add "G". The first step would be to determine that the "G" should be inserted between "D" and "M". Alternately you could say that "G" should be inserted at position 2 (where "M" is). Then move "M" and "T" to make room and put in "G" in the now available position 2.

Taking this example and using the String compareTo method you might do something like the following:

                        compare A to G
                        "A".compareTo("G") is less than 0 so 
                              go to  the next thing in the array
                        compare D to G
                        "D".compareTo("G") is less than 0 so 
                              go to  the next thing in the array
                        compare M to G
                        "M".compareTo("G") is greater than 0 so 
                             make a space for G
                             put G into the space just made 
                             DONE
                  

Importantly the contents of the instance of the SortedArrayList class should always be in sorted order each time the add method finishes.

• Change the indexOf method of SortedArrayList to take advantage of the fact that the items are in sorted order as follows. Instead of starting at position 0 and searching forward to find the item requested, start in the middle of the list. Go forward or backward from there as appropriate. (Do not use binary search. If you do not know what binary search is, then you will not be tempted.)
• Change the method add(index, item) so that always throws an exception. Give the exception some likely text. For instance "Allowing this function to work as a defined could break sorting order so its usage is being blocked".

Requirements

• Initialize SortedArrayList to start with an underlying array of size 100. Your grow method will be called several times to make space.
• The only Data Structure you should use in this assignment is the SortedArrayList that you developed for this assignment. You may use only one instance of SortedArrayList. (You may also use the string arrays returned by ReadSCV or the split method of the String class. But you should only uses those while inputting the data.)
• SortedArrayList must behave as described above.
• (Repeated from hw3) You must store data in classes you create. These classes should hold exactly as much information as is contained a row of the data file. You may use the class design suggested above for your classes.
• (Repeated from hw3) You MUST use inheritance in your class design.
• (Repeated from hw3) You may read the contents of shuffzips.csv at most once. (Be sure to use the homework 4 version of shuffzips.csv)
• (Repeated from hw3) After reading in the data, your program should support user interaction similar to the following:

  Enter a zip code to lookup (00000 to quit): 19380
        19380 West Chester,PA       Pop:43281  Lat:39.95  Lon:-75.60
  Enter a zip code to lookup (00000 to quit): 07040
        07040 Maplewood,NJ       Pop:20973  Lat:40.73  Lon:-74.27
  Enter a zip code to lookup (00000 to quit): 00614
        00614 Arecibo,PR       Lat: 18.45  Lon:-66.73
  Enter a zip code to lookup (00000 to quit): 09848
        09848 Apo,AE
  Enter a zip code to lookup (00000 to quit): 88888
        Not Found
  Enter a zip code to lookup (00000 to quit): q
  Goodbye
        

• (Repeated from hw3) All printing of information about a place should be done from toString. So, for instance, in the above interaction all of the printout of search results (other than "not found") should be done with a single line which might look like
  System.out.println(place);
• (Repeated from hw3) Encapsulation. All classes should expose only that which other classes need. There should be no public instance variables
• (Repeated from hw3) Statics. Do not use any static variables or static methods.
• Use one of the methods discussed in lab 3 to collect the output of your program. The output should show your program on at least the following zip codes:
  • 19010
  • 07040
  • 09311
  • 81288
  • 16427

Electronic Submissions

1. README:

The following steps for submission assume that you created a project directory named HW4 in the directory /home/YOU/CS151/ on the UNIX servers

1. Make sure all of your code files and the requested output file are in that directory. (Use scp as needed to copy files from your local machine to that directory on UNIX)
2. Similarly put the README file into the project directory on UNIX
3. On a UNIX machine, go to the directory /home/YOU/CS151
4. Enter /home/gtowell/bin/submit -c 151 -p 4 -d HW4

Approximate Grading

1. 45% -- Program follows requirements above. Most of this will be in the SortedArrayList class. Note that this includes the requested output file
2. 20% -- Program compiles and runs
3. 15% -- program follows style and design guidelines
4. 10% -- Readme
5. 10% -- Other