* * *

Author Topic: TVirtualStringTree: Can I do a binary search when the content is sorted?  (Read 1206 times)

EganSolo

  • Full Member
  • ***
  • Posts: 135
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

  • Hero Member
  • *****
  • Posts: 5336
Use the OnCompareNodes event of the TVirtualStringTree to allow any type comparison, just return -1,0,1 appropriately on the Result parameter.
Good judgement is the result of experience … Experience is the result of bad judgement.

OS : Windows 7 64 bit
Laz: Lazarus 1.4.4 FPC 2.6.4 i386-win32-win32/win64

EganSolo

  • Full Member
  • ***
  • Posts: 135
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?



GetMem

  • Hero Member
  • *****
  • Posts: 3186
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].
« Last Edit: April 09, 2018, 06:36:21 pm by GetMem »

EganSolo

  • Full Member
  • ***
  • Posts: 135
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

  • Hero Member
  • *****
  • Posts: 5336
binary search requires all nodes to be accessible randomly, that is not the cases with a tree structure.
Good judgement is the result of experience … Experience is the result of bad judgement.

OS : Windows 7 64 bit
Laz: Lazarus 1.4.4 FPC 2.6.4 i386-win32-win32/win64

 

Recent

Get Lazarus at SourceForge.net. Fast, secure and Free Open Source software downloads Open Hub project report for Lazarus