Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Page 1 of 2 12 LastLast
Results 1 to 15 of 22
  1. #1
    New Coder
    Join Date
    Nov 2008
    Posts
    14
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Pascal Tree pathway search help

    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.

    Can anyone see what I'm missing?

  • #2
    Master Coder
    Join Date
    Dec 2007
    Posts
    6,682
    Thanks
    436
    Thanked 890 Times in 879 Posts
    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;
    regards

  • #3
    New Coder
    Join Date
    Nov 2008
    Posts
    14
    Thanks
    1
    Thanked 0 Times in 0 Posts
    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 04:45 PM.

  • #4
    Master Coder
    Join Date
    Dec 2007
    Posts
    6,682
    Thanks
    436
    Thanked 890 Times in 879 Posts
    Quote Originally Posted by psychofox19 View Post
    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.

    best regards

  • #5
    New Coder
    Join Date
    Nov 2008
    Posts
    14
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Code:
    //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 07:00 PM.

  • #6
    Master Coder
    Join Date
    Dec 2007
    Posts
    6,682
    Thanks
    436
    Thanked 890 Times in 879 Posts
    ok, thank you. I'll be back with some results.

    best regards

  • #7
    Master Coder
    Join Date
    Dec 2007
    Posts
    6,682
    Thanks
    436
    Thanked 890 Times in 879 Posts
    Code:
    //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

  • #8
    New Coder
    Join Date
    Nov 2008
    Posts
    14
    Thanks
    1
    Thanked 0 Times in 0 Posts
    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.

  • #9
    Master Coder
    Join Date
    Dec 2007
    Posts
    6,682
    Thanks
    436
    Thanked 890 Times in 879 Posts
    Quote Originally Posted by psychofox19 View Post
    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

  • #10
    New Coder
    Join Date
    Nov 2008
    Posts
    14
    Thanks
    1
    Thanked 0 Times in 0 Posts
    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;

  • #11
    Master Coder
    Join Date
    Dec 2007
    Posts
    6,682
    Thanks
    436
    Thanked 890 Times in 879 Posts
    Quote Originally Posted by psychofox19 View Post
    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

    best regards
    Last edited by oesxyl; 11-02-2008 at 09:36 PM.

  • #12
    New Coder
    Join Date
    Nov 2008
    Posts
    14
    Thanks
    1
    Thanked 0 Times in 0 Posts
    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.

  • #13
    Master Coder
    Join Date
    Dec 2007
    Posts
    6,682
    Thanks
    436
    Thanked 890 Times in 879 Posts
    Quote Originally Posted by psychofox19 View Post
    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.

    best regards

  • #14
    New Coder
    Join Date
    Nov 2008
    Posts
    14
    Thanks
    1
    Thanked 0 Times in 0 Posts
    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 11:03 PM.

  • #15
    Master Coder
    Join Date
    Dec 2007
    Posts
    6,682
    Thanks
    436
    Thanked 890 Times in 879 Posts
    Quote Originally Posted by psychofox19 View Post
    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:

    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


  •  
    Page 1 of 2 12 LastLast

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •