TreeView node to full path

This is the forum for miscellaneous technical/programming questions.

Moderator: 2ffat

TreeView node to full path

Postby mark_c » Tue Oct 24, 2017 1:44 am

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
BCBJ Veteran
BCBJ Veteran
 
Posts: 86
Joined: Thu Jun 21, 2012 1:13 am

Re: TreeView node to full path

Postby mark_c » Tue Oct 24, 2017 8:43 am

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;


}
mark_c
BCBJ Veteran
BCBJ Veteran
 
Posts: 86
Joined: Thu Jun 21, 2012 1:13 am

Re: TreeView node to full path

Postby rlebeau » Tue Oct 24, 2017 10:41 am

mark_c wrote: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();
    }
}
Remy Lebeau (TeamB)
Lebeau Software
User avatar
rlebeau
BCBJ Author
BCBJ Author
 
Posts: 1457
Joined: Wed Jun 01, 2005 3:21 am
Location: California, USA

Re: TreeView node to full path

Postby mark_c » Tue Oct 24, 2017 11:45 am

thank you rlebeau
mark_c
BCBJ Veteran
BCBJ Veteran
 
Posts: 86
Joined: Thu Jun 21, 2012 1:13 am

Re: TreeView node to full path

Postby mark_c » Fri Oct 27, 2017 11:42 am

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="";
        }
}
mark_c
BCBJ Veteran
BCBJ Veteran
 
Posts: 86
Joined: Thu Jun 21, 2012 1:13 am

Re: TreeView node to full path

Postby rlebeau » Fri Oct 27, 2017 1:32 pm

mark_c wrote: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;
Last edited by rlebeau on Mon Oct 30, 2017 1:16 pm, edited 1 time in total.
Remy Lebeau (TeamB)
Lebeau Software
User avatar
rlebeau
BCBJ Author
BCBJ Author
 
Posts: 1457
Joined: Wed Jun 01, 2005 3:21 am
Location: California, USA

Re: TreeView node to full path

Postby mark_c » Fri Oct 27, 2017 11:35 pm

thank you again rlebeau
mark_c
BCBJ Veteran
BCBJ Veteran
 
Posts: 86
Joined: Thu Jun 21, 2012 1:13 am

Re: TreeView node to full path

Postby mark_c » Wed Nov 01, 2017 10:56 am

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
mark_c
BCBJ Veteran
BCBJ Veteran
 
Posts: 86
Joined: Thu Jun 21, 2012 1:13 am

Re: TreeView node to full path

Postby rlebeau » Wed Nov 01, 2017 7:07 pm

mark_c wrote: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;
}
Remy Lebeau (TeamB)
Lebeau Software
User avatar
rlebeau
BCBJ Author
BCBJ Author
 
Posts: 1457
Joined: Wed Jun 01, 2005 3:21 am
Location: California, USA

Re: TreeView node to full path

Postby mark_c » Thu Nov 02, 2017 7:40 am

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();
        }
}
//---------------------------------------------------------------------------
mark_c
BCBJ Veteran
BCBJ Veteran
 
Posts: 86
Joined: Thu Jun 21, 2012 1:13 am

Re: TreeView node to full path

Postby rlebeau » Thu Nov 02, 2017 2:19 pm

mark_c wrote: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.
Remy Lebeau (TeamB)
Lebeau Software
User avatar
rlebeau
BCBJ Author
BCBJ Author
 
Posts: 1457
Joined: Wed Jun 01, 2005 3:21 am
Location: California, USA

Re: TreeView node to full path

Postby mark_c » Fri Nov 03, 2017 2:23 pm

thank you again

is it fair to think that, a TreeView generates a strongly unbalanced tree?
mark_c
BCBJ Veteran
BCBJ Veteran
 
Posts: 86
Joined: Thu Jun 21, 2012 1:13 am

Re: TreeView node to full path

Postby rlebeau » Fri Nov 03, 2017 3:43 pm

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


I don't know what that means.
Remy Lebeau (TeamB)
Lebeau Software
User avatar
rlebeau
BCBJ Author
BCBJ Author
 
Posts: 1457
Joined: Wed Jun 01, 2005 3:21 am
Location: California, USA

Re: TreeView node to full path

Postby mark_c » Sat Nov 04, 2017 12:36 am

mark_c
BCBJ Veteran
BCBJ Veteran
 
Posts: 86
Joined: Thu Jun 21, 2012 1:13 am

Re: TreeView node to full path

Postby rlebeau » Mon Nov 06, 2017 5:51 pm



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.
Remy Lebeau (TeamB)
Lebeau Software
User avatar
rlebeau
BCBJ Author
BCBJ Author
 
Posts: 1457
Joined: Wed Jun 01, 2005 3:21 am
Location: California, USA

Next

Return to Technical

Who is online

Users browsing this forum: Exabot [Bot] and 13 guests

cron