handout #9
CSE143—Computer Programming II
Programming Assignment #3
due: Thursday,
This assignment will give you practice with linked lists. You are to write a class AssassinManager that allows a client to manage a game of assassin. Each person playing assassin has a particular target that he/she is trying to assassinate. One of the things that makes the game more interesting to play is that initially each person knows only who they are assassinating (they don't know who is trying to assassinate them nor do they know who other people are trying to assassinate). You are working on a program for the “game administrator” who needs to keep track of who is stalking whom and the history of who killed whom.
The game of assassin is played as follows. You start out with a group of people who want to play the game. For example, let's say that we have five people playing whose names are Joe, Sally, Jim, Carol and Chris. A circular chain of assassination targets is established (what is called the “kill ring” in the sample log of execution). For example, we might decide Joe should stalk Sally, Sally should stalk Jim, Jim should stalk Carol, Carol should stalk Chris and Chris should stalk Joe.
Joe --> Sally --> Jim --> Carol -->
Chris
^ |
| V
+--------<--------<---------<--------+
When someone is assassinated, the chain needs to be relinked by “skipping” that person. For example, suppose that Jim is assassinated first (obviously this would have been by Sally). Sally needs a new target, so we give her Jim's target: Carol. Thus, the chain becomes:
+-------->--------+
^ |
| V
Joe --> Sally
Jim Carol --> Chris
^ |
| V
+--------<--------<---------<--------+
The main program has been written for you and is called AssassinMain. It reads a file of names, shuffles the names, and constructs an object of type AssassinManager. You are writing the AssassinManager class. The main program then asks the user for the names of the victims in order until the game is over (until there is just one player left alive), calling methods of the AssassinManager class to carry out the tasks involved in administering the game.
Your class will keep track of two different lists: the list of those currently alive and the list of those who are dead. Each is to be stored in a linked list. We are requiring you to use our node class which is called AssassinNode. The AssassinNode class has three data fields: one for the name of the person, one for the name of the killer and a “next” field to keep track of the next value in the list. The AssassinNode class appears at the end of this write-up.
Your class should have the following public
methods.
Method |
Description |
AssassinManager(String[]
names) |
This
is your method for constructing an assassin manager object. It should add the names from the array into
the kill ring in the same order in which they appear in the array. For example, if the names appear in the
order {“John”, “Sally”, “Fred”}, then in the initial kill ring we should see
that John is stalking Sally who is stalking Fred who is stalking John. You may assume that the names are nonempty
strings and that there are no duplicate names
(ignoring case). Your method should
throw an IllegalArgumentException if the array has 0 length. |
void
printKillRing() |
This
method should print the names of the people in the kill ring, one per line,
indented four spaces, with output of the form “<name> is stalking
<name>”. |
void
printGraveyard() |
This
method should print the names of the people in the graveyard, one per line,
indented four spaces, with output of the form “<name> was killed by
<name>”. It should print the
names in reverse kill order (most recently killed first, then next more
recently killed, and so on). It should
produce no output if the graveyard is empty. |
boolean
killRingContains (String
name) |
This
should return true if the given name is in the current kill ring and should
return false otherwise. It should
ignore case in comparing names. |
boolean
graveyardContains (String
name) |
This
should return true if the given name is in the current graveyard and should
return false otherwise. It should
ignore case in comparing names. |
boolean
gameOver() |
This
should return true if the game is over (i.e., if the kill ring has just one
person in it) and should return false otherwise. |
String
winner() |
This
should return the name of the winner of the game. It should return null if the game is not
over. |
void
kill(String name) |
This
method records the killing of the person with the given name, transferring
the person from the kill ring to the graveyard. This operation should not change the kill
ring order of printKillRing (i.e., whoever used to be printed first should
still be printed first unless that’s the person who was killed, in which case
the person who used to be printed second should now be printed first). It should throw an IllegalArgumentException
if the given name is not part of the current kill ring and it should throw an
IllegalStateException if the game is over (it doesn’t matter which it throws
if both are true). It should ignore
case in comparing names. |
This is meant to be an exercise in Java linked list manipulation. As a result, you will be required to adhere to the following rules:
· You must use our AssassinNode class for your lists. You are not allowed to modify it.
· You may not construct any arrays or ArrayLists or other data structures to solve this problem. You must solve it using linked lists. You can examine the array of Strings passed to the constructor, but you are not allowed to modify it.
· If there are n names in the array of Strings passed to your constructor, you should ask for a new AssassinNode exactly n times. This means that as people are killed, you have to move their node from the kill ring to the graveyard without creating any new nodes.
The main effect of the rules above is that your constructor will create an initial set of nodes (the initial kill ring) and then your class will not create any more nodes for the rest of the program execution. That means that you need to solve the problem of moving people from the kill ring to the graveyard by rearranging references, not by creating new nodes. Of course, you are allowed to declare local variables of type AssassinNode (like the variables “current” and “prev” in handout 9) because otherwise you can’t solve the problem at all. Local variables of type AssassinNode are not the same as node objects and, therefore, don’t count against the limit of n nodes.
For this assignment we are specifying what data
fields you should have in your class.
You should have exactly two data fields: a reference to the front of the
kill ring and a reference to the front of the graveyard. You are not allowed to have any other data
fields.
For this particular program, it is intuitive to
store the kill ring in what is known as a “circular” linked list. Normally lists have the value “null” stored
in the next field of the last node of the list.
Such lists are known as “null terminated” lists. In a circular list, the final element stores
a reference to the first element in the list.
But most novices find it difficult to work with a circular list,
especially since all of our examples involve null-terminated lists. There
is no need to use a circular list to solve the problem, so you are encouraged
to solve it with a null-terminated list.
If you feel strongly that you want to attempt the circular list, you are
allowed to do so, but it is likely to make the program harder to write.
You will want to write your own testing program (AssassinMain,
for example, never generates any of the exceptions you have to handle). When your class is in good shape, you can use
the AssassinMain program to make sure it works properly. A log of execution for AssassinMain appears
at the end of this write-up. Your
program should exactly reproduce the format and general behavior demonstrated
in the log, although you won’t exactly recreate this scenario because of the
“shuffling” of the names that AssassinMain performs.
In terms of correctness, your class must provide
all of the functionality described above and satisfy all of the constraints
mentioned in this writeup. In terms of
style, we will be grading on your use of comments, good variable names,
consistent indentation and good coding style to implement these operations.
You should name your file AssassinManager.java
and you should turn it in electronically from the “assignments” link on the
class web page. A collection of files
needed for the assignment is included on the web page as ass3.zip. You will need to have AssassinNode.java,
AssassinMain.java and names.txt all in the same directory as your
AssassinManager.java in order to run AssassinMain.
Using
jGRASP
In
jGRASP you can use a structure viewer to see what your list looks like (you do
so by dragging one of your fields from the debug window outside the window and
jGRASP will launch a viewer). This
viewer will show you the structure of the list, but won’t show you the contents
of the nodes. You can fix this by
selecting the wrench icon (“Configure the structure to view mapping”). Under “Value Expressions” say:
_node_.name
Then click on apply and you should see the names
in the nodes. You can also adjust
settings like the Width (to see more of the name) or Scale (to stretch or
shrink the diagram).
AssassinNode
Class
// The AssassinNode class is used to store the
information for one
// player in the game of assassin. Initiallly the "killer" field
// is set to null, but when the person is killed,
this should be
// set to the name of the killer.
public class AssassinNode {
public String name;
// this person's name
public String killer;
// name of who killed this person
public AssassinNode next;
// next node in the list
public AssassinNode(String name) {
this(name,null);
}
public AssassinNode(String name, AssassinNode next) {
this.name = name;
this.killer = null;
this.next = next;
}
}
Log of
execution (user input underlined)
Current kill ring:
Bobby
Warner is stalking Joe Martin
Joe Martin
is stalking Ruth Martin
Ruth
Martin is stalking Tad Martin
Tad Martin
is stalking Phoebe Wallingford
Phoebe
Wallingford is stalking Erica Kane
Erica Kane
is stalking Anita Santos
Anita
Santos is stalking Jackson Montgomery
Jackson
Montgomery is stalking Bobby Warner
Current graveyard:
next victim? Joe Martin
Current kill ring:
Bobby
Warner is stalking Ruth Martin
Ruth
Martin is stalking Tad Martin
Tad Martin
is stalking Phoebe Wallingford
Phoebe
Wallingford is stalking Erica Kane
Erica Kane
is stalking Anita Santos
Anita
Santos is stalking Jackson Montgomery
Jackson
Montgomery is stalking Bobby Warner
Current graveyard:
Joe Martin
was killed by Bobby Warner
next victim? Joe Martin
Joe Martin is already dead.
Current kill ring:
Bobby
Warner is stalking Ruth Martin
Ruth
Martin is stalking Tad Martin
Tad Martin
is stalking Phoebe Wallingford
Phoebe
Wallingford is stalking Erica Kane
Erica Kane
is stalking Anita Santos
Anita
Santos is stalking Jackson Montgomery
Jackson
Montgomery is stalking Bobby Warner
Current graveyard:
Joe Martin
was killed by Bobby Warner
next victim? tad
martin
Current kill ring:
Bobby
Warner is stalking Ruth Martin
Ruth
Martin is stalking Phoebe Wallingford
Phoebe
Wallingford is stalking Erica Kane
Erica Kane
is stalking Anita Santos
Anita
Santos is stalking Jackson Montgomery
Jackson
Montgomery is stalking Bobby Warner
Current graveyard:
Tad Martin
was killed by Ruth Martin
Joe Martin
was killed by Bobby Warner
next victim? BOBBY warner
Current kill ring:
Ruth
Martin is stalking Phoebe Wallingford
Phoebe
Wallingford is stalking Erica Kane
Erica Kane
is stalking Anita Santos
Anita
Santos is stalking Jackson Montgomery
Jackson
Montgomery is stalking Ruth Martin
Current graveyard:
Bobby
Warner was killed by Jackson Montgomery
Tad Martin
was killed by Ruth Martin
Joe Martin
was killed by Bobby Warner
next victim? ERICA KANE
Current kill ring:
Ruth
Martin is stalking Phoebe Wallingford
Phoebe
Wallingford is stalking Anita Santos
Anita
Santos is stalking Jackson Montgomery
Jackson
Montgomery is stalking Ruth Martin
Current graveyard:
Erica Kane
was killed by Phoebe Wallingford
Bobby
Warner was killed by Jackson Montgomery
Tad Martin
was killed by Ruth Martin
Joe Martin
was killed by Bobby Warner
next victim? anita
Current kill ring:
Ruth
Martin is stalking Phoebe Wallingford
Phoebe
Wallingford is stalking Jackson Montgomery
Jackson
Montgomery is stalking Ruth Martin
Current graveyard:
Anita
Santos was killed by Phoebe Wallingford
Erica Kane
was killed by Phoebe Wallingford
Bobby
Warner was killed by Jackson Montgomery
Tad Martin
was killed by Ruth Martin
Joe Martin
was killed by Bobby Warner
next victim? stuart
reges
Unknown person.
Current kill ring:
Ruth
Martin is stalking Phoebe Wallingford
Phoebe
Wallingford is stalking Jackson Montgomery
Jackson
Montgomery is stalking Ruth Martin
Current graveyard:
Anita
Santos was killed by Phoebe Wallingford
Erica Kane
was killed by Phoebe Wallingford
Bobby
Warner was killed by Jackson Montgomery
Tad Martin
was killed by Ruth Martin
Joe Martin
was killed by Bobby Warner
next victim? phoebe
Current kill ring:
Ruth Martin is stalking Jackson Montgomery
Jackson
Montgomery is stalking Ruth Martin
Current graveyard:
Phoebe
Wallingford was killed by Ruth Martin
Anita
Santos was killed by Phoebe Wallingford
Erica Kane
was killed by Phoebe Wallingford
Bobby
Warner was killed by Jackson Montgomery
Tad Martin
was killed by Ruth Martin
Joe Martin
was killed by Bobby Warner
next victim? ruth
martin
Game was won by Jackson Montgomery
Final graveyard is as follows:
Ruth
Martin was killed by Jackson Montgomery
Phoebe
Wallingford was killed by Ruth Martin
Anita
Santos was killed by Phoebe Wallingford
Erica Kane
was killed by Phoebe Wallingford
Bobby
Warner was killed by Jackson Montgomery
Tad Martin
was killed by Ruth Martin
Joe Martin
was killed by Bobby Warner