TreeView node to full path

[mark_c]

hello, i would like to convert all nodes of a treeview in the full path, how is it possible?

thank you

Code: Select all

void __fastcall TForm1::Button1Click(TObject *Sender)
{
        ListBox1->Clear();
        TTreeNode *CurItem = TreeView1->Selected; // from the selected item to last

        AnsiString path;

        while(CurItem)
        {
                if(CurItem->Level==0)
                        path="c:\\MYDIR";
                else
                        path+="\\"+CurItem->Text;
                ListBox1->Items->Add(path);
                CurItem = CurItem->GetNext();
        }
}


INPUT

Code: Select all

DIR_1
   DIR_2
      DIR_3
         DIR_4
            DIR_5
               DIR_6
               DIR_7
            DIR_8
               DIR_9
               DIR_10
               DIR_11
               DIR_12
               DIR_13


OUTPUT WRONG

Code: Select all

c:\MYDIR\DIR_1
c:\MYDIR\DIR_1\DIR_2
c:\MYDIR\DIR_1\DIR_2\DIR_3
c:\MYDIR\DIR_1\DIR_2\DIR_3\DIR_4
c:\MYDIR\DIR_1\DIR_2\DIR_3\DIR_4\DIR_5
c:\MYDIR\DIR_1\DIR_2\DIR_3\DIR_4\DIR_5\DIR_6
c:\MYDIR\DIR_1\DIR_2\DIR_3\DIR_4\DIR_5\DIR_6\DIR_7
c:\MYDIR\DIR_1\DIR_2\DIR_3\DIR_4\DIR_5\DIR_6\DIR_7\DIR_8
c:\MYDIR\DIR_1\DIR_2\DIR_3\DIR_4\DIR_5\DIR_6\DIR_7\DIR_8\DIR_9
c:\MYDIR\DIR_1\DIR_2\DIR_3\DIR_4\DIR_5\DIR_6\DIR_7\DIR_8\DIR_9\DIR_10
c:\MYDIR\DIR_1\DIR_2\DIR_3\DIR_4\DIR_5\DIR_6\DIR_7\DIR_8\DIR_9\DIR_10\DIR_11
c:\MYDIR\DIR_1\DIR_2\DIR_3\DIR_4\DIR_5\DIR_6\DIR_7\DIR_8\DIR_9\DIR_10\DIR_11\DIR_12
c:\MYDIR\DIR_1\DIR_2\DIR_3\DIR_4\DIR_5\DIR_6\DIR_7\DIR_8\DIR_9\DIR_10\DIR_11\DIR_12\DIR_13


OUTPUT CORRECT

Code: Select all

c:\TEMP\CREA_RDO
c:\TEMP\CREA_RDO\DIR_2
c:\TEMP\CREA_RDO\DIR_2\DIR_3
c:\TEMP\CREA_RDO\DIR_2\DIR_3\DIR_4
c:\TEMP\CREA_RDO\DIR_2\DIR_3\DIR_4\DIR_5
c:\TEMP\CREA_RDO\DIR_2\DIR_3\DIR_4\DIR_5\DIR_6
c:\TEMP\CREA_RDO\DIR_2\DIR_3\DIR_4\DIR_5\DIR_6\DIR_7
c:\TEMP\CREA_RDO\DIR_2\DIR_3\DIR_4\DIR_5\DIR_8
c:\TEMP\CREA_RDO\DIR_2\DIR_3\DIR_4\DIR_5\DIR_8\DIR_9
c:\TEMP\CREA_RDO\DIR_2\DIR_3\DIR_4\DIR_5\DIR_8\DIR_9\DIR_10
c:\TEMP\CREA_RDO\DIR_2\DIR_3\DIR_4\DIR_5\DIR_8\DIR_9\DIR_10\DIR_11
c:\TEMP\CREA_RDO\DIR_2\DIR_3\DIR_4\DIR_5\DIR_8\DIR_9\DIR_10\DIR_11\DIR_12
c:\TEMP\CREA_RDO\DIR_2\DIR_3\DIR_4\DIR_5\DIR_8\DIR_9\DIR_10\DIR_11\DIR_12\DIR_13


[mark_c]

solved with this code by (Fred Caillea) http://www.delphigroups.info/2/81/325693.html

Code: Select all

AnsiString __fastcall AddSlash(const AnsiString S1, const AnsiString S2)
 {
    AnsiString retStr;
    if (*AnsiLastChar(S1) != '\\')
       retStr = S1 + '\\' + S2;
    else
       retStr = S1 + S2;
    return retStr;
}


/*---------------------------------------------------------------------*/
 AnsiString __fastcall GetNodePath(TTreeNode* Node)
 {
    AnsiString retStr;
    if (Node)
    {
       TTreeNode* p = Node->Parent;
       retStr = Node->Text;
       while (p)
       {
          retStr = AddSlash(p->Text, retStr);
          p = p->Parent;
       }
    }
    return retStr;


}


[rlebeau]

hello, i would like to convert all nodes of a treeview in the full path, how is it possible?

Try something like this:

Code: Select all

#include <SysUtils.hpp>

String __fastcall GetNodePath(TTreeNode *Node)
{
    String path;
    TTreeNode *Parent = Node->Parent;
    if (Parent)
        path = GetNodePath(Parent);
    else
        path = "c:\\MYDIR\\";
    return IncludeTrailingPathDelimiter(path) + Node->Text;
}

void __fastcall TForm1::Button1Click(TObject *Sender)
{
    ListBox1->Items->BeginUpdate();
    try
    {
        ListBox1->Clear();
        TTreeNode *CurItem = TreeView1->Selected; // from the selected item to last
        while (CurItem)
        {
            ListBox1->Items->Add(GetNodePath(path));
            CurItem = CurItem->GetNext();
        }
    }
    __finally
    {
        ListBox1->Items->EndUpdate();
    }
}


[mark_c]

thank you rlebeau

[mark_c]

this is an alternative to the previous code; what I do not explain is because the final path is reversed.

this is what I expect
C:\mypath\dir1\dir2\dir3

but that's what I get
C:\mypath\dir3\dir2\dir1

I think it's due to how the binary tree is visited, how do I fix it?

thank you

Code: Select all

        ListBox1->Clear();
        AnsiString s, path="C:\\mypath\\";
        TTreeNode *Node = TreeView1->Items->GetFirstNode();

        while(Node)
        {
                if(Node)
                {
                        TTreeNode* p = Node->Parent;
                        s = Node->Text;

                        while(p)
                        {
                                s+= "\\" + p->Text;
                                p = p->Parent;
                        }
                }
                ListBox1->Items->Add(path+s);
                Node = Node->GetNext();
                s="";
        }
}


[rlebeau]

I think it's due to how the binary tree is visited, how do I fix it?

You are iterating a given Node's parents in backward order from leaf up to root. You are appending each parent's text to the *end* of the path string, which is what you should do when iterating forward. But when iterating backward, you need to prepend the text to the *front* of the string instead.

Change this line:

Code: Select all

s+= "\\" + p->Text;


To this:

Code: Select all

s = p->Text + "\\" + s;


[mark_c]

thank you again rlebeau

[mark_c]

in the last version of the code, there are two nested cycles (while) and mean that we are in the presence of an algorithm with a O (n ^ 2) complexity.

In the first version, however, a main function that contains a loop (while), call another function wich contain another loop (while), I think that also this version is an O (n ^ 2) complexity.

If I use as input a number of directories that build 1 million paths, I get it as the final run time: 17 minutes for the first version, and 30 minutes for the second, is it due to compiler optimizations?

thank you Mark

[rlebeau]

If I use as input a number of directories that build 1 million paths, I get it as the final run time: 17 minutes for the first version, and 30 minutes for the second, is it due to compiler optimizations?

No, it is simply because your looping code is very inefficient in general.

First off, make sure to call ListBox1->Items->BeginUpdate() to disable screen updated on every call to Add(), and then call ListBox1->Items->EndUpdate() when done. Or, add the strings to a separate TStringList first, then assign that to the TListBox when done.

But more importantly, you are using a GetFirst/GetNext loop to iterate through every node in the tree from top to bottom without regard to any branching, so you end up generating related paths multiple times instead of caching and reusing them. For example, lets look at your first 3 nodes:

Code: Select all

DIR_1
   DIR_2
      DIR_3


Code: Select all

c:\MYDIR\DIR_1
c:\MYDIR\DIR_1\DIR_2
c:\MYDIR\DIR_1\DIR_2\DIR_3


On the first node, you generate "c:\MYDIR\DIR_1".

On the next node, you re-generate "c:\MYDIR\DIR_1" again, even though you already generated it once before, and then append "DIR_2" to it.

On the next node, you re-generate "c:\MYDIR\DIR_1\DIR_2" (and thus "c:\MYDIR\DIR_1") again, even though you already generated them before, and then append "DIR_3" to it.

And so on. The deeper you go down the tree, the more repetition you have. You re-generate the same strings over and over, which requires looping over the same nodes over and over.

A recursive Parent/Child loop would eliminate those duplicate generations, by eliminating any need to loop backwards through the parent chains at all. For example:

Code: Select all

void AddNodeToList(const AnsiString &BasePath, TTreeNode *Node, TStrings *List)
{
    String path = IncludeTrailingPathDelimiter(BasePath) + Node->Text;
    List->Add(path);
    TTreeNode *child = Node->getFirstChild();
    while (child)
    {
        AddNodeToList(path, child, List);
        child = child->getNextSibling();
    }
}
[code]

Then you can do this:

[code]
ListBox1->Items->BeginUpdate();
try
{
    ListBox1->Clear();
    AnsiString path = "C:\\mypath\\";
    TTreeNode *Node = TreeView1->Items->GetFirstNode();
    while (Node)
    {
        AddNodeToList(path, Node, ListBox->Items);
        Node = Node->getNextSibling();
    }
}
__finally
{
    ListBox1->Items->EndUpdate();
}
[/code]

Or this:

[code]
TStringList *List - new TStringList;
try
{
    AnsiString path = "C:\\mypath\\";
    TTreeNode *Node = TreeView1->Items->GetFirstNode();
    while (Node)
    {
        AddNodeToList(path, Node, List);
        Node = Node->getNextSibling();
    }
    ListBox1->Items->Assign(List);
}
__finally
{
    delete List;
}


[mark_c]

thnak you

this version is similar to yours, I think, the final time is now 22 minutes instead of the previous 30 minutes: Do you agree or have I made a mistake?

Code: Select all

void __fastcall TForm1::Button3Click(TObject *Sender)
{
        ListBox1->Clear();
        ListBox1->Items->BeginUpdate();
        TTreeNode *CurItem = TreeView1->Items->GetFirstNode();

        int t_start=GetTickCount();

        while(CurItem)
        {
                if(CurItem->Level == 0)
                        AddNodeToList("C:\\MYPATH\\", CurItem);
                CurItem = CurItem->GetNext();
        }

        ListBox1->Items->EndUpdate();

        Label1->Caption = GetTickCount()-t_start;
        Label2->Caption = ListBox1->Items->Count;
}
//---------------------------------------------------------------------------

void AddNodeToList(const AnsiString &BasePath, TTreeNode *Node)
{
        String path = IncludeTrailingPathDelimiter(BasePath) + Node->Text;

        Form1->ListBox1->Items->Add(path);

        TTreeNode *child = Node->getFirstChild();

        while(child)
        {
                AddNodeToList(path, child);
                child = child->getNextSibling();
        }
}
//---------------------------------------------------------------------------

[rlebeau]

this version is similar to yours, I think, the final time is now 22 minutes instead of the previous 30 minutes: Do you agree or have I made a mistake?

The Level property calculates its value dynamically by enumerating parent nodes:

Code: Select all

function TTreeNode.GetLevel: Integer;
var
  Node: TTreeNode;
begin
  Result := 0;
  Node := Parent;
  while Node <> nil do
  begin
    Inc(Result);
    Node := Node.Parent;
  end;
end;


Couple that with your use of TTreeNode::GetNext() to touch ALL nodes in the Tree, you are not gaining any performance benefits, not to mention you are back to accessing the same nodes multiple times (since AddNodeToList() already touches child nodes, and then you touch them again in your own loop).

Since your Button event is only adding Level 0 nodes to the ListBox, there is no reason to use TTreeNode::GetNext() to touch any nodes at levels 1 and higher. Use TTreeNode::GetNextSibling() instead to enumerate only the nodes at Level 0, like I showed earlier:

Code: Select all

void __fastcall TForm1::Button3Click(TObject *Sender)
{
    DWORD t_start, t_end;

    ListBox1->Clear();
    ListBox1->Items->BeginUpdate();
    try
    {
        t_start = GetTickCount();
        TTreeNode *CurItem = TreeView1->Items->GetFirstNode();
        while (CurItem)
        {
            AddNodeToList("C:\\MYPATH\\", CurItem);
            CurItem = CurItem->GetNextSibling();
        }
        t_end = GetTickCount();
    }
    __finally
    {
        ListBox1->Items->EndUpdate();
    }

    Label1->Caption = t_end - t_start;
    Label2->Caption = ListBox1->Items->Count;
}


That should be significantly faster than your GetNext() loop.

That being said, TTreeView is not really intended to be used for such large numbers of nodes that you are working with. You might consider switching to a Virtual TreeView instead.

[mark_c]

thank you again

is it fair to think that, a TreeView generates a strongly unbalanced tree?

[rlebeau]

is it fair to think that, a TreeView generates a strongly unbalanced tree?

I don't know what that means.

[mark_c]

here is an example http://blogs.perl.org/users/ovid/2013/0 ... ained.html

[rlebeau]

here is an example http://blogs.perl.org/users/ovid/2013/0 ... ained.html

Balance applies to binary trees. TTreeView is not a binary tree, as it doesn't satisfy the "each node has, at most, two children" requirement. A TTreeNode can have many many children.