Introduction

Assignment 4 is designed to prepare you for the midterm at the end of next week. You will need to use all of the concepts and skills you have learned so far this quarter to implement a class that computes all of the prime numbers up to some integer n. The technique you are to use, known as the Sieve of Eratosthenes, was developed by a Greek (Eratosthenes) who lived in the third century BC.

The goals of Assignment 4 are:

• To introduce the concept of generics.
• To practice constructing and using iterators.
• To practice retrofitting unfamiliar code to meet new requirements.
• To introduce the use of the queue ADT.
• To review lists and linked list implementations.
• To urge you to consider the complexity of an operation before implementing it.
• To practice reading and understanding unfamiliar code.
• To practice writing code with good, consistent style.

As usual, your code will be evaluated not only on functionality but also on quality. Make sure to comment your code appropriately and follow Java conventions.

This assignment has two deadlines. The checkpoint deadline is a bonus to encourage you to start the assignment early. The entire assignment is due at the regular time (9:00 p.m. on Tuesday). Read the Turn-in section below for details.

Background

The Sieve of Eratosthenes is described by the following pseudocode:

Fill a list with the consecutive integers 2 through n inclusive.
Create an empty queue to store primes.
do {
    Obtain the next prime (P) by removing the first value in the list.
    Add P to the queue of primes.
    Iterate through the list, eliminating numbers divisible by P.
} while (P < sqrt(n));
All remaining values in the list are prime, so transfer them to the queue.

Problem Statement

Assignment 4 has six starter files:

• IntLinkList.java: This file contains a linked list implementation of an integer list and a corresponding iterator. The code should be familiar (both to code developed in lecture and your Homework 2), but you should be sure to peruse the classes carefully before starting the assignment. You will need to modify this class to use generics and will use it in two roles in this assignment. First, this class will serve as the list that the Sieve algorithm requires. Second, this class is used to implement LinkQueue.
• IntListNode.java: This class serves as the node used by the IntLinkList class. You will need to modify this class when you retrofit IntLinkList to use generics.
• LinkQueue.java: The LinkQueue class contained in this file assumes a properly implemented LinkList class (which you will create using IntLinkList.java as a starting point). It implements the Queue interface and will be used as the Queue required by the Sieve algorithm. You will not need to modify this file.
• outputLog.pdf: This file contains sample output from SieveMain being run with a working implementation of Sieve. Given the same inputs, your code will need to produce output that matches the output in this sample.
• Queue.java: This interface defines the basic operations in the Queue ADT. You are not allowed (and will not need) to define additional Queue operations to complete this assignment.
• SieveMain.java: The test class contained in this file was used to produce the sample output and is an example of how the Sieve you will write may be used. You may use this file for testing but should be aware that you will need to write additional code to fully test your Sieve.

You should be able to complete this assignment in stages. Remember to test your code thoroughly after each step to keep debugging simple and to ensure a stable codebase for the later stages.

First, use the provided IntLinkList and IntListNode classes to create LinkList and ListNode classes. Your new classes should differ from the originals in three ways:

• LinkList and ListNode should both use generics. That is, you should, for example, be able to create an instance of LinkList that stores Strings and another that stores Integers. (Note: To complete this requirement, you will need to modify the iterator included in LinkList, too.)
• Since your LinkList can store objects of any type, you should not use "==" to determine if an object stored in the list is equal to another object. Instead, use ".equals(...)".
• Your LinkList should perform adds to the rear of the list and removes from the front of the list in O(1) time. You may need to add an additional field to LinkList to implement this functionality.

Next, define a class called Sieve with the following public methods:

In addition, you are required to adhere to the following constraints when implementing Sieve:

• All traversals through your list should be performed using the iterator provided in the LinkList class. You should only use the get and remove methods on the first item in the list.
• You should construct only one LinkList and one Queue in your Sieve class. You may create no other container classes or arrays.
• Your implementation of Sieve should never search for primes that it has found before.
  1. If a user calls computeTo with a value n1 and later calls it with a value n2 such that n1 >= n2, your implementation of Sieve should set its internal state appropriately but should not discard any values in the queue of prime numbers.
  2. If a user calls computeTo with a value n1 and later calls it with a value n2 such that n2 > n1, then your implementation of Sieve should use the primes it has already found rather than searching for primes in the range 2 to n1.
• You should guarantee that your Sieve is never in a corrupt state. For example, your Sieve might be asked to compute up to one value of n and then asked to compute up to a different value of n without a call on reportResults ever being made. Similarly, your object might be asked to compute up to some value of n and then be asked to reportResults more than once. Each call on reportResults, getMax and getCount should behave appropriately given the previous call on computeTo, no matter how often they are called or in what order. Finally, notice that if reportResults, getMax or getCount are called before a legal call on computeTo, they throw an exception to indicate that the operation is not legal given the object's state.
• Since you have a Queue interface available, you should use variables of type Queue rather than type LinkQueue to write your Sieve class. Since no interface is available for a List, you should use variables of type LinkList. (No interface for Lists is provided because iterators make the problem somewhat more difficult; we will see a solution for this after the midterm.)

Turn-in

• In terms of correctness, your classes must provide all of the functionality described above while abiding by the stated constraints.
• In terms of style, we will be grading your use of JavaDoc comments, good variable names, consistent indentation, and good coding style to implement these operations.
• To encourage you to get started early, this assignment has an optional "checkpoint" due at 12:00 p.m. (noon) on Saturday, July 15. If you submit your LinkList.java and ListNode.java files electronically by the checkpoint deadline, you will receive 2 bonus points on the assignment. To receive the bonus points, your LinkList must use generics and pass our suite of tests. (Our tests will check that your add, remove, get, and indexOf methods continue to work as expected.) Note that your LinkList does not need to implement the O(1) add to the rear and remove from the front operations to earn the bonus points.
• Name your files LinkList.java, ListNode.java, and Sieve.java and turn them in electronically from the assignments link on the class web page by 9:00 p.m. on Tuesday, July 18. Remember to test your code thoroughly!
• Unlike the previous three assignments, you do not need to answer any additional questions to complete this homework.

Hints and Tips

• Make sure to read and understand all of the code you have been given before starting the assignment.
• When in doubt, consult the message board. If your question has not yet been answered or if you run into a question that you can help answer, post!
• Stage 1, transforming IntLinkList and IntListNode to LinkList and ListNode, should require extensive but small modifications. You will need to change types throughout both classes (as well as in the enclosed iterator class), and we encourage you to test your code thoroughly before making any changes to comply with the performance requirements. The performance requirements can be implemented with an additional field and changes to a single method.
• You will need to write your own testing program for Stage 2, writing the Sieve class. When Sieve has been fully implemented and passes your own testing program, use SieveMain to make sure your output complies with the sample output provided.
• You will find the method "double Math.sqrt(double)" useful for implementing Sieve.
• This assignment really does bring together all of the concepts and skills we have covered so far in this class. Use it as a chance to prepare yourself for the midterm and don't hesitate to ask questions about difficulties you run into.