prune recursive search paths
-
26-06-2021 - |
Вопрос
my knowledge is limited, writing in C++ for 2 months
In this function string code
is recursively decrements chars until the base case ""
is found. I want to prune some paths before the base case is found, and for some string code
a path to the base case will not be found. For the prune I want to compare an attribute in the path with parameter int time
. This searches a trie made of 'nodeT'
struct charT {
char letter;
nodeT *next;
};
struct nodeT {
bool isOperation;
bool isCode;
int time;
Vector<charT> alpha;
};
nodeT *root
usage:
string code = "12345";
int time = convertToEpoch(20120815); //my epoch function
containsCode(code, time)
bool containsCode(string code, int time)
{
if(root == NULL) return false;
else return containsCodeHelper(root, code, time);
}
bool containsCodeHelper(nodeT *w, string code, int time)
{
if(code == "") //base case: all char found
return w->isCode;
else {
if (w->isOperation && w->time != time) return false; //case 2: time check OK <- at a midpoint in the path
for(int i = 0; i < w->alpha.size(); i++) { //Loop through the leaf
if (w->alpha[i].letter == code[0]) //case 3: leaf exists
return containsCodeHelper(w->alpha[i].next, code.substr(1), time);
}
}
return false; //if no path
}
This function worked well before adding the time check prune, it now loops, returns false
if outside time but then starts again with the candidate string code
from char location 0.
Questions: 1) Is a nested return false
kicking the recursion back to the next call for loop, 2) should the time prune be placed in the for loop with a logical return false
or return
'path', 3) is this more fundamentally messed-up and I need to learn a C++ concept <- please explain if yes.
Also, the posted function is a simplified version of the actual function - there is a modifier to time and a 'step over' path that I left out. In past question I found that these 'addons' distract from the question.
Решение
after some reworking it now functions fine - possibly it always did; I changed to read attribute return w->isCode
to return true
, that seemed to be the biggest issue - I will debug the trie constructor and see if it is setting the attribute at the end of each path.
boolcontainsCodeHelper(nodeT *w, string code, int time)
{
if(code == "") //base case: all char found
return true;
else {
if ( w->isOperation && (!((w->begin-wag) <= time && time <= (w->end+wag) ) && time != 9999 ) )
return false; //case 2: time
else {
for(int i = 0; i < w->alpha.size(); i++) { //Loop through all of the children of the current node
if (w->alpha[i].letter == word[0])
return containsCodeHelper(w->alpha[i].next, word.substr(1), time, wag);
else if (word[0] == 'ž') //step over '0' all subnodes
if (containsCodeHelper(w->alpha[i].next, word.substr(1), time, wag))
return true;
}
}
}
return false; //if char is missing - meaning the exact code is not there - terminates garbage subnode paths
}
I don't see any difference between having return false;
at the end and leaving it out. Also still confused as why the special case needs if( bool fn()) return true;
rather than just return ( bool fn());
i found that solution through trial and error with help from another stack overflow thread