Josephus Problem

ListIterator, Circular Double Linked-List, and Testing

Description

The Josephus problem is named after Flavius Josephus, a historian and a reluctant leader of a revolt against the Roman Empire. When it appeared Josephus and his band were about to be captured, they chose to commit suicide rather than be enslaved. It is believed that the procedure they followed was for everyone in his band to form a circle and starting in a given direction, at a certain band member, count around the circle a predetermined number. When this number is reached, the person leaves the circle and commits suicide. The circle shrinks as the counting continues. When a person drops out of the circle, the count starts over with the next person.

Implement a simulation of the Josephus Problem, using a ListIterator Interface and a Circular Double-Linked List. Use a set of test data to thoroughly test your simulation.

Double Linked Node

• Create a generic class DoubleLinkedNode<E> which stores a single field of data, and pointers to next and previous
• Provide a constructor which sets the single data field in your DoubleLinkedNode
• The methods E getData(), void setData(E data)
• The methods DoubleLinkedNode<E> getNext(), void setNext(DoubleLinkedNode<E> next)
• The methods DoubleLinkedNode<E> getPrevious(), void setPrevious(DoubleLinkedNode<E> previous)
• An overridden String toString() method which returns data.toString()

Circular Double Linked-List

• Create a generic class CircularDoubleLinkedList<E> which implements the Iterable<E> interface
• Provide a default constructor which creates an empty list
• A method void add(E data) adds an item to the end of the list
• A method void add(int index, E data) which adds an item at the specified index
• A method E get(int index) returns the data stored at the specified index
• A method E remove(int index) which removes and returns an item from the list
• A method int size()
• An overridden String toString() which returns a String of all values V from the front to the end of the list using the following format

[V0,V1,V,V,V,...,VN]

All methods which accept an index (add, get, remove) should work for both positive and negative input. Positive values indicate moving clockwise through the list, while negative values indicate moving counter-clockwise through the list. Also, these methods should work for any index size (you can use modulus to force the index to be in range of the list).

ListIterator

• Create a class CircularDoubleIterator which implements the entire ListIterator interface.
• CircularDoubleIterator should be a private inner class of CircularDoubleLinkedList.
• Make sure to handle exceptions correctly

Josephus

• Create a class Josephus which uses CircularDoubleLinkedList from above
• A method LinkedList<Integer> testList(int size, int start, int step, boolean isClockwise)

testList takes as its input:

• size - number of people in circle
• start - the position of where to start counting from
• step - predetermined number for counting off
• isClockwise - if isClockwise is true, counting occurs in a clockwise manner. If isClockwise is not true, then counting occurs in a counter-clockwise manner.

testList returns a LinkedList<Integer> (you can use Java's Linked List for this) of the people in the order that they were removed. The last person standing should be the last person in this list.

Feel free to implement other methods in any of the classes which will help solve this problem.

Example

There are seven members in the band, numbered 1 through 7, and you start at 1 and count off by threes in a clockwise direction. Band members will be eliminated in the order 3, 6, 2, 7, 5, 1. In this example, the band member at position number 4 will remain at last

Testing

Please thoroughly test your code and briefly discuss your testing strategy. Turn in all test code.