Kevin Jackson Kevin Jackson - 3 months ago 11
Java Question

Single-iteration over hierarchy in Java 8

How can I implement single-loop iteration over a hierarchy of different objects?

(I have used for-loops but these represent a different areas of a grid -- I can barely follow all the values used for positioning. Using a single loop would drastically simplify things.)

This hierarchy of objects is what I have....

class Hierarchical < PT extends Hierarchical<?,?,?>,T,CT extends Hierarchical< ?, ?, ? >>{
ObservableList< Hierarchical > children; //Zero or more objects..
}

class Seed extends Hierarchical { /* never has children-objects */ }
class Tree extends Hierarchical { ... }
class Planet extends Hierarchical { ... }


Edit: Children in the Planet instance are Trees, same for Trees containing Seeds.

...and this is what I want to do:

Planet p = new Planet(); //trees/seeds are instantiated internally.
Iterator< ? > itr = p.getChildren().iterator();
while ( itr.hasNext() ) {
Object obj = itr.next();
if ( obj instanceof Planet ){ /* cast to Planet & do stuff */ }
if ( obj instanceof Tree ){ /* cast to Tree & do stuff */ }
if ( obj instanceof Seed ){ /* cast to Seed & do stuff */ }
}


Clearly the answer lies in
Iterator< ? > itr = p.getChildren().iterator();
but how can it be implemented? It would seem that every level of the hierarchy would need to keep a position of it's children in the event its children start looping through their children. It's been far too long, I'm not familiar with design-patterns & java's collections anymore. :(

I'll note that I had an error when trying to use
Iterator< Hierarchical > itr = p.getChildren().iterator();
because p is of type Planet.

Edit: This needs to be "Depth-Last" (...or FIFO?). The looping is to simplify generation of the UI so the order is important.

Answer

If I have understood you right, you want to be able to visit every object in an object graph and do something with each object?

When each object implements a common interface, as yours do, this is simply resolved using recursion. Your only decision is whether you want to do depth-first recursion or breadth-first.

For depth first, you would want something like

public void visit(Hierarchical h) {
    // do something with h
    Iterator<Hierarchical> children = h.getChildren();
    while(children.hasNext()) {
        visit(children.next());
    }
}

It would seem that every level of the hierarchy would need to keep a position of it's children in the event its children start looping through their children

Using recursion in this way, you don't need to keep track of any 'position' - the state of the iterator is kept on the stack as you call the method again, so as the stack unwinds, when you get to a 'seed', you will roll back up the stack a level and call the next iteration of the iterator.

For breadth-first, you will need to process an entire node first, collecting branches as you go. When you have finished processing all children you need to start on the collection of branches.

public void visit(Hierarchical h) {
    List<Hierarchical> branches = new LinkedList<>();
    Iterator<Hierarchical> children = h.getChildren();

    while(children.hasNext()) {
        Hierarchical h = children.next();
        // do something with h
        if(h.hasChildren()) {
            branches.add(h);
        }
    }

    for(Hierarchical branch : branches) {
        visit(branch);
    }
}