ICS 211 Homework H06: Iterating over Beer Flights

Purpose

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

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 Beer Flight 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 beers in a flight.

Create a JosephusBeerFlight class that implements the IBeerTasting interface.

public interface IBeerTasting {
  
  /**
   * Returns a List of the beers in the order they were tasted. This method
   * doesn't destroy the flight of beers.
   * @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 Beers in the order they were tasted.
   */
  List<Beer> tasteBeers(int start, int step, boolean isClockwise);
}

The JosephusBeerFlight class must have a constructor that takes an array of Beers, the Beers in the flight.

The tasteBeers method should create a CircularDoublyLinkedList<Beer> and use the CircularDoublyLinkedList<Beer>.iterator() to choose the beers.

Example

JosephusBeerFlight flight = new JosephusBeerFlight([Beer1, Beer2, Beer3, Beer4, Beer5, Beer6, Beer7]);
LinkedList<Beer> tasting1 = flight.tasteBeers(1, 3, true);
LinkedList<Beer> tasting2 = flight.tasteBeers(4, 2, false);

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

• In tasting1 you start at 1 and count off by threes in a clockwise direction. Beers will be tasted in the order Beer3, Beer6, Beer2, Beer7, Beer5, Beer1, Beer4.
• In tasting2 you start at 4 and count off by twos in a counter-clockwise direction. Beers will be tasted in the order Beer3, Beer1, Beer6, Beer4, Beer7, Beer2, Beer5.

We are going to use the JosephusBeerFlightTest.java JUnit tests to evaluate your JosephusBeerFlight 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 file H06.zip
4. Sign into 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 of the posted assignments. Select the assignment that you want to turn in and attach your H06.zip file accept the honor pledge to submit the assignment.