21

Just for a bit of background I am trying to write a Depth First Sort in Apex. I have been successful writing the method using recursion but when testing with some large data volumes I have hit the Stack Depth Governor Limit.

I am now trying to implement the iterative algorithm (on the wikipedia page). The problem I am facing is best explained using the code snippet below:

while(!stack.isEmpty()) {
    frame = stack.top();
    for (Frame child : frame.children()) {
         if (some condition) {
             continue; //on the while loop, not the for loop
         }
    }
    //this line of code must only execute if 'some condition' is false for all children
    stack.pop();
}

A quick search turns up how to do this in java: Breaking out of nested loops in Java. But apex doesn't support named loops, what would be the cleanest way of doing this in apex?

  • presumably there's some more code that goes in the loop, otherwise wouldn't this be an infinite loop if (some condition) is true ? – superfell May 28 '13 at 15:21
  • 1
    Shouldn't the last line (frame.pop();) be popping the top off the stack rather than the frame? That way the next while loop iteration will pickup the next item at the top of the stack. – Daniel Ballinger May 29 '13 at 0:10
23

One easy way, and which gives some nice structure to the code is to make the inner loop a separate function, e.g.

while(!stack.isEmpty()) {
    Frame frame = stack.top();
    if (frameCondition(frame))
        continue;
    frame.pop();
}

boolean frameCondition(Frame f) {
    for (Frame c : f.children()) {
         if (some condition)
              return true;
    }
    return false;
}
8

Here is another option, as I imagine you will have might have a few of Set<Frame>s to keep track of the discovered and explored frames.

while(!stack.isEmpty()) {
    frame = stack.top();

    boolean treeEdgeDiscovered = false;
    for (Frame child : frame.children()) {

        if (frameIsNotDiscoveredAndNotExplored) {
            // Push child frame to the top of the stack after marking as discovered
            treeEdgeDiscovered = true;
            break;
        } 
    }

    if(!treeEdgeDiscovered) {
        // Track that frame has been explored. Maybe with a Set<Frame>?

        // I assume this should actually be popping the top off the stack 
        // rather than the frame
        stack.pop();
    }
}

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.