Smart Home Smart Home - 1 month ago 11
Objective-C Question

Tree Traversal via Blocks with a premature stopping condition

I'm doing In-Order traversal of a Binary tree with a certain method executed on each node. I do this using a

inOrderTraversalWithOperation:
method as shown below that uses a Block to define the function that is needed at each node.

-(void) inOrderTraversalWithOperation:(void (^) (BinaryTreeNode *))operation
{
[self.leftChild inOrderTraversalWithOperation:operation];
if (operation)
{
operation(self);
}
[self.rightChild inOrderTraversalWithOperation:operation];

}


Suppose I want to stop when the Block execution hits a certain condition. One way to do it is to make the
inOrderTraversalWithOperation:
return a
BOOL
, and make the Block return a
BOOL
, as shown below.

But I am wondering if I can do it using the
BOOL *stop
approach used by Apple in many of its APIs. How do the Blocks with that flag work "underneath"?

-(BOOL) inOrderTraversalWithStopOperation:(BOOL (^) (BinaryTreeNode *))operation
{
BOOL shouldStop = NO;

shouldStop = [self.leftChild inOrderTraversalWithStopOperation:operation];
if (operation !=nil && shouldStop == NO)
{
shouldStop = operation(self);
}

if (!shouldStop)
{
shouldStop = [self.rightChild inOrderTraversalWithStopOperation:operation];
}

return shouldStop;
}


EDIT
Based on Josh's comment it looks like
BOOL *stop
will allow this but I still need
inOrderTraversalWithStopOperation:
to return a
BOOL


-(BOOL) inOrderTraversalWithStopOperation:(void (^) (BinaryTreeNode *, BOOL *))operation
{
BOOL shouldStop = NO;

shouldStop = [self.leftChild inOrderTraversalWithStopOperation:operation];
if (operation !=nil && shouldStop == NO)
{
operation(self, &shouldStop);
}

if (!shouldStop)
{
shouldStop = [self.rightChild inOrderTraversalWithStopOperation:operation];
}

return shouldStop;
}

Answer

The "stop" argument to an enumeration Block is just like any other indirect return value: you're passing an address from one scope so that the next scope can put something there. That something is then available in the original scope.

To add a stop flag to your operation type, you'd change its signature

typedef void (^NodeOperation)(BinaryTreeNode *, BOOL *);

In the calling context of the Block, you do what you've already done: create a BOOL for this flag and set it to NO. Then you pass its address in to the Block: operation(self, &stop);.

Inside the operation, you set the flag if necessary by dereferencing it and assigning a value: *stop = YES; (it would be a good idea to check that it's not NULL first; dereferencing NULL is illegal).

Back in the controlling scope, do what you're already doing: check the flag after each operation and decide what to do.

There's code samples for this mechanism in my related answer to What is the BOOL *stop argument for enumerateObjectsUsingBlock: used for?

To control the recursive method invocations, you have to pass information back somehow. You can do that most easily with the direct return value. The other option (although I don't think it buys you anything in this case) would be to add a BOOL pointer parameter to the method; then you can just keep passing around that same reference to every level. (That would probably mean creating a helper method so that the original caller doesn't have to worry about that argument.)