...

View Full Version : Pascal Tree pathway search help



psychofox19
11-02-2008, 12:15 PM
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:



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.



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:



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.

Can anyone see what I'm missing?

oesxyl
11-02-2008, 12:34 PM
is a very long time since I write something in pascal so some things could be wrong in what I say, :)



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;




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;


regards

psychofox19
11-02-2008, 04:40 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:



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;

oesxyl
11-02-2008, 06:46 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:



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.

best regards

psychofox19
11-02-2008, 06:57 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.

I have commented out sections from the tuneSearch procedure or tuneSearch2 function and I have determined that it crashes during the recursion in tuneSearch2

oesxyl
11-02-2008, 07:01 PM
ok, thank you. I'll be back with some results.

best regards

oesxyl
11-02-2008, 08: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.

best regards

psychofox19
11-02-2008, 08:04 PM
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.

oesxyl
11-02-2008, 08:12 PM
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.

best regards

psychofox19
11-02-2008, 09:19 PM
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:



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


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;

oesxyl
11-02-2008, 09:31 PM
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:



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.

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
best regards

psychofox19
11-02-2008, 10:07 PM
Okay I added another if statement to contain the recursion when the tree node is empty



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.

oesxyl
11-02-2008, 10:33 PM
Okay I added another if statement to contain the recursion when the tree node is empty



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.

best regards

psychofox19
11-02-2008, 10:49 PM
I have now got an idea to put an if statement such as

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.

oesxyl
11-02-2008, 11:38 PM
I have now got an idea to put an if statement such as

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:

http://en.wikipedia.org/wiki/Ternary_search_tries

decide which method fit with your problem and then will try to implement in pascal.

never cross my mind until now, this is a homework assignment?

best regards

psychofox19
11-02-2008, 11:43 PM
No, it's part of business project I have been charged with and I just needed some intellectual feedback.

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?

oesxyl
11-02-2008, 11:59 PM
No, it's part of business project I have been charged with and I just needed some intellectual feedback.
no problem, I will help as I can no matter what is, :)


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'm afraid I don't know. Since now was only a problem of logic and basic programming but last time when I write in pascal was a very very long time ago so I have no idea what is now in pascal.
But you must build a hash to have a efficient search. Start looking for what is done in another languages if you don't find something in pascal.

best regards

psychofox19
11-03-2008, 01:04 AM
I've done it! *dances a little jig

Here it is:


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


What was happening 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
if (pos <= length(path)) then it was going to carry on recursing and the pos variable seemed to reverse until it reached 1 again for some reason that I cannot fathom why.

Anyway you've been a great help and I thank you for taking your time to help me out!

oesxyl
11-03-2008, 01:16 AM
I've done it! *dances a little jig

how did you solve the case when t is nil?


Anyway you've been a great help and I thank you for taking your time to help me out!
it's no problem, I like to help, :)

best regards

psychofox19
11-03-2008, 01:25 AM
how did you solve the case when t is nil?


Ah, you do have a point there... I might sleep on it and get back to you with something if I can. Good night!

psychofox19
11-03-2008, 06:35 PM
Okay I've solved it, or at least I've tricked the computer into not crashing by looking at the next subnode and if it sees it doesn't exist then it returns the current t.

But obviously doing that it would return whatever value was inside that root node even if it had something you were looking for there or not.

So I just tricked it by removing whatever value it had in the tree copy so it ends up bringing up the no matches found if statement branch.

Here it is:



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

oesxyl
11-03-2008, 06:52 PM
Okay I've solved it, or at least I've tricked the computer into not crashing by looking at the next subnode and if it sees it doesn't exist then it returns the current t.

But obviously doing that it would return whatever value was inside that root node even if it had something you were looking for there or not.

So I just tricked it by removing whatever value it had in the tree copy so it ends up bringing up the no matches found if statement branch.

Here it is:



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

I'm glad you solve your problem, :)

best regards



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum