Here is some classic pseudocode for finding the minimum-element position in a list of Integers:
min = null;
for each element e in the list // hey, why not use an ordinary iterator for this?
if (min==null || e < min)
min = e;
// now min holds the minimum element, or null if the list was empty
You can do something like that for this problem, too. Your job is a little more complicated, for four reasons:
min and e must be positions, not
elements, so you can keep track of the best eligible position for
findNextPosition to return. (Why can't
findNextPosition just return an element?)
The positions min and e must be
compared to see which is "best" (which can't be done just with the
< operator). You must also figure out what to do in
case of ties.
(To compare positions, you must use compareTo on
their elements, casting to Comparable at the risk of a
ClassCastException. If you find yourself doing this a
lot, consider writing a convenience method to clarify your code and
avoid code duplication.)
You have to ignore ineligible positions e in the
list. Among other things, that means you need to keep track of
whether you have passed old yet as you scan the list.
(If old.element()==3, then p.element() is
eligible only if it is after old in the list.)
You have to consider the case where old==null, at
least if you are going to allow the call
findNextPosition(null) as suggested in the previous hint.
By the way - a comment in the pseudocode above suggests that
when findNextPosition needs to scan through the list
positions in left-to-right order, it can simply use one of the list
iterators you've already written. (As long as you have given that
iterator a public nextPosition method. If not, it is
easy to turn your next method into a
nextPosition method, and then introduce a new
next method that simply calls nextPosition,
as here.)
I actually recommend doing that; it will simplify your code and make your life easier. The whole point of writing iterators is that they make your life easier - even when writing other iterators!
Jason Eisner - jason@cs.jhu.edu - $Date: 2004/02/18 07:15:17 $