2
\$\begingroup\$

I wrote an algorithm that returns all k-sized subgraphs of another given graph. Because I don't want to make the runtime of the next() call of the iterator depended on k, I don't want to return a new object every time. Instead I have one fixed instance-variable subG in the iterator that is changed between the calls und always represents the current subgraph that was calculated. It acts as a view that can be copied if needed if you want to use it further.
This method works fine and this is not my problem.

If I want to use hasNext(), I'd need to calculate the next subgraph, which would change the view subG as a side-effect. This is not wanted. Currently I'm using my own interface for this iterator:

/**
 * Interface for all iterators that always return the same object, but change it in order to return the next value.
 * Therefore, the object should not be changed unintentionally, because that would result in unwanted side-effects.
 * This prevents the use of "hasNext()" as this would have to calculate the next value for the object, but this method
 * is not expected to have side-effects. The only method that changes the object is generateNext(), which also is
 * its only purpose.
 *
 * The standard pattern for using this interface would be:
 * while (iter.hasCurrent()) {
 *     doSomethingWith(iter.getCurrent());
 *     iter.generateNext();
 * }
 */
public interface BlindIterator<T> {

    /**
     * @return True iff the current element is a valid return.
     */
    boolean hasCurrent();

    /**
     * @return Returns the current element, but does NOT generate the next element. This method can be called
     * as often as wanted, without any side-effects.
     */
    T getCurrent();

    /**Generates the next element, which can then be retrieved with getCurrent(). This method thus only provides
     * this side-effect. If it is called while the current element is invalid, it may produce and exception,
     * depending on the implementation on the iterator.
     */
    void generateNext();
}

I've never written something like this. Is there a better pattern for this, if any?

\$\endgroup\$
1
\$\begingroup\$

I think most people would be surprised and annoyed by an iterator that mutated previously yielded values every time you called next. While it makes sense to take what you can from the concept of an iterator, the thing you're trying to make isn't an iterator. (Perhaps the idea of a "cursor" would be more applicable, IDK.)

Your proposed interface {hasCurrent, getCurrent, generateNext} seems fine. I do have some questions/suggestions.

  1. If not x.hasCurrent(), does x.getCurrent() return null, or throw an exception, or what?
  2. Depending on 1 (particularly if it doesn't throw an exception), .getCurrent() sounds more like a read-only property, in which case just call it .current(). (or maybe even just .value)
  3. .generateNext() specifically doesn't make anything (because we're supposing that would be expensive); it changes the thing in question. Therefore maybe call it .mutate() or .becomeNext()
  4. A void return is usually a wasted opportunity, even if just for a little extra debugging context. Exactly what will be best to return here depends on exactly how this is going to be used. Returning boolean success might save you a call to .hasNext(); returning T might save you a call to .current(). Probably boolean is better, but it's hard to say.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 1. It should trow an exception if hasCurrent() is false, but I'm not sure how do implement this. Can I use default-methods for this? 2.&3. Yea, I renamed them, thanks. 4. I'll look what I need, but I also already thought about that. \$\endgroup\$ – Morinator Apr 3 at 15:01
  • \$\begingroup\$ But the concern about runtime is justified. This thing can generate 1 million subgraphs in a few seconds this way. Creating millions of objects takes a long time doesn't it? \$\endgroup\$ – Morinator Apr 3 at 15:09
  • \$\begingroup\$ I have very little experience specific to java. How to throw an exception I don't recall being too finicky, if that's the way you want to go. \$\endgroup\$ – ShapeOfMatter Apr 3 at 18:01
  • \$\begingroup\$ As for the runtime efficiency; I don't know. My intuition is that, if you structure your context so that only one (or a handful) of these millions of objects are alive in memory at once (i.e. they're getting garbage-collected at about the same rate as they're being generated) then it should be fine. Your concern about the cost of generating each next sub-graph scaling with the sub-graph size makes sense (of course I can't confirm it 'cause I haven't seen your code), but you're paying dearly (in terms of safety and intelligibility of your code) to avoid it with this mutable-state solution. \$\endgroup\$ – ShapeOfMatter Apr 3 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.