Board index » delphi » More nagging about tries

More nagging about tries

Hi,

Quote
Simon Ulfsbecker wrote:
> procedure DeleteSeq(lastNode:PTrieNode);
> begin
>   if not IsLeaf(lastNode) then
>     lastNode^.name:=NO_ID_STR_C
>   else
> end;

> However, if the gene to be deleted happens to have no other genes after it
> (like z-44), the node with the last genebase stored (c, in z-44's case) is a
> leaf and should be disposed. The node above should then eventually become a
> leaf and should be disposed and so on until we reach a node which isn't a
> leaf.

Or which is another gene (has a non-empty name), I suppose?

Quote
> I don't know how to implement this!

I would recommend that you keep track of the last node that has
either a non-empty name or only *one* child while traversing the
tree (that's how it is written) and searching for a gene.

For simplicity, let's assume you search for genes given the sequence
of bases. In this case, your searching procedure might look like this:

   function SearchGene(node : PTrieNode; seq : string) : PTrieNode;
   var i, j, k : integer;
   begin
      i := 1;
      while (i <= length(seq)) and (node <> nil) do
      begin
         j := 0;
         k := 1;
         while (k <= MAX_CHILD_C) and (j = 0) do
         begin
            if (node^.child[k] <> nil) and
             (node^.child[k]^.edge = seq[i]) then j := k;
            inc(k);
         end;
         if j = 0 then node := nil
         else node := node^.child[j];
         inc(i);
      end;
      SearchGene := node;
   end;

   ...

   Found := SearchGene(root, 'actgt');  { for example }
   if Found = nil then
      writeln('Not found.')
   else if Found^.name = NO_ID_STR_C then
      writeln('Exists, but wasn''t  entered.')
   else writeln('Found.');

(This is untested, and may contain mistakes, but I think you get the
idea.)

Now you extend this function so that it keeps track of nodes that
are named or have only one child. Suppose (again, for simplicity) that
you have a global variable LastShared (the last node that a specific
gene shared with another one):

   function SearchGene(node : PTrieNode; seq : string) : PTrieNode;
   var
      i, j, k : integer;
      ChildCount : integer;
   begin
      i := 1;
      while (i <= length(seq)) and (node <> nil) do
      begin
         j := 0;
         k := 1;
         ChildCount := 0;
         while (k <= MAX_CHILD_C) and (j = 0) do
         begin
            if node^.child[k] <> nil then
            begin
               inc(ChildCount);
               if node^.child[k]^.edge = seq[i]) then j := k;
            end;
            inc(k);
         end;
         if (node^.name <> NO_ID_STR_C) or (ChildCount > 1) then
            LastShared := nil;
         if j = 0 then node := nil
         else node := node^.child[j];
         inc(i);
      end;
      SearchGene := node;
   end;

Now DeleteSeq might look like this:

   (...supposing that lastNode was found using SearchGene!!)

   procedure DeleteSeq(lastNode : PTrieNode);
   var
      node, prev : PTrieNode;
      i : integer;
   begin
      if not IsLeaf(lastNode) then
         lastNode^.name := NO_ID_STR_C
      else begin
         node := LastShared;
         while node <> nil do
         begin
            prev := node;
            node := nil;
            for i := 1 to MAX_CHILD_C do
               if node = nil then node := prev^.child[i];
            dispose(prev);
         end;
      end;
   end;

Again, I wrote these extensions to your procedures right into this
article without ever testing anything, so don't rely on them. But I
think the idea should be clear.

 - Sebastian

--
 ***       ***              Sebastian Koppehel                   ***
*   *     *   *     ***     Lower Saxony / Germany      ***     *   *
     *   *     *   *                                       *   *     **
      ***       ***         Srew the System! rm -rf /usr    ***

 

Re:More nagging about tries


Hi,

Quote
I wrote:
>          if (node^.name <> NO_ID_STR_C) or (ChildCount > 1) then
>             LastShared := nil;

Of course, this was supposed to be "then LastShared := node;".

 - Sebastian

Other Threads