Problem with a tree pathway search

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:

[code]
type MelodyTree = ^TreeNode;
TreeNode = record
upBranch: MelodyTree;
downBranch: MelodyTree;
sameBranch: MelodyTree;
title: string;
phrase: string;
end;
[/code]

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;
[/code]

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;
[/code]

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 nested If statements in tuneSearch2.

Can anyone see what I'm missing?

Comments

  • : 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:
    :
    : [code]:
    : type MelodyTree = ^TreeNode;
    : TreeNode = record
    : upBranch: MelodyTree;
    : downBranch: MelodyTree;
    : sameBranch: MelodyTree;
    : title: string;
    : phrase: string;
    : end;
    : [/code]:
    :
    : 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;
    : [/code]:
    :
    : 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;
    : [/code]:
    :
    : 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 nested If statements in tuneSearch2.
    :
    : Can anyone see what I'm missing?
    :
    What compiler are you using?

    Recursion frequently eats up all available memory, causing the program to crash. Does the program give a address where the crash occurred? If you have that then your compiler may be able to direct you to the problem line.

    Or try putting a break point at the beginning of each procedure to isolate the failure point.


  • : What compiler are you using?
    :
    : Recursion frequently eats up all available memory, causing the
    : program to crash. Does the program give a address where the crash
    : occurred? If you have that then your compiler may be able to direct
    : you to the problem line.
    :
    : Or try putting a break point at the beginning of each procedure to
    : isolate the failure point.
    :

    Hi, I am using Bloodshed Dev-Pascal, Bloodshed doesn't have a break point feature. I've made some major changes so far but i'm still unsuccessful.

    This is where tuneSeacrh is first initialized, melodies is a copy of MelodyTree:

    [code]
    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.
    [/code]

    Then this is the newer tuneSearch procedure:
    [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;

    if(t^.title <> '') then
    writeln('A match was found: phrase', t^.phrase, ' in the song ', t^.title)
    else
    writeln('There were no search matches for: ',p)
    end else
    begin
    writeln('This pitch change is empty');
    end;
    end;
    [/code]

    Finally the modified tuneSearch2:
    [code]
    function tuneSearch2(t:MelodyTree; path:string; pos:integer):MelodyTree;
    begin
    if (pos <= length(path)) then
    begin
    if(upcase(path[pos]) ='D') then begin
    tuneSearch2:= tuneSearch2(t^.downBranch, path, pos+1);
    end else begin
    if(upcase(path[pos]) = 'S') then begin
    tuneSearch2:= tuneSearch2(t^.sameBranch, path, pos+1);
    end else begin
    if(upcase(path[pos]) = 'U') then begin
    tuneSearch2:= tuneSearch2(t^.upBranch, path, pos+1);
    end;
    end;
    end;
    end;
    tuneSearch2:= t;
    end;
    [/code]

    Now it doesn't crash but it just doesn't stop at the correct point and possibly goes 1 root node beyond what I need and displays the message "There were no search matches for: ssddssdd"

    Anyway I've finally seen what the actual problem is! The whole path[pos] string array, the string path isn't an array but I wanted to check each character in that string one at a time at the nth position so I must have used the wrong method to check each character one at a time.

    Do you know what string function I need to use?
  • I've been doing a lot of intensive debugging and I've done it to a great extent, though I can't seem to solve it for when t is nil.

    Here it is:
    [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
    if(upcase(path[pos]) = 'U') then
    tuneSearch2:= tuneSearch2(t^.upBranch, path, pos+1)
    end else begin
    tuneSearch2:= t;
    end;
    end;
    [/code]

    What was happening before was that the string pos function had to start at the value 1 instead of 0 because it isn't like a normal array, so it ends up spouting out a special character.

    Secondly after the pathway was enacted correctly, since I hadn't placed the tuneSearch2:= t; in the 'else' section of the overall if statement [code]if (pos <= length(path)) then[/code] it was going to carry on recursing and the pos variable seemed to reverse until it reached 1 again.



  • : Hi, I am using Bloodshed Dev-Pascal, Bloodshed doesn't have a break
    : point feature.

    A break point is not a feature. It's simply inserting some action into the code that stands out and indicates the process has reached that point in the program. For example:
    [code]
    Procedure Whatever ;

    begin
    WriteLn ('Break point 1 ') ;
    halt ;
    etc..
    end ;
    [/code]
    If the program prints out 'Break point 1 ' and then stops you know the program is getting to the procedure called Whatever, otherwise you know the program is crashing before it gets to Whatever. Either way you can go back and move the break point, or several breaks points without the halt, and narrow down exactly where the program is crashing.


  • Do you know of a way in which i can solve this for when t is nil?

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories