CS 201: Data Structures (Winter 2017)
HW08: Zoo displayer reprise
Due: Monday, 02/13 at 22:00
This is a pair programming assignment. You will continue with your same partner (unless I have told you otherwise).
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
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
- JavadocEzImage.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
There are four parts to this assignment: modifyingZooAnimal
to be
Comparable
, writing testing code for your implementation of
SortedList
, implementing SortedList
, and revising
your ZooDisplayer
to make use of your SortedList
implementation.
You should work through each part in order.
Part A: Making ZooAnimal Comparable
In this assignment, you'll be puttingZooAnimal
s in a
SortedList
. Rather than having to sort the list after adding all
the animals, the animals are always added in sorted order. That means the
SortedList
will need a way to compare two ZooAnimal
s.
You've seen an example of a class that implements the Comparable
interface: String
implements this interface. The
Comparable
interface includes a single method, compareTo(T
o)
. You use this method as follows:
myZooAnimal.compareTo(otherZooAnimal)
myZooAnimal
comes
before otherZooAnimal
in sorted order, 0
if
myZooAnimal
and otherZooAnimal
are equal in the
sorted order, and a positive number if myZooAnimal
comes after
otherZooAnimal
in sorted order.
Change
ZooAnimal
to implementComparable<ZooAnimal>
, meaning it can be compared to otherZooAnimal
s:The sorted order forpublic class ZooAnimal implements Comparable<ZooAnimal>
ZooAnimal
s 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 older animals appearing before younger animals).Write your
public int compareTo(ZooAnimal otherZooAnimal)
method. Test it and make sure it works properly before you continue. Themain
method inZooAnimal
is likely a good place to write these tests.- To facilitate testing your
compareTo
method, you should make sure thatZooAnimal
has a constructor with the following signature, allowing you (and me) to easily makeZooAnimal
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 twoZooAnimal
s 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 implementComparable
, it's good style to make sure that yourequals
method returns true if and only ifcompareTo
returns0
.
Part B: Writing testing code
In Part C of the assignment, you'll be implementing a
SortedLinkedList
that stores ZooAnimal
s. 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.
You'll be implementing all of the methods in SortedList
,
except the optional iterator()
.
-
To begin your
SortedList
implementation, you'll write aSortedListTester.java
that should have only static methods and tests each of the public methods you'll implement inSortedLinkedList
. You can run your tests starting with aCarlSortedList<ZooAnimal>
. You should write your tests so that it will be easy to switchCarlSortedList<ZooAnimal>
for theSortedLinkedList
you'll write. -
Your tests should check edge cases (e.g., adding to an empty 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 giraffe and then an anteater, the anteater is at position 0 in the list. When checking if something throws an exception, you'll find it helpful to usetry
-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 likeSystem.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 behavior 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.
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 storeZooAnimal
s, so you'll indicate you are implementing this interface with the generic type always beingZooAnimal
:Some of you may be tempted to retain the generic type for fun. I really want you to do it only forpublic class SortedLinkedList implements SortedList<ZooAnimal> { // Your implementation here! }
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.
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
ZooAnimal
s. Even though your textbook does not make
Node
s 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: aString
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 thefilePath
isnull
or there is not a file at the correspondingfilePath
, your method should not crash but should simply construct aZooDisplayer
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
inZooDisplayer
:- Have exactly the same behaviour as specified in hw03, but now using an objected-oriented design.
- As a more interesting alternative, implement Part E extension below.
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
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.
bold
and computer output in black:
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/hw08/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 Goodbye!
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 useCarlSortedList
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 tonextLine
before prompting the user for their next input. Behavior 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
Submit to Moodle azip
archive containing:
ZooDisplayer.java
,ZooAnimal.java
,SortedListTester.java
, andSortedLinkedList.java
.
Follow the previously established guidelines.
Please make sure that every file you submit has your name and your partner's name at the top. ForZooDisplayer
and ZooAnimal
, keep
the original authors' names in the comments but add your names, noting that you
worked on it for hw08. For instance, if I worked on hw03 with Paris Geller and
hw08 with Lane Kim, I would have comments like:
/** [Some description of my class] @author Paris Geller (hw03) @author Jed Yang (hw03 and hw08) @author Lane Kim (hw08) */
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
containscompareTo
,equals
, and a constructor that takes the parameters specified above.SortedListTester
checks a range of test cases and tests all methods.SortedLinkedList
implementsSortedList<ZooAnimal>
.SortedLinkedList
contains a nested classNode
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 throwingNullPointerException
s.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.