Hi Folks,
I've had problems with recursive functions before, but this one's making me
crazy.
I have a trie (tree) data structure and I'm trying to find a sequence of ints
in the trie.
- (HSMM_TrieNode*) getTrieNodeFromContextSequence:(NSMutableArray *)aSequence
withNode:(HSMM_TrieNode*) aNode
{
int coincidence;
BOOL found = NO;
HSMM_TrieNode* endNode = nil;
NSMutableArray* mutableSeq = [[NSMutableArray alloc]
initWithArray:aSequence copyItems:YES];
for(HSMM_TrieNode* child in [aNode children])
{
coincidence = [[mutableSeq objectAtIndex:0] intValue];
if([child coincidenceID] == coincidence)
{
endNode = child;
found = YES;
break;
}
}
if(([endNode depth] < ([self contextDepth] - 1)) && ([mutableSeq count]
> 1) && (found == YES))
{
[mutableSeq removeObjectAtIndex:0];
[self getTrieNodeFromContextSequence:mutableSeq
withNode:endNode];
}
[mutableSeq release];
return endNode;
}
The caller sends the sequence of ints (NSNumbers) and the root node of the trie
to search. If I NSLog the guts of this method, I can see that it is, in fact,
recursing down the trie, and correctly following the branch with the matching
ints (coincidenceID numbers), and reaching the point I need to reach. The
problem is that it's not returning the last node in the trie (i.e., the last
match), but rather is returning the first match. And I have no idea why...
Those last few tests before recursing are just checking that 1) I haven't gone
too deep in the trie (I actually want the last node *before* the leaf --
"contextDepth" is the max depth of the trie), 2) that I haven't run out of ints
in the sequence, and 3) that I actually found branch to continue searching
down. If trie doesn't have a match for the start of the sequence, the nil
return is handled by the caller.
Can anyone see why the caller is getting the first match, rather than the last?
Immense thanks to anyone who can see what's up.
J.
James B Maxwell
Composer/Doctoral Student
School for the Contemporary Arts (SCA)
School for Interactive Arts + Technology (SIAT)
Simon Fraser University
jbmaxw...@rubato-music.com
jbmax...@sfu.ca
_______________________________________________
Cocoa-dev mailing list (Cocoa-dev@lists.apple.com)
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 arch...@mail-archive.com
