Hi, what I'm trying to accomplish is to create a search function that traverses a ternary tree in a user defined pathway obtained through a string input, and returns the current tree to display the values of that tree root outside of the function.
Here is the data structure of this ternary tree in Pascal:
Code:
type MelodyTree = ^TreeNode;
TreeNode = record
upBranch: MelodyTree;
downBranch: MelodyTree;
sameBranch: MelodyTree;
title: string;
phrase: string;
end;
This procedure starts the search by taking a user input in the format 'uusdusd' u standing for up pathway and so on.
Code:
procedure tuneSearch(p:string; t:MelodyTree);
begin
p:= trim(p); //removes extra whitespacing
if (length(p)>0) then // non-empty line
begin
tuneSearch2(t, p, 0);
t:= tuneSearch2;
writeln('A match was found: phrase', t^.phrase, ' in the song ', t^.tune);
end else
begin
writeln('This pitch change is empty');
end;
end;
Then it goes to this function that uses recursion to traverse the tree in the pathway obtained a character at a time from the string Path:
Code:
function tuneSearch2(t:MelodyTree; path:string; pos:integer):MelodyTree;
begin
while length(path)<>0 do
begin
if(upcase(path[pos]) ='D') then
tuneSearch2(t^.downBranch, path, pos+1)
else if(upcase(path[pos]) = 'S') then
tuneSearch2(t^.sameBranch, path, pos+1)
else
tuneSearch2(t^.upBranch, path, pos+1)
end;
end;
return t;
end;
Now for some reason when I type in a search parameter such as 'ssddssdd' which contains the song phrase: "I'm in love with her and I feel fine" in the title: [I feel fine] the program just crashes when I run the nested If statements in tuneSearch2 that initialize the recursion.
is a very long time since I write something in pascal so some things could be wrong in what I say,
Code:
procedure tuneSearch(p:string; t:MelodyTree);
begin
p:= trim(p); //removes extra whitespacing
if (length(p)>0) then // non-empty line
begin
t:= tuneSearch2(t, p, 0);
writeln('A match was found: phrase', t^.phrase, ' in the song ', t^.tune);
end else
begin
writeln('This pitch change is empty');
end;
end;
Code:
function tuneSearch2(t:MelodyTree; path:string; pos:integer):MelodyTree;
begin
while length(path)<>0 do
begin
if(upcase(path[pos]) ='D') then
t := tuneSearch2(t^.downBranch, path, pos+1)
else if(upcase(path[pos]) = 'S') then
t := tuneSearch2(t^.sameBranch, path, pos+1)
else
t := tuneSearch2(t^.upBranch, path, pos+1)
end;
end;
return t;
end;
Hi, thanks for the reply, I tried your new code and I also changed the statement for my while loop as I noticed that it was redundant as it was before.
However with the new changes it is still doing the same thing, though it is displaying something on the screen before it closes but it shuts down too fast for me to read it. I don't know how to put break points into blooshed dev pascal.
here's the new code for tuneSearch and tuneSearch2:
Code:
procedure tuneSearch(p:string; t:MelodyTree);
begin
p:= trim(p); //removes extra whitespacing
if (length(p)>0) then // non-empty line
begin
t:= tuneSearch2(t, p, 0);
writeln('A match was found: phrase', t^.phrase, ' in the song ', t^.title);
end else
begin
writeln('This pitch change is empty');
end;
end;
//////////////////////////////////
function tuneSearch2(t:MelodyTree; path:string; pos:integer):MelodyTree;
begin
while pos <= length(path) do
begin
if(upcase(path[pos]) ='D') then
t:= tuneSearch2(t^.downBranch, path, pos+1)
else if(upcase(path[pos]) = 'S') then
t:= tuneSearch2(t^.sameBranch, path, pos+1)
else
t:= tuneSearch2(t^.upBranch, path, pos+1)
end;
tuneSearch2:= t;
end;
Last edited by psychofox19; 11-02-2008 at 03:45 PM..
Hi, thanks for the reply, I tried your new code and I also changed the statement for my while loop as I noticed that it was redundant as it was before.
However with the new changes it is still doing the same thing, though it is displaying something on the screen before it closes but it shuts down too fast for me to read it. I don't know how to put break points into blooshed dev pascal.
here's the new code for tuneSearch and tuneSearch2:
Code:
procedure tuneSearch(p:string; t:MelodyTree);
begin
p:= trim(p); //removes extra whitespacing
if (length(p)>0) then // non-empty line
begin
t:= tuneSearch2(t, p, 0);
writeln('A match was found: phrase', t^.phrase, ' in the song ', t^.title);
end else
begin
writeln('This pitch change is empty');
end;
end;
//////////////////////////////////
function tuneSearch2(t:MelodyTree; path:string; pos:integer):MelodyTree;
begin
while pos <= length(path) do
begin
if(upcase(path[pos]) ='D') then
t:= tuneSearch2(t^.downBranch, path, pos+1)
else if(upcase(path[pos]) = 'S') then
t:= tuneSearch2(t^.sameBranch, path, pos+1)
else
t:= tuneSearch2(t^.upBranch, path, pos+1)
end;
tuneSearch2:= t;
end;
if you can post a piece of code where you use this and don't work I will try to debug it.
//Main program code, displaying menu and entering option
begin
writeln(' *** Melody Search Engine ***');
repeat
Menu;
write('Option? ');
readln(option);
case option of
'l': // (l)oad melody data
begin
write('Load melodies from which file? ');
readln(melodyFilename);
LoadMelodies(melodyFilename);
end;
'd': // (d)isplay the tree
begin
displayTree(melodies);
end;
's': // (s)earch for a tune
begin
writeln('Type in the sequence of u/s/d pitch changes to search for:');
readln(pitch);
writeln;
tuneSearch(pitch,melodies);
end;
end;
until (option='q') or (option='Q');
end.
I have commented out sections from the tuneSearch procedure or tuneSearch2 function and I have determined that it crashes during the recursion in tuneSearch2
Last edited by psychofox19; 11-02-2008 at 06:00 PM..
//Main program code, displaying menu and entering option
begin
writeln(' *** Melody Search Engine ***');
repeat
Menu;
write('Option? ');
readln(option);
case option of
'l': // (l)oad melody data
begin
write('Load melodies from which file? ');
readln(melodyFilename);
LoadMelodies(melodyFilename);
end;
'd': // (d)isplay the tree
begin
displayTree(melodies);
end;
's': // (s)earch for a tune
begin
writeln('Type in the sequence of u/s/d pitch changes to search for:');
readln(pitch);
writeln;
tuneSearch(pitch,melodies);
end;
end;
until (option='q') or (option='Q');
end.
melodies is dynamic alocated but I don't see anywhere in the code you post if is or not create with new( and dispose later) and initialised. I guess you do this in LoadMelodies procedure. Try to check first if melodies is ok.
Hi, the variable melodies is initialized and works fine and I have already been able to traverse and display the tree structure as a visual aid from the menu option Display Tree. It is just a copy of the MelodyTree record for content editing purposes.
Hi, the variable melodies is initialized and works fine and I have already been able to traverse and display the tree structure as a visual aid from the menu option Display Tree. It is just a copy of the MelodyTree record for content editing purposes.
ok.
Try another thing. In tuneSearch2 you use upBranch, downBranch and someBranch but you didn't check if are valid pointers.
Yes they don't seem to be valid, I don't know why because I've been able to do it with other procedures.
I've made a couple of other positive changes but it's still not enough:
Code:
function tuneSearch2(t:MelodyTree; path:string; pos:integer):MelodyTree;
begin
if (pos <= length(path)) then
begin
if(upcase(path[pos]) ='D') then
tuneSearch2:= tuneSearch2(t^.downBranch, path, pos+1)
else if(upcase(path[pos]) = 'S') then
tuneSearch2:= tuneSearch2(t^.sameBranch, path, pos+1)
else
tuneSearch2:= tuneSearch2(t^.upBranch, path, pos+1)
end;
tuneSearch2:= t;
end;
Well i'll show you an example of the procedures that I have used recursion with these pointers:
This procedure is initialized in the main code in one of the above posts
Code:
procedure displayTree(t: MelodyTree);
// pre: true
// post: displays the tree t on the screen
begin
writeln;
DisplayTree2(t,0); // extra parameter used for indenting the levels of the tree
writeln;
end;
///////////////////
procedure displayTree2(t:MelodyTree;n:integer);
// pre: sufficient whitespace (2*n spaces) (and a label character if not the
// root node) has so far been written on the current line, ready to
// display the root value
// post: the whole tree has been displayed, each subtree two spaces more
// indented than its parent
begin
if t<>nil then
begin
write('#',n,' ');
writeln(t^.phrase:2); // display root node data
if (t^.downBranch<>nil) then // only display down subtree if non-empty
begin
write('D-':2*n+2); // display the chararcters 'D-' and indent ready for the subtree
DisplayTree2(t^.downBranch,n+1); // traverses to the next down branch
end;
if (t^.sameBranch<>nil) then // only display same subtree if non-empty
begin
write('S-':2*n+2); // display the chararcters 'S-' and indent ready for the subtree
DisplayTree2(t^.sameBranch,n+1); // traverses to the next same branch
end;
if (t^.upBranch<>nil) then // only display up subtree if non-empty
begin
write('U-':2*n+2); // display the chararcters 'U-' and indent ready for the subtree
DisplayTree2(t^.upBranch,n+1); // traverses to the next up branch
end;
end else begin
writeln;
writeln('The tree is empty.'); //displays if the tree is empty
end;
end;
Yes they don't seem to be valid, I don't know why because I've been able to do it with other procedures.
I've made a couple of other positive changes but it's still not enough:
Code:
function tuneSearch2(t:MelodyTree; path:string; pos:integer):MelodyTree;
begin
if (pos <= length(path)) then
begin
if(upcase(path[pos]) ='D') then
tuneSearch2:= tuneSearch2(t^.downBranch, path, pos+1)
else if(upcase(path[pos]) = 'S') then
tuneSearch2:= tuneSearch2(t^.sameBranch, path, pos+1)
else
tuneSearch2:= tuneSearch2(t^.upBranch, path, pos+1)
end;
tuneSearch2:= t;
end;
calling tuneSearch2 with first argument nil have no sense so you must modify the function to test if is nil and jump to the next branch to continue the search.
Also you must return nil if search fail and test the reurned result in tuneSearch.
Edit:is normal, because is a ternary tree, that some leaf on the border to be nil else ends as a graph with cycles,
check to see how you init the record when you reach a final leaf
Okay I added another if statement to contain the recursion when the tree node is empty
Code:
function tuneSearch2(t:MelodyTree; path:string; pos:integer):MelodyTree;
begin
if (pos <= length(path)) then
begin
if(t<>nil) then
begin
if(upcase(path[pos]) ='D') then
tuneSearch2:= tuneSearch2(t^.downBranch, path, pos+1)
else if(upcase(path[pos]) = 'S') then
tuneSearch2:= tuneSearch2(t^.sameBranch, path, pos+1)
else
tuneSearch2:= tuneSearch2(t^.upBranch, path, pos+1)
end;
end;
tuneSearch2:= t;
end;
However when I put in a pathway although it doesn't crash anymore it just spouts the message "There were no search matches for: suu" so I think it may be skipping past the point I need or not going far enough.
Okay I added another if statement to contain the recursion when the tree node is empty
Code:
function tuneSearch2(t:MelodyTree; path:string; pos:integer):MelodyTree;
begin
if (pos <= length(path)) then
begin
if(t<>nil) then
begin
if(upcase(path[pos]) ='D') then
tuneSearch2:= tuneSearch2(t^.downBranch, path, pos+1)
else if(upcase(path[pos]) = 'S') then
tuneSearch2:= tuneSearch2(t^.sameBranch, path, pos+1)
else
tuneSearch2:= tuneSearch2(t^.upBranch, path, pos+1)
end;
end;
tuneSearch2:= t;
end;
However when I put in a pathway although it doesn't crash anymore it just spouts the message "There were no search matches for: suu" so I think it may be skipping past the point I need or not going far enough.
is not ok. if t^.downBranch, t^.sameBranch or t^.upBranch are nil you must continue search on the non-nil branches until t is nil. In the same time have no sense to continue to search if t is non-nil and t^.downBranch, t^.sameBranch and t^.upBranch are nil.
I have now got an idea to put an if statement such as
Code:
if(t^.downBranch<>nil) then
and traverse to the next branch if true but complete the function with the previous node, but I don't know how to traverse back up to the root node of the current one.
Edit: I mean putting that inside the original if(upcase(path[pos]) = 'D') then begin statement.
Last edited by psychofox19; 11-02-2008 at 10:03 PM..
I have now got an idea to put an if statement such as
Code:
if(t^.downBranch<>nil) then
and traverse to the next branch if true but complete the function with the previous node, but I don't know how to traverse back up to the root node of the current one.
Edit: I mean putting that inside the original if(upcase(path[pos]) = 'D') then begin statement.
coding is the last part of a project.
start from here:
Before you post, read our: 
