VirtualTreeview: when to sort children?

Question

Hi all, I depend on VirtualTreeView to display thousands of items which are bound to change occasionally and when this happens the tree is cleaned and populated again.

Sorting is done automatically (toAutoSort flag set) but this has an unwanted effect of initializing all the nodes recursively and this is a very expensive operation as you can imagine.

So when should I call the .Sort method when toAutoSort is off? (DoInitChildren looked plausible but I got weird results like reversed results occasionaly so I assume that's no good event to sort the children.)

Answer 1

The general rule in this sort of scenario is to sort after all the new items have been added. That way you only sort (and initialize) once.

Answer 2

Unless the entire tree is completely different every time, you can get better performance by not clearing the tree, but by separately building a new list of items (just identification of the items), sorting that list, then walking both trees in order... the general algorithm looks something like this (the left list is the "new list" and the right list is the "existing list"):

LeftCur := 0;
RightCur := 0;
while (LeftCur < TotalLeft) and (RightCur < TotalRight) then
  begin
    if LeftList[LeftCur] = RightList[RightCur] then
      begin
        // matches, so just advance 
        Inc(LeftCur);
        Inc(RightCur);            
      end
    else if LeftList[LeftCur] < RightList[RightCur] then
      begin
        // insert happens BEFORE RightCur
        InsertLeftItemToRight;
        Inc(RightCur);
        Inc(TotalRight);
      end
    else if LeftList[LeftCur] > RightList[RightCur] then
      begin
        DeleteRightItem;
        Dec(TotalRight);
      end;
  end;
  While RightCur < TotalRight do
    begin
      DeleteRightItem;
      Dec(TotalRight);
    end;
  While LeftCur < TotalLeft do
    AppendLeftItemToRight;

This way the list remains sorted, and you only have to complete loading an item in the InsertLeftItemToRight steps. In a tree, whenever you match, you run a similar routine for the children. This concept is weighted against the fact that items in the existing list are not going to change much or may be expensive to fully load.