Generally, you make MyNode also hold a weak reference to its parent node. (see
NSTreeNode/NSView for example)
Then, when testing a node, can quickly recurse up the tree looking for a
desired ancestor.
On 27 Apr 2010, at 16:33, Keith Blount wrote:
> Hello,
>
> I have a model object that represents a single node in a tree (it can be used
> in an NSOutlineView for instance). As such, it has a "children"
> NSMutableArray iVar which can store other objects of the same class, which in
> turn may have their own children.
>
> E.g:
>
> @interface MyNode : NSObject
> {
> NSMutableArray *children;
> }
> @end
>
> Whereby "children" would contain instances of MyNode which in turn have
> "children" that may contain other instances of MyNode (obviously the above is
> just a grossly simplified version of my actual class which does much more).
>
> There are occasions when I need to check if one node object is the descendant
> of another node object. My current code for this is as follows:
>
> - (BOOL)isDescendantOfOrOneOfNodes:(NSArray*)nodes
> {
> // Returns YES if we are contained anywhere inside the array passed in,
> including inside sub-nodes.
> NSEnumerator *enumerator = [nodes objectEnumerator];
> id node = nil;
> while (node = [enumerator nextObject])
> {
> if (node == self) return YES; // Found ourself
> // Check all sub-nodes
> if ([[node children] count] > 0)
> {
> if([selfisDescendantOfOrOneOfNodes:[node children]])
> returnYES;
> }
> }
> // Didn't find self inside any of the nodes passed in
> returnNO;
> }
>
> - (BOOL)isDescendantOfNodes:(NSArray*)nodes
> {
> // Returns YES if any node in the array passed in is an ancestor of ours.
> NSEnumerator *enumerator = [nodes objectEnumerator];
> id node = nil;
> while (node = [enumerator nextObject])
> {
> // Note that the only difference between this and
> isAnywhereInsideChildrenOfNodes: is that we don't check
> // to see if we are actually one of the items in the array passed in,
> only if we are one of their descendants.
> // Check sub-nodes
> if ([[node children] count] > 0)
> {
> if([selfisDescendantOfOrOneOfNodes:[node children]])
> returnYES;
> }
> }
>
> // Didn't find self inside any of the nodes passed in
> returnNO;
> }
>
> So, in use, e.g:
>
> if ([firstNode isDescendantOfOneOfNodes:[NSArray arrayWithObject:secondNode]])
> // ... do something (e.g. prevent secondNode from being added as a child
> of firstNode).
>
>
> My question is simply, is there a faster way of doing this? There are
> occasions when I need to run through and check potentially thousands of nodes
> each with thousands of descendants, and in this situation these checks can be
> quite time-consuming and slow things down. I know 10.5 introduced fast
> enumeration (e.g. "for (id node in nodes)"), and the only reason I'm not
> using that is that I need to support 10.4 too (I tested it and fast
> enumeration does speed things up a little, but not as much as I need at the
> volumes I'm talking about). So I'm just wondering if there is anything in the
> above that can be optimised to be faster. If not, I probably just need to
> re-examine where I'm calling these methods again, but I figured I'd start
> with first principles and initially check to see if there is any obvious
> quicker way of checking that an object is a descendant of another in the
> above situation that I might be missing.
>
> Thanks and all the best,
> Keith
>
>
>
> _______________________________________________
>
> Cocoa-dev mailing list ([email protected])
>
> Please do not post admin requests or moderator comments to the list.
> Contact the moderators at cocoa-dev-admins(at)lists.apple.com
>
> Help/Unsubscribe/Update your Subscription:
> http://lists.apple.com/mailman/options/cocoa-dev/cocoadev%40mikeabdullah.net
>
> This email sent to [email protected]
_______________________________________________
Cocoa-dev mailing list ([email protected])
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com
This email sent to [email protected]
