LGenerics: what changed

Revision 3 to 4. 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		-	~~`$.store.book[?@.price < 10].title`~~
	825	+	```text
	826	+	$.store.book[?@.price < 10].title
	827	+	```
826	828
827	829		or
828	830
829		-	~~`$['store']['book'][?@['price'] < 10]['title']`~~
	831	+	```text
	832	+	$['store']['book'][?@['price'] < 10]['title']
	833	+	```
830	834
831	835		or
832	836
833		-	~~`$["store"]["book"][?@["price"] < 10]["title"]`~~
	837	+	```text
	838	+	$["store"]["book"][?@["price"] < 10]["title"]
	839	+	```
834	840
835	841		These are just different ways of writing a query to select book titles which price is less than 10.
836	842
837	843		#### Syntax
838	844
839	845		The implementation of JSONPath in LGenerics tries to follow the syntax described in the [RFC 9535](https://www.rfc-editor.org/rfc/rfc9535).
840	846
841	847		Any query starts with \$ sign followed by some (possibly zero) number of segments, leading and trailing spaces are not allowed.
842	848
843	849		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	850
845	851		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	852
847	853		\| Element \| Descrition \|
848	854		\|----\|----\|
849	855		\| \$ \| root node identifier (query argument) \|
850	856		\| @ \| current node identifier \|
851	857		\| \[\<selectors\>\] \| child segment: selects zero or more children of a node; contains one or more selectors, separated by commas \|
852	858		\| .name \| shorthand for \['name'\] or \["name"\] \|
853	859		\| .* \| shorthand for \[*\] \|
854	860		\| ..\[\<selectors\>\] \| descendant segment: selects zero or more descendants of a node; contains one or more selectors, separated by commas \|
855	861		\| ..name \| shorthand for ..\['name'\] \|
856	862		\| ..* \| shorthand for ..\[*\] \|
857	863		\| 'name' \| name selector: selects a named child of an object \|
858	864		\| * \| wildcard selector: selects all children of a node \|
859	865		\| 7 \| index selector: selects an indexed child of an array (0-based) \|
860	866		\| 0:42:5 \| array slice selector: start:end:step for arrays \|
861	867		\| ?\<logical-expr\> \| filter selector: selects particular children using a logical expression \|
862	868		\| length(@.foo) \| function extension: invokes a function in a filter expression \|
863	869
864	870		Basic syntax elements
865	871
866	872		Index and slice selectors have certain peculiarities:
867	873
868	874		:* `$.book[1]` matches the second book
869	875
870	876		:* `$.book[-1]` matches the last book
871	877
872	878		:* `$.book[2:]` matches the third and all following books
873	879
874	880		:* `$.book[-2:]` matches the last two books
875	881
876	882		:* `$.book[:2]` matches the first two books
877	883
878	884		:* `$.book[::]` matches all books
879	885
880	886		:* `$.book[::-1]` matches all books in reverse order
881	887
882	888		The filter selector is a logical expression containing logical operators, comparison operators, and function calls.
883	889
884	890		\| Precedence \| Operator type \| Syntax \|
885	891		\|------------\|---------------\|--------------------------\|
886	892		\| 5 \| Grouping \| ( ... ) \|
887	893		\| 4 \| Logical NOT \| ! \|
888	894		\| 3 \| Relations \| ==, !=, \>, \<, \>=, \<= \|
889	895		\| 2 \| Logical AND \| && \|
890	896		\| 1 \| Logical OR \| \<nowiki\> \|
891	897
892	898		Filter expressions operator precedence
893	899
894	900		It is also highly recommended to implement 5 functions whose syntax and semantics are predefined in the specifications:
895	901
896	902		- `length()`
897	903		- `count()`
898	904		- `match()`
899	905		- `search()`
900	906		- `value()`
901	907
902	908		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	909
904	910		#### Implementation
905	911
906	912		In LGenerics, the JSONPath implementation can be found in the LgJsonPath unit.
907	913
908	914		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	915
910	916		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	917
912	918		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	919
914	920		It is also possible to register user-defined functions, which, however, requires some caution.
915	921
916	922		The specs seems to be realized in its entirety and the implementation is successfully passing the current compliance tests.
917	923
918	924		A small example, JSON document taken from the specifications:
919	925
920	926		``` pascal
921	927		program test_jp;
922	928		{$mode objfpc}{$h+}
923	929		uses
924	930		SysUtils, LgUtils, LgJson, lgJsonPath;
925	931
926	932		const
927	933		Json: string =
928	934		'{ "store": { ' +
929	935		' "book": [ ' +
930	936		' { "category": "reference", ' +
931	937		' "author": "Nigel Rees", ' +
932	938		' "title": "Sayings of the Century",' +
933	939		' "price": 8.95 ' +
934	940		' }, ' +
935	941		' { "category": "fiction", ' +
936	942		' "author": "Evelyn Waugh", ' +
937	943		' "title": "Sword of Honour", ' +
938	944		' "price": 12.99 ' +
939	945		' }, ' +
940	946		' { "category": "fiction", ' +
941	947		' "author": "Herman Melville", ' +
942	948		' "title": "Moby Dick", ' +
943	949		' "isbn": "0-553-21311-3", ' +
944	950		' "price": 8.99 ' +
945	951		' }, ' +
946	952		' { "category": "fiction", ' +
947	953		' "author": "J. R. R. Tolkien", ' +
948	954		' "title": "The Lord of the Rings", ' +
949	955		' "isbn": "0-395-19395-8", ' +
950	956		' "price": 22.99 ' +
951	957		' } ' +
952	958		' ], ' +
953	959		' "bicycle": { ' +
954	960		' "color": "red", ' +
955	961		' "price": 399 ' +
956	962		' } ' +
957	963		' } ' +
958	964		'} ';
959	965
960	966		var
961	967		Doc, CurrNode: specialize TGAutoRef<TJsonNode>;
962	968		Path: IJsonPath;
963	969		List: TJpNodeList;
964	970		Node: TJpNode;
965	971		begin
966	972		if not Doc.Instance.Parse(Json) then begin
967	973		WriteLn('Oops, failed to parse document');
968	974		Halt;
969	975		end;
970	976
971	977		if JpParseQuery('$..author', Path) then begin
972	978		WriteLn('All authors: ');
973	979		List := Path.Match(Doc.Instance);
974	980		for Node in List do begin
975	981		CurrNode.Instance.Parse(Node.AsJson);
976	982		WriteLn(CurrNode.Instance.FormatJson(DefaultJsonFmtStyle, 2));
977	983		end;
978	984		WriteLn;
979	985		end;
980	986
981	987		if JpParseQuery('$..[?@.isbn]', Path) then begin
982	988		WriteLn('Anything that has an ISBN:');
983	989		List := Path.Match(Doc.Instance);
984	990		for Node in List do begin
985	991		CurrNode.Instance.Parse(Node.AsJson);
986	992		WriteLn(CurrNode.Instance.FormatJson(DefaultJsonFmtStyle, 2));
987	993		end;
988	994		WriteLn;
989	995		end;
990	996
991	997		if JpParseQuery('$..[?@.color == "red"]', Path) then begin
992	998		WriteLn('Anything that is red: ');
993	999		List := Path.Match(Doc.Instance);
994	1000		for Node in List do begin
995	1001		CurrNode.Instance.Parse(Node.AsJson);
996	1002		WriteLn(CurrNode.Instance.FormatJson(DefaultJsonFmtStyle, 2));
997	1003		end;
998	1004		WriteLn;
999	1005		end;
1000	1006
1001	1007		if JpParseQuery('$..[?search(@.title, "[Hh]ono")]', Path) then begin
1002	1008		WriteLn('Anything that contains "Hono" or "hono" in the title: ');
1003	1009		List := Path.Match(Doc.Instance);
1004	1010		for Node in List do begin
1005	1011		CurrNode.Instance.Parse(Node.AsJson);
1006	1012		WriteLn(CurrNode.Instance.FormatJson(DefaultJsonFmtStyle, 2));
1007	1013		end;
1008	1014		end;
1009	1015		end.
1010	1016		```
1011	1017
1012	1018		It prints:
1013	1019
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		-	~~` }`~~
	1020	+	```text
	1021	+	All authors:
	1022	+	{"location": "$['store']['book'][0]['author']", "value": "Nigel Rees"}
	1023	+	{"location": "$['store']['book'][1]['author']", "value": "Evelyn Waugh"}
	1024	+	{"location": "$['store']['book'][2]['author']", "value": "Herman Melville"}
	1025	+	{"location": "$['store']['book'][3]['author']", "value": "J. R. R. Tolkien"}
	1026	+
	1027	+	Anything that has an ISBN:
	1028	+	{
	1029	+	"location": "$['store']['book'][2]",
	1030	+	"value": {
	1031	+	"category": "fiction",
	1032	+	"author": "Herman Melville",
	1033	+	"title": "Moby Dick",
	1034	+	"isbn": "0-553-21311-3",
	1035	+	"price": 8.99
	1036	+	}
	1037	+	}
	1038	+	{
	1039	+	"location": "$['store']['book'][3]",
	1040	+	"value": {
	1041	+	"category": "fiction",
	1042	+	"author": "J. R. R. Tolkien",
	1043	+	"title": "The Lord of the Rings",
	1044	+	"isbn": "0-395-19395-8",
	1045	+	"price": 22.99
	1046	+	}
	1047	+	}
	1048	+
	1049	+	Anything that is red:
	1050	+	{
	1051	+	"location": "$['store']['bicycle']",
	1052	+	"value": {"color": "red", "price": 399}
	1053	+	}
	1054	+
	1055	+	Anything that contains "Hono" or "hono" in the title:
	1056	+	{
	1057	+	"location": "$['store']['book'][1]",
	1058	+	"value": {
	1059	+	"category": "fiction",
	1060	+	"author": "Evelyn Waugh",
	1061	+	"title": "Sword of Honour",
	1062	+	"price": 12.99
	1063	+	}
	1064	+	}
	1065	+	```
1058	1066
1059	1067		## Performance
1060	1068
1061	1069		### Containers
1062	1070
1063	1071		#### Performance of hash maps
1064	1072
1065	1073		There is a [wonderful benchmark](https://www.benibela.de/fpc-map-benchmark_en.html) from BeniBela, which also covers hashmaps from LGenerics.
1066	1074
1067	1075		### Algorithms on arrays/vectors
1068	1076
1069	1077		#### Sorting
1070	1078
1071	1079		(This section is outdated.)
1072	1080
1073	1081		The benchmark sorts 1000000 integers and calculates the number of CPU cycles spent on one element and involves:
1074	1082
1075	1083		- QuickSort_ItemList_Context from unit SortBase (Rtl/SortBase)
1076	1084		- TOrderingArrayUtils.Sort from Fcl-Stl.GArrayUtils (Fcl-Stl)
1077	1085		- TArrayHelper.Sort from Rtl-Generics.Generics.Collections (Rtl-Generics)
1078	1086		- std::sort from libstdc++ (std::sort)
1079	1087		- std::stable_sort from libstdc++ (std::stable_sort)
1080	1088		- TGOrdinalArrayHelper.QuickSort (LG/QuickSort)
1081	1089		- TGOrdinalArrayHelper.IntroSort (LG/IntroSort)
1082	1090		- TGOrdinalArrayHelper.DualPivotQuickSort (LG/DualPivotQuickSort)
1083	1091		- TGOrdinalArrayHelper.PDQSort (LG/PDQSort)
1084	1092		- TGComparableArrayHelper.MergeSort (LG/MergeSort)
1085	1093		- TGComparableTimSort.Sort (LG/TimSort)
1086	1094		- TGOrdinalArrayHelper.Sort (LG/Sort)
1087	1095		- A negative value indicates that the algorithm exhibits quadratic behavior.
1088	1096
1089	1097		![](/wiki-images/a/a7/Sort_bench_1000000.png)
1090	1098
1091	1099		### Algorithms on graphs
1092	1100
1093	1101		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	1102
1095	1103		So, AGraph vs LGenerics:
1096	1104
1097	1105		\| problem \| graph \| AGraph time(ms) \| LGenerics time(ms) \| notes \|
1098	1106		\|----\|----\|----\|----\|----\|
1099	1107		\| BFS traversal \| undirected, V=500000, E=4000000 \| 640 \| 109 \| \|
1100	1108		\| BFS traversal \| directed, V=500000, E=4000000 \| 484 \| 94 \| \|
1101	1109		\| 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	1110		\| Strongly connected components \| directed, V=500000, E=4000000 \| 1060 \| 265 \| \|
1103	1111		\| Single-source shortest path \| undirected, V=500000, E=4000000 \| 3011 \| 842 \| \|
1104	1112		\| Single-source shortest path \| directed, V=500000, E=4000000 \| 2153 \| 718 \| \|
1105	1113		\| Single-pair shortest path \| undirected, V=500000, E=4000000 \| 2777 \| 31 \| \|
1106	1114		\| Single-pair shortest path \| directed, V=500000, E=4000000 \| 1825 \| 47 \| \|
1107	1115		\| Minimum spanning tree \| undirected, V=500000, E=4000000 \| 5974 \| 640 \| \|
1108	1116		\| Maximum flow \| dense, V=1000, E=499500 \| 29499 \| 47 \| \|
1109	1117		\| Maximum flow \| sparse, V=64000, E=512000 \| 3339 \| 63 \| \|
1110	1118		\| Planarity test \| undirected, V=219086, E=657252 \| 1419 \| 172 \| \|
1111	1119		\| Maximum clique \| DIMACS brock200_2.clq, V=200, E=9876 \| 84210 \| 16 \| \|
1112	1120		\| Maximum clique \| DIMACS brock200_4.clq, V=200, E=13089 \| Cancelled(timeout 1 h) \| 312 \| \|
1113	1121
1114	1122		### Algorithms on strings/sequences
1115	1123
1116	1124		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	1125
1118	1126		It seems the C++ version only supports single-byte strings, so only compared to the single-byte version of SimRatioLevEx():
1119	1127
1120	1128		Dataset SimRatioLevEx() token_set_ratio()
1121	1129
1122	1130		Short/big_dist 1154 6440
1123	1131		Short/small_dist 967 3020
1124	1132		Medium/big_dist 811 3450
1125	1133		Medium/small_dist 702 1470
1126	1134		Long/big_dist 1966 15000
1127	1135		Long/small_dist 1061 2250
1128	1136
1129	1137		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	1138
1131	1139		The Go version, on the contrary, always works with Unicode strings:
1132	1140
1133	1141		Dataset SimRatioLevExUtf8() TokenSetRatio()
1134	1142
1135	1143		Short/big_dist 2143 18705
1136	1144		Short/small_dist 1593 2224
1137	1145		Medium/big_dist 1266 15062
1138	1146		Medium/small_dist 853 1742
1139	1147		Long/big_dist 3853 79851
1140	1148		Long/small_dist 1269 3126
1141	1149
1142	1150		Go version: go1.10.4 linux/amd64; FPC-3.3.1-10683-g2a19e152b7 -O3. The benchmark was run on a virtual Linux machine.
1143	1151
1144	1152		### Performance of JSON operations
1145	1153
1146	1154		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	1155
1148	1156		\| description \| FpJson \| JsonTools \| lgJson \| notes \|
1149	1157		\|----\|----\|----\|----\|----\|
1150	1158		\| 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	1159		\| 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	1160		\| 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	1161		\| Search in a moderately sized document using path (750000 repeats), milliseconds \| 8549 \| 5398 \| 873 \| \|
1154	1162		\| Dynamic creation of a small document and reading it as formatted JSON (150000 repeats), milliseconds \| 7597 \| 4150 \| 1903 \| \|
1155	1163		\| Saving a moderate size document to a stream (10000 repeats), milliseconds \| 4820 \| 4587 \| 827 \| \|
1156	1164		\| RFC 8259 compliance test, 295 test files from test/json_testset/testset \| 5 failed \| 23 failed \| all passed \| \|
1157	1165
1158	1166		#### Performance of export to JSON
1159	1167
1160	1168		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	1169
1162	1170		TJSONStreamer.CollectionToJSON() was taken as a reference implementation (FpJsonStreamer for short), other members:
1163	1171
1164	1172		- PdoToJson() with a collection as parameter (PdoCollection);
1165	1173		- PdoToJson() with array as parameter and field name list registration (PdoRecordFieldMap);
1166	1174		- PdoToJson() with array as parameter and custom callback registration (PdoRecordCallback);
1167	1175
1168	1176		Each member exports the data several times (number of attempts is pre-defined), the best time is taken as the result.
1169	1177
1170	1178		The full benchmark code can be found in the folder LGenerics/example/json/json_export_bench.
1171	1179
1172	1180		Results on author's machine:
1173	1181
1174	1182		-------<JSON size 20 KB>-------
1175	1183		FpJsonStreamer......1,045 ms.
1176	1184		Rating: 22,23 MB/s.
1177	1185		PdoCollection.......0,123 ms.
1178	1186		Rating: 164,36 MB/s.
1179	1187		PdoRecordFieldMap...0,089 ms.
1180	1188		Rating: 226,76 MB/s.
1181	1189		PdoRecordCallback...0,057 ms.
1182	1190		Rating: 356,65 MB/s.
1183	1191		-------<JSON size 100 KB>-------
1184	1192		FpJsonStreamer......5,647 ms.
1185	1193		Rating: 20,51 MB/s.
1186	1194		PdoCollection.......0,626 ms.
1187	1195		Rating: 160,7 MB/s.
1188	1196		PdoRecordFieldMap...0,443 ms.
1189	1197		Rating: 226,72 MB/s.
1190	1198		PdoRecordCallback...0,285 ms.
1191	1199		Rating: 352,29 MB/s.
1192	1200		-------<JSON size 1 MB>-------
1193	1201		FpJsonStreamer......80,298 ms.
1194	1202		Rating: 14,34 MB/s.
1195	1203		PdoCollection.......6,552 ms.
1196	1204		Rating: 152,63 MB/s.
1197	1205		PdoRecordFieldMap...4,701 ms.
1198	1206		Rating: 212,71 MB/s.
1199	1207		PdoRecordCallback...3,107 ms.
1200	1208		Rating: 321,85 MB/s.
1201	1209		-------<JSON size 10 MB>-------
1202	1210		FpJsonStreamer......3554,483 ms.
1203	1211		Rating: 3,24 MB/s.
1204	1212		PdoCollection.......71,202 ms.
1205	1213		Rating: 140,57 MB/s.
1206	1214		PdoRecordFieldMap...53,309 ms.
1207	1215		Rating: 187,75 MB/s.
1208	1216		PdoRecordCallback...37,39 ms.
1209	1217		Rating: 267,69 MB/s.
1210	1218		-------<JSON size 50 MB>-------
1211	1219		FpJsonStreamer......84343,47 ms.
1212	1220		Rating: 0,68 MB/s.
1213	1221		PdoCollection.......350,224 ms.
1214	1222		Rating: 142,99 MB/s.
1215	1223		PdoRecordFieldMap...260,963 ms.
1216	1224		Rating: 191,89 MB/s.
1217	1225		PdoRecordCallback...183,328 ms.
1218	1226		Rating: 273,16 MB/s.
1219	1227
1220	1228		#### Performance of JSON Type Definition
1221	1229
1222	1230		Test schema:
1223	1231
1224	1232		``` json
1225	1233		{
1226	1234		"definitions": {
1227	1235		"point": {
1228	1236		"properties": {
1229	1237		"x": {"type": "int32"},
1230	1238		"y": {"type": "int32"}
1231	1239		}
1232	1240		},
1233	1241		"shape": {"enum": ["circle", "ellipce", "rectangle", "rhombus", "triangle"]},
1234	1242		"figure": {
1235	1243		"properties": {
1236	1244		"name": {"type": "string"},
1237	1245		"shape": {"ref": "shape"},
1238	1246		"area": {"type": "float64"},
1239	1247		"center": {"ref": "point"}
1240	1248		}
1241	1249		}
1242	1250		},
1243	1251		"elements": {"ref": "figure"}
1244	1252		}
1245	1253		```
1246	1254
1247	1255		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	1256
1249	1257		Full source code of the test application:
1250	1258
1251	1259		``` pascal
1252	1260		program jtd_test;
1253	1261
1254	1262		{$mode objfpc}{$H+}
1255	1263
1256	1264		uses
1257	1265		Classes, SysUtils, fpJsonRtti, lgJson, lgJsonTypeDef, Figures;
1258	1266
1259	1267		type
1260	1268		{$PUSH}{$M+}
1261	1269		TMyPoint = class
1262	1270		private
1263	1271		FX,
1264	1272		FY: Integer;
1265	1273		published
1266	1274		property x: Integer read FX write FX;
1267	1275		property y: Integer read FY write FY;
1268	1276		end;
1269	1277		{$POP}
1270	1278
1271	1279		TMyFigure = class(TCollectionItem)
1272	1280		private
1273	1281		FArea: Double;
1274	1282		FCenter: TMyPoint;
1275	1283		FName: string;
1276	1284		FShape: TShape;
1277	1285		public
1278	1286		constructor Create(ACollection: TCollection); override;
1279	1287		destructor Destroy; override;
1280	1288		published
1281	1289		property name: string read FName write FName;
1282	1290		property shape: TShape read FShape write FShape;
1283	1291		property area: Double read FArea write FArea;
1284	1292		property center: TMyPoint read FCenter;
1285	1293		end;
1286	1294
1287	1295		constructor TMyFigure.Create(ACollection: TCollection);
1288	1296		begin
1289	1297		inherited Create(ACollection);
1290	1298		FCenter := TMyPoint.Create;
1291	1299		end;
1292	1300
1293	1301		destructor TMyFigure.Destroy;
1294	1302		begin
1295	1303		FCenter.Free;
1296	1304		inherited;
1297	1305		end;
1298	1306
1299	1307		var
1300	1308		s: string;
1301	1309
1302	1310		procedure TestCollection;
1303	1311		var
1304	1312		c: TCollection;
1305	1313		Start, Stop: QWord;
1306	1314		begin
1307	1315		c := TCollection.Create(TMyFigure);
1308	1316		Start := GetTickCount64;
1309	1317		with TJSONDeStreamer.Create(nil) do
1310	1318		try
1311	1319		JSONToCollection(s, c);
1312	1320		finally
1313	1321		Free;
1314	1322		end;
1315	1323		Stop := GetTickCount64;
1316	1324		c.Free;
1317	1325		WriteLn('TJSONDeStreamer.JSONToCollection: ', Stop - Start);
1318	1326		end;
1319	1327
1320	1328		procedure TestJtd;
1321	1329		var
1322	1330		Node: TJsonNode;
1323	1331		Schema: TJtdSchema;
1324	1332		eList: TJtdErrorList;
1325	1333		Figures: TFigureList;
1326	1334		Start, Stop: QWord;
1327	1335		begin
1328	1336		Start := GetTickCount64;
1329	1337		if not TJsonNode.TryParse(s, Node) then begin
1330	1338		WriteLn('Failed to load data');
1331	1339		exit;
1332	1340		end;
1333	1341		Stop := GetTickCount64;
1334	1342		WriteLn('Loading data into TJsonNode: ', Stop - Start);
1335	1343
1336	1344		if not TJtdSchema.TryLoadFromFile('schema.json', Schema) then begin
1337	1345		WriteLn('Failed to load schema');
1338	1346		exit;
1339	1347		end;
1340	1348
1341	1349		Start := GetTickCount64;
1342	1350		if Validate(Node, Schema, eList) <> jvrOk then begin
1343	1351		WriteLn('Failed to validate data');
1344	1352		exit;
1345	1353		end;
1346	1354		Stop := GetTickCount64;
1347	1355		Schema.Free;
1348	1356		WriteLn('TJsonNode data validation: ', Stop - Start);
1349	1357
1350	1358		Start := GetTickCount64;
1351	1359		Figures := TFigureList.ReadJson(Node) as TFigureList;
1352	1360		Stop := GetTickCount64;
1353	1361		Figures.Free;
1354	1362		Node.Free;
1355	1363		WriteLn('Loadind JTD class from TJsonNode: ', Stop - Start);
1356	1364
1357	1365		Start := GetTickCount64;
1358	1366		Figures := TFigureList.ReadJson(s) as TFigureList;
1359	1367		Stop := GetTickCount64;
1360	1368		Figures.Free;
1361	1369		WriteLn('Direct loading of JTD class: ', Stop - Start);
1362	1370		end;
1363	1371
1364	1372		procedure LoadData;
1365	1373		begin
1366	1374		with TStringStream.Create do
1367	1375		try
1368	1376		LoadFromFile('data.json');
1369	1377		s := DataString;
1370	1378		finally
1371	1379		Free;
1372	1380		end;
1373	1381		end;
1374	1382
1375	1383		begin
1376	1384		LoadData;
1377	1385
1378	1386		TestCollection;
1379	1387		TestJtd;
1380	1388
1381	1389		end.
1382	1390		```
1383	1391
1384	1392		On my machine, it prints results like this:
1385	1393
1386	1394		TJSONDeStreamer.JSONToCollection: 5304
1387	1395		Loading data into TJsonNode: 1513
1388	1396		TJsonNode data validation: 1732
1389	1397		Loadind JTD class from TJsonNode: 515
1390	1398		Direct loading of JTD class: 1560
1391	1399
1392	1400		Conclusion: the total validation and loading time of the JTD class is still noticeably better than the TCollection load time (3760 vs 5304).
1393	1401
1394	1402		The direct load time of the JTD class is better than the load time of the TCollection by more than three times.
1395	1403
1396	1404		---
1397	1405		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	1406		Category: JSON
1399	1407		Category: Libraries

Back to history