Computer Science 210
Data Structures

Fall 2016, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

This week's lab will give you some practice with iterators, writing more methods for Vectors, and recursive data structures.

You may work alone or with a partner on this lab. Only one submission per group is needed.

Getting Set Up

Download and extract the starter project that includes code you will need to use and modify for this lab.

Create a document where you will record your answers to the lab questions. If you use plain text, call it "lab6.txt". If it's a Word document, you can call it whatever you'd like, but when you submit, be sure you convert it to a PDF document "lab6.pdf" before you submit it.

Iterators and Iterables

Before we get into the linked list tasks, we first take a look at a topic that will become much more relevant with our more advanced data structures: iterators.

Read the topic notes linked from the schedule page and look at the examples before proceeding.

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

Last week, 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 the starter package you downloaded at the beginning of this lab. 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.

You should 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 last week's lab if you wish). (10 points)

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

Memory Diagram

Consider this main method that uses the RatioList and Ratio classes from the RatioListApplet example.

    public static void main(String args[]) {

        RatioList rats = new RatioList(new Ratio(7, 9), null);
        rats = new RatioList(new Ratio(3, 4), rats);
        rats = new RatioList(new Ratio(1, 10), rats);

        Ratio theSum = rats.getSum();
        System.out.println(theSum);
    }

Extending the RatioList

The extensions to RatioList will be graded as practice programs.

1. Write a recursive method size of class RatioList that returns the number of Ratios in a RatioList. You may assume it is called on a non-null RatioList (i.e., there is at least one Ratio already in the list). (4 points)
2. Write a recursive method addToEnd of class RatioList that takes a Ratio as its only parameter and puts the given Ratio in a new RatioList node at the end of the linked list. Hint: recursively call addToEnd on the rest of each RatioList until you find the one with a null rest, and construct a new RatioList to replace that null rest. You may assume it is called on a non-null RatioList (i.e., there is at least one Ratio already in the list). (7 points)
3. Write a main method in your modified version of the RatioList class that thoroughly tests your two new methods. (4 points)

Submitting

Before 10:00 AM, Wednesday, October 26, 2016, submit your lab for grading. There are two things to do to complete the submission: (i) Copy your file with the answers to the lab questions into your project directory. Be sure to use the correct file name. If you prepared your answers in Word, export to a PDF file and submit that. and (ii) upload a copy of your lab (a .7z or .zip file containing your project directory) to Blackboard under "Lab6". Don't forget to check your programming assignment programs for compliance with the Style Guide for CSIS 210 Programs

Grading

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