Re: Fastest way to check for descendants of an object
Re: Fastest way to check for descendants of an object
- Subject: Re: Fastest way to check for descendants of an object
- From: Keith Blount <email@hidden>
- Date: Tue, 27 Apr 2010 11:05:54 -0700 (PDT)
Indeed, I believe that's my problem - currently when I add objects to my children array I do things such as [[myNode children] addObject:newNode], meaning I have nowhere to catch it. I'll update my code to add some accessors as you suggest, and change my - (NSMutableArray *)children accessor to - (NSArray *)children so that the compiler can catch any slips where I try to manipulate it directly. Regarding the weak reference to the parent, I guess I don't need to worry about that getting released because if it is, then so will the children be, or else by then they will refer to a different parent object.
Thank you!
________________________________
From: Mike Abdullah <email@hidden>
To: Keith Blount <email@hidden>
Cc: email@hidden
Sent: Tue, April 27, 2010 6:37:25 PM
Subject: Re: Fastest way to check for descendants of an object
Well that's pretty easy if you're writing proper accessor methods like:
- (NSArray *)children;
- (void)insertObject:(MyNode *)node inChildrenAtIndex:(NSUInteger)index;
- (void)removeObjectFromChildrenAtIndex:(NSUInteger)index;
Just call -setParent: or similar in the implementation.
On 27 Apr 2010, at 17:39, Keith Blount wrote:
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@hidden>
>To: Keith Blount <email@hidden>
>Cc: email@hidden
>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@hidden)
>>
>>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:
>>
>>This email sent to email@hidden
>>
>
>
>
_______________________________________________
Cocoa-dev mailing list (email@hidden)
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:
This email sent to email@hidden