GSet

TSet

TSet provides a data structure that will store, sorted, your data using a Red / Black Tree. This approach is said to be a little faster when making many changes to the data in the tree compared to, for example, an AVL Tree.

The TSet (and several other data structures) were contributed to FPC in 2012 and appears to have had little attention since then. Documentation is scant, see below.

The idea with TSet (and many similar data 'frameworks') is that you provide a sorting function that is aware of the nature of your data and, as you add or search for data to the structure, it uses you function to navigate around the tree. This approach is much faster than iterating over a linear list for example.

In use, you may do something like this -

pascal

program TSetDemo;
{$mode objfpc}{$H+}
{$modeswitch advancedrecords} 
uses
    SysUtils, gvector, gset;        
    
type
    PNote=^TNote;
    TNote = record      // This is our data
        Title : string;
        NoteSize   : integer;
    end;   
      
type
    TLess = record
        class function c(L, R: PNote): Boolean; static;
    end;

type
    TNoteSet = specialize TSet<PNote, TLess>;    
         

// ------------------------
    
var
    NoteSet : TNoteSet;
        
    
class function TLess.c(L, R: PNote): Boolean;       // Our sorting function
begin
    Result := L^.Title < R^.Title;
end;              
    
    
procedure AddItemToSet(Title : string; NoteSize : integer);
var
    SomeData: PNote;
begin
    new(SomeData);
    SomeData^.NoteSize := NoteSize;
    SomeData^.Title := Title;
    NoteSet.Insert(SomeData);
end;  

                                 
procedure TestTSet();
var
    it : TNoteSet.TIterator;
    pMin: TNoteSet.PNode;
begin
    NoteSet := TNoteSet.Create;
    AddItemToSet('abc', 22);   
    AddItemToSet('abc', 100);     // Note, a duplicate !
    AddItemToSet('xyz', 700);
    AddItemToSet('ghi', 3125);
    
    it := NoteSet.Min;                  
    if it <> nil then begin
        pMin := it.FNode;             // So we can come back to it.
        repeat
            writeln(it.GetData^.Title + ' ' + inttostr(it.GetData^.NoteSize));
        until not it.Next;
        
        // OK, here we Free or Dispose as appropriate.
        it.FNode := pMin;
        repeat
            dispose(it.GetData);
        until not it.Next;
    end;
    it.Free;
    NoteSet.free;
end;                                   

begin
    TestTSet();
end.

A few notes

Obviously, you can store what ever you want in the data record. Its up to you to create it and, importantly, free it.
In this example we create an iterator and, for convenience, we set it back to first item and use it again. We could free and recreate it as an alternative and, if the data has changed, we must do that. Important, that call to NoteSet.Min allocates memory, you must free it before recalling or finishing up.

Performance

While a Red Black Tree is reported to be faster when altering data, my tests do not show an appreciable improvement over the TAvgLvlTree. Your results may vary and if its important, do some tests of your own. I, personally, consider the TAvgLvlTree is just a little more comfortable in the FPC setting, it uses a number of conventions that we tend to expect and is likely to be better supported by the FPC community.

Thanks to AVK in the forum, without who's help I would have walked away from this topic.

Talk about this page

Nobody has opened a bench for this page yet. Sign in to open one.

GSet

TSet

A few notes

Performance

See Also

Talk about this page