LGenerics: what changed

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

Title: LGenerics

New		Line
1	+	## About
2	+
3	+	Collection of generic algorithms and data structures for Free Pascal.
4	+
5	+	Requires: FPC 3.2.2+, Lazarus 2.2+.
6	+
7	+	Author: A.Koverdyaev (avk)
8	+
9	+	License: Apache License 2.0
10	+
11	+	## Download
12	+
13	+	GitHub: <https://github.com/avk959/LGenerics>
14	+
15	+	## Features
16	+
17	+	#### Implemented primitives
18	+
19	+	- stack (unit lgStack)
20	+	- queue (unit lgQueue)
21	+	- deque (unit lgDeque)
22	+	- vector (unit lgVector)
23	+	- vector of bits (unit lgVector)
24	+	- priority queue based on binary heap (unit lgPriorityQueue)
25	+	- priority queue with key update and melding based on pairing heap (unit lgPriorityQueue)
26	+	- sorted list (unit lgList)
27	+	- hashed list - array based list with the ability to fast search by key (unit lgList)
28	+	- hashset (unit lgHashSet)
29	+	- fine-grained concurrent hashset (unit lgHashSet)
30	+	- sorted set (unit lgTreeSet)
31	+	- set of arbitrary size (unit lgUtil, TGSet)
32	+	- hash multiset (unit lgHashMultiSet)
33	+	- fine-grained concurrent hashmultiset (unit lgHashMultiSet)
34	+	- sorted multiset (unit lgTreeMultiSet)
35	+	- hashmap (unit lgHashMap)
36	+	- fine-grained concurrent hashmap (unit lgHashMap)
37	+	- sorted map (unit lgTreeMap)
38	+	- hash multimap (unit lgMultiMap)
39	+	- tree multimap (unit lgMultiMap)
40	+	- list miltimap (unit lgMultiMap)
41	+	- bijective map (unit lgBiMap)
42	+	- sparse 2D table (unit lgTable2D)
43	+	- disjoint set (unit lgHashSet)
44	+	- AVL tree (unit lgAvlTree)
45	+	- red-black tree (unit lgRbTree)
46	+	- some treap variants (unit lgTreap)
47	+	- general rooted tree (unit lgRootTree)
48	+	- sparse labeled undirected graph (unit lgSimpleGraph)
49	+	- sparse labeled directed graph (unit lgSimpleDigraph)
50	+	- lite containers based on advanced records
51	+	- extended IEnumearble interface - filtering, mapping, etc.
52	+
53	+	#### Algorithms on graphs
54	+
55	+	- core functions:
56	+	- vertices/edges addition/removal/query/enumeration, edge contraction, degree
57	+	- load/save to own binary format, primitive export to DOT format
58	+	- connectivity:
59	+	- connected/strongly connected components, bipartite detection, degeneracy, k-core
60	+	- articulation points, bridges, biconnected components
61	+	- edge-connectivity
62	+	- traversals:
63	+	- BFS/DFS traversals with visitors,
64	+	- cycle/negative cycle detection,
65	+	- topological sort
66	+	- operations:
67	+	- induced subgraphs, complement, reverse, union, intersect, symmetric difference,
68	+	- chordality testing
69	+	- planarity testing: FMR Left-Right Planarity algorithm
70	+	- distance within graph:
71	+	- eccentricity, radius, diameter, center, periphery
72	+	- matching:
73	+	- maximum cardinality matching on bipartite/arbitrary graphs
74	+	- minimum/maximum weight matching on bipartite graphs
75	+	- dominators in flowgraps: simple iterative and Semi-NCA algorithms
76	+	- some suggestions for NP-hard problems:
77	+	- maximum independent set, maximal independent sets enumeration
78	+	- maximum clique, cliques enumeration
79	+	- minimum vertex cover, minimal vertex covers enumeration
80	+	- vertex coloring, approximations and exact
81	+	- minimum dominating set
82	+	- Hamiltonian cycles and paths
83	+	- local search TSP approximations, BnB TSP solver
84	+	- minimum spanning trees: Prims's and Kruskal's algorithms
85	+	- single source shortest paths:
86	+	- Dijkstra with pairing heap, Bellman-Ford-Moor with Tarjan's subtree disassembly(BFMT)
87	+	- single pair shortest paths:
88	+	- Dijkstra with binary heap, BFMT, bidirection Dijkstra, A, NBA
89	+	- all pairs shortest paths:
90	+	- Floyd–Warshall, Johnson, BFMT
91	+	- networks:
92	+	- maximum flow: push/relabel, capacity scaling Dinitz
93	+	- minimum-cost flow: Busacker-Gowen, cost scaling push/relabel algorithm
94	+	- global minimum cut: Stoer–Wagner, Nagamochi-Ibaraki
95	+
96	+	#### Algorithms on arrays and vectors
97	+
98	+	(mostly unit lgArrayHelpers)
99	+
100	+	- reverse, right/left cyclic shifts
101	+	- permutations
102	+	- binary search
103	+	- N-th order statistics
104	+	- inversion counting
105	+	- distinct values selection
106	+	- quicksort
107	+	- introsort
108	+	- dual pivot quicksort
109	+	- mergesort
110	+	- timsort (unit lgMiscUtils)
111	+	- counting sort
112	+	- radix sort
113	+	- translation of Orson Peters' PDQSort algorithm
114	+	- static segment tree
115	+	- longest increasing subsequence
116	+	- ...
117	+
118	+	#### Algorithms on strings and sequences
119	+
120	+	(units lgStrHelpers, lgSeqUtils)
121	+
122	+	- exact string matching
123	+	- Boyer-Moore string matching algorithm(in Fast Search variant, unit lgStrHelpers)
124	+	- Boyer-Moore-Horspool-Raita algorithm (unit lgStrHelpers)
125	+	- Aho-Corasick automation for multiple string matching
126	+	- longest common subsequence of two sequences:
127	+	- reducing the LCS problem to LIS
128	+	- Kumar-Rangan algorithm for LCS
129	+	- Myers algorithm for LCS
130	+	- the Levenshtein distance:
131	+	- simple DP algorithm
132	+	- modified Berghel-Roach algorithm
133	+	- Myers bit-vector algorithm with cut-off heuristic
134	+	- LCS distance:
135	+	- Myers algorithm for LCS distance
136	+	- fuzzy string matching(k differences)
137	+	- Ukkonen EDP algorithm
138	+	- fuzzy string matching with preprocessing(something similar to fuzzywuzzy)
139	+
140	+	#### Other features
141	+
142	+	- non-cryptogarphic hashes (unit lgHash):
143	+	- Yann Collet's xxHash32, xxHash64
144	+	- Austin Appleby's MurmurHash2, MurmurHash2A, MurmurHash3_x86_32, MurmurHash64A
145	+	- brief and dirty implementation of futures concept (unit lgAsync)
146	+	- brief channel implementation (unit lgAsync)
147	+	- brief implementation of thread pool (unit lgAsync)
148	+	- 128-bit integers (unit lgInt128)
149	+	- JSON validator/parser/generator (unit lgJson)
150	+	- JSON Patch/Diff (unit lgJson)
151	+	- JSON serialization/deserialization of native Pascal data structures using RTTI(unit lgPdo)
152	+	- JSON Type Definition schemas(unit lgJsonTypeDef)
153	+	- validating a JSON document against a JTD schema(unit lgJsonTypeDef)
154	+	- generating Pascal code from a JTD schema(unit lgJtdCodegen)
155	+	- inferring JTD schemas from example data(unit lgJtdInfer)
156	+	- JSONPath implementation(unit LgJsonPath)
157	+	- CSV document processing (unit lgCsvUtils)
158	+	- Eisel-Lemire fast string-to-double conversion algorithm (unit lgJson)
159	+	- Ryū double-to-string conversion algorithm (unit lgJson)
160	+
161	+	## Support for JSON Patch
162	+
163	+	The TJsonPatch class from the lgJson unit implements the JSON Patch ([RFC 6902](https://datatracker.ietf.org/doc/html/rfc6902)) functionality. JSON Patch is a JSON document format (media type is application/json-patch+json) for expressing a sequence of operations applied to a target JSON document; it is always an array of objects, each representing a single operation, supported set of operations: ADD, REMOVE, REPLACE, MOVE, COPY, and TEST.
164	+
165	+	For example, for this document:
166	+
167	+	``` json
168	+	{
169	+	"foo": [1, 3],
170	+	"boo": ["bar", "baz"]
171	+	}
172	+	```
173	+
174	+	applying this patch
175	+
176	+	``` json
177	+	[
178	+	{"op": "add", "path": "/foo/1", "value": "fizz"},
179	+	{"op": "replace", "path": "/boo/1", "value": "qux"},
180	+	{"op": "add", "path": "/ozz", "value": "zoo"}
181	+	]
182	+	```
183	+
184	+	will have the following result:
185	+
186	+	``` json
187	+	{
188	+	"foo": [1, "fizz", 3],
189	+	"boo": ["bar", "qux"],
190	+	"ozz": "zoo"
191	+	}
192	+	```
193	+
194	+	The TJsonPatch class also contains a POC implementation of the Diff utility, which generates a patch by comparing source and target documents.
195	+
196	+	For example, for this source:
197	+
198	+	``` json
199	+	{
200	+	"a": 1,
201	+	"b": null,
202	+	"c": ["test", "plop"]
203	+	}
204	+	```
205	+
206	+	and for this target:
207	+
208	+	``` json
209	+	{
210	+	"a": 6,
211	+	"c": ["test", "flop"],
212	+	"d": "baz"
213	+	}
214	+	```
215	+
216	+	it will generate a patch like this:
217	+
218	+	``` json
219	+	[
220	+	{"op": "replace", "path": "/a", "value": 6},
221	+	{"op": "remove", "path": "/b"},
222	+	{"op": "replace", "path": "/c/1", "value": "flop"},
223	+	{"op": "add", "path": "/d", "value": "baz"}
224	+	]
225	+	```
226	+
227	+	## Exporting structures to JSON format
228	+
229	+	A unit has been added to LGenerics for exporting Pascal data structures to JSON format and vice versa. The following types are currently supported (called PDOs for short):
230	+
231	+	- numeric, boolean or string types, some limited support of variants;
232	+	- enumerations (exported in string form as the name of the corresponding constant);
233	+	- sets (exported as an array of its elements);
234	+	- regular records, it is possible to register a list of field names or a custom serialization callback;
235	+	- classes, using published properties or by registering a custom callback (TStrings and TCollection as a special case);
236	+	- objects (only by registering a custom serialization callback);
237	+	- static arrays of PDO (only one-dimensional, multidimensional arrays are written as one-dimensional);
238	+	- dynamic arrays of PDO;
239	+	- variant arrays (currently only one-dimensional);
240	+
241	+	### Serialization
242	+
243	+	Function PdoToJson() saves native data structure to JSON format.
244	+
245	+	For example, this code:
246	+
247	+	``` pascal
248	+	program test;
249	+
250	+	{$mode objfpc}{$h+}{$optimization noorderfields}
251	+
252	+	uses
253	+	SysUtils, lgUtils, lgJson, lgPdo;
254	+
255	+	type
256	+	TDayOfWeek = 1..7;
257	+	TDaySet = set of TDayOfWeek;
258	+	TMember = record
259	+	Name: string;
260	+	Age: Integer;
261	+	VisitDays: TDaySet;
262	+	end;
263	+
264	+	const
265	+	Members: array of TMember = (
266	+	(Name: 'Alice'; Age: 21; VisitDays: [1, 3, 5]),
267	+	(Name: 'Bob'; Age: 25; VisitDays: [2, 5, 6]));
268	+	var
269	+	n: specialize TGAutoRef<TJsonNode>;
270	+	s: string;
271	+
272	+	begin
273	+	RegisterRecordFields(TypeInfo(TMember), ['name', 'age', 'visitDays']);
274	+	s := PdoToJson(TypeInfo(Members), Members);
275	+	if not n.Instance.Parse(s) then
276	+	WriteLn('Oops, something went wrong :(')
277	+	else
278	+	WriteLn(n.Instance.FormatJson([jfoEgyptBrace, jfoSingleLineArray]));
279	+	end.
280	+	```
281	+
282	+	produces this JSON:
283	+
284	+	``` json
285	+	[
286	+	{
287	+	"name": "Alice",
288	+	"age": 21,
289	+	"visitDays": [1, 3, 5]
290	+	},
291	+	{
292	+	"name": "Bob",
293	+	"age": 25,
294	+	"visitDays": [2, 5, 6]
295	+	}
296	+	]
297	+	```
298	+
299	+	### Deserialization
300	+
301	+	Procedure PdoLoadJson() is used to load JSON back to the native data structure.
302	+
303	+	Let's change the previous example a bit:
304	+
305	+	``` pascal
306	+	program test;
307	+
308	+	{$mode objfpc}{$h+}{$optimization noorderfields}
309	+
310	+	uses
311	+	SysUtils, lgJson, lgPdo, lgMiscUtils;
312	+
313	+	type
314	+	TDayOfWeek = 1..7;
315	+	TDaySet = set of TDayOfWeek;
316	+	TMember = record
317	+	Name: string;
318	+	Age: Integer;
319	+	VisitDays: TDaySet;
320	+	end;
321	+
322	+	const
323	+	Members: array of TMember = (
324	+	(Name: 'Alice'; Age: 21; VisitDays: [1, 3, 5]),
325	+	(Name: 'Bob'; Age: 25; VisitDays: [2, 5, 6]));
326	+	var
327	+	s: string;
328	+	MemberList: array of TMember = nil;
329	+	I: Integer;
330	+	begin
331	+	RegisterRecordFields(TypeInfo(TMember), ['name', 'age', 'visitDays']);
332	+	s := PdoToJson(TypeInfo(Members), Members);
333	+	//Let's try to read the resulting JSON back into the MemberList array
334	+	PdoLoadJson(TypeInfo(MemberList), MemberList, s);
335	+	for I := 0 to High(MemberList) do begin
336	+	WriteLn('Member ', I);
337	+	WriteLn(' Name: ', MemberList[I].Name);
338	+	WriteLn(' Age: ', MemberList[I].Age);
339	+	WriteLn(' VisitDays: ', Stringify(TypeInfo(TDaySet), MemberList[I].VisitDays));
340	+	end;
341	+	end.
342	+	```
343	+
344	+	it prints
345	+
346	+	Member 0
347	+	Name: Alice
348	+	Age: 21
349	+	VisitDays: {1, 3, 5}
350	+	Member 1
351	+	Name: Bob
352	+	Age: 25
353	+	VisitDays: {2, 5, 6}
354	+
355	+	## Support for JSON Type Definition
356	+
357	+	[JSON Type Definition (aka RFC 8927)](https://jsontypedef.com) is an easy-to-learn, standardized way to define a schema for JSON data.
358	+
359	+	##### Why a schema for JSON?
360	+
361	+	The schema provides a way to describe the structure and to some extent the semantics of the document, with which:
362	+
363	+	- it becomes possible to validate the document, i.e. to distinguish the "correct" document from the "incorrect" one;
364	+	- a validated document can be safely deserialized into a native data structure;
365	+	- and finally, it becomes possible to automatically generate this particular native data structure;
366	+
367	+	##### Why JSON Typedef?
368	+
369	+	It is simple, standardized, well documented, and there are a fair number of implementations for various programming languages(of course, Pascal is not among them).
370	+
371	+	Strictly speaking, JSON Typedef is a subset of JSON Schema. According to the author, the expressiveness of the JTD was intentionally limited to be no more powerful than what can be expressed in the type systems of of major programming languages.
372	+
373	+	In short, for most projects this may be exactly what you need.
374	+
375	+	TL;DR
376	+
377	+	There is not much point in describing the features of the JTD schemas, it is well explained in the documentation.
378	+
379	+	##### Validation
380	+
381	+	Suppose we should to receive JSON messages like
382	+
383	+	``` json
384	+	{
385	+	"firstName": "John",
386	+	"lastName": "Doe",
387	+	"age": 42
388	+	}
389	+	```
390	+
391	+	such JSON can be described by the JTD scheme
392	+
393	+	``` json
394	+	{
395	+	"properties": {
396	+	"firstName": {"type": "string"},
397	+	"lastName": {"type": "string"},
398	+	"age": {"type": "uint8"}
399	+	}
400	+	}
401	+	```
402	+
403	+	And let us get the message
404	+
405	+	``` json
406	+	{
407	+	"firstName": "Bill",
408	+	"lastName": "Smith",
409	+	"age": -5
410	+	}
411	+	```
412	+
413	+	which we need to check for consistency with the scheme.
414	+
415	+	First we need to load the JSON representation of the schema into the corresponding Pascal structure - TJtdSchema class. For example, let our schema be located in the file PersonSchema.json, code
416	+
417	+	``` pascal
418	+	Schema := TJtdSchema.Create;
419	+	try
420	+	Schema.LoadFromFile('PersonSchema.json')
421	+	except
422	+	//something to do in case of an exception
423	+	end;
424	+	```
425	+
426	+	will load the schema and then it can be used repeatedly. In turn, the received JSON(let it be the string S) should be loaded into TJsonNode class, for example like this:
427	+
428	+	``` pascal
429	+	Person := TJsonNode.Create;
430	+	Person.AsJson := S;
431	+	```
432	+
433	+	The Validate(yep!) function is used to validate against the schema; its main parameters are the loaded JSON sample, the loaded schema, and the (out) list of errors found. The error list is an array of InstancePath/SchemaPath pairs, which are JSON pointers. The first one points to the part of the document(instance) that is invalid, and the second one points to the part of the schema that rejected that input. The purpose of the other parameters is described in detail in the lgJsonTypeDef source.
434	+
435	+	So this code
436	+
437	+	``` pascal
438	+	var
439	+	ErrList: TJtdErrorList;
440	+	e: TValidateError;
441	+	...
442	+	case Validate(Person, Schema, ErrList) of
443	+	jvrOk: {It's okay, the document is correct};
444	+	jvrErrors:
445	+	for e in ErrList do
446	+	WriteLn('Error: instance path = ', e.InstancePath, ', schema path = ', e.SchemaPath);
447	+	else
448	+	//dealing with the remaining cases
449	+	end;
450	+	```
451	+
452	+	will print
453	+
454	+
455	+	Error: instance path = /age, schema path = /properties/age/type
456	+
457	+	##### Code generation from schemas
458	+
459	+	Because of RTTI's limited capabilities, it was decided to create a separate hierarchy of classes(see lgJtdTypes unit) to generate the Pascal code according to the given JTD scheme.
460	+
461	+	This hierarchy would have to reflect the JSON Typedef type system and be able to load/save itself from/to different JSON representations.
462	+
463	+	The part of the implementation responsible for code generation, specifically the TJtdPasCodegen class, can be found in the lgJtdCodegen unit.
464	+
465	+	To generate a Pascal unit, the TJtdPasCodegen class needs the schema itself (mandatory), the name of the unit (desirable), the name of the root class (optional), and if the code is to be saved to a file, the name of the file.
466	+
467	+	For example, suppose we have the following scheme:
468	+
469	+	``` json
470	+	{
471	+	"definitions": {
472	+	"fruits": {"enum": ["apple", "banana", "strawberry"],
473	+	"metadata": {
474	+	"description": "this is fruits enumeration description",
475	+	"enumDescription": {
476	+	"apple": "this is apple description",
477	+	"banana": "this is banana description",
478	+	"strawberry": "this is strawberry description"
479	+	}
480	+	}
481	+	},
482	+	"nameList": {"elements": {"type": "string"}}
483	+	},
484	+	"properties": {
485	+	"firstName": {"type": "string"},
486	+	"lastName": {"type": "string"},
487	+	"age": {"type": "uint8"},
488	+	"friends": {"ref": "nameList", "nullable": true},
489	+	"favoriteFruit": {"ref": "fruits", "nullable": true}
490	+	},
491	+	"metadata": {
492	+	"description": "this is Person description",
493	+	"preferredName": "person"
494	+	}
495	+	}
496	+	```
497	+
498	+	and we have loaded it into a TJtdSchema instance named PersonSchema, code
499	+
500	+	``` pascal
501	+	with TJtdPasCodegen.Create(PersonSchema) do
502	+	try
503	+	UnitName := 'Person';
504	+	SaveToFile('person.pas');
505	+	finally
506	+	Free;
507	+	end;
508	+	```
509	+
510	+	will create a (nice-looking :)) unit in the application folder, whose root class will be able to load/save JSONs compliant to the schema.
511	+
512	+	``` pascal
513	+	{
514	+	This unit was automatically created by JtdPasCodegen, do not edit.
515	+	}
516	+	unit Person;
517	+
518	+	{$MODE OBJFPC}{$H+}{$B-}
519	+
520	+	interface
521	+
522	+	uses
523	+	SysUtils, lgJson, lgJtdTypes;
524	+
525	+	type
526	+
527	+	TNameList = class sealed(specialize TJtdList<TJtdString>)
528	+	class function GetJtdClass: TJtdEntityClass; override;
529	+	end;
530	+
531	+	{ this is fruits enumeration description }
532	+	TFruits = (
533	+	apple, // this is apple description
534	+	banana, // this is banana description
535	+	strawberry // this is strawberry description
536	+	);
537	+
538	+	{ Container for some TFruits enumeration element }
539	+	TFruitsElem = class sealed(specialize TJtdEnum<TFruits>)
540	+	class function GetJtdClass: TJtdEntityClass; override;
541	+	end;
542	+
543	+	{ this is Person description }
544	+	TPerson = class sealed(TJtdObject)
545	+	private
546	+	FFirstName: TJtdString;
547	+	FLastName: TJtdString;
548	+	FAge: TJtdUInt8;
549	+	FFriends: TNameList;
550	+	FFavoriteFruit: TFruitsElem;
551	+	procedure SetFirstName(aValue: TJtdString);
552	+	procedure SetLastName(aValue: TJtdString);
553	+	procedure SetAge(aValue: TJtdUInt8);
554	+	procedure SetFriends(aValue: TNameList);
555	+	procedure SetFavoriteFruit(aValue: TFruitsElem);
556	+	protected
557	+	procedure DoReadJson(aNode: TJsonNode); override;
558	+	procedure DoReadJson(aReader: TJsonReader); override;
559	+	procedure DoWriteJson(aWriter: TJsonStrWriter); override;
560	+	public
561	+	class function GetJtdClass: TJtdEntityClass; override;
562	+	procedure Clear; override;
563	+	{ refers to "firstName" JSON property }
564	+	property FirstName: TJtdString read FFirstName write SetFirstName;
565	+	{ refers to "lastName" JSON property }
566	+	property LastName: TJtdString read FLastName write SetLastName;
567	+	{ refers to "age" JSON property }
568	+	property Age: TJtdUInt8 read FAge write SetAge;
569	+	{ refers to "friends" JSON property; is nullable }
570	+	property Friends: TNameList read FFriends write SetFriends;
571	+	{ refers to "favoriteFruit" JSON property; is nullable }
572	+	property FavoriteFruit: TFruitsElem read FFavoriteFruit write SetFavoriteFruit;
573	+	end;
574	+
575	+	implementation
576	+
577	+	{ TNameList }
578	+
579	+	class function TNameList.GetJtdClass: TJtdEntityClass;
580	+	begin
581	+	Result := TNameList;
582	+	end;
583	+
584	+	{ TFruitsElem }
585	+
586	+	class function TFruitsElem.GetJtdClass: TJtdEntityClass;
587	+	begin
588	+	Result := TFruitsElem;
589	+	end;
590	+
591	+	{ TPerson }
592	+
593	+	class function TPerson.GetJtdClass: TJtdEntityClass;
594	+	begin
595	+	Result := TPerson;
596	+	end;
597	+
598	+	procedure TPerson.Clear;
599	+	begin
600	+	FreeAndNil(FFirstName);
601	+	FreeAndNil(FLastName);
602	+	FreeAndNil(FAge);
603	+	FreeAndNil(FFriends);
604	+	FreeAndNil(FFavoriteFruit);
605	+	end;
606	+
607	+	procedure TPerson.SetFirstName(aValue: TJtdString);
608	+	begin
609	+	if aValue = FFirstName then exit;
610	+	FFirstName.Free;
611	+	FFirstName := aValue;
612	+	end;
613	+
614	+	procedure TPerson.SetLastName(aValue: TJtdString);
615	+	begin
616	+	if aValue = FLastName then exit;
617	+	FLastName.Free;
618	+	FLastName := aValue;
619	+	end;
620	+
621	+	procedure TPerson.SetAge(aValue: TJtdUInt8);
622	+	begin
623	+	if aValue = FAge then exit;
624	+	FAge.Free;
625	+	FAge := aValue;
626	+	end;
627	+
628	+	procedure TPerson.SetFriends(aValue: TNameList);
629	+	begin
630	+	if aValue = FFriends then exit;
631	+	FFriends.Free;
632	+	FFriends := aValue;
633	+	end;
634	+
635	+	procedure TPerson.SetFavoriteFruit(aValue: TFruitsElem);
636	+	begin
637	+	if aValue = FFavoriteFruit then exit;
638	+	FFavoriteFruit.Free;
639	+	FFavoriteFruit := aValue;
640	+	end;
641	+
642	+	{$PUSH}{$WARN 5057 OFF}
643	+	procedure TPerson.DoReadJson(aNode: TJsonNode);
644	+	var
645	+	p: TJsonNode.TPair;
646	+	Flags: array[0..4] of Boolean;
647	+	I: Integer;
648	+	begin
649	+	if not aNode.IsObject then ReadError;
650	+	Clear;
651	+	System.FillChar(Flags, SizeOf(Flags), 0);
652	+	for p in aNode.Entries do
653	+	case p.Key of
654	+	'firstName':
655	+	begin
656	+	FFirstName := TJtdString(TJtdString.ReadJson(p.Value));
657	+	Flags[0] := True;
658	+	end;
659	+	'lastName':
660	+	begin
661	+	FLastName := TJtdString(TJtdString.ReadJson(p.Value));
662	+	Flags[1] := True;
663	+	end;
664	+	'age':
665	+	begin
666	+	FAge := TJtdUInt8(TJtdUInt8.ReadJson(p.Value));
667	+	Flags[2] := True;
668	+	end;
669	+	'friends':
670	+	begin
671	+	FFriends := TNameList(TNameList.ReadJson(p.Value));
672	+	Flags[3] := True;
673	+	end;
674	+	'favoriteFruit':
675	+	begin
676	+	FFavoriteFruit := TFruitsElem(TFruitsElem.ReadJson(p.Value));
677	+	Flags[4] := True;
678	+	end;
679	+	else
680	+	UnknownProp(p.Key);
681	+	end;
682	+	for I := 0 to System.High(Flags) do
683	+	if not Flags[I] then
684	+	case I of
685	+	0: PropNotFound('firstName');
686	+	1: PropNotFound('lastName');
687	+	2: PropNotFound('age');
688	+	3: PropNotFound('friends');
689	+	4: PropNotFound('favoriteFruit');
690	+	else
691	+	end;
692	+	end;
693	+	{$POP}
694	+
695	+	{$PUSH}{$WARN 5057 OFF}
696	+	procedure TPerson.DoReadJson(aReader: TJsonReader);
697	+	var
698	+	Flags: array[0..4] of Boolean;
699	+	I: Integer;
700	+	begin
701	+	if aReader.TokenKind <> tkObjectBegin then ReadError;
702	+	Clear;
703	+	System.FillChar(Flags, SizeOf(Flags), 0);
704	+	repeat
705	+	if not aReader.Read then ReadError;
706	+	if aReader.TokenKind = tkObjectEnd then break;
707	+	case aReader.Name of
708	+	'firstName':
709	+	begin
710	+	FFirstName := TJtdString(TJtdString.ReadJson(aReader));
711	+	Flags[0] := True;
712	+	end;
713	+	'lastName':
714	+	begin
715	+	FLastName := TJtdString(TJtdString.ReadJson(aReader));
716	+	Flags[1] := True;
717	+	end;
718	+	'age':
719	+	begin
720	+	FAge := TJtdUInt8(TJtdUInt8.ReadJson(aReader));
721	+	Flags[2] := True;
722	+	end;
723	+	'friends':
724	+	begin
725	+	FFriends := TNameList(TNameList.ReadJson(aReader));
726	+	Flags[3] := True;
727	+	end;
728	+	'favoriteFruit':
729	+	begin
730	+	FFavoriteFruit := TFruitsElem(TFruitsElem.ReadJson(aReader));
731	+	Flags[4] := True;
732	+	end;
733	+	else
734	+	UnknownProp(aReader.Name);
735	+	end;
736	+	until False;
737	+	for I := 0 to System.High(Flags) do
738	+	if not Flags[I] then
739	+	case I of
740	+	0: PropNotFound('firstName');
741	+	1: PropNotFound('lastName');
742	+	2: PropNotFound('age');
743	+	3: PropNotFound('friends');
744	+	4: PropNotFound('favoriteFruit');
745	+	else
746	+	end;
747	+	end;
748	+	{$POP}
749	+
750	+	procedure TPerson.DoWriteJson(aWriter: TJsonStrWriter);
751	+	begin
752	+	aWriter.BeginObject;
753	+	aWriter.AddName('firstName');
754	+	FirstName.WriteJson(aWriter);
755	+	aWriter.AddName('lastName');
756	+	LastName.WriteJson(aWriter);
757	+	aWriter.AddName('age');
758	+	Age.WriteJson(aWriter);
759	+	aWriter.AddName('friends');
760	+	Friends.WriteJson(aWriter);
761	+	aWriter.AddName('favoriteFruit');
762	+	FavoriteFruit.WriteJson(aWriter);
763	+	aWriter.EndObject;
764	+	end;
765	+
766	+	end.
767	+	```
768	+
769	+	##### Schema inference
770	+
771	+	Also added support for inferring JTD schemas from JSON samples.
772	+
773	+	At least the examples from [this article](https://jsontypedef.com/docs/jtd-infer/) run as expected.
774	+
775	+	For example, this simple program:
776	+
777	+	``` pascal
778	+	program infer_test;
779	+
780	+	{$mode objfpc}{$H+}
781	+
782	+	uses
783	+	SysUtils, lgUtils, lgJson, lgJtdInfer;
784	+
785	+	var
786	+	Schema: specialize TGUniqRef<TJsonNode>;
787	+
788	+	const
789	+	Lincoln = '{"name":"Abraham Lincoln","isAdmin": true}';
790	+	Sherman = '{"name":"William Sherman","isAdmin": false,"middleName": "Tecumseh"}';
791	+
792	+	begin
793	+	Schema.Instance := TJtdInferrer.Infer([Lincoln, Sherman], []);
794	+	WriteLn(Schema.Instance.FormatJson(DefaultJsonFmtStyle));
795	+	end.
796	+	```
797	+
798	+	generates such a schema:
799	+
800	+	``` json
801	+	{
802	+	"properties": {
803	+	"name": {"type": "string"},
804	+	"isAdmin": {"type": "boolean"}
805	+	},
806	+	"optionalProperties": {
807	+	"middleName": {"type": "string"}
808	+	}
809	+	}
810	+	```
811	+
812	+	The /example/json/jtd folder contains a small schema editor to demonstrate the functionality of JSON Typedef.
813	+
814	+	## Support for JSONPath
815	+
816	+	#### About JSONPath
817	+
818	+
819	+	JSONPath enables you to search for particular data in a JSON document using a simple query syntax somewhat similar to XPath.
820	+
821	+	It is based on Stefan Gessner's popular proposal( [2007-02-21](https://goessner.net/articles/JsonPath/)), and now finally achieved Proposed Standard status: [RFC 9535](https://www.rfc-editor.org/rfc/rfc9535) .
822	+
823	+	A JSONPath query might look like this:
824	+
825	+	`$.store.book[?@.price < 10].title`
826	+
827	+	or
828	+
829	+	`$['store']['book'][?@['price'] < 10]['title']`
830	+
831	+	or
832	+
833	+	`$["store"]["book"][?@["price"] < 10]["title"]`
834	+
835	+	These are just different ways of writing a query to select book titles which price is less than 10.
836	+
837	+	#### Syntax
838	+
839	+	The implementation of JSONPath in LGenerics tries to follow the syntax described in the [RFC 9535](https://www.rfc-editor.org/rfc/rfc9535).
840	+
841	+	Any query starts with \$ sign followed by some (possibly zero) number of segments, leading and trailing spaces are not allowed.
842	+
843	+	The whole process can be depicted as a pipe, where each step selects some number of child nodes ( possibly zero), which are then passed to the next step. The result of this is a list of Nodes, Nodelist in terms of specifications.
844	+
845	+	It is worth noting that in specs terminology, a JSONPath Node represents a pair, the JSON value along with its location within the query argument.
846	+
847	+	\| Element \| Descrition \|
848	+	\|----\|----\|
849	+	\| \$ \| root node identifier (query argument) \|
850	+	\| @ \| current node identifier \|
851	+	\| \[\<selectors\>\] \| child segment: selects zero or more children of a node; contains one or more selectors, separated by commas \|
852	+	\| .name \| shorthand for \['name'\] or \["name"\] \|
853	+	\| .* \| shorthand for \[*\] \|
854	+	\| ..\[\<selectors\>\] \| descendant segment: selects zero or more descendants of a node; contains one or more selectors, separated by commas \|
855	+	\| ..name \| shorthand for ..\['name'\] \|
856	+	\| ..* \| shorthand for ..\[*\] \|
857	+	\| 'name' \| name selector: selects a named child of an object \|
858	+	\| * \| wildcard selector: selects all children of a node \|
859	+	\| 7 \| index selector: selects an indexed child of an array (0-based) \|
860	+	\| 0:42:5 \| array slice selector: start:end:step for arrays \|
861	+	\| ?\<logical-expr\> \| filter selector: selects particular children using a logical expression \|
862	+	\| length(@.foo) \| function extension: invokes a function in a filter expression \|
863	+
864	+	Basic syntax elements
865	+
866	+	Index and slice selectors have certain peculiarities:
867	+
868	+	:* `$.book[1]` matches the second book
869	+
870	+	:* `$.book[-1]` matches the last book
871	+
872	+	:* `$.book[2:]` matches the third and all following books
873	+
874	+	:* `$.book[-2:]` matches the last two books
875	+
876	+	:* `$.book[:2]` matches the first two books
877	+
878	+	:* `$.book[::]` matches all books
879	+
880	+	:* `$.book[::-1]` matches all books in reverse order
881	+
882	+	The filter selector is a logical expression containing logical operators, comparison operators, and function calls.
883	+
884	+	\| Precedence \| Operator type \| Syntax \|
885	+	\|------------\|---------------\|--------------------------\|
886	+	\| 5 \| Grouping \| ( ... ) \|
887	+	\| 4 \| Logical NOT \| ! \|
888	+	\| 3 \| Relations \| ==, !=, \>, \<, \>=, \<= \|
889	+	\| 2 \| Logical AND \| && \|
890	+	\| 1 \| Logical OR \| \<nowiki\> \|
891	+
892	+	Filter expressions operator precedence
893	+
894	+	It is also highly recommended to implement 5 functions whose syntax and semantics are predefined in the specifications:
895	+
896	+	- `length()`
897	+	- `count()`
898	+	- `match()`
899	+	- `search()`
900	+	- `value()`
901	+
902	+	The match() and search() functions use a special flavor of regular expression (I-Regexp, [RFC 9485](https://www.rfc-editor.org/rfc/rfc9485)) for interoperability purposes.
903	+
904	+	#### Implementation
905	+
906	+	In LGenerics, the JSONPath implementation can be found in the LgJsonPath unit.
907	+
908	+	JSONPath functionality is represented by the IJsonPath COM interface, which currently (end of February 2024) contains 12 basic matching methods for different types of input and output data and an additional Params\[\] property for setting parameters in parametric queries.
909	+
910	+	To get a reference to the IJsonPath interface, one can use an overloaded version of the JpParseQuery() function with the required set of parameters.
911	+
912	+	In addition to the built-in functions defined in the specification, some extra functions of greater or lesser utility have been added; a list and description can be found in the unit header.
913	+
914	+	It is also possible to register user-defined functions, which, however, requires some caution.
915	+
916	+	The specs seems to be realized in its entirety and the implementation is successfully passing the current compliance tests.
917	+
918	+	A small example, JSON document taken from the specifications:
919	+
920	+	``` pascal
921	+	program test_jp;
922	+	{$mode objfpc}{$h+}
923	+	uses
924	+	SysUtils, LgUtils, LgJson, lgJsonPath;
925	+
926	+	const
927	+	Json: string =
928	+	'{ "store": { ' +
929	+	' "book": [ ' +
930	+	' { "category": "reference", ' +
931	+	' "author": "Nigel Rees", ' +
932	+	' "title": "Sayings of the Century",' +
933	+	' "price": 8.95 ' +
934	+	' }, ' +
935	+	' { "category": "fiction", ' +
936	+	' "author": "Evelyn Waugh", ' +
937	+	' "title": "Sword of Honour", ' +
938	+	' "price": 12.99 ' +
939	+	' }, ' +
940	+	' { "category": "fiction", ' +
941	+	' "author": "Herman Melville", ' +
942	+	' "title": "Moby Dick", ' +
943	+	' "isbn": "0-553-21311-3", ' +
944	+	' "price": 8.99 ' +
945	+	' }, ' +
946	+	' { "category": "fiction", ' +
947	+	' "author": "J. R. R. Tolkien", ' +
948	+	' "title": "The Lord of the Rings", ' +
949	+	' "isbn": "0-395-19395-8", ' +
950	+	' "price": 22.99 ' +
951	+	' } ' +
952	+	' ], ' +
953	+	' "bicycle": { ' +
954	+	' "color": "red", ' +
955	+	' "price": 399 ' +
956	+	' } ' +
957	+	' } ' +
958	+	'} ';
959	+
960	+	var
961	+	Doc, CurrNode: specialize TGAutoRef<TJsonNode>;
962	+	Path: IJsonPath;
963	+	List: TJpNodeList;
964	+	Node: TJpNode;
965	+	begin
966	+	if not Doc.Instance.Parse(Json) then begin
967	+	WriteLn('Oops, failed to parse document');
968	+	Halt;
969	+	end;
970	+
971	+	if JpParseQuery('$..author', Path) then begin
972	+	WriteLn('All authors: ');
973	+	List := Path.Match(Doc.Instance);
974	+	for Node in List do begin
975	+	CurrNode.Instance.Parse(Node.AsJson);
976	+	WriteLn(CurrNode.Instance.FormatJson(DefaultJsonFmtStyle, 2));
977	+	end;
978	+	WriteLn;
979	+	end;
980	+
981	+	if JpParseQuery('$..[?@.isbn]', Path) then begin
982	+	WriteLn('Anything that has an ISBN:');
983	+	List := Path.Match(Doc.Instance);
984	+	for Node in List do begin
985	+	CurrNode.Instance.Parse(Node.AsJson);
986	+	WriteLn(CurrNode.Instance.FormatJson(DefaultJsonFmtStyle, 2));
987	+	end;
988	+	WriteLn;
989	+	end;
990	+
991	+	if JpParseQuery('$..[?@.color == "red"]', Path) then begin
992	+	WriteLn('Anything that is red: ');
993	+	List := Path.Match(Doc.Instance);
994	+	for Node in List do begin
995	+	CurrNode.Instance.Parse(Node.AsJson);
996	+	WriteLn(CurrNode.Instance.FormatJson(DefaultJsonFmtStyle, 2));
997	+	end;
998	+	WriteLn;
999	+	end;
1000	+
1001	+	if JpParseQuery('$..[?search(@.title, "[Hh]ono")]', Path) then begin
1002	+	WriteLn('Anything that contains "Hono" or "hono" in the title: ');
1003	+	List := Path.Match(Doc.Instance);
1004	+	for Node in List do begin
1005	+	CurrNode.Instance.Parse(Node.AsJson);
1006	+	WriteLn(CurrNode.Instance.FormatJson(DefaultJsonFmtStyle, 2));
1007	+	end;
1008	+	end;
1009	+	end.
1010	+	```
1011	+
1012	+	It prints:
1013	+
1014	+	`All authors:`\
1015	+	` {"location": "$['store']['book'][0]['author']", "value": "Nigel Rees"}`\
1016	+	` {"location": "$['store']['book'][1]['author']", "value": "Evelyn Waugh"}`\
1017	+	` {"location": "$['store']['book'][2]['author']", "value": "Herman Melville"}`\
1018	+	` {"location": "$['store']['book'][3]['author']", "value": "J. R. R. Tolkien"}`\
1019	+	``\
1020	+	`Anything that has an ISBN:`\
1021	+	` {`\
1022	+	` "location": "$['store']['book'][2]",`\
1023	+	` "value": {`\
1024	+	` "category": "fiction",`\
1025	+	` "author": "Herman Melville",`\
1026	+	` "title": "Moby Dick",`\
1027	+	` "isbn": "0-553-21311-3",`\
1028	+	` "price": 8.99`\
1029	+	` }`\
1030	+	` }`\
1031	+	` {`\
1032	+	` "location": "$['store']['book'][3]",`\
1033	+	` "value": {`\
1034	+	` "category": "fiction",`\
1035	+	` "author": "J. R. R. Tolkien",`\
1036	+	` "title": "The Lord of the Rings",`\
1037	+	` "isbn": "0-395-19395-8",`\
1038	+	` "price": 22.99`\
1039	+	` }`\
1040	+	` }`\
1041	+	``\
1042	+	`Anything that is red:`\
1043	+	` {`\
1044	+	` "location": "$['store']['bicycle']",`\
1045	+	` "value": {"color": "red", "price": 399}`\
1046	+	` }`\
1047	+	``\
1048	+	`Anything that contains "Hono" or "hono" in the title:`\
1049	+	` {`\
1050	+	` "location": "$['store']['book'][1]",`\
1051	+	` "value": {`\
1052	+	` "category": "fiction",`\
1053	+	` "author": "Evelyn Waugh",`\
1054	+	` "title": "Sword of Honour",`\
1055	+	` "price": 12.99`\
1056	+	` }`\
1057	+	` }`
1058	+
1059	+	## Performance
1060	+
1061	+	### Containers
1062	+
1063	+	#### Performance of hash maps
1064	+
1065	+	There is a [wonderful benchmark](https://www.benibela.de/fpc-map-benchmark_en.html) from BeniBela, which also covers hashmaps from LGenerics.
1066	+
1067	+	### Algorithms on arrays/vectors
1068	+
1069	+	#### Sorting
1070	+
1071	+	(This section is outdated.)
1072	+
1073	+	The benchmark sorts 1000000 integers and calculates the number of CPU cycles spent on one element and involves:
1074	+
1075	+	- QuickSort_ItemList_Context from unit SortBase (Rtl/SortBase)
1076	+	- TOrderingArrayUtils.Sort from Fcl-Stl.GArrayUtils (Fcl-Stl)
1077	+	- TArrayHelper.Sort from Rtl-Generics.Generics.Collections (Rtl-Generics)
1078	+	- std::sort from libstdc++ (std::sort)
1079	+	- std::stable_sort from libstdc++ (std::stable_sort)
1080	+	- TGOrdinalArrayHelper.QuickSort (LG/QuickSort)
1081	+	- TGOrdinalArrayHelper.IntroSort (LG/IntroSort)
1082	+	- TGOrdinalArrayHelper.DualPivotQuickSort (LG/DualPivotQuickSort)
1083	+	- TGOrdinalArrayHelper.PDQSort (LG/PDQSort)
1084	+	- TGComparableArrayHelper.MergeSort (LG/MergeSort)
1085	+	- TGComparableTimSort.Sort (LG/TimSort)
1086	+	- TGOrdinalArrayHelper.Sort (LG/Sort)
1087	+	- A negative value indicates that the algorithm exhibits quadratic behavior.
1088	+
1089	+	<figure>
1090	+	<img src="sort_bench_1000000.png" width="800" />
1091	+	</figure>
1092	+
1093	+	### Algorithms on graphs
1094	+
1095	+	For performance comparison the AGraph library (taken from [here](https://github.com/zamtmn/agraphlaz)) was chosen as a reference implementation. All tests were compiled for x86 and run on win64 machine (unfortunately the 64-bit version of AGraph crashes on these tests).
1096	+
1097	+	So, AGraph vs LGenerics:
1098	+
1099	+	\| problem \| graph \| AGraph time(ms) \| LGenerics time(ms) \| notes \|
1100	+	\|----\|----\|----\|----\|----\|
1101	+	\| BFS traversal \| undirected, V=500000, E=4000000 \| 640 \| 109 \| \|
1102	+	\| BFS traversal \| directed, V=500000, E=4000000 \| 484 \| 94 \| \|
1103	+	\| Connected components \| undirected, V=500000, E=4000000 \| 764 \| 0 \| If no edges were removed, TGSimpleGraph always knows the number and ownership of connected components \|
1104	+	\| Strongly connected components \| directed, V=500000, E=4000000 \| 1060 \| 265 \| \|
1105	+	\| Single-source shortest path \| undirected, V=500000, E=4000000 \| 3011 \| 842 \| \|
1106	+	\| Single-source shortest path \| directed, V=500000, E=4000000 \| 2153 \| 718 \| \|
1107	+	\| Single-pair shortest path \| undirected, V=500000, E=4000000 \| 2777 \| 31 \| \|
1108	+	\| Single-pair shortest path \| directed, V=500000, E=4000000 \| 1825 \| 47 \| \|
1109	+	\| Minimum spanning tree \| undirected, V=500000, E=4000000 \| 5974 \| 640 \| \|
1110	+	\| Maximum flow \| dense, V=1000, E=499500 \| 29499 \| 47 \| \|
1111	+	\| Maximum flow \| sparse, V=64000, E=512000 \| 3339 \| 63 \| \|
1112	+	\| Planarity test \| undirected, V=219086, E=657252 \| 1419 \| 172 \| \|
1113	+	\| Maximum clique \| DIMACS brock200_2.clq, V=200, E=9876 \| 84210 \| 16 \| \|
1114	+	\| Maximum clique \| DIMACS brock200_4.clq, V=200, E=13089 \| Cancelled(timeout 1 h) \| 312 \| \|
1115	+
1116	+	### Algorithms on strings/sequences
1117	+
1118	+	It was curious to compare the performance of the SimRatioLevEx() function (which is inspired by FuzzyWuzzy) with some incarnations of the FuzzyWuzzy ([listed here](https://pypi.org/project/fuzzywuzzy/)) on benchmark datasets. Disclamer: SimRatioLevEx() does not reproduce FuzzyWuzzy, but it does some things in a similar way, in particular, SimRatioLevEx() in smTokenSetEx mode and token_set_ratio() do roughly the same job.
1119	+
1120	+	It seems the C++ version only supports single-byte strings, so only compared to the single-byte version of SimRatioLevEx():
1121	+
1122	+	Dataset SimRatioLevEx() token_set_ratio()
1123	+
1124	+	Short/big_dist 1154 6440
1125	+	Short/small_dist 967 3020
1126	+	Medium/big_dist 811 3450
1127	+	Medium/small_dist 702 1470
1128	+	Long/big_dist 1966 15000
1129	+	Long/small_dist 1061 2250
1130	+
1131	+	The numbers indicate the run time in milliseconds; the C++ version was compiled with gcc-8.1.0 with options -O3 -m64; the Pascal version was compiled with FPC-3.3.1-9941-g8e6e9bbf33, -O3. The benchmark was run on a Windows x64 machine.
1132	+
1133	+	The Go version, on the contrary, always works with Unicode strings:
1134	+
1135	+	Dataset SimRatioLevExUtf8() TokenSetRatio()
1136	+
1137	+	Short/big_dist 2143 18705
1138	+	Short/small_dist 1593 2224
1139	+	Medium/big_dist 1266 15062
1140	+	Medium/small_dist 853 1742
1141	+	Long/big_dist 3853 79851
1142	+	Long/small_dist 1269 3126
1143	+
1144	+	Go version: go1.10.4 linux/amd64; FPC-3.3.1-10683-g2a19e152b7 -O3. The benchmark was run on a virtual Linux machine.
1145	+
1146	+	### Performance of JSON operations
1147	+
1148	+	A small performance comparison of the lgJson. TJsonNode class with some other implementations, the benchmark was compiled for x86_64 and run on a win64 machine.
1149	+
1150	+	\| description \| FpJson \| JsonTools \| lgJson \| notes \|
1151	+	\|----\|----\|----\|----\|----\|
1152	+	\| Average parsing speed on a set of JSON samples from the example/json/parse_bench folder, MB/s \| 34,45 \| 46,11 \| 68,12 \| \|
1153	+	\| Average validating speed on a set of JSON samples from the example/json/parse_bench folder, MB/s \| 34,4 \| 46,02 \| 349,48 \| FpJson does not provide any function to validate JSON, so a parser was used \|
1154	+	\| Recursive traversal (using the built-in enumerator) of the document of moderate size (34 KB) with all values read (50000 repeats), milliseconds \| 8315 \| 6802 \| 639 \| \|
1155	+	\| Search in a moderately sized document using path (750000 repeats), milliseconds \| 8549 \| 5398 \| 873 \| \|
1156	+	\| Dynamic creation of a small document and reading it as formatted JSON (150000 repeats), milliseconds \| 7597 \| 4150 \| 1903 \| \|
1157	+	\| Saving a moderate size document to a stream (10000 repeats), milliseconds \| 4820 \| 4587 \| 827 \| \|
1158	+	\| RFC 8259 compliance test, 295 test files from test/json_testset/testset \| 5 failed \| 23 failed \| all passed \| \|
1159	+
1160	+	#### Performance of export to JSON
1161	+
1162	+	Datasets used: a collection of simple items (with three string properties and one integer property) and an array of records whose fields contain values that coincide with the values of the collection's item properties (i.e. the resulting JSONs should be the same). The number of elements in the datasets was chosen so that the size of the resulting JSON approximately corresponded to the values (20KB, 100KB, 1MB, 10MB, 50MB).
1163	+
1164	+	TJSONStreamer.CollectionToJSON() was taken as a reference implementation (FpJsonStreamer for short), other members:
1165	+
1166	+	- PdoToJson() with a collection as parameter (PdoCollection);
1167	+	- PdoToJson() with array as parameter and field name list registration (PdoRecordFieldMap);
1168	+	- PdoToJson() with array as parameter and custom callback registration (PdoRecordCallback);
1169	+
1170	+	Each member exports the data several times (number of attempts is pre-defined), the best time is taken as the result.
1171	+
1172	+	The full benchmark code can be found in the folder LGenerics/example/json/json_export_bench.
1173	+
1174	+	Results on author's machine:
1175	+
1176	+	-------<JSON size 20 KB>-------
1177	+	FpJsonStreamer......1,045 ms.
1178	+	Rating: 22,23 MB/s.
1179	+	PdoCollection.......0,123 ms.
1180	+	Rating: 164,36 MB/s.
1181	+	PdoRecordFieldMap...0,089 ms.
1182	+	Rating: 226,76 MB/s.
1183	+	PdoRecordCallback...0,057 ms.
1184	+	Rating: 356,65 MB/s.
1185	+	-------<JSON size 100 KB>-------
1186	+	FpJsonStreamer......5,647 ms.
1187	+	Rating: 20,51 MB/s.
1188	+	PdoCollection.......0,626 ms.
1189	+	Rating: 160,7 MB/s.
1190	+	PdoRecordFieldMap...0,443 ms.
1191	+	Rating: 226,72 MB/s.
1192	+	PdoRecordCallback...0,285 ms.
1193	+	Rating: 352,29 MB/s.
1194	+	-------<JSON size 1 MB>-------
1195	+	FpJsonStreamer......80,298 ms.
1196	+	Rating: 14,34 MB/s.
1197	+	PdoCollection.......6,552 ms.
1198	+	Rating: 152,63 MB/s.
1199	+	PdoRecordFieldMap...4,701 ms.
1200	+	Rating: 212,71 MB/s.
1201	+	PdoRecordCallback...3,107 ms.
1202	+	Rating: 321,85 MB/s.
1203	+	-------<JSON size 10 MB>-------
1204	+	FpJsonStreamer......3554,483 ms.
1205	+	Rating: 3,24 MB/s.
1206	+	PdoCollection.......71,202 ms.
1207	+	Rating: 140,57 MB/s.
1208	+	PdoRecordFieldMap...53,309 ms.
1209	+	Rating: 187,75 MB/s.
1210	+	PdoRecordCallback...37,39 ms.
1211	+	Rating: 267,69 MB/s.
1212	+	-------<JSON size 50 MB>-------
1213	+	FpJsonStreamer......84343,47 ms.
1214	+	Rating: 0,68 MB/s.
1215	+	PdoCollection.......350,224 ms.
1216	+	Rating: 142,99 MB/s.
1217	+	PdoRecordFieldMap...260,963 ms.
1218	+	Rating: 191,89 MB/s.
1219	+	PdoRecordCallback...183,328 ms.
1220	+	Rating: 273,16 MB/s.
1221	+
1222	+	#### Performance of JSON Type Definition
1223	+
1224	+	Test schema:
1225	+
1226	+	``` json
1227	+	{
1228	+	"definitions": {
1229	+	"point": {
1230	+	"properties": {
1231	+	"x": {"type": "int32"},
1232	+	"y": {"type": "int32"}
1233	+	}
1234	+	},
1235	+	"shape": {"enum": ["circle", "ellipce", "rectangle", "rhombus", "triangle"]},
1236	+	"figure": {
1237	+	"properties": {
1238	+	"name": {"type": "string"},
1239	+	"shape": {"ref": "shape"},
1240	+	"area": {"type": "float64"},
1241	+	"center": {"ref": "point"}
1242	+	}
1243	+	}
1244	+	},
1245	+	"elements": {"ref": "figure"}
1246	+	}
1247	+	```
1248	+
1249	+	The TJSONDeStreamer loading a collection of figures was taken as a reference implementation. To create more or less extreme conditions, a test JSON of size 62267256 bytes was generated, JTD class(unit Figures) was generated using TJtdPasCodegen.
1250	+
1251	+	Full source code of the test application:
1252	+
1253	+	``` pascal
1254	+	program jtd_test;
1255	+
1256	+	{$mode objfpc}{$H+}
1257	+
1258	+	uses
1259	+	Classes, SysUtils, fpJsonRtti, lgJson, lgJsonTypeDef, Figures;
1260	+
1261	+	type
1262	+	{$PUSH}{$M+}
1263	+	TMyPoint = class
1264	+	private
1265	+	FX,
1266	+	FY: Integer;
1267	+	published
1268	+	property x: Integer read FX write FX;
1269	+	property y: Integer read FY write FY;
1270	+	end;
1271	+	{$POP}
1272	+
1273	+	TMyFigure = class(TCollectionItem)
1274	+	private
1275	+	FArea: Double;
1276	+	FCenter: TMyPoint;
1277	+	FName: string;
1278	+	FShape: TShape;
1279	+	public
1280	+	constructor Create(ACollection: TCollection); override;
1281	+	destructor Destroy; override;
1282	+	published
1283	+	property name: string read FName write FName;
1284	+	property shape: TShape read FShape write FShape;
1285	+	property area: Double read FArea write FArea;
1286	+	property center: TMyPoint read FCenter;
1287	+	end;
1288	+
1289	+	constructor TMyFigure.Create(ACollection: TCollection);
1290	+	begin
1291	+	inherited Create(ACollection);
1292	+	FCenter := TMyPoint.Create;
1293	+	end;
1294	+
1295	+	destructor TMyFigure.Destroy;
1296	+	begin
1297	+	FCenter.Free;
1298	+	inherited;
1299	+	end;
1300	+
1301	+	var
1302	+	s: string;
1303	+
1304	+	procedure TestCollection;
1305	+	var
1306	+	c: TCollection;
1307	+	Start, Stop: QWord;
1308	+	begin
1309	+	c := TCollection.Create(TMyFigure);
1310	+	Start := GetTickCount64;
1311	+	with TJSONDeStreamer.Create(nil) do
1312	+	try
1313	+	JSONToCollection(s, c);
1314	+	finally
1315	+	Free;
1316	+	end;
1317	+	Stop := GetTickCount64;
1318	+	c.Free;
1319	+	WriteLn('TJSONDeStreamer.JSONToCollection: ', Stop - Start);
1320	+	end;
1321	+
1322	+	procedure TestJtd;
1323	+	var
1324	+	Node: TJsonNode;
1325	+	Schema: TJtdSchema;
1326	+	eList: TJtdErrorList;
1327	+	Figures: TFigureList;
1328	+	Start, Stop: QWord;
1329	+	begin
1330	+	Start := GetTickCount64;
1331	+	if not TJsonNode.TryParse(s, Node) then begin
1332	+	WriteLn('Failed to load data');
1333	+	exit;
1334	+	end;
1335	+	Stop := GetTickCount64;
1336	+	WriteLn('Loading data into TJsonNode: ', Stop - Start);
1337	+
1338	+	if not TJtdSchema.TryLoadFromFile('schema.json', Schema) then begin
1339	+	WriteLn('Failed to load schema');
1340	+	exit;
1341	+	end;
1342	+
1343	+	Start := GetTickCount64;
1344	+	if Validate(Node, Schema, eList) <> jvrOk then begin
1345	+	WriteLn('Failed to validate data');
1346	+	exit;
1347	+	end;
1348	+	Stop := GetTickCount64;
1349	+	Schema.Free;
1350	+	WriteLn('TJsonNode data validation: ', Stop - Start);
1351	+
1352	+	Start := GetTickCount64;
1353	+	Figures := TFigureList.ReadJson(Node) as TFigureList;
1354	+	Stop := GetTickCount64;
1355	+	Figures.Free;
1356	+	Node.Free;
1357	+	WriteLn('Loadind JTD class from TJsonNode: ', Stop - Start);
1358	+
1359	+	Start := GetTickCount64;
1360	+	Figures := TFigureList.ReadJson(s) as TFigureList;
1361	+	Stop := GetTickCount64;
1362	+	Figures.Free;
1363	+	WriteLn('Direct loading of JTD class: ', Stop - Start);
1364	+	end;
1365	+
1366	+	procedure LoadData;
1367	+	begin
1368	+	with TStringStream.Create do
1369	+	try
1370	+	LoadFromFile('data.json');
1371	+	s := DataString;
1372	+	finally
1373	+	Free;
1374	+	end;
1375	+	end;
1376	+
1377	+	begin
1378	+	LoadData;
1379	+
1380	+	TestCollection;
1381	+	TestJtd;
1382	+
1383	+	end.
1384	+	```
1385	+
1386	+	On my machine, it prints results like this:
1387	+
1388	+	TJSONDeStreamer.JSONToCollection: 5304
1389	+	Loading data into TJsonNode: 1513
1390	+	TJsonNode data validation: 1732
1391	+	Loadind JTD class from TJsonNode: 515
1392	+	Direct loading of JTD class: 1560
1393	+
1394	+	Conclusion: the total validation and loading time of the JTD class is still noticeably better than the TCollection load time (3760 vs 5304).
1395	+
1396	+	The direct load time of the JTD class is better than the load time of the TCollection by more than three times.
1397	+
1398	+	---
1399	+	From the Free Pascal wiki, page "LGenerics", as it stood on 2024-05-14 after a change by Avk, 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).
1400	+	Category: JSON
1401	+	Category: Libraries

Back to history