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. :)

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;

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.

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.