Delphi VirtualStringTree - Check for Duplicates?

Question

Yeah, I know I post a lot of questions, but thats because I either need assurance that I am doing it right, what I am doing wrong, or if I am totally clueless, and cant find anything in the documentation. Anyways,

I am trying to check for duplicate nodes. Here is how I would want to do it:

Loop thru my nodes, and compare each single node's text (record), but if I got many nodes, wouldnt that be too time and memory consuming? Would there be a better approach for this?

Thanks! - Jeff.

EDIT: Thanks to Deltics, I got it working! In case we have some people with the same question, here is some working code, using 2 levels of nodes in VST!

Procedure UncheckDuplicates;
Var
 ParentNode,ChildNode : PVirtualNode;
 I,J                  : Integer;
 SL                   : TStringList;
 SkypeID              : String;
Begin

   SL := TStringlist.Create;
   try
        ParentNode                      := frmMain.vtSkype.GetFirst;

           for I := 0 to frmMain.vtSkype.RootNodeCount - 1 do
             begin
               ChildNode                := ParentNode.FirstChild;
                 for J := 0 to ParentNode.ChildCount - 1 do
                     begin
                        if NodeIsChecked(ChildNode) then
                          begin
                            SkypeID             := GetData(ChildNode).SkypeID;
                              if SL.IndexOf(SkypeID) <> -1 then
                                begin
                                  ChildNode.CheckState          := csUncheckedNormal;
                                end
                                else 
                                begin
                                  SL.Add(SkypeID);
                                end;
                          end;                          
                     ChildNode                := ChildNode.NextSibling;   
                     end;


               ParentNode               := ParentNode.NextSibling;
             end;


   finally
     SL.Free;
   end;

frmMain.vtSkype.Refresh;


End;

I am not afraid to share my code, I owe it to the community. :)

Incantation

If you're checking nodes' text, you're doing it wrong. Look for duplicates in your underlying data structure. Once you've eliminated the duplicates there, then set RootNodeCount or ChildCount to make the control create nodes for all your items. The tree control should not be where you store your program's data. It's just a view of the data. – Ingamar

@Rob - Yes, but it was easier to say Text. I store my stuff in records, like everyone else ;) – Incantation

According to your code, you store your stuff in the tree-view control. The idea is that you should have a completely separate data structure that you can manipulate and explore without being tied to the tree control. You shouldn't have to reference PVirtualNode at all. (And besides that, you should really use the GetNextSibling method instead of directly reading the NextSibling field; the method ensures the node you get has been properly initialized.) – Ingamar

@Rob - I am not sure of how I would do that. The way shown was the way I was taught how it worked. – Incantation

@Rob @Incantation Rob is right, but doing it the "right" way is more complex. When you come to need to work with your model without any UI, i.e. without a tree view, then you'll understand why Rob said this. But until then I don't think you need to worry too much. – Senate

Answer 1

It depends at what point you are checking for duplicates.

If it is at the point at which you are adding items and you are adding all items at the same time, (or if it is possible/appropriate to move you duplicate check to point at which the treeview is populated, rather than working with an already populated tree) then maintaining a list of already added items as you go could be the simplest way, e.g. assuming you are adding items from a simple stringlist (in strings in this illustration code):

  alreadyAdded := TStringList.Create;
  try
    alreadyAdded.Sorted := TRUE;  // Sorting ensures an efficient binary lookup for IndexOf()...

    for i := 0 to Pred(strings.count) do
    begin
      if alreadyAdded.IndexOf(strings[i]) <> -1 then
        CONTINUE;

      AddNode(strings[i]);
      alreadyAdded.Add(strings[i]);
    end;
  finally
    alreadyAdded.Free;
  end;

Fore

Wrote some working code based on this example, thank you, works like a charm! Why didn't I think of that?! :P – Incantation

Answer 2

Normally you'd collect all your strings into a list and then sort it. You can then loop through and check adjacent items for equality.

That's O(n log n) assuming a reasonable sort algorithm as opposed to the naive algorithm which is O(n^2). If you don't have loads of items then the naive will work perfectly well though.

Senate

@deltics I don't think there is much hierarchy based on previous questions. How would you do it? – Senate

See my answer - decided my comment to your comment wasn't much help. I haven't look at "previous questions" (presumably from the same poster?) but on the strength of this question alone, the simple fact that a treeview is involved, rather than a listbox or listview etc, strongly suggests the presence of hierarchy. – Fore

@Fore - I use VT solely for the speed. But yes, there is 2 levels of nodes (0 and 1) – Incantation

Answer 3

David's version will work. If you have D2010 or later, you could also use a Set collection from DeHL, which uses a hash to check for duplicates and can process your list in O(n) time.

Adequacy

or even the newly minted standalone Collections – Senate