GSet: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: GSet

New		Line
1	+	## TSet
2	+
3	+	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]].
4	+
5	+	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.
6	+
7	+	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.
8	+
9	+	In use, you may do something like this -
10	+
11	+	``` pascal
12	+	program TSetDemo;
13	+	{$mode objfpc}{$H+}
14	+	{$modeswitch advancedrecords}
15	+	uses
16	+	SysUtils, gvector, gset;
17	+
18	+	type
19	+	PNote=^TNote;
20	+	TNote = record // This is our data
21	+	Title : string;
22	+	NoteSize : integer;
23	+	end;
24	+
25	+	type
26	+	TLess = record
27	+	class function c(L, R: PNote): Boolean; static;
28	+	end;
29	+
30	+	type
31	+	TNoteSet = specialize TSet<PNote, TLess>;
32	+
33	+
34	+	// ------------------------
35	+
36	+	var
37	+	NoteSet : TNoteSet;
38	+
39	+
40	+	class function TLess.c(L, R: PNote): Boolean; // Our sorting function
41	+	begin
42	+	Result := L^.Title < R^.Title;
43	+	end;
44	+
45	+
46	+	procedure AddItemToSet(Title : string; NoteSize : integer);
47	+	var
48	+	SomeData: PNote;
49	+	begin
50	+	new(SomeData);
51	+	SomeData^.NoteSize := NoteSize;
52	+	SomeData^.Title := Title;
53	+	NoteSet.Insert(SomeData);
54	+	end;
55	+
56	+
57	+	procedure TestTSet();
58	+	var
59	+	it : TNoteSet.TIterator;
60	+	pMin: TNoteSet.PNode;
61	+	begin
62	+	NoteSet := TNoteSet.Create;
63	+	AddItemToSet('abc', 22);
64	+	AddItemToSet('abc', 100); // Note, a duplicate !
65	+	AddItemToSet('xyz', 700);
66	+	AddItemToSet('ghi', 3125);
67	+
68	+	it := NoteSet.Min;
69	+	if it <> nil then begin
70	+	pMin := it.FNode; // So we can come back to it.
71	+	repeat
72	+	writeln(it.GetData^.Title + ' ' + inttostr(it.GetData^.NoteSize));
73	+	until not it.Next;
74	+
75	+	// OK, here we Free or Dispose as appropriate.
76	+	it.FNode := pMin;
77	+	repeat
78	+	dispose(it.GetData);
79	+	until not it.Next;
80	+	end;
81	+	it.Free;
82	+	NoteSet.free;
83	+	end;
84	+
85	+	begin
86	+	TestTSet();
87	+	end.
88	+	```
89	+
90	+	### A few notes
91	+
92	+	- Obviously, you can store what ever you want in the data record. Its up to you to create it and, importantly, free it.
93	+	- 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.
94	+
95	+	### Performance
96	+
97	+	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.
98	+
99	+	Thanks to AVK in the forum, without who's help I would have walked away from this topic.
100	+
101	+	### See Also
102	+
103	+	- [[Data Structures, Containers, Collections]]
104	+	- <https://forum.lazarus.freepascal.org/index.php/topic,56580.0.html>
105	+	- <http://history.ioinformatics.org/conf/c6_boza.pdf>
106	+	- <https://ioinformatics.org/journal/INFOL101.pdf>
107	+	- <https://en.wikipedia.org/wiki/Red_black_tree>
108	+
109	+	---
110	+	From the Free Pascal wiki, page "GSet", as it stood on 2021-10-19 after a change by Dbannon, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).
111	+	Category: Data Structures

Back to history