LGenerics: what changed

Revision 2 to 3. Removed lines have a minus sign; added lines have a plus sign.

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

Back to history