Skip to content

Iterator Implementation Lab

Learning Objectives

  • Gain experience programming iterators.
  • Gain experience implementing generic classes.

Submission: You can get credit for Part 1 by showing your completed answers to your instructor. If you are unable to attend, you must contact your instructor and submit a PDF through Canvas. Parts 2-4 must be submitted through Gradescope. You may only receive credit for Parts 2-4 if you have completed Part 1.

Part 1 - Reviewing GapList

Download the following file:

Take a few minutes to read over this file to make sure you understand how it works. Once you have done so, work with your group to answer the following questions. Once you have finished, confirm your answers with the instructor.

  1. There are multiple classes defined in the file GapList.java. List each of the classes along with the interfaces that they implement.

  2. Are inner classes able to access the private instance variables of the enclosing class? If so, find an example of this in GapList.java. Provide the line number and explain how the private instance variable is being used.

  3. What will be printed by the following code snippet?

    GapList arr = new GapList(5);
arr.add(0, "Hello");
arr.add(2, "World");
arr.add(4, "!");

System.out.println(arr.size());
System.out.println(arr.capacity());
for (String s : arr) {
    System.out.println(s);
}
    Write your answer then check it by creating a driver file.

  4. Consider the following code snippet: 

    GapList arr = new GapList(3);
arr.add(0, "Hello");
arr.add(1, "World");
arr.add(1, null);

System.out.println(arr.size());
Iterator<String> it = arr.iterator();
System.out.println(it.hasNext());
System.out.println(it.next());
System.out.println(it.hasNext());
System.out.println(it.next());

    What will be printed when this code is executed?

  5. Note that the advance method is called from hasNext. This is slightly unusual. Typically, hasNext methods don't change the state of the iterator, they only check the state to determine whether there are any remaining items. In part, this is because hasNext may or may not be called before next. We can't rely on it. Why are we confident in this implementation that hasNext will be called at least once for each call to next?

  6. The next method includes the following statement:

    return elements[index++];

    Would the method still work correctly if we changed it to this?

    return elements[++index];

  7. We could have made index an instance variable of the GapList class.

    GapList arr = new GapList(3);
arr.add(0, "A");
arr.add(1, "B");
arr.add(2, "C");

for (String outer : arr) {
    for (String inner : arr) {
        System.out.println(inner + " " + outer);
    }
}

    Consider the code snippet above, and then explain why doing so would be a bad idea. (If you don't see the problem, go ahead and try executing this code after moving index into GapList).


Part 2 - Implement a Skip Iterator

Download the following files:

Complete SkipScanner.java so that it conforms to the provided javadoc comments. You can test your iterator with the SkipScannerTest JUnit tests.

Part 3 - Implement a Skip Iterator with Generics

Download the following test file:

Make a copy of your working SkipScanner.java class to a new file named SkipScannerGeneric.java. Change the SkipScannerGeneric class so that instead of accepting an array of Strings it will accept an array containing any type of object.

Part 4 - Implement the NGram iterator

Download the following files:

Complete NGramScanner.java so that it conforms to the provided javadoc comments. You can test your iterator with the NGramScannerTest JUnit tests.

Code Submission

Submit the following files through Gradescope:

  • SkipScanner.java
  • NGramScanner.java
  • SkipScannerGeneric.java

Going Further

If you have extra time, implement a PrimesGenerator class that implements Iterable<Integer>. Your class should make it possible to iterate over prime numbers as in the following example:

    public static void main(String[] args) {
        for (int p : new PrimesGenerator(10)) {
            System.out.println(p);
        }
    }

In this case, the expected output would be the first ten primes:

2
3
5
7
11
13
17
19
23
29

Your implementation should not pre-generate all of the required values. Each call to next should dynamically find the next available prime.

There is nothing to submit for this exercise.