Question: Programming Project 2 In this project, you will be simulating the Josephus problem using a circular linked list. A skeleton code for CircularList, a complete
Programming Project 2 In this project, you will be simulating the Josephus problem using a circular linked list. A skeleton code for CircularList, a complete JUnit test suite, Leader.java and two text files (data files) are all provided for you. You need to complete the code in the CircularList.java file. You dont need to touch any of the other files. Read the javadoc comment for each method and make sure your method behaves exactly the way it is supposed to. The data files PresidentsAndVicePresidents.txt and PrimeMinisters.txt should be in the same directory where your .classpath is. Your program should pass all the tests in the test suite. Your first job is to download the code and read the existing code and the test module. Write one method at a time and test it before tackling the next method.
/** Implementation of Josephus problem. The Josephus problem
is named aftr the historian Flavius Josephus. For more
information on this problem visit:
http://en.wikipedia.org/wiki/Josephus_problem
*/
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.List;
public class CircularList
private Node
private int count; // number of elements in the list
// Complexity: O(1)
/** Constructs an empty Josephus circle
*/
public CircularList() {
head = null;
count = 0;
}
// Complexity: O(n)
/** Constructs an Josephus circle by adding the
elements from a list
@param list The List of items of type E
*/
public CircularList(List
head = null;
for (int i = 0; i < list.size(); i++)
add(list.get(i));
}
// Complexity O(1)
/** Inserts the specified element in the list at the
last position
@param dataItem the element to add
*/
public void add(E dataItem) {
// To be completed by the student
}
// Complexity ???
/** appends all the elements from the list
to the Josephus circle.
@param list the List of elements to add
*/
public void addAll(List
for (int i = 0; i < list.size(); i++) {
add(list.get(i));
}
}
// Complexity ???
/** returns a reference to the element at
position index
@param index The index of the element being sought
@return A reference to the element at position index
@throws IndexOutOfBoundsException if index is out of range
*/
public E get(int index) {
// To be completed by the student
}
/** Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* @param o the element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object o) {
// To be completed by the student
}
// Complexity O(n)
/** Sets the element at position index to reference
anEntry.
@param index The position of the element that is to
be set
@param anEntry The new value at position index
@return the element that was previously at position index
@throws IndexOutOfBoundsException if index is out of range
*/
public E set(int index, E anEntry) {
if ((index < 0) || (index >= count))
throw new IndexOutOfBoundsException(Integer.toString(index));
// To be completed by the student
}
// Complexity ???
/** Inserts the specified element in the list at a
given index
@param index The position at which the new element
is to be inserted
@param anEntry The element to add
@throws IndexOutOfBoundsException if index is out of range
*/
public void add(int index, E anEntry) {
// To be completed by the student
}
// Complexity ???
/** removes the element at position index
@param index The index of the element to be removed
@return The element that was removed
@throws IndexOutOfBoundsException if index is invalid
*/
public E remove(int index) {
// To be completed by the student
}
// Complexity O(n)
/** removes the item from the list if it is present
@param item item to be removed
@throws NoSuchElementException if the item is not found
*/
public void remove(E item) {
// To be completed by the student
}
// Complexity O(n)
/** sets the start position for the Josephus game
@param index The starting position
@throws IndexOutOfBoundsException if index is invalid
*/
public void setStartPosition(int index) {
// To be completed by the student
}
/* This private utility method is used in startJosephus
method.
Complexity O(1)
*/
private void removeAfter(Node
node.next = node.next.next;
node.next.previous = node;
count--;
}
/** simulates the Josephus game by killing every other person
until the winner is the only one left.
@return The survivor of the game
*/
private E startJosephus() {
while (count > 1) {
removeAfter(head);
head = head.next;
}
return head.data;
}
/** returns the sole survivor of the Josephus game
@return the sole survivor of the Josephus game
*/
public E getWinner() {
return startJosephus();
}
/** Returns a list-iterator of the elements in this list
(in proper sequence), starting at the beginning
of the list. Also provides methods to traverse
the list in the reverse order.
*/
public ListIterator
return new MyIterator();
}
/** @return The number of elements in the list
*/
public int size() {
return count;
}
// this is an inner class implementing the ListIterator
// interface.
// visit http://docs.oracle.com/javase/6/docs/api/java/util/ListIterator.html
// for a complete list of methods in ListIterator
// Your book uses the ListIterator methods to implement
// a doubly linked list (pages 112- 120)
// I am using only hasNext(), next(), previous() and hasPrevious()
// methods here.
private class MyIterator implements ListIterator
private Node
private Node
private boolean firstTime = true;
/** checks if a current item E is the last
in the collection
*/
public boolean hasNext() {
return (forward != null);
}
/** returns the next item in the collection if
there is one. If there is no more items
throws NoSuchElementException
*/
public E next() {
if (forward == null) throw
new NoSuchElementException();
else {
E item = forward.data;
forward = forward.next;
if (forward == head) forward = null;
return item;
}
}
/** checks if a current item is the first
in the collection
*/
public boolean hasPrevious() {
return (backward != null);
}
/** returns the previous item in the collection if
there is one. If there is no more items
throws NoSuchElementException
*/
public E previous() {
if (backward == null) throw
new NoSuchElementException();
else {
if (firstTime) {
backward = backward.previous;
firstTime = false;
}
E item = backward.data;
backward = backward.previous;
if (backward == head.previous) backward = null;
return item;
}
}
/* this operation is not supported */
public void add(E obj) {
throw new UnsupportedOperationException();
}
/* this operation is not supported */
public void set(E obj) {
throw new UnsupportedOperationException();
}
/* this operation is not supported */
public int previousIndex() {
throw new UnsupportedOperationException();
}
/* this operation is not supported */
public int nextIndex() {
throw new UnsupportedOperationException();
}
/* this operation is not supported */
public void remove() {
throw new UnsupportedOperationException();
}
}
/* the keyword "static" in the class header indicates
that the Node
class. In the Java API documentation, static inner
classes are also called nested classes.
Generally, we want to keep the details of the Node
class private. Thus the qualifier "private" is applied
to the class as well to the data fields and constructor.
However, the data fields and methods of an inner class
are visible anywhere within the enclosing class (also
known as the "parent" class.
*/
private static class Node
private E data;
private Node
private Node
/** constructor Creates an empty node with both next and
previous fields set to be null
@param dataItem - item to be inserted
*/
private Node(E dataItem) {
data= dataItem;
previous = next = null;
}
/** creates a new node that references another node
@param dataItem The data stored
@param previousNodeRef The node previous to this node
@param nextNodeRef The node next to this node
*/
private Node(E dataItem, Node
data = dataItem;
previous = previousNodeRef;
next = nextNodeRef;
}
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help