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

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. — Rob Kennedy, Jan 15 '11 at 00:08
@Rob - Yes, but it was easier to say Text. I store my stuff in records, like everyone else ;) — Jeff, Jan 15 '11 at 16:08
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.) — Rob Kennedy, Jan 15 '11 at 19:54
@Rob - I am not sure of how I would do that. The way shown was the way I was taught how it worked. — Jeff, Jan 15 '11 at 19:56
@Rob @Jeff 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. — David Heffernan, Jan 16 '11 at 19:01

score 1 · Answer 1 · answered Jan 14 '11 at 23:16

1

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.

answered Jan 14 '11 at 23:16

David Heffernan

601,492
42
1,072
1,490

@deltics I don't think there is much hierarchy based on previous questions. How would you do it? – David Heffernan Jan 14 '11 at 23:44
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. – Deltics Jan 14 '11 at 23:52
@Deltics - I use VT solely for the speed. But yes, there is 2 levels of nodes (0 and 1) – Jeff Jan 15 '11 at 11:43

score 1 · Answer 2 · answered Jan 14 '11 at 23:25

1

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.

answered Jan 14 '11 at 23:25

Mason Wheeler

82,511
50
270
477

1

or even the newly minted standalone Collections – David Heffernan Jan 14 '11 at 23:31

score 1 · Accepted Answer · answered Jan 14 '11 at 23:49

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;

Wrote some working code based on this example, thank you, works like a charm! Why didn't I think of that?! :P — Jeff, Jan 15 '11 at 16:01

Delphi VirtualStringTree - Check for Duplicates?

3 Answers3

Linked