News Bearers, Inc. is a courier service, and the owner, Ursula, wishes to keep track of her messengers. She doesn't really care in what order they are stored or whether she has random access to all of them. It is only important, for now, to be able to add new messengers to the list and print out all of them.
Messenger class, where each messenger will have a name and an ID number. You
may also add other properties, such as an age, if you would like. Provide
methods that return the name and ID, and also a toString method
that returns information about the messenger in a String.Messenger as it is constructed,
use a class (also known as static) variable. In Java,
static means "one per class," or "shared among all objects of
the class." Usually we create instance variables, where each
object has its own copy of the data. For example, each messenger will
keep track of its name and ID as instance variables. To keep track of
the next available ID number, though, we want a variable that is shared among
all the messengers. The static keyword indicates this.
Create a class variable, static int nextAvailableID, that is initialized
to 0 (or 1) when it is declared. Each messenger will set its ID based
on the class variable and then increment it, so that the next messenger gets
a different ID. LinkedList, construct five Messenger
objects, and add them to the list. Then print out the contents of the
list, using an iterator. Remember to import LinkedList,
and Iterator from java.util.
(Analysis Question: In what class
should you create your main method?)
There is some bad news to be delivered, and News Bearers, Inc. has taken on the dangerous mission. Nobody really wants to be the one to take the news; the way goes through enemy territory and, even if the messenger gets through, the classic fate of the bearer of bad news may be waiting. (Let's just say, this is how the phrase "Don't shoot the messenger" became relevant.)
To determine which messenger will be sent, Ursula sits all of her messengers
down in a circle, selects a number, and starts to count off. Messengers
are allowed to leave the circle one by one, and the last messenger left is the
one who will deliver the bad news. The counting off procedure is slightly
unusual, however, because it is actually the messenger after the last one counted
who gets to leave the circle. Consider the following example with 5 messengers,
in which the number selected for counting off is 7.
 |
 |
 |
| We'll start at the "head" of the list and move forward. Since it is circular, the "head" simply refers to whatever the current element in the list is. We count off 7 messengers: Alyce, Autumn, Brad, Jon, Zach, Alyce, and Autumn. Brad is declared "safe" and removed from the circle. |
We then count off 7 messengers again, starting with Jon (the next person in the list, since Brad was removed). The seven are Jon, Zach, Alyce, Autumn, Jon, Zach, and Alyce. Autumn is declared safe and removed. | Autumn was removed, so we now begin with Jon and count off as before. This time Zach is removed. |
 |
 |
| We begin the counting with Alyce, and Jon is removed. | Since Alyce is the last one left, she will be the messenger to take the bad news. |
CircularLLIterator class, which provides
an iterator through a linear LinkedList object that makes it
appear to be a circular linked list. Read the class documentation for
CircularLLIterator, which implements the ListIterator
interface. Notice that to get a circular linked list iterator, you construct
a CircularLLIterator instance directly rather than asking the
linked list for it. (The LinkedList class has iterator
and listIterator methods, but no circularListIterator
method.)CircularLLIterator class to implement the bad news
bearers problem described above. Count off by 7, as in the example.
Identify each "safe" messenger as you remove it from the list and
identify the bad news bearer at the end. Even if you used different
names for your messengers, verify that your messengers are removed in the
same order as in the example above. (Note that you cannot use the usual iterator
loop pattern with a CircularLLIterator or you will go into an
infinite loop.)ValidatedInputReader
class to prompt the user for this value You could
also prompt the user for the number of messengers and their names if you want.Debug
class for printing intermediate results for debugging purposes.
(First read its class documentation.) For
example, your program could print the initial list of messengers (after they
have been constructed but before the choosing algorithm begins) only if debugging
has been turned on. It could also print the name of the lucky messenger being
declared "safe" and the messengers left in the list after each iteration
of the algorithm only if debugging is on.
LinkedList object called llist.
You could get a normal (non-circular) ListIterator object for
it with the method call llist.listIterator(). Both the
linear iterator returned by the listIterator method and the circular
iterator created by constructing a CircularLLIterator object
implement the ListIterator interface, so both support the same
set of methods. Look over the list of methods in CircularLLIterator
and identify which methods (if any) must be implemented differently for a
linear or circular list iterator and which methods (if any) could share the
same implementation if we created a new, abstract
LLIterator class.iterator method for your
initial list traversal of the messenger list, when you printed the names of
all the messengers. Could you have used a linear list iterator (an object
returned by the listIterator method) for that traversal?
Could you have used a circular list iterator? Why or why not?
* This problem was inspired by a classical mathematics problem known as the Josephus Problem. See, for example, Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth, and Patashnik (Addison-Wesley, 1989). You could also refer to Section 8.3 in Java Software Structures: Designing and Using Data Structures, by Lewis and Chase (Addison-Wesley, 2005).
Authors: Autumn C. Spaulding autumn@max.cs.kzoo.edu
and Alyce Brady abrady@kzoo.edu