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

Question

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

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

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

The order is not important, but it might come out as depth-first order.

This should be absolutely possible if you have your tree class conform to [NSFastEnumeration](https://developer.apple.com/library/mac/#documentation/Cocoa/Reference/NSFastEnumeration_protocol/Reference/NSFastEnumeration.html). What have you tried so far? — waldrumpus, Sep 06 '12 at 14:19
The above response is correct. I'd look into Apple's Documentation and make your tree conform to NSFastEnumeration, as mentioned. https://developer.apple.com/library/mac/#documentation/Cocoa/Reference/NSFastEnumeration_protocol/Reference/NSFastEnumeration.html — MikeS, Sep 06 '12 at 14:23
I don't know Fast Enumeration that much yet. Right now I am looking into finding a node in a tree and need to return the node with the minimum value, and also need to return a 1 for left branch, or a 2 for right branch, for some related info... so I thought if using tree traversal (recursion), it can be kind of messy (might need a global variable or a mutable array to keep the states) (it is: for a tree of nodeViews, find the nodeView that is closest to a point on screen, and need to tell whether it is the left child or right child "connection point" of the viewNode is closest to that point) — Jeremy L, Sep 06 '12 at 14:37

Jody Hagins · Answer 1 · 2012-09-06T15:06:27.350

When you implement fast enumeration, you do not have to return all the elements at once. Of course, all you get if you return them one at a time is fast enumeration syntax, without much of the performance benefit.

You could return a single element each time countByEnumeratingWithState:objects:count is called, or you could return all the elements, or even just N elements.

For example, lets say you have a huge tree. You could use the stack buffer passed to you, and its length:

NSUInteger numItemsToReturn = MIN(100, lengthOfStackBuffer);

Then, you could continue your tree traversal up to numItemsToReturn or until you reached the end of your tree.

The internal infrastructure will keep calling countByEnumeratingWithState:objects:count until it has "seen" the right number of elements.

Note, however, that if you only return part of the data, you will have to store information in the state so you know where to resume the next time. That's what extra is for.

EDIT

Saw your comment on the original post... If you want to support fast-enumeration, then it's pretty easy, as mentioned above.

However, if you just want to traverse the tree to do stuff, you may want to consider an enumeration API. For example:

-(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.
}

Users could then 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.
}];

score 1 · Answer 2 · answered Sep 06 '12 at 14:32

As Jody and waldrumpus say, you should conform to NSFastEnumeration. This would allow you to write:

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

In addition to this, there are as you say a number of ways to enumerate i.e. traverse your tree: Depth first (preorder, inorder, postorder) or breadth first come to mind. You could subclass your tree and offer different implementations of the delegate method countByEnumeratingWithState:objects:count as fits, or (better) have a typedef and property that describes how the tree is to be traversed and appeal to this in the delegate method.

Patrick · Answer 3 · 2012-09-06T14:56:39.130

If you want to traverse the tree in multiple ways (pre-, in-, post-order), you might also consider creating your own NSEnumerator subclasses instead of just conforming to NSFastEnumeration.

So create the NSPreorderEnumerator, NSInorderEnumerator, and NSPostOrderEnumerator subclasses which know how to traverse the tree.

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

You can then 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 loop in reverse.

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

3 Answers3