You will probably want to write a method to find the next position,
something like protected Position findNextPosition(Position
old), where old is the position that was just
returned by the iterator.
The simplest implementation is for findNextPosition to
scan the whole list from left to right each time it is called, looking
for the "best eligible position." A position is eligible if it
has not been returned yet by the iterator. And among the new
positions, some are better than others (should be returned sooner),
because they have smaller elements or because they are earlier in the
sequence.
So here are the four things you have to figure out:
If you know that old is the last position that was
returned, how can you tell whether another position p is eligible?
If p1 and p2 are both eligible
positions, how can you tell which is better? (That is, how can you
tell which should be returned first by the sorted iterator?)
How can you scan the list from left to right and find the best eligible position?
findNextPosition(old) is supposed to find the
next position to return after old. But to get us
started, how about finding the very first position? (In the example, this was the leftmost "3".) We have to
find it when we construct the iterator in the first place.
Can you define the first position in terms of our concepts "best"
and "eligible"? (Which positions are eligible when you first
construct the iterator?) If so, perhaps a lot of the code you need
will already be sitting in findNextPosition. So rather
than duplicate that code, can you enhance the definition of
findNextPosition so that you can use it to find the first
position as well -- perhaps through the call
findNextPosition(null)?
If you get really stuck, here are some more hints about how to scan the list. But try hard to figure it out yourself first!
Jason Eisner - jason@cs.jhu.edu - $Date: 2004/02/18 07:19:00 $