Many thanks for the reply, much appreciated. That makes sense - the only (or rather difficulty) is ensuring the node always has an up-to-date reference to its parent given the number of scenarios in which it could change (for instance, if a node is copied etc). Thanks again, Keith
________________________________ From: Mike Abdullah <[email protected]> To: Keith Blount <[email protected]> Cc: [email protected] Sent: Tue, April 27, 2010 4:50:41 PM Subject: Re: Fastest way to check for descendants of an object 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]
