1.

Download the provided code and read it over.

2.

In the class

ListUtils

within the

cs445.lab10

package, write the generic method

static void printList(ListInterface list)

, which prints the contents of a List.

You should rely entirely on iterators; do not use the List's

.get()

method. Test that your method works

properly.

3.

Within the same class, write the method

static void removeShortStrings(ListInterface list, int limit)

, which

removes all strings shorter than

limit

. Again, rely only on iterators for element access, and test that

your method works. Do not use the List's

.get()

or

.remove(int)

methods.

4.

Within

cs445.lab10.SieveOfEratosthenes

, implement method

ListInterface primesUpTo(int max)

. This method should use the Sieve of

Eratosthenes to build and return a list of integers containing all of the primes up to

max

. Use instances

from Lab 9 to test your program. Again, do not use

.get()

or

.remove(int)

from List in your

method.

In this lab, you implemented several methods, including a

sieving technique

for determining all of the prime

integers up to a threshold. More importantly, you practiced using iterators.

package cs445.lab10; import java.util.Iterator; public class ListUtils { public static  void printList(ListInterface list) { // TODO: Complete this method } public static void removeShortStrings(ListInterface list, int limit) { // TODO: Complete this method } public static void main(String[] args) { ListInterface myList = new ArrayList(); myList.add("Apples"); myList.add("are"); myList.add("so"); myList.add("good"); myList.add("..."); myList.add("in"); myList.add("fact"); myList.add("I"); myList.add("eat"); myList.add("them"); myList.add("when"); myList.add("I"); myList.add("write"); myList.add("programs"); // prints "Apples are so good ... in fact I eat them when I write programs" System.out.println("Original list:"); printList(myList); //prints "Apples write programs" System.out.println("Strings of length 5 or greater:"); removeShortStrings(myList, 5); printList(myList); } } 

package cs445.lab10; import java.util.Arrays; import java.util.Iterator; import java.util.NoSuchElementException; /** * A class that implements the ADT list using a resizable array. * @author Frank M. Carrano * @author Timothy M. Henry * @author William C. Garrison III * @version 4.1 */ public class ArrayList<E> implements ListInterface<E> { private E[] list; private int size; private static final int DEFAULT_CAPACITY = 10; public ArrayList() { this(DEFAULT_CAPACITY); } public ArrayList(int initialCapacity) { if (initialCapacity < 0) { initialCapacity = DEFAULT_CAPACITY; } @SuppressWarnings("unchecked") E[] tempList = (E[])new Object[initialCapacity]; list = tempList; size = 0; } public void add(E newEntry) { add(size, newEntry); } public void add(int newPosition, E newEntry) { if (newPosition >= 0 && newPosition <= size) { if (newPosition <= size - 1) { makeRoom(newPosition); } list[newPosition] = newEntry; size++; ensureCapacity(); } else { throw new IndexOutOfBoundsException("Given position " + newPosition + " for add's new entry is out of bounds."); } } public E remove(int position) { return remove(position, false); } /** * This is a helper method that allows me to print an error on regular calls * to remove, but not if called through the iterator. */ private E remove(int position, boolean fromIterator) { if (!fromIterator) { System.err.print("Call to remove() detected! "); System.err.println("In this lab, you should use iterators instead."); } if (position >= 0 && position <= size - 1) { assert !isEmpty(); E result = list[position]; if (position < size - 1) { removeGap(position); } size--; return result; } else { throw new IndexOutOfBoundsException("Illegal position " + position + " given to remove operation."); } } public void clear() { for (int index = 0; index < size; index++) { list[index] = null; } size = 0; } public E set(int position, E newEntry) { if (position >= 0 && position < size) { assert !isEmpty(); E originalEntry = list[position]; list[position] = newEntry; return originalEntry; } else { throw new IndexOutOfBoundsException("Illegal position " + position + " given to replace operation."); } } public E get(int position) { System.err.print("Call to get() detected! "); System.err.println("In this lab, you should use iterators instead."); if (position >= 0 && position < size) { assert !isEmpty(); return list[position]; } else { throw new IndexOutOfBoundsException("Illegal position " + position + " given to getEntry operation."); } } public E[] toArray() { @SuppressWarnings("unchecked") E[] result = (E[])new Object[size]; for (int index = 0; index < size; index++) { result[index] = list[index]; } return result; } public boolean contains(E entry) { return indexOf(entry) >= 0; } public int indexOf(E entry) { int result = -1; for (int index = 0; result < 0 && index < size; index++) { if ((entry == null && list[index] == null) || (entry != null && entry.equals(list[index]))) { result = index; } } return result; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } private void ensureCapacity() { int capacity = list.length; if (size >= capacity) { int newCapacity = 2 * capacity; list = Arrays.copyOf(list, newCapacity); } } private void makeRoom(int newPosition) { assert (newPosition >= 0) && (newPosition < size); for (int index = size - 1; index >= newPosition; index--) { list[index + 1] = list[index]; } } private void removeGap(int position) { assert (position >= 0) && (position < size); int removedIndex = position; int lastIndex = size; for (int index = removedIndex; index < lastIndex; index++) { list[index] = list[index + 1]; } } public Iterator iterator() { return new ArrayListIterator(); } private class ArrayListIterator implements Iterator<E> { private int nextIndex; private boolean wasNextCalled; private ArrayListIterator() { nextIndex = 0; wasNextCalled = false; } public boolean hasNext() { return nextIndex < size; } public E next() { if (hasNext()) { wasNextCalled = true; E next = list[nextIndex]; nextIndex++; return next; } else { throw new NoSuchElementException("No more elements to iterate"); } } public void remove() { if (wasNextCalled) { // Call the containing object's remove method ArrayList.this.remove(nextIndex-1, true); nextIndex--; wasNextCalled = false; } else { throw new IllegalStateException("Cannot call remove now"); } } } } 

package cs445.lab10; /** * An interface for the ADT list. * @author Frank M. Carrano * @author Timothy M. Henry * @author William C. Garrison III * @version 4.1 */ public interface ListInterface<E> extends Iterable<E> { /** * Adds a new entry to the end of this list. * Entries currently in the list are unaffected. The list's size is * increased by 1. * @param newEntry The object to be added as a new entry. */ public void add(E newEntry); /** * Adds a new entry at a specified position within this list. * Entries originally at and above the specified position are at the next * higher position within the list. The list's size is increased by 1. * @param newPosition An integer that specifies the desired position of the * new entry. * @param newEntry The object to be added as a new entry. * @throws IndexOutOfBoundsException if newPosition < 0 or * newPosition > getSize(). */ public void add(int newPosition, E newEntry); /** * Removes the entry at a given position from this list. * Entries originally at positions higher than the given position are at the * next lower position within the list, and the list's size is decreased by * 1. * @param position An integer that indicates the position of the entry to * be removed. * @return A reference to the removed entry. * @throws IndexOutOfBoundsException if position < 0 or * position >= getSize(). */ public E remove(int position); /** * Removes all entries from this list. */ public void clear(); /** * Replaces the entry at a given position in this list. * @param position An integer that indicates the position of the entry to * be replaced. * @param newEntry The object that will replace the entry at the position * position. * @return The original entry that was replaced. * @throws IndexOutOfBoundsException if position < 0 or * position >= getSize(). */ public E set(int position, E newEntry); /** * Retrieves the entry at a given position in this list. * @param position An integer that indicates the position of the desired * entry. * @return A reference to the indicated entry. * @throws IndexOutOfBoundsException if position < 0 or * position >= getSize(). */ public E get(int position); /** * Retrieves all entries that are in this list in the order in which they * occur in the list. * @return A newly allocated array of all the entries in the list. If the * list is empty, the returned array is empty. */ public E[] toArray(); /** * Determines whether this list contains a given entry. * @param entry The object that is the desired entry. * @return True if the list contains entry, or false if not. */ public boolean contains(E entry); /** * Determines the first index of a given entry. * @param entry The object that is the desired entry. * @return The first index of the entry if it is in the list; -1 if not. */ public int indexOf(E entry); /** * Gets the size of this list. * @return The integer number of entries currently in the list. */ public int getSize(); /** * Sees whether this list is empty. * @return True if the list is empty, or false if not. */ public boolean isEmpty(); } 

package cs445.lab10; import java.util.Iterator; public class SieveOfEratosthenes { public static ListInterface primesUpTo(int max) { // TODO: Complete this method return null; } public static void main(String[] args) { int end = 0; try { end = new Integer(args[0]); } catch (NumberFormatException e) { System.out.println("Please use a integer parameter for maximum value"); return; } catch (ArrayIndexOutOfBoundsException e) { System.out.println("Please use a integer parameter for maximum value"); return; } ListInterface result = primesUpTo(end); if (result != null) { System.out.println("Primes:"); ListUtils.printList(result); System.out.println(" "); } else { System.out.println("primesUpTo() returned null. Did you complete it?"); } } }