This assignment will teach you about the structure of lists by having
you implement an interesting way to iterate over them. It will also
teach you how to separately design individual components that make up a
A warning: The time it took you to complete PA1 is probably not a
good predictor of how long PA2 will take. This is more involved. Start
early, start often.
A common pattern in user interfaces is the pagination of results –
that is, splitting a list of results across pages. Shopping sites do it
at the bottom of their search results, for example:
The numbers 1 2 3 … 20 refer to pages of results, with page-by page
traversal via next and previous actions.
This project will have two kinds of iterators that you implement – a
Paginator, which iterates back and forth between pages, and a
which iterates through the items on a page. You will implement them for
two different implementations of list – doubly-linked lists and array
lists. In total, you’ll implement those four classes along with tests
for them. You’ll also implement a few list methods that we left out for
you to practice with these structures.
The provided classes
DL for “doubly-linked”) and
CSE12ArrayList contain the list implementations whose contents will be
paginated. Each of these classes implements a
paginate method that
null. You can fill this in with a call to the
appropriate paginator’s constructor once you decide on a design for it.
We’ve provided you with mostly complete implementations of a simple
array list and a simple doubly-linked lists. You will implement three
methods (stubbed out with TODO comments):
paginate. Note that you’ll be implementing each of these methods
twice – once for array lists and once for doubly-linked lists.
There is a file called
TestLists.java that you can use to write tests
for these methods. Like in PA1 for Bag implementations, it is
parameterized to run all the tests for both list implementations,
makeList method that you can use to instantiate new lists.
Implementing the first two of these—
good place to start, because it will get you familiar with the existing
list data structures that are in place. The description of these methods
is in the interface description in
You will implement two subclasses of
Paginator<E>, one for each type
of lists. The
Paginator<E> abstract class implements
ListIterator<Page<E>>. You can read the official Java documentation
You will not implement the
set methods (the
ones listed as optional) – we’ve provided
Paginator as an abstract
class with default implementations of these three methods that simply
throw exceptions; you don’t need to alter these at all.
You have a lot of choice in how you implement
Paginator; the starter
code begins with the class totally blank, and you will choose fields, a
constructor, and how to implement all the required methods from
ListIterator. For reference, there are 6 methods to implement –
Some examples are below.
Each time the
previous() methods are called on a
Paginator, it returns a
Page. The type
Page<E> is defined in
Page.java to be equivalent to
Iterator<E>; the documentation for
You will write two classes that implement
Page, again one for the
linked list and one for array lists. You won’t implement the
method (listed as optional).
Page implementation should have
next method. The
next() method should return, sequentially, the items in the subset for
The example below illustrates the core behavior of both kinds of
// Create and populate a list (this should work for either kind of list)
Here are diagrams that should give you an idea of how the above data is
Using the Doubly Linked List implementation
Using the Array implementation
You are responsible for testing your implementation. You should test
Paginator independently and thoroughly to ensure that they
behave as you expect. You can write all of your tests in the
TestLists.java test class that we set up for you.
In the grader, your tests will be evaluated by running them against
several bad implementations, which we will not show you the source
code for. You will be able to see feedback on this via the autograder.
You can test for exceptions by using the
expected annotation on a
@Test(expected = IndexOutOfBoundsException.class)
For example, for testing that a method throws a
NoSuchElementException, you’d replace
You should make sure to do all of the following:
ALPage, test thoroughly
DLPage, test thoroughly
set), test thoroughly
set), test thoroughly
There are some things you should do:
- Read the documentation for
- Tackle the assignment in this order:
- First, write the
findFirstmethods in the
two list classes, and test them to make sure they work. This
will get you familiar with the list implementations’ structure.
- Second, on paper, in a drawing program, or in plain text, not
in code, come up with a design for the fields and constructors
for one pair of
Paginatorclasses. Draw pictures
and come up with examples of simple situations, like two pages
of two elements each, and think about what would be stored in
the fields of the two classes after different uses of
and what the layout of the list will look like when the call to
paginate()is made. The example above can guide you, but you
might want to start with something even simpler.
- Third, translate your idea for the
Pageyou have in mind into
code. Construct any
Nodes or arrays you need to construct it
in a test, and then implement the
methods and check that they work as you expect. Make sure you
get a simple version working before you go on! You might come
back and edit this design, but you should make sure you know
- Fourth, do the same for the
Paginatorclass you have in mind.
At this point, you’ll have a constructor for the
and can fill in the
paginatemethod of the corresponding list
class with a use of the constructor. Start testing the
Paginatorby creating sample lists that correspond to your
examples from earlier, and then filling and and using the
various methods required by
- Repeat the process for the other list implementation, or, at any
time pause and try the other.
- First, write the
There are a few things you should explicitly not do on this assignment.
- Outside of tests, you should never call the constructors for
or the list classes (inside tests, it’s very much encouraged). The
Pageimplementations shouldn’t be constructing
new nodes or
contentsarrays, only using references to existing
Paginatorclasses should not get references to list objects.
They can get references to contents, like nodes or arrays, and be
passed information when constructed, but they should not receive a
reference to the list itself.
Pageclasses should not make any changes to
the contents of the list (if we were implementing the optional
ListIterator, we would, but
the methods we are implementing should not).
- Don’t change the list classes beyond the bodies of the
paginate. In particular, don’t
change access modifiers like
private; instead, figure out how to
pass that information to where it needs to go.
There are also a few things you can assume (and correspondingly don’t
need to bother testing).
perPageparameter will always be greater than 0
- The various methods that manipulate list elements (e.g.
findFirst, and so on), will never be
- You can assume that the list that created an iterator is not changed
between calls to the iterator’s methods – that is, if you create an
iterator, then add an element, the iterator doesn’t have to
carefully take into account that addition before calling
This is a real-world assumption, not simply done to simplify the
assignment. Real-world code turns this case into an error: you can
look up the documentation on “fail-fast iterators” and
to see more about why.
Use automatic formatting options to handle whitespace and syntactic
choices about braces.
Strive to make your code as readable as possible without the use of
excessive comments. Write a javadoc header comment on each method you
write. Focus the header comment on any interesting effects the method
has (e.g. changing an index field, manipulating references to
You’ll submit to the pa2 assignment in Gradescope. What you’ll see is
output like this:
The idea is that you are trying to separate the wheat from the
The wheat is our reference implementation: your tests should all pass
on our implementation. The chaff is 13 implementations we wrote that
are broken in various ways.
Your goal is similar to, but not quite the same as, your goal in PA1
with the bag implementations. A really good test suite will pass all
tests on our reference (the wheat), and have some test fail on each
broken implementation (it will identify all chaff). You don’t have to
uniquely distinguish here, just distinguish the bad implementations by
failing some test.
The names of the chaffs may give hints about what may be wrong with
them. Four are related to find/remove, and the other nine are related to
Paginators and Pages. You can fail some tests on the reference
implementation (it will come with a small deduction per failed test),
and you’ll still get credit for each chaff that fails a different set of
tests from the reference implementation.
This is all the feedback you will get before submission. After
submission, you will be graded on the correctness of your
implementation, on your tests, and on overall style. This testing-based
feedback gives you a way to gain confidence in your implementation. If
you aren’t sure how something should behave, add a test and make sure it
passes on your implementation and the reference implementation. The
chaffs don’t force you to think of every possible situation, and our
tests may well test more thoroughly still than just catching all the
The grade breakdown will be:
- 50% implementation
- 10% for the two list methods
- 20% for each page/paginator combination
- 40% testing
- 1% if your tests all pass the reference implementation
- 1% point deduction for each test that fails the reference
implementation (max 5% deduction)
- 3% for each chaff that you detect (13 chaffs total)
- 10% style and design
There will be additional (significant) deductions for violating the DO
NOT constraints above.