ICS 211 Homework H06: Iterating over Cheese

Purpose

For our last List homework assignment, we are going to simulate a cheese plate made of different cheeses that you can taste in different orders. To facilitate this we will use a circular doubly linked list to hold the cheeses. The list will implement the ListIterator interface. We’ll then use the Josephus problem to choose the order in which we taste the cheeses.

Tasks

1. Create a package named edu.ics211.h06

This is where we will put some of our classes for homework 06.

2. Create a Circular Doubly Linked List class named CircularDoublyLinkedList that implements IList211 and Iterable.

The next figure shows my New Class dialog.

Note: You should make sure the generic class entries agree. In this case they are all <E>.

Use the private inner DLinkedNode class like you did for homework H05.

private class DLinkedNode {
  E item;
  DLinkedNode next;
  DLinkedNode prev;
  
  public DLinkedNode(E item, DLinkedNode next, DLinkedNode prev) {
    this.item = item;
    this.next = next;
    this.prev = prev;
  }
}

You probably want to keep track of both head and tail since the list is circular.

In your CircularDoublyLinkedList you will need another private class that implements the ListIterator interface.

public interface ListIterator<E> {
  void add(E e); // Inserts the specified element to the list. (Optional for this assignment)
  boolean hasNext(); // Returns true if this list iterator has more elements while traversing in the forward direction.
  boolean hasPrevious(); // Returns true if this list iterator has more elements while traversing in the reverse direction.
  E next(); // Returns the next Element.
  int nextIndex(); // Returns the index of the next element.
  E previous(); // Returns the previous Element
  int previousIndex(); // Returns the index of the previous element.
  void remove(); // Removes from the list the last element that was returned.
  void set(E e); // Replaces the last element returned. (Optional for this assignment)
}

The iterator method will return a new instance of your private inner class.

In addition to the default constructor, your CircularDoublyLinkedList will need a constructor that takes an array and builds the list from the items in the array. You can loop over the items in the array adding them to the list.

public CircularDoublyLinkedList(E[] items) {
  this();
  for(E item: items) {
    add(item);
  }
}

Since this class is circular:

• head.prev == tail and tail.next == head
• The ListIterator’s hasNext() is true if size > 0
• The ListIterator’s hasPrevious() is true if size > 0;

Use CircularDoublyLinkedListTest.java to test your linked list class.

3. Create a Josephus Cheese Plate class that uses your CircularDoublyLinkedList class.

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.

Instead of people and committing suicide we are going to simulate tasting different cheeses.

Create a JosephusCheesePlate class that implements the ICheeseTasting interface.

public interface ICheeseTasting {
  /**
   * Returns a List of the cheeses in the order they were tasted. This method
   * doesn't destroy the cheese plate.
   * @param start the position of where to start the tasting. This is a ones based index.
   * @param step the predetermined number for counting off.
   * @param isClockwise if true the counting occurs in a clockwise/increasing order.
   *        If false the counting occurs in a counter clockwise/decreasing order.
   * @return A List of Cheese in the order they were tasted.
   */
  List<Cheese> tasteCheeses(int start, int step, boolean isClockwise);
}

The JosephusCheesePlate class must have a constructor that takes an array of Cheeses, the Cheeses in the plate.

The tasteCheeses method should create a CircularDoublyLinkedList<Cheese> and use the CircularDoublyLinkedList<Cheese>.iterator() to choose the cheeses.

Example

JosephusCheesePlate plate = new JosephusCheesePlate([Cheese1, Cheese2, Cheese3, Cheese4, Cheese5, Cheese6, Cheese7]);
LinkedList<Cheese> tasting1 = plate.tasteCheeses(1, 3, true);
LinkedList<Cheese> tasting2 = plate.tasteCheeses(4, 2, false);

There are seven Cheeses Cheeses in the flight, numbered 1 through 7.

• In tasting1 you start at 1 and count off by threes in a clockwise direction. Cheeses will be tasted in the order Cheese3, Cheese6, Cheese2, Cheese7, Cheese5, Cheese1, Cheese4.
• In tasting2 you start at 4 and count off by twos in a counter-clockwise direction. Cheeses will be tasted in the order Cheese3, Cheese1, Cheese6, Cheese4, Cheese7, Cheese2, Cheese5.

We are going to use the JosephusCheesePlateTest.java JUnit tests to evaluate your JosephusCheesePlate class for correctness.

Grading Rubric

Turning in the Assignment

The assignment is due on Friday at 11:55pm. You may turn it in early.

1. Does your code follow the Java Coding Standard and pass CheckStyle?
2. Does your code pass the JUnit Tests?
3. Export your project following the instructions at the bottom of the page. Name the zip file <your username>H06. So my zip file would be cmooreH06.zip.
4. Sign in to Laulima, then navigate to the ICS211 site. In the left-hand side of the site, there is an Assignments tab/link. Click on it and view all the posted assignments. Select the assignment that you want to turn in and attach your <username>H06.zip file accept the honor pledge to submit the assignment.