ICS 211 Homework H05: 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.h05

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

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

Create a CircularDoublyLinkedList class that implements IList211 and Iterable. The iterator() method should return a ListIterator

public interface ListIterator<E> {
  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)
}

In your CircularDoublyLinkedList you will need a private class that implements the ListIterator interface. The iterator method will return a new instance of your private inner class.

Your CircularDoublyLinkedList will need a constructor that takes an array and builds the list.

public CircularDoublyLinkedList(E[] items) {
  ...
}

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 with:

• A private CircularDoublyLinkedList to hold the beers.
• A constructor that takes an array of Beers, the Beers in the flight.
• A method tasteBeers that returns a List of Beers. This method should use your CircularDoublyLinkedList.iterator() to choose the beers.

 
     /**
      * Returns a LinkedList<Beer> 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 tasting from
      * @param step - predetermined number for counting off
      * @param isClockwise - if isClockwise is true, counting occurs in a
      * clockwise/increasing manner. If isClockwise is not true, then counting occurs
      * in a counter-clockwise/decreasing manner.
      * @return LinkedList<Beers> of the Beers as they were tasted.
      */
     LinkedList<Beers> tasteBeers(int start, int step, boolean isClockwise) {
       // your code
     }
   

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.

4. Create your own JUnit tests for CircularDoublyLinkedList.

Create the JUnit test class CircularDoublyLinkedListTest.

Please thoroughly test your code and briefly discuss your testing strategy. Make sure that you test the ListIterator methods.

We are going to use the JosephusBeerFlightTest.java JUnit tests to evaluate your JosephusBeerFlight class for correctness.

Testing

Please thoroughly test your code and briefly discuss your testing strategy. Make sure that you test the different sorting algorithms. Turn in all your test code.

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 H05.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 H05.zip file accept the honor pledge to submit the assignment.