Using Objective-C, is there a way to convert a tree to Fast Enumeration?

Question

If there is a tree that has rootNode , and it points to the left and right for its child nodes (binary tree), is there a way to convert it to Fast Enumeration, as in Objective-C 2.0? So we can do

 for (id node in [tree allNodes]) { // do something } 

preferably without creating an O (n) object for memory size using a collection object such as NSMutableArray , NSSet or NSDictionary .

The order is not important, but it may appear as an order of depth.

Answer 1

When you perform a quick enumeration, you do not need to return all elements at once. Of course, all you get if you return them one at a time is a quick enumeration syntax without significant performance benefit.

You can return one element each time countByEnumeratingWithState:objects:count is called, or you can return all elements, or even just N elements.

For example, let's say you have a huge tree. You can use the stack buffer passed to you and its length:

 NSUInteger numItemsToReturn = MIN(100, lengthOfStackBuffer); 

You can then continue traversing the tree until numItemsToReturn or until you reach the end of your tree.

The internal infrastructure will continue to call countByEnumeratingWithState:objects:count until it sees the correct number of elements.

Please note that if you are only returning a piece of data, you will need to store the information in state so that you know where you can resume it next time. This is for extra .

EDIT

Commented out on the original post ... If you want to support fast enumeration, then this is pretty easy, as mentioned above.

However, if you just want to traverse the tree to do something, you may need to consider the enumeration API. For instance:

 -(void)enumerateWithOptions:(MyTreeEnumerationOptions)options usingBlock:^(id object, unsigned int level, BOOL isLeaf, BOOL *stop)block { // In here, you can use the options to determine if you are doing // pre/post depth first search, breadth-first, reverse, even concurrent. // You also provide an easy way to communicate to the caller not only the // object at this node, but the tree-depth of this node, whether it is a // leaf, and anything else you want to communicate. } 

Then users could call:

 [tree enumerateWithOptions:PreOrderDepthFirst usingBlock:^(id object, unsigned int level, BOOL isLeaf, BOOL *stop) { // Execute whatever code you want with this object... // Set *stop = YES to abort the enumeration. }]; 

Answer 2

As Jody and Valdrump say, you must comply with NSFastEnumeration . This will allow you to write:

 for (id node in tree) { // do something } 

In addition to this, there are, as you say, several ways to list, i.e. cross your tree: first comes the depth (pre-order, order, order) or width. You can subclass your tree and suggest various implementations of the delegate method countByEnumeratingWithState:objects:count as appropriate or (better) have a typedef and property that describes how the tree should be traversed and appeal it to the delegate method.

Answer 3

If you want to cross the tree in several ways (pre-, in, post-order), you might also consider creating your own NSEnumerator subclasses instead of matching NSFastEnumeration .

Subclass NSPreorderEnumerator, NSInorderEnumerator, and NSPostOrderEnumerator that know how to navigate the tree.

Then your tree objects respond with -preorderEnumerator , -inorderEnumerator , -postorderEnumerator , returning a new enumerator created for your tree.

Then you can do

 for(id node in [tree preorderEnumerator]) { // do stuff } for(id node in [tree postorderEnumerator]) { // do stuff } 

NSArray does something similar with -reverseObjectEnumerator , which allows you to reverse.