handout #15
CSE143X—Computer Programming I & II
Programming Assignment #6
due: Monday, 11/5/12,
11 pm
This assignment will give you practice with linked lists. You are to write a class called 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.
The constructor for the AssassinManager class will be passed an object of type List<String>. You can manipulate this object the same way you would manipulate an ArrayList<String>. So you can call methods like size and get and you can write a for-each loop using this object, but you are not allowed to modify it. You will need to include the following line at the beginning of your class to have access to List:
import java.util.*;
Your class should have the following
public methods.
|
Method |
Description |
|
AssassinManager(List<String>
names) |
This
is your method for constructing an assassin manager object. It should add the names from the list into
the kill ring in the same order in which they appear in the list. For example, if the list contains {“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 (reported in that
order). 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 list
is empty. |
|
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>”. If there is only one
person in the ring, it should report that the person is stalking themselves
(e.g., “John is stalking John”). |
|
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 sequences of AssassinNode objects. You can examine the list 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 7) 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.
In lecture and section we have been looking at nodes of type ListNode that have just two fields: a field called data of type int and a field called next that points to the next value in the list. The AssassinNode class has three fields. The first two are fields for storing data called name and killer (they are used to store the name of a player and the name of the person who killed that player). The third field is called next and it serves the same purpose as the next field in the ListNode class.
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 should turn it in electronically from the “homework”
link on the class web page. A collection
of files needed for the assignment is included on the web page, including
several name files and several logs of execution. You will need to have AssassinNode.java,
AssassinMain.java, and whatever names file you are using all in the same
directory as your AssassinManager.java in order to run AssassinMain. You can use the output comparison tool to check
your output.
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)
Welcome to the CSE143 Assassin Manager
What name file do you want to use this time?
names3.txt
Do you want the names shuffled? (y/n)?
n
Current kill ring:
Athos is
stalking Porthos
Porthos is stalking Aramis
Aramis is stalking Athos
Current graveyard:
next victim? Aramis
Current kill ring:
Athos is
stalking Porthos
Porthos is stalking Athos
Current graveyard:
Aramis was killed by Porthos
next victim? Athos
Game was won by Porthos
Final graveyard is as follows:
Athos was
killed by Porthos
Aramis was killed by Porthos