For years I've been populating treeviews from self referencing tables (eg ID & LinkToID) using simple recursive functions - essentially populating a branch at a time. Since generally the tables involved were small (think email mailboxes) it worked fast enough.

I now have a case where I have c10k nodes to populate and using the recursive approach it was taking c12 seconds which was not acceptable. My new approach takes less than 1/2 second. It can only work where the table has a numeric ID.

I'm "lucky" in that my table starts at 1 otherwise I'd have to adjust the code so not to many nodes were created initially.


procedure TForm1.Button1Click(Sender: TObject);
var
Cntr: integer;
MaxItems: integer;
Node: TELTreeItem;
begin
ToC.Items.BeginUpdate;
Manual.Open;
MaxItems := Manual.RecordCount - 1;
for Cntr := 0 to MaxItems do ToC.Items.Add(nil, IntToStr(Cntr));
while not Manual.Eof do begin
 Node := ToC.Items[Manual_ID.AsInteger - 1];
 Node.Text := Manual_Title.AsString;
 if not Manual_Link.IsNull then Node.Parent := ToC.Items[Manual_Link.AsInteger - 1];
 Node.Tag := Manual_ID.AsInteger;
 Manual.Next;
end;
for Cntr := MaxItems downto 0 do begin
 if ToC.Items[Cntr].Text = '' then ToC.Items.Delete(ToC.Items[Cntr]);
end;
ToC.Items.EndUpdate;
end;

The initial creating the nodes takes c70 ms, setting the data takes c400 ms.

As always any suggestions on how to improve it would be welcome.

Opening the table exclusive did help (overall time down to c300ms) but its not something I can do in a multi user environment.

Roy Lambert

Roy

> For years I've been populating treeviews from self referencing tables (eg ID & LinkToID) using simple recursive
functions - essentially populating a branch at a time. Since generally the tables involved were small (think email
mailboxes) it worked fast enough.
>
> I now have a case where I have c10k nodes to populate and using the recursive approach it was taking c12 seconds which
was not acceptable. My new approach takes less than 1/2 second. It can only work where the table has a numeric ID.
>

12 seconds down to <  0.5, you are just being greedy!   Seriously though how many of the items have a parent (ie need to
be moved) ?.  If it's a high percentage then the TELtree (?) treeview seems very quick at moving nodes.

Am I right in thinking that if you ever delete records the procedure could blow up with range errors?

John

John


ElTreeLite (and I presume heavy work in a different way to a standard TTreeView. Exactly how different I don't know but to give an example with a standard treeview I can't set the parent, I have to add children.

How many items have a parent? All but the top four! That makes it c9,500

Without spending time trying to understand someone else's code I'm guessing that the nodes aren't actually moved and that its a paint thing. The parent is simple a TElTreeItem and the item list remains the same, in the same order.

<<Am I right in thinking that if you ever delete records the procedure could blow up with range errors?>>

I suddenly thought about that. Well really after building for the 8th time and realising it was getting longer and there were a lot of blank nodes I switched to a query.......

procedure TnlhOLMVForm.InitialBuildTree(const CatDir, ShowWhichBooks: string);
var
Cntr: integer;
FirstID: integer;
LastID: integer;
MaxItems: integer;
Node: TELTreeItem;
Qry: TEDBQuery;
sl: TStringList;
begin
olmSession.LocalConfigPath := CatDir;
ToC.Items.Clear;
Qry := TEDBQuery.Create(nil);
Qry.SessionName := 'olm';
Qry.DatabaseName := 'olm';
Qry.SQL.Text := 'SELECT MIN(_ID), MAX(_ID) FROM Contents';
Qry.ExecSQL;
FirstID := Qry.Fields[0].AsInteger;
LastID := Qry.Fields[1].AsInteger;
MaxItems := (LastID - FirstID) + 10;
Qry.Close;
Qry.SQL.Text := 'SELECT _ID, (_ID-' + IntToStr(FirstID) + ') AS ID, (_Link-' + IntToSTr(FirstID) + ') AS LINK, _Title FROM Contents';
if ShowWhichBooks <> '' then begin
 if 0 = Pos(',', ShowWhichBooks) then begin
  Qry.SQL.Text := Qry.SQL.Text + ' WHERE _Book = ' + QuotedStr(Trim(ShowWhichBooks));
 end else begin
  sl := TStringList.Create;
  sl.CommaText := ShowWhichBooks;
  Qry.SQL.Text := Qry.SQL.Text + ' WHERE ';
  for Cntr := 0 to sl.Count - 1 do begin
   Qry.SQL.Text := Qry.SQL.Text + '_Book = ' + QuotedStr(Trim(sl[Cntr]));
   if Cntr <> sl.Count - 1 then Qry.SQL.Text := Qry.SQL.Text + ' OR ';
  end;
  sl.Free;
 end;
end;
Qry.ExecSQL;
ToC.Items.BeginUpdate;
for Cntr := 0 to MaxItems do ToC.Items.Add(nil, '');
while not Qry.Eof do begin
 Node := ToC.Items[Qry.Fields[1].AsInteger];
 Node.Text := Qry.Fields[3].AsString;
 if not Qry.Fields[2].IsNull then Node.Parent := ToC.Items[Qry.Fields[2].AsInteger];
 Node.Tag := Qry.Fields[0].AsInteger;
 Qry.Next;
end;
for Cntr := MaxItems downto 0 do begin
 if ToC.Items[Cntr].Text = '' then ToC.Items.Delete(ToC.Items[Cntr]);
end;
ToC.Items.EndUpdate;
Qry.Close;
Qry.Free;
end;

Roy Lambert

Roy,

<< For years I've been populating treeviews from self referencing tables (eg
ID & LinkToID) using simple recursive functions - essentially populating a
branch at a time. Since generally the tables involved were small (think
email mailboxes) it worked fast enough.

I now have a case where I have c10k nodes to populate and using the
recursive approach it was taking c12 seconds which was not acceptable. My
new approach takes less than 1/2 second. It can only work where the table
has a numeric ID. >>

Are you trying to populate the entire treeview in one shot ?  I know you're
saying "populating a branch at a time", but it also seems like you're doing
the whole thing, based upon your code.

If you are trying to populate the entire tree, then I wouldn't do so.
Instead, populate only the current level that is visible, and use the Expand
events of the treeview to populate the children on-demand.

--
Tim Young
Elevate Software
www.elevatesoft.com

Tim

>If you are trying to populate the entire tree, then I wouldn't do so.
>Instead, populate only the current level that is visible, and use the Expand
>events of the treeview to populate the children on-demand.

That was my first thought. Its for my on-line user editable manual. So I thought figure out which component the mouse was over, look that up in the database and display back up the tree. I discarded it because only if a node has children attached does the expand/collapse button appear. This means that you have to click on a node to find out if children exist. Until you do there's no indication and I think a lot of people (apart from the click anything and everything brigade) will think that's the end of it.

Currently I'm thinking of moving to a different approach using TAdvExplorerTreeView (if I can figure out how to - TMS documentation must have improved since my licence lapsed)

Roy Lambert

Roy,

<< That was my first thought. Its for my on-line user editable manual. So I
thought figure out which component the mouse was over, look that up in the
database and display back up the tree. I discarded it because only if a node
has children attached does the expand/collapse button appear. This means
that you have to click on a node to find out if children exist. Until you do
there's no indication and I think a lot of people (apart from the click
anything and everything brigade) will think that's the end of it. >>

You can set the TTreeNode.HasChildren property to indicate whether there are
any children or not without actually populating them, and you can get the
count of the children very fast for the current node level.  None of this
involves actually populating the nodes, which is the time-consuming part.

--
Tim Young
Elevate Software
www.elevatesoft.com

Tim

>You can set the TTreeNode.HasChildren property to indicate whether there are
>any children or not without actually populating them, and you can get the
>count of the children very fast for the current node level. None of this
>involves actually populating the nodes, which is the time-consuming part.

That's roughly what I was doing (TElTreeLite is a bit different).

Going down the tree is great - just display the various "books" (4 of them) roughly 47ms.

Going UP the tree is a fraction more difficult I decided that from a given start point I wanted to display the selected nodes siblings, its parents and all books. All parents and books get an expand/collapse button unconditionally. Siblings and selected node would be tested for children. I'm still trying to figure out an efficient way to build the tree going upwards. All the functionality seems to be AddChild and none AddParent

Roy Lambert

Tim


Building a tree upwards is bad enough but it pales into insignificance with the extra coding involved to handle a second press of F1 in the app without the on-line manual having been closed and freed. So I decided I could just wipe and rebuild each time its fast enough at 40ms.

Now the fun really starts. I need a three state button - expand, collapse, show the bits that haven't been loaded yet

I think I'll stick with populating the whole tree (depending on speed trials over my wireless connection to my LAN)


Roy Lambert

Roy,

<< Going UP the tree is a fraction more difficult I decided that from a
given start point I wanted to display the selected nodes siblings, its
parents and all books. All parents and books get an expand/collapse button
unconditionally. Siblings and selected node would be tested for children.
I'm still trying to figure out an efficient way to build the tree going
upwards. All the functionality seems to be AddChild and none AddParent
>>

Why would you need to go "up" ?  Isn't the only way to get where you are
currently is to go down through all of the levels ?

--
Tim Young
Elevate Software
www.elevatesoft.com

Tim

>Why would you need to go "up" ? Isn't the only way to get where you are
>currently is to go down through all of the levels ?

Only if you start at the top

This is for my on-line manual. So visualise some user pressing F1. I'm trapping that key and work out the component below the mouse cursor (subject to some restrictions eg it has to be a TWinControl descendant) and pass the component, form and app names over to the OLM sub system.

I'm still thinking about it but currently I'm going to allow help to be stored for container controls (eg panels, pagecontrols) rather than the ultimate control so I can have a tree which would go app-form-container..container-control.

So I start at the bottom and work my way up. I could locate the app node, then the form node but then if I want to go any further building downwards I'd have to build all branches until I hit the control I actually want.

I'm still working on how I want it to look but I'm leaning towards a crossover of hierarchical table of contents type and the current google type that MS seems to be using in their office products.

Roy Lambert