CS 201: Data Structures (Winter 2018)

HW07: Zoo displayer reprise

1. Goals

To understand how to implement a List variant using links (specifically, a sorted linked list), and to see how testing up front can help you when writing code.

2. Setup

This is a pair programming assignment. Check Moodle for new partner pairings.

The code that you write for this assignment will build on your ZooDisplayer code and use the SortedList ADT, a variation of the List ADT. The starter files contain:

• SortedList.java - Javadoc
• EzImage.java
• CarlSortedList.class
• CarlSortedList$SortedListIterator.class

You should not make any changes to SortedList or EzImage.

You will build on top of ZooDisplayer and ZooAnimal files that you or your partner made for hw03. (If neither of you have a (close to) working version of hw03, please email or talk to me and I'll help you.) Place a copy of these files in the unzipped folder.

3. Specification

Part A: Making ZooAnimal Comparable

myZooAnimal.compareTo(otherZooAnimal)

• Change ZooAnimal to implement Comparable<ZooAnimal>, meaning it can be compared to other ZooAnimals:

  public class ZooAnimal implements Comparable<ZooAnimal>

  The sorted order for ZooAnimals should follow the same conventions as for hw03: alphabetized by animal species, then name in case of identical species, and then year of birth in case of identical names (with younger animals appearing before older animals).

• Write your public int compareTo(ZooAnimal otherZooAnimal) method. Test it and make sure it works properly before you continue. The main method in ZooAnimal is likely a good place to write these tests.

• To facilitate testing your compareTo method, you should make sure that ZooAnimal has a constructor with the following signature, allowing you (and me) to easily make ZooAnimal instances:

  public ZooAnimal(String name, String species, int birthYear, String imageLocation);

• Implement one more method in ZooAnimal: equals(ZooAnimal otherZooAnimal). You want to make it so that if two ZooAnimals have the same name, species, and age, equals returns true. Otherwise, equals should return false. Again, test and make sure your implementation works before you continue. Whenever you implement Comparable, it's good style to make sure that your equals method returns true if and only if compareTo returns 0.

Part B: Writing testing code

In Part C of the assignment, you'll be implementing a SortedLinkedList that stores ZooAnimals. Your list will always be sorted such that add(ZooAnimal newItem) places the item into its appropriate place in the list to maintain sorted order. You'll be implementing the interface SortedList. Take a moment and look at this interface. It's very similar to List, except for the way that add works and the fact that you can't replace an item or add an item at a specific position. (Why not?)

You'll be implementing all of the methods in SortedList, except the optional iterator().

• To begin your SortedList implementation, you'll write a SortedListTester.java that should have only static methods and tests each of the public methods you'll implement in SortedLinkedList. You can run your tests starting with a CarlSortedList<ZooAnimal>. You should write your tests so that it will be easy to switch CarlSortedList<ZooAnimal> for the SortedLinkedList you'll write.

• Your tests should check edge cases (e.g., adding to an empty list, a list with just one element, or a list with multiple elements; adding to beginning, middle, or end of the list; trying to remove an animal that isn't in the list) and make sure to check a range of uses. For instance, you might test that get throws the proper exception if the given position is out of bounds, or make sure if you add a bear and then an aardvark, the aardvark is at position 0 in the list. When checking if something throws an exception, you'll find it helpful to use try-catch. You should make sure to write your tests so that when you run them, it's easy to see what you have tested and whether your program is working correctly. For example, you might write something like System.out.println("List should be empty here. isEmpty() returns " + list.isEmpty());. You are also welcome to make your calls print only if a test fails, and have them display a helpful message about what has failed and why (e.g., that the list should have had animals A, B, and C, but actual contents was A and C).

If you write your tests well, it will help you to see when you've correctly implemented the SortedLinkedList in part C. Once you've finished making sure your tests check for the appropriate behaviour and that all tests pass for CarlSortedList<ZooAnimal>, you should switch out CarlSortedList<ZooAnimal> for SortedLinkedList. If you end up implementing iterator(), you should also write tests for that method.

In the past, there was a definite correlation with having good testing code in Part B and having a correct implementation in Part C. Please take this part seriously!

Part C: Implementing SortedLinkedList

You will write a class SortedLinkedList that implements all of the methods in the SortedList interface.

• Your SortedLinkedList only needs to store ZooAnimals, so you'll indicate you are implementing this interface with the generic type always being ZooAnimal:

  public class SortedLinkedList implements SortedList<ZooAnimal>
  {
     // Your implementation here!
  }
  

  Some of you may be tempted to retain the generic type for fun. I really want you to do it only for ZooAnimal this time. In future assignments you will have a chance to play with generic types.
• Your implementation must use a linked structure to store entries in the list. Do not use an array structure: you will get more practice with arrays in future assignments. Your class should not use any built-in Java List/LinkedList classes: you are writing your own implementation of a linked list!
• In the comment for each public method you implement, please indicate its worst case running time in Big Oh notation in terms of the length n of the list. Of course, write the most reasonable, best bound you can give. Don't write $O(n^2)$ when you can write $O(n)$, etc.

Start off by copying all of the method signatures from SortedList into SortedLinkedList. For the void methods, you don't need to put any code into the method bodies yet; for the methods that return something, just have them return some default value (e.g., false, -1, or null, depending on the type you need to return). You should now be able to compile your code, and run your SortedListTester. All or most of your tests will fail, but you're now set up to start implementing!

Write a private static class Node that store ZooAnimals. Even though your textbook does not make Nodes static, we discussed in class the benefit. As a rule of thumb, a nested class should be static unless there is good reason it needs access to the private instance variables of the outer class.

Begin your implementation by making a constructor for SortedLinkedList. Then go through your methods one by one and implement them.

With each method you implement, re-run SortedListTester and make sure that the tests run as you expect. When you've finished implementing SortedLinkedList, you should be able to run SortedListTester and see that all of your tests pass.

Challenge: Iterator

Implementing the iterator method is optional; if you implement it, you'll be able to use the colon notation in for-each loops to iterate over your SortedList. I advise saving iterator until the end, to do if you have time.

If you're not implementing iterator(), make calling that method throw an UnsupportedOperationException:

public Iterator<ZooAnimal> iterator()
{
   throw new UnsupportedOperationException("iterator() not implemented!");
}

If you choose to implement an iterator, see these notes to find out more about how to do it. If you go this route, you should be able to write an iterator where both next() and hasNext() are O(1).

Part D: Revising ZooDisplayer

Revise ZooDisplayer so that it's done in an object-oriented style.

• Your new version of ZooDisplayer (keep the same name as for hw03) should have a constructor that takes one argument: a String with the location of the file with the zoo animals (e.g., ZooExample.txt):

  /** Constructs a new ZooDisplayer containing the animals in the file at
      filePath.  If filePath is null, constructs an empty ZooDisplayer.
      @param filePath path to the file from which to load zoo animals
  */
  public ZooDisplayer(String filePath);
  

• The animals should be loaded and stored in a SortedLinkedList. If the filePath is null or there is not a file at the corresponding filePath, your method should not crash but should simply construct a ZooDisplayer with no animals. You should be able to use much of your existing code for this part.

• Your code must also have the following three methods:

  /** Prints a text version of the zoo that lists the animals' names, species,
      and ages.
  */
  public void displayZooAsText();
  
  /** Displays a picture of the zoo where each animal's picture is concatenated
      to the right of the previous animal
  */
  public void displayZooAsPicture();
  
  /** Adds animal to the zoo.
      @param animal
  */
  public void addAnimal(ZooAnimal animal);
  

• Check and make sure that your method signatures (the name of the method, the return type, and the arguments passed in) exactly match the signatures above. You must have the right signatures to get credit.
• You have two options for main in ZooDisplayer:
  1. Have exactly the same behaviour as specified in hw03, but now using an objected-oriented design.
  2. As a more interesting alternative, implement Part E extension below.
  These options are worth the same number of points, even though one is substantially harder than the other.

To implement the two display methods you will likely only have to make small revisions to your existing code.

Note that if you don't implement iterator above, you cannot use the for-each loop (colon syntax) to work through the list. This likely means that your code will by asymptotically slower than if you were using the iterator (which is fine). But make sure you understand why this is the case.

(Optional) Part E: Extending ZooDisplayer

As an optional challenge, make it so that the the user can add or remove animals interactively.

The user should be able to run ZooDisplayer either with:

java ZooDisplayer ZooExample.txt

java ZooDisplayer

In the former case, the animals in ZooExample.txt should be loaded; in the latter, no animals should be loaded. Then, the program should prompt the user by asking "What would you like to do?". There are five valid answers: "add animal", "remove animal", "display text", "display picture", and "exit":

• add animal: The program should prompt the user for the animal's species, name, year of birth, and picture location. If the picture location can't be found, the program should reprompt until the user enters a valid file location. You do not need to worry about checking that the file is actually a picture, and it's okay if your program crashes if it's not a picture.
• remove animal: The program should prompt the user for the animal's name, and remove the first animal with that name from the list; an animal might be removed if the zoo traded that animal to another zoo. If no animal with that name is found, a message should be displayed to the user, but the program shouldn't crash or end: the user should be able to keep interacting.
• display text: The program should print the text display for the current zoo (just as in one of the command line usages in hw03).
• display picture: The program should display an image of the current zoo. The program does not need to worry about getting rid of any previous windows displaying the zoo. The program should be able to display an empty zoo without crashing (either by displaying an empty window or printing some text indicating there's nothing to display).
• exit: The program should end.

What would you like to do?
add animal
What is the species of the animal you're adding?
cat
What is the animal's name?
Eris
And what year was Eris born?
2011
Where can I find a picture of Eris?
cs201/hw07/zooPics/foobar.jpg
You must enter a valid path to an image of the cat.
koala.jpg
Animal added.
What would you like to do?
display my zoo!
Unrecognized command: display my zoo!
Valid commands: add animal, remove animal, display text, display picture, and exit.
What would you like to do?
remove animal
Which animal would you like to remove?
Byron
Byron was not found in the zoo.
What would you like to do?
display image
What would you like to do?
exit
Farewell!

4. Code notes

• Keep testing your list implementation incrementally, and make sure that your test cases cover a range of situations.
• Your final ZooDisplayer should not need to use CarlSortedList at all.
• In Scanner, there are methods like nextInt that get input, but don't consume the next line token. If you use one of these methods and then want to get more input from the user, you'll need to follow up with a call to nextLine before prompting the user for their next input. Behaviour indicative of not having handled this properly is if the Scanner doesn't seem to wait for the next user input.

5. Submission and grading

• ZooDisplayer.java,
• ZooAnimal.java,
• SortedListTester.java, and
• SortedLinkedList.java.

Follow the previously established guidelines.

/** [Some description of my class]
    @author Paris Geller (hw03)
    @author Jed Yang (hw03 and hw07)
    @author Lane Kim (hw07)
*/

Assignment requirements

This is a partial list of the things that we'll be looking for when evaluating your work (in addition to style):

• ZooAnimal contains compareTo, equals, and a constructor that takes the parameters specified above.
• SortedListTester checks a range of test cases and tests all methods.
• SortedLinkedList implements SortedList<ZooAnimal>.
• SortedLinkedList contains a nested class Node that is private and static.
• The comments in SortedLinkedList indicate the asymptotic efficiency of your implementations of each public method, in terms of the current size n of the list.
• SortedLinkedList passes all of your tests and all of our tests. This includes never throwing NullPointerExceptions.
• ZooDisplayer responds correctly to various command-line usages described above.
• Program minimizes duplicate code by abstracting into appropriate methods.
• All methods mentioned in the assignment are present in your code.

Grading

• Assignment requirements [20 points]
• Comments, style, and design [5 points]

This assignment modified from one designed by Anna Rafferty.

Start early, have fun, and discuss questions on Moodle.