ICS 211 Homework H04: Sortable Beer List (Doubly linked implementation)

Purpose

Our first abstract data structure is the List. For this homework assignment we are going to implement a sortable list using a linked node to store the items in the list. This assignment should give you more practice with Eclipse and implementing an interface. We will also use our implementation of the list as a member variable and learn how delegation can make your programming easier.

At the end of this homework you will have two different SortableList classes that have different implementations. Your SortableBeerList class can choose which one to use.

Tasks

1. Create a package named edu.ics211.h04

This is where we will put all our classes for homework 04.

2. Create a class named SortableList that implements the IList211 and ISortableList interfaces

public interface IList211<E> {
  E get(int index);
  E set(int index, E element);
  int indexOf(Object obj);
  int size();
  boolean add(E e);
  void add(int index, E element);
  E remove(int index);
}

public interface ISortableList<E>{
  void insertionSort(Comparator<E> compare);
  void bubbleSort(Comparator<E> compare);
  void selectionSort(Comparator<E> compare);
  int getNumberOfSwaps();
  int getNumberOfComparisons();
  double getSortTime();
}

The SortableList in edu.ics211.h04 must use a DLinkedNode a private inner class to store the items in the list.

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;
  }
}

Use the Comparator to compare the items in the list. The sort methods should sort the list in ascending order, smallest at the beginning, largest at the end.

3. Create a SortableBeerList that implements IList211 and automatically sorts the list of Beers

The class SortableBeerList implements IList211<Beer> and has:

• A private SortableList<Beer> member variable. This is how we are going to store and sort the beers.
• A constructor that takes a Comparator<Beer> as the parameter. This is how the SortableBeerList will decide the order of the beers.
• All the methods of IList211. It can delegate the operations (methods) to the SortableList member variable.

You should be able to copy your edu.ics211.h03.SortableBeerList java file into edu.ics211.h04. Then change the package and it should work.

4. Create your own JUnit tests for SortableList.

Create the JUnit test class SortableListTest. If you are happy with your H03 tests, copy the files to edu.ics211.h04 and change the package line.

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

We are going to use the SortableBeerListTest.java JUnit tests to evaluate your SortableBeerList 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 H04.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 H04.zip file accept the honor pledge to submit the assignment.