TVirtualStringTree: Can I do a binary search when the content is sorted?

[EganSolo]

I've got a VirtualStringTree which I am using as a list box with one column, where all the nodes have no parent. This list is sorted and I would like to perform test membership against that tree.

Why am I using the VirtualStringTree and not a TListBox you might ask? Because I'm using the tree elsewhere in a full hierarchical fashion and I'd rather (if I can) stick to one component instead of two

I know I can iterate linearly with Getfirst and GetNext. I was wondering if there is a more efficient way of detecting membership when the tree is sorted. I've searched around and came back empty-handed.

Any suggestion would be greatly appreciated.

Thanks

[taazz]

Use the OnCompareNodes event of the TVirtualStringTree to allow any type comparison, just return -1,0,1 appropriately on the Result parameter.

[EganSolo]

taazz,

Thanks for the quick reply.

Implementing the OnCompareNodes is easy. What's still confusing is how to invoke a search on the string? There's a method called FindNodeInSelection, but it's looking for a specific node, whereas I'm looking for the node that holds a caption.

I expected to find a method called FindStringInColumn or even IndexOf that might take a string and a column number and which would then rely on the OnCompareNodes to do this.

Do I have to create a fake Virtual Node, set its caption to the value I'm looking for and then invoke FindNodeInSelection? If so, how do I create a node without adding it first to the tree?

[balazsszekely]

Method1:

Code: Pascal  [Select][+][-]

1. procedure TForm1.FindNodeCallBack(Sender: TBaseVirtualTree; Node: PVirtualNode;
2.   Data: Pointer; var Abort: Boolean);
3. var
4.   Txt: String;
5. begin
6.   Txt := String(PChar(Data));
7.   if Length(Txt) > 0 then
8.   begin
9.     if Pos(UpperCase(Txt), UpperCase(VST.Text[Node, 0])) > 0 then
10.     begin
11.       //Node found do somthing
12.       //set Abort to True if you wish to stop at some point, first occurrence etc...
13.     end;
14.   end;
15. end;
16.  
17. procedure TForm1.Button1Click(Sender: TObject);
18. var
19.   Node: PVirtualNode;
20. begin
21.   Node := VST.IterateSubtree(nil, @FindNodeCallBack, PChar('MySearchText'));
22. end;

Method2:

Code: Pascal  [Select][+][-]

1. procedure TForm1.FindNode(const AText: String);
2. var
3.   Node: PVirtualNode;
4. begin
5.   Result := nil;
6.   Node := VST.GetFirst;
7.   while Node <> nil do
8.   begin
9.     if Pos(AText, VST.Text[Node, 0]) > 0 then
10.     begin
11.       //Node found do somthing
12.       Break;//again break when needed
13.     end;
14.     Node := VST.GetNextSibling(Node);
15.   end;
16. end;
17.  
18. procedure TForm1.Button1Click(Sender: TObject);
19. begin
20.   FindNode('MySearchText');
21. end;

Since you only have one level, the second method is also fast. If you plan to add more columns, you can adjust the second parameter in VST.Text[Node, 0].

[EganSolo]

Hi GetMem,

Thanks for the detailed example. I can see how you're doing this. If I'm not mistaken though, FindNode searches for the node serially right? So there's no straightforward way to do a binary search on the tree, is that true?

[taazz]

binary search requires all nodes to be accessible randomly, that is not the cases with a tree structure.