GSet

From Free Pascal wiki
Revision as of 06:02, 19 October 2021 by Dbannon (talk | contribs) (first cut)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

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 -

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.

See Also