Computer Science 210
Data Structures

Fall 2017, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

In this longer-than-usual lab, you will be working with iterators and linked lists more extensively. Since it's a long lab, you will also have 12 days, including a lab session, to work on it. However, you will almost certainly not finish in just the two hours of lab.

You will be assigned a partner to work with on this lab. Only one submission per group is needed.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository iterators-lab-yourgitname for this Lab. One member of the group should follow the link to set up the repository on GitHub, then that person should email the instructor with the other group members' GitHub usernames so they can be granted access. This will allow all members of the group to clone the repository and commit and push changes to the origin on GitHub.

Please answer lab questions in the README.md file in your group's GitHub repository. You may submit scans or legible photos of your memory diagrams, or you may create them in a drawing program. Either way, these should be included in your repository.

Iterators and Iterables

Before we get into the linked list tasks, we first take a look at some iterators.

The Iterators example includes two custom iterators over Vectors: the VectorEvenIterator will return only the elements of the Vector from even-numbered indices, and PrefixSumIterator returns, at each step, the sum of all values up to and including the current position (try it!). The latter works only on Vectors of Integer.

More Vector Methods

In a recent project, you developed an extension of the Vector class that included a Comparator-based sort method. We will continue in that direction for this task, creating an extension of Vector uncreatively called ExtendedVector that will include three new methods, plus a main method that tests these.

Some code for ExtendedVector.java is in your repository. In that code you will find stubs of three methods:

everyNth

(7 points) This method takes an int (let's call it n) as its parameter, and returns a new ExtendedVector whose contents are every n^th element from the ExtendedVector on which it is called.

For the sample ExtendedVector called green in the provided main method, which has the contents

"I" "will" "not" "eat" "green" "eggs" "and" "ham"

the ExtendedVector returned by the call green.everyNth(3) should have the contents

"I" "eat" "and"

atLeast

(7 points) This method takes two parameters: a value of the same type as is in the ExtendedVector and a Comparator capable of comparing elements of that type. The returned ExtendedVector should include all elements from the ExtendedVector on which it is called where the values are at least as big as the value given as the first parameter, as compared by the given Comparator.

For our ExtendedVector named green in the example, the ExtendedVector returned by the call

green.atLeast("eggs", new structure5.NaturalComparator())

should have the contents

"will" "not" "green" "eggs" "ham"

shuffle

(6 points) This method takes no parameters. It simply shuffles the values in the ExtendedVector. Ideally, the shuffling should be such that every element has an equal probability to end up in every position.

Also expand the main method to do more thorough tests. You should create at least two more instances of ExtendedVector that contain two different types of data. At least one of these should be a custom class (you may reuse one from an earlier lab or project if you wish). (10 points)

Your implementations of these methods and the additional tests will be graded as a practice program.

Methods on Lists and Iterators

The ListMethods class in the provided starter code includes two methods that find the maximum value from a collection of Integer values. One takes a List<Integer> parameter, which, as we will see, can be any class that implements java.util.List and contains Integer values. The second takes an Iterator<Integer> parameter.

More Iterators

Earlier in this lab, you wrote a method of our ExtendedVector class that returned another ExtendedVector that contained "every n^th" element from the original. Here, we are going to take that same idea and apply it to an iterator.

So considering the same example as above, if your Vector is called samIAm and contains the Strings:

"I" "will" "not" "eat" "green" "eggs" "and" "ham"

The code

  Iterator<String> iter = new EveryNthVectorIterator(samIAm, 3);
  while (iter.hasNext()) {
     System.out.println(iter.next());
  }

should print

I
eat
and

Hint: This is very similar to the VectorEvenIterator you wrote.

Next, we'll do the same thing but for the SimpleLinkedList class.

Before proceeding, read the section of the topic notes about the iterator for the SimpleLinkedList example, and study its code to make sure you understand it. There is a copy in your repository.

1. Create another class within SimpleLinkedList.java called SimpleListEveryNthIterator. The existing SimpleListIterator class is a good model to follow. Note that your constructor will need an extra parameter to indicate how far to skip ahead on each iteration, and that value will need to be stored in an instance variable of your iterator.
2. Add a method to SimpleLinkedList called everyNthIterator that constructs and returns an instance of SimpleListEveryNthIterator. It should be very similar to the existing iterator method.
3. Add code to the main method in SimpleLinkedList that tests your new iterator.

SimpleLinkedList Practice Programs

For the two practice programs below, you may implement the methods for both within the copy of the SimpleLinkedList example that is in your repository.

The methods of the RatioList linked list were all recursive. We can also write recursive versions of the SimpleLinkedList methods. For example, we could rewrite add as follows:

   public void add(int pos, E obj) {

        // negative positions not allowed
        if (pos < 0) {
            throw new IndexOutOfBoundsException(
              "Attempt to add at negative position " + pos);
        }

        head = add(pos, obj, head);
    }

    private SimpleListNode<E> add(int pos, E obj, SimpleListNode<E> startAt) {

        // if we are adding to an empty list it must be at position 0
        if ((startAt == null) && (pos != 0)) {
            throw new IndexOutOfBoundsException("Position too large for add");
        }

        // are we adding at the front of this part?
        if (pos == 0) {
            return new SimpleListNode<E>(obj, startAt);
        }

        // we are adding somewhere else, so let the recursion do the work
        startAt.setNext(add(pos - 1, obj, startAt.next()));
        return startAt;
    }

Notice that we needed to add a private helper method that is aware of the internals of the list structure (it takes the extra parameter which is a SimpleListNode).

More Memory Diagram Practice

Consider the following program:

public class SimpleLinkedListExample {

    public static void main(String args[]) {

        SimpleLinkedList<GenericPair<Integer,String>> a = 
            new SimpleLinkedList<GenericPair<Integer,String>>();

        a.add(new GenericPair<Integer,String>(120,"Intro to Programming"));
        // draw first diagram of memory when the get method call below
        // is about to return its value
        System.out.println("Added " + a.get(0));        
        a.add(new GenericPair<Integer,String>(210,"Data Structures"));
        a.add(new GenericPair<Integer,String>(225,"Advanced Programming"));
        
        // find and remember the GenericPair with the longest String
        Iterator<GenericPair<Integer,String>> i = a.iterator();
        GenericPair<Integer,String> longest = i.next();
        while (i.hasNext()) {
            GenericPair<Integer,String> pair = i.next();
            if (pair.getSecond().length() > longest.getSecond().length()) {
                longest = pair;
                // draw second diagram of memory at this point when pair
                // refers to the (210, "Data Structures") GenericPair object
            }
        }
        System.out.println(longest);
    }
}

As you can see, it uses two classes from previous examples: GenericPair and SimpleLinkedList. Note: use the original SimpleLinkedList, not the one you modified for previous sections of this lab.

Submitting

Your submission requires that all required deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.

Grading

This assignment is worth 170 points, which are distributed as follows: