-
-
Notifications
You must be signed in to change notification settings - Fork 3
/
LinkedListArray.pas
2405 lines (2095 loc) · 83.8 KB
/
LinkedListArray.pas
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
{-------------------------------------------------------------------------------
This Source Code Form is subject to the terms of the Mozilla Public
License, v. 2.0. If a copy of the MPL was not distributed with this
file, You can obtain one at http://mozilla.org/MPL/2.0/.
-------------------------------------------------------------------------------}
{===============================================================================
Linked List Array
This unit provides base class (TLinkedListArray) for implementing a simple
doubly-linked list which is completely stored inside an array.
TLinkedListArray class should not be directly instantiated. Instead,
a derived class, which will specialize this base class for a selected type,
should be created.
A specialized class (TIntegerLinkedListArray) with Integer as item type is
implemented and provided as an example.
Version 1.1.1 (2024-05-02)
Last change 2024-05-02
©2018-2024 František Milt
Contacts:
František Milt: frantisek.milt@gmail.com
Support:
If you find this code useful, please consider supporting its author(s) by
making a small donation using the following link(s):
https://www.paypal.me/FMilt
Changelog:
For detailed changelog and history please refer to this git repository:
github.com/TheLazyTomcat/Lib.LinkedListArray
Dependencies:
AuxClasses - github.com/TheLazyTomcat/Lib.AuxClasses
* AuxExceptions - github.com/TheLazyTomcat/Lib.AuxExceptions
AuxTypes - github.com/TheLazyTomcat/Lib.AuxTypes
* BinaryStreamingLite - github.com/TheLazyTomcat/Lib.BinaryStreamingLite
ListSorters - github.com/TheLazyTomcat/Lib.ListSorters
StrRect - github.com/TheLazyTomcat/Lib.StrRect
Library AuxExceptions is required only when rebasing local exception classes
(see symbol LinkedListArray_UseAuxExceptions for details).
BinaryStreamingLite can be replaced by full BinaryStreaming.
Library AuxExceptions might also be required as an indirect dependency.
Indirect dependencies:
SimpleCPUID - github.com/TheLazyTomcat/Lib.SimpleCPUID
UInt64Utils - github.com/TheLazyTomcat/Lib.UInt64Utils
WinFileInfo - github.com/TheLazyTomcat/Lib.WinFileInfo
===============================================================================}
(*******************************************************************************
Not implemented as a generic class because of backward compatibility with
older Delphi.
To create a derived/specialized class from base class, use following template
and replace @ClassName@ with a class identifier and @Type@ with identifier of
used type. Also remember to implement proper comparison function for a chosen
type.
Optional methods are not required to be implemented, but they might be usefull
in some instances (eg. when item contains reference-counted types, pointers
or object references).
== Declaration template ======================================================
--------------------------------------------------------------------------------
@ClassName@ = class(TLinkedListArray)
protected
Function GetItem(ListIndex: TLLAListIndex): @Type@; virtual;
procedure SetItem(ListIndex: TLLAListIndex; Value: @Type@); virtual;
//procedure PayloadInit(Payload: PLLAPayload); override;
//procedure PayloadAdded(Payload: PLLAPayload); override;
//procedure PayloadFinal(Payload: PLLAPayload); override;
//procedure PayloadCopy(SrcPayload,DstPayload: PLLAPayload); override;
Function PayloadCompare(Payload1,Payload2: PLLAPayload): Integer; override;
//Function PayloadEquals(Payload1,Payload2: PLLAPayload): Boolean; override;
//procedure PayloadWrite(Payload: PLLAPayload; Stream: TStream); override;
//procedure PayloadRead(Payload: PLLAPayload; Stream: TStream); override;
public
constructor Create;
Function First: @Type@; reintroduce;
Function Last: @Type@; reintroduce;
Function IndicesOf(Item: @Type@; out ArrayIndex: TLLAArrayIndex; out ListIndex: TLLAListIndex): Boolean; reintroduce;
Function ArrayIndexOf(Item: @Type@): TLLAArrayIndex; reintroduce;
Function ListIndexOf(Item: @Type@): TLLAListIndex; reintroduce;
Function ArrayFind(Item: @Type@; out ArrayIndex: TLLAArrayIndex): Boolean; reintroduce;
Function ListFind(Item: @Type@; out ListIndex: TLLAListIndex): Boolean; reintroduce;
Function Add(Item: @Type@; out ArrayIndex: TLLAArrayIndex): TLLAListIndex; reintroduce; overload;
Function Add(Item: @Type@): TLLAListIndex; reintroduce; overload;
procedure Insert(ListIndex: TLLAListIndex; Item: @Type@); reintroduce;
Function Extract(Item: @Type@): @Type@; reintroduce;
Function Remove(Item: @Type@): Integer; reintroduce;
property Items[ListIndex: TLLAListIndex]: @Type@ read GetItem write SetItem; default;
end;
== Implementation template ====================================================
--------------------------------------------------------------------------------
Function @ClassName@.GetItem(ListIndex: TLLAListIndex): @Type@;
begin
Result := @Type@(Pointer(GetPayloadPtrByListIndex(ListIndex))^);
end;
//------------------------------------------------------------------------------
procedure @ClassName@.SetItem(ListIndex: TLLAListIndex; Value: @Type@);
begin
SetPayloadPtrByListIndex(ListIndex,@Value);
end;
//------------------------------------------------------------------------------
// Method called for each payload that is implicitly (eg. when changing the
// Count property to a higher number) added to the list. It is NOT called when
// payload is added explicitly (e.g. using method Add).
// Payload is filled with zeroes in default implementation.
//procedure @ClassName@.PayloadInit(Payload: PLLAPayload);
//begin
//{$MESSAGE WARN 'Implement payload initialization to suit actual type.'}
//end;
//------------------------------------------------------------------------------
// Method called when a payload is explicitly (ie. using methods Add or Insert)
// added to the list.
// Nothing is done in default implementation.
//procedure @ClassName@.PayloadAdded(Payload: PLLAPayload);
//begin
//{$MESSAGE WARN 'Implement payload addition to suit actual type.'}
//end;
//------------------------------------------------------------------------------
// Method called for each payload that is implicitly (e.g. when changing the
// Count property to a lower number) or explicitly (e.g. using method Delete)
// removed from the list.
// Nothing is done with the payload in default behavior.
//procedure @ClassName@.PayloadFinal(Payload: PLLAPayload);
//begin
//{$MESSAGE WARN 'Implement payload finalization to suit actual type.'}
//end;
//------------------------------------------------------------------------------
// Called when payload is copied to the list from an external source (eg. in
// methods Assign and Append).
// Can be used for example to create copies of objects instead of just copying
// their instance reference.
// Payload is copied without any further processing in default implementation.
//procedure @ClassName@.PayloadCopy(SrcPayload,DstPayload: PLLAPayload);
//begin
//{$MESSAGE WARN 'Implement payload copy to suit actual type.'}
//end;
//------------------------------------------------------------------------------
// This method is called when there is a need to compare two payloads, for
// example when sorting the list.
// Must return positive number when Payload1 is higher/larger than Payload2
// (ie. they are in wrong order), zero when they are equal and negative number
// when Payload1 is lower/smaller than Payload2 (when they are in correct order).
// Has no default implementation.
// This method must be implemented in derived classes!
Function @ClassName@.PayloadCompare(Payload1,Payload2: PLLAPayload): Integer;
begin
{$MESSAGE WARN 'Implement comparison to suit actual type.'}
end;
//------------------------------------------------------------------------------
// Called when two payloads are compared for equality (e.g. when searching for a
// particular item).
// In default implementation, it calls PayloadCompare and when that returns
// zero, payloads are considered to be equal.
//Function @ClassName@.PayloadEquals(Payload1,Payload2: PLLAPayload): Boolean;
//begin
//{$MESSAGE WARN 'Implement equality comparison to suit actual type.'}
//end;
//------------------------------------------------------------------------------
// Called for each item being written to the stream.
// Default implementation direcly writes PayloadSize bytes from the payload
// memory to the stream, with no further processing.
//procedure @ClassName@.PayloadWrite(Payload: PLLAPayload; Stream: TStream);
//begin
//{$MESSAGE WARN 'Implement payload write to suit actual type.'}
//end;
//------------------------------------------------------------------------------
// Method called for each item being read from the stream.
// Default implementation reads PayloadSize bytes directly to the payload
// memory with no further processing.
// If any processing must be done when loading a payload, it must be performed
// here, because PayloadAdded is NOT called.
//procedure @ClassName@.PayloadRead(Payload: PLLAPayload; Stream: TStream);
//begin
//{$MESSAGE WARN 'Implement payload read to suit actual type.'}
//end;
//==============================================================================
constructor @ClassName@.Create;
begin
inherited Create(SizeOf(@Type@));
end;
//------------------------------------------------------------------------------
Function @ClassName@.First: @Type@;
begin
Result := @Type@(Pointer(inherited First)^);
end;
//------------------------------------------------------------------------------
Function @ClassName@.Last: @Type@;
begin
Result := @Type@(Pointer(inherited Last)^);
end;
//------------------------------------------------------------------------------
Function @ClassName@.IndicesOf(Item: @Type@; out ArrayIndex: TLLAArrayIndex; out ListIndex: TLLAListIndex): Boolean;
begin
Result := inherited IndicesOf(@Item,ArrayIndex,ListIndex);
end;
//------------------------------------------------------------------------------
Function @ClassName@.ArrayIndexOf(Item: @Type@): TLLAArrayIndex;
begin
Result := inherited ArrayIndexOf(@Item);
end;
//------------------------------------------------------------------------------
Function @ClassName@.ListIndexOf(Item: @Type@): TLLAListIndex;
begin
Result := inherited ListIndexOf(@Item);
end;
//------------------------------------------------------------------------------
Function @ClassName@.ArrayFind(Item: @Type@; out ArrayIndex: TLLAArrayIndex): Boolean;
begin
Result := inherited ArrayFind(@Item,ArrayIndex);
end;
//------------------------------------------------------------------------------
Function @ClassName@.ListFind(Item: @Type@; out ListIndex: TLLAListIndex): Boolean;
begin
Result := inherited ListFind(@Item,ListIndex);
end;
//------------------------------------------------------------------------------
Function @ClassName@.Add(Item: @Type@; out ArrayIndex: TLLAArrayIndex): TLLAListIndex;
begin
Result := inherited Add(@Item,ArrayIndex);
end;
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Function @ClassName@.Add(Item: @Type@): TLLAListIndex;
begin
Result := inherited Add(@Item);
end;
//------------------------------------------------------------------------------
procedure @ClassName@.Insert(ListIndex: TLLAListIndex; Item: @Type@);
begin
inherited Insert(ListIndex,@Item);
end;
//------------------------------------------------------------------------------
Function @ClassName@.Extract(Item: @Type@): @Type@;
var
TempPtr: PLLAPayload;
begin
TempPtr := inherited Extract(@Item);
If Assigned(TempPtr) then
Result := @Type@(Pointer(TempPtr)^)
else
Result := {$MESSAGE WARN 'Set to some invalid value (eg. 0, nil, '''', ...).'};
end;
//------------------------------------------------------------------------------
Function @ClassName@.Remove(Item: @Type@): TLLAListIndex;
begin
Result := inherited Remove(@Item);
end;
*******************************************************************************)
unit LinkedListArray;
{
LinkedListArray_UseAuxExceptions
If you want library-specific exceptions to be based on more advanced classes
provided by AuxExceptions library instead of basic Exception class, and don't
want to or cannot change code in this unit, you can define global symbol
LinkedListArray_UseAuxExceptions to achieve this.
}
{$IF Defined(LinkedListArray_UseAuxExceptions)}
{$DEFINE UseAuxExceptions}
{$IFEND}
//------------------------------------------------------------------------------
{$IFDEF FPC}
{$MODE ObjFPC}
{$MODESWITCH ClassicProcVars+}
{$DEFINE FPC_DisableWarns}
{$MACRO ON}
{$ENDIF}
{$H+}
interface
uses
SysUtils, Classes,
AuxTypes, AuxClasses{$IFDEF UseAuxExceptions}, AuxExceptions{$ENDIF};
{===============================================================================
Library-specific exceptions
===============================================================================}
type
ELLAException = class({$IFDEF UseAuxExceptions}EAEGeneralException{$ELSE}Exception{$ENDIF});
ELLAInvalidValue = class(ELLAException);
ELLAIncompatibleObject = class(ELLAException);
ELLAIndexError = class(ELLAException);
ELLAArrayIndexOutOfBounds = class(ELLAIndexError);
ELLAListIndexOutOfBounds = class(ELLAIndexError);
{===============================================================================
--------------------------------------------------------------------------------
TLinkedListArray
--------------------------------------------------------------------------------
===============================================================================}
type
TLLAListIndex = Integer;
TLLAArrayIndex = Integer;
TLLAPayload = record end; // zero-size placeholder
PLLAPayload = ^TLLAPayload;
//------------------------------------------------------------------------------
{
Following types are intended mainly for debugging purposes where they are
used for passing of otherwise internal informations.
}
type
TLLAGlobalInfo = record
ItemSize: TMemSize;
MemorySize: TMemSize;
Memory: Pointer;
FirstFree: TLLAArrayIndex;
LastFree: TLLAArrayIndex;
FirstUsed: TLLAArrayIndex;
LastUsed: TLLAArrayIndex;
end;
TLLAItemInfo = record
Prev: TLLAListIndex;
Next: TLLAListIndex;
ListIndex: TLLAListIndex;
ArrayIndex: TLLAArrayIndex;
end;
{===============================================================================
TLinkedListArray - class declaration
===============================================================================}
type
TLinkedListArray = class(TCustomListObject)
protected
fPayloadSize: TMemSize;
fItemSize: TMemSize;
fMemorySize: TMemSize;
fMemory: Pointer;
fCount: Integer;
fUpdateCounter: Integer;
fChanged: Boolean;
fOnChangeEvent: TNotifyEvent;
fOnChangeCallback: TNotifyCallback;
fLoading: Boolean;
fTempPayload: Pointer;
fFirstFree: TLLAArrayIndex;
fLastFree: TLLAArrayIndex;
fFirstUsed: TLLAArrayIndex;
fLastUsed: TLLAArrayIndex;
// getters, setters
Function GetItemPtr_LL(ArrayIndex: TLLAArrayIndex): Pointer; virtual; // does no check index for validity
Function GetItemPtr(ArrayIndex: TLLAArrayIndex): Pointer; virtual;
Function GetPayloadPtrByArrayIndex(ArrayIndex: TLLAArrayIndex): PLLAPayload; virtual;
procedure SetPayloadPtrByArrayIndex(ArrayIndex: TLLAArrayIndex; Value: PLLAPayload); virtual;
Function GetPayloadPtrByListIndex(ListIndex: TLLAListIndex): PLLAPayload; virtual;
procedure SetPayloadPtrByListIndex(ListIndex: TLLAListIndex; Value: PLLAPayload); virtual;
// custom list overrides
Function GetCapacity: Integer; override;
procedure SetCapacity(Value: Integer); override;
Function GetCount: Integer; override;
procedure SetCount(Value: Integer); override;
// payload management
procedure PayloadInit(Payload: PLLAPayload); virtual;
procedure PayloadAdded(Payload: PLLAPayload); virtual;
procedure PayloadFinal(Payload: PLLAPayload); virtual;
procedure PayloadCopy(SrcPayload,DstPayload: PLLAPayload); virtual;
Function PayloadCompare(Payload1,Payload2: PLLAPayload): Integer; virtual;
Function PayloadEquals(Payload1,Payload2: PLLAPayload): Boolean; virtual;
procedure PayloadWrite(Payload: PLLAPayload; Stream: TStream); virtual;
procedure PayloadRead(Payload: PLLAPayload; Stream: TStream); virtual;
// sorting and defragmentation utilities
Function SortCompare(ListIndex1,ListIndex2: Integer): Integer; virtual;
procedure SortExchange(ListIndex1,ListIndex2: Integer); virtual;
Function DefragCompare(Index1,Index2: Integer): Integer; virtual;
procedure DefragExchange(Index1,Index2: Integer); virtual;
// changes
procedure DoChange; virtual;
// initialization/finalization
procedure Initialize(PayloadSize: TMemSize); virtual;
procedure Finalize; virtual;
procedure InitializeAllItems; virtual;
procedure FinalizeAllItems; virtual;
// internals
procedure InternalDecouple(ArrayIndex: TLLAArrayIndex); virtual;
procedure InternalDelete(ArrayIndex: TLLAArrayIndex); virtual;
Function InternalCompatible(List: TLinkedListArray): Boolean; virtual;
procedure InternalReadFromStream(Stream: TStream; Buffered: Boolean); virtual;
public
constructor Create(PayloadSize: TMemSize); overload;
destructor Destroy; override;
// updates
procedure BeginUpdate; virtual;
Function EndUpdate: Integer; virtual;
// indices bounds (LowIndex, HighIndex and CheckIndex are returning/accepting list indices)
Function LowIndex: Integer; override;
Function HighIndex: Integer; override;
Function CheckIndex(Index: Integer): Boolean; override;
Function LowArrayIndex: TLLAArrayIndex; virtual;
Function HighArrayIndex: TLLAArrayIndex; virtual;
Function CheckArrayIndex(ArrayIndex: TLLAArrayIndex): Boolean; virtual;
Function LowListIndex: TLLAListIndex; virtual;
Function HighListIndex: TLLAListIndex; virtual;
Function CheckListIndex(ListIndex: TLLAListIndex): Boolean; virtual;
// indices conversion and manipulation
Function GetArrayIndex(ListIndex: TLLAListIndex): TLLAArrayIndex; virtual;
Function GetListIndex(ArrayIndex: TLLAArrayIndex): TLLAListIndex; virtual;
// previous/next item in the linked list
{
Following will return an array index of previous or next item, where item
can be selected either by its array or list index.
}
Function PreviousFromArrayIndex(ArrayIndex: TLLAArrayIndex): TLLAArrayIndex; virtual;
Function NextFromArrayIndex(ArrayIndex: TLLAArrayIndex): TLLAArrayIndex; virtual;
Function PreviousFromListIndex(ListIndex: TLLAListIndex): TLLAArrayIndex; virtual;
Function NextFromListIndex(ListIndex: TLLAListIndex): TLLAArrayIndex; virtual;
// first/last item
// returns array index of first listed item, -1 when none is listed
Function FirstArrayIndex: TLLAArrayIndex; virtual;
// returns array index of last listed item, -1 when none is listed
Function LastArrayIndex: TLLAArrayIndex; virtual;
Function First: PLLAPayload; virtual;
Function Last: PLLAPayload; virtual;
// searching
Function IndicesOf(Item: PLLAPayload; out ArrayIndex: TLLAArrayIndex; out ListIndex: TLLAListIndex): Boolean; virtual;
Function ArrayIndexOf(Item: PLLAPayload): TLLAArrayIndex; virtual;
Function ListIndexOf(Item: PLLAPayload): TLLAListIndex; virtual;
Function ArrayFind(Item: PLLAPayload; out ArrayIndex: TLLAArrayIndex): Boolean; virtual;
Function ListFind(Item: PLLAPayload; out ListIndex: TLLAListIndex): Boolean; virtual;
// list methods
Function Add(Item: PLLAPayload; out ArrayIndex: TLLAArrayIndex): TLLAListIndex; overload; virtual;
Function Add(Item: PLLAPayload): TLLAListIndex; overload; virtual;
procedure Insert(ListIndex: TLLAListIndex; Item: PLLAPayload); virtual;
procedure Move(SrcListIndex,DstListIndex: TLLAListIndex); virtual;
procedure Exchange(ListIndex1,ListIndex2: TLLAListIndex); virtual;
Function Extract(Item: PLLAPayload): PLLAPayload; virtual; // does not call PayloadFinal
Function Remove(Item: PLLAPayload): TLLAListIndex; virtual;
procedure Delete(ListIndex: TLLAListIndex); virtual;
procedure Clear; virtual;
// list manipulation
procedure Reverse; virtual;
procedure Sort(Reversed: Boolean = False); virtual;
procedure Defragment; virtual;
// list object access
Function IsEqual(List: TLinkedListArray): Boolean; virtual;
procedure Assign(List: TLinkedListArray); virtual;
procedure Append(List: TLinkedListArray); virtual;
{
streaming
Note that the items (their payload) are stored in the order they are present
in the linked list, not by their order in the array.
If parameter Buffered is set to false (default), then items are saved one
by one.
If it is set to true, then entire data stream is constructed in the memory
and then saved as a whole. This might not be possible in case of memory
shortage, that is why this parameter is by default set to false. Also, if
the Stream is a descendant of TCustomMemoryStream, the buffering is not
done as it is assumed the writes/reads goes into memory anyway.
Read/Write methods are only saving/loading the payloads, nothing more.
This, among others, means you have to set count to appropriate number
before doing the read.
Load/Save methods are first storing number of items (Count) and only then
the payloads. When loading, the list is first cleared, then the Count is
set to a stored count and this number of items is then read.
}
procedure WriteToStream(Stream: TStream; Buffered: Boolean = False); virtual;
procedure ReadFromStream(Stream: TStream; Buffered: Boolean = False); virtual;
procedure SaveToStream(Stream: TStream; Buffered: Boolean = False); virtual;
procedure LoadFromStream(Stream: TStream; Buffered: Boolean = False); virtual;
procedure WriteToFile(const FileName: String; Buffered: Boolean = False); virtual;
procedure ReadFromFile(const FileName: String; Buffered: Boolean = False); virtual;
procedure SaveToFile(const FileName: String; Buffered: Boolean = False); virtual;
procedure LoadFromFile(const FileName: String; Buffered: Boolean = False); virtual;
// debugging
procedure DbgGetGlobalInfo(out GlobalInfo: TLLAGlobalInfo); virtual;
Function DbgGetArrayItemInfo(ArrayIndex: TLLAArrayIndex; out ItemInfo: TLLAItemInfo): Boolean; virtual;
Function DbgGetListItemInfo(ListIndex: TLLAListIndex; out ItemInfo: TLLAItemInfo): Boolean; virtual;
Function DbgArrayItemIsUsed(ArrayIndex: TLLAArrayIndex): Boolean; virtual;
// properties
property PayloadSize: TMemSize read fPayloadSize;
property ArrayPointers[ArrayIndex: TLLAArrayIndex]: PLLAPayload read GetPayloadPtrByArrayIndex;
property ListPointers[ListIndex: TLLAListIndex]: PLLAPayload read GetPayloadPtrByListIndex;
property OnChange: TNotifyEvent read fOnChangeEvent write fOnChangeEvent;
property OnChangeEvent: TNotifyEvent read fOnChangeEvent write fOnChangeEvent;
property OnChangeCallback: TNotifyCallback read fOnChangeCallback write fOnChangeCallback;
end;
{===============================================================================
--------------------------------------------------------------------------------
TIntegerLinkedListArray
--------------------------------------------------------------------------------
===============================================================================}
{===============================================================================
TIntegerLinkedListArray - class declaration
===============================================================================}
type
TIntegerLinkedListArray = class(TLinkedListArray)
protected
Function GetItem(ListIndex: TLLAListIndex): Integer; virtual;
procedure SetItem(ListIndex: TLLAListIndex; Value: Integer); virtual;
Function PayloadCompare(Payload1,Payload2: PLLAPayload): Integer; override;
procedure PayloadWrite(Payload: PLLAPayload; Stream: TStream); override;
procedure PayloadRead(Payload: PLLAPayload; Stream: TStream); override;
public
constructor Create;
Function First: Integer; reintroduce;
Function Last: Integer; reintroduce;
Function IndicesOf(Item: Integer; out ArrayIndex: TLLAArrayIndex; out ListIndex: TLLAListIndex): Boolean; reintroduce;
Function ArrayIndexOf(Item: Integer): TLLAArrayIndex; reintroduce;
Function ListIndexOf(Item: Integer): TLLAListIndex; reintroduce;
Function ArrayFind(Item: Integer; out ArrayIndex: TLLAArrayIndex): Boolean; reintroduce;
Function ListFind(Item: Integer; out ListIndex: TLLAListIndex): Boolean; reintroduce;
Function Add(Item: Integer; out ArrayIndex: TLLAArrayIndex): TLLAListIndex; reintroduce; overload;
Function Add(Item: Integer): TLLAListIndex; reintroduce; overload;
procedure Insert(ListIndex: TLLAListIndex; Item: Integer); reintroduce;
Function Extract(Item: Integer): Integer; reintroduce;
Function Remove(Item: Integer): Integer; reintroduce;
property Items[ListIndex: TLLAListIndex]: Integer read GetItem write SetItem; default;
end;
implementation
uses
ListSorters, StrRect, BinaryStreamingLite;
{$IFDEF FPC_DisableWarns}
{$DEFINE FPCDWM}
{$DEFINE W4055:={$WARN 4055 OFF}} // Conversion between ordinals and pointers is not portable
{$DEFINE W5024:={$WARN 5024 OFF}} // Parameter "$1" not used
{$ENDIF}
{===============================================================================
--------------------------------------------------------------------------------
TLinkedListArray
--------------------------------------------------------------------------------
===============================================================================}
{===============================================================================
TLinkedListArray - internals
===============================================================================}
type
TLLAItem = record
Prev: TLLAArrayIndex;
Next: TLLAArrayIndex;
{
Negative ListIndex marks an unused item.
}
ListIndex: TLLAListIndex;
{
ArrayIndex field does not belong to the actual item it is stored in. It
belongs to an item with list index equal to array index of storing item.
This way, a list-array indices map is constructed for fast access when
using list index - when an item of specific list index is requested, its
array index is stored at item whose array index is equal to the requested
list index.
}
ArrayIndex: TLLAArrayIndex;
Payload: TLLAPayload;
end;
PLLAItem = ^TLLAItem;
{===============================================================================
TLinkedListArray - class implementation
===============================================================================}
{-------------------------------------------------------------------------------
TLinkedListArray - protected methods
-------------------------------------------------------------------------------}
Function TLinkedListArray.GetItemPtr_LL(ArrayIndex: TLLAArrayIndex): Pointer;
begin
{$IFDEF FPCDWM}{$PUSH}W4055{$ENDIF}
Result := Pointer(PtrUInt(fMemory) + (PtrUInt(ArrayIndex) * PtrUInt(fItemSize)));
{$IFDEF FPCDWM}{$POP}{$ENDIF}
end;
//------------------------------------------------------------------------------
Function TLinkedListArray.GetItemPtr(ArrayIndex: TLLAArrayIndex): Pointer;
begin
If CheckArrayIndex(ArrayIndex) then
Result := GetItemPtr_LL(ArrayIndex)
else
raise ELLAArrayIndexOutOfBounds.CreateFmt('TLinkedListArray.GetItemPtr: Array index (%d) out of bounds.',[ArrayIndex]);
end;
//------------------------------------------------------------------------------
Function TLinkedListArray.GetPayloadPtrByArrayIndex(ArrayIndex: TLLAArrayIndex): PLLAPayload;
begin
Result := Addr(PLLAItem(GetItemPtr(ArrayIndex))^.Payload);
end;
//------------------------------------------------------------------------------
procedure TLinkedListArray.SetPayloadPtrByArrayIndex(ArrayIndex: TLLAArrayIndex; Value: PLLAPayload);
var
PayloadPtr: PLLAPayload;
begin
PayloadPtr := GetPayloadPtrByArrayIndex(ArrayIndex); // raises exception on invalid index
System.Move(PayloadPtr^,fTempPayload^,fPayloadSize);
System.Move(Value^,PayloadPtr^,fPayloadSize);
If not PayloadEquals(fTempPayload,Value) then
DoChange;
end;
//------------------------------------------------------------------------------
Function TLinkedListArray.GetPayloadPtrByListIndex(ListIndex: TLLAListIndex): PLLAPayload;
begin
If CheckListIndex(ListIndex) then
Result := GetPayloadPtrByArrayIndex(GetArrayIndex(ListIndex))
else
raise ELLAListIndexOutOfBounds.CreateFmt('TLinkedListArray.GetPayloadPtrByListIndex: List index (%d) out of bounds.',[ListIndex]);
end;
//------------------------------------------------------------------------------
procedure TLinkedListArray.SetPayloadPtrByListIndex(ListIndex: TLLAListIndex; Value: PLLAPayload);
begin
If CheckListIndex(ListIndex) then
SetPayloadPtrByArrayIndex(GetArrayIndex(ListIndex),Value)
else
raise ELLAListIndexOutOfBounds.CreateFmt('TLinkedListArray.SetPayloadPtrByListIndex: List index (%d) out of bounds.',[ListIndex]);
end;
//------------------------------------------------------------------------------
Function TLinkedListArray.GetCapacity: Integer;
begin
Result := fMemorySize div fItemSize;
end;
//------------------------------------------------------------------------------
procedure TLinkedListArray.SetCapacity(Value: Integer);
var
OldCapacity: Integer;
i: TLLAArrayIndex;
ItemPtr: PLLAItem;
begin
If Value >= 0 then
begin
If Value <> Capacity then
begin
If Value > Capacity then
begin
// increasing capacity, add new free items
OldCapacity := Capacity;
fMemorySize := TMemSize(Value) * fItemSize;
ReallocMem(fMemory,fMemorySize);
For i := TLLAArrayIndex(OldCapacity) to HighArrayIndex do
with PLLAItem(GetItemPtr_LL(i))^ do
begin
Prev := Pred(i);
Next := Succ(i);
ListIndex := -1;
ArrayIndex := -1;
end;
PLLAItem(GetItemPtr(HighArrayIndex))^.Next := -1;
If not CheckArrayIndex(fFirstFree) then
fFirstFree := OldCapacity;
If CheckArrayIndex(fLastFree) then
begin
PLLAItem(GetItemPtr_LL(fLastFree))^.Next := OldCapacity;
PLLAItem(GetItemPtr(OldCapacity))^.Prev := fLastFree;
end
else PLLAItem(GetItemPtr(OldCapacity))^.Prev := -1;
fLastFree := HighArrayIndex;
end
else
begin
// capacity is decreased, remove existing items
BeginUpdate; // defer change notifications from Defragment
try
{
Defragment ensures that all used items are at the beginning of
the array and that all items are in the order they apear in their
linked lists.
}
Defragment;
If Value < fCount then
begin
// removing some used items
If not fLoading then
For i := HighArrayIndex downto TLLAArrayIndex(Value) do
begin
ItemPtr := PLLAItem(GetItemPtr_LL(i));
If CheckListIndex(ItemPtr^.ListIndex) then
PayloadFinal(Addr(ItemPtr^.Payload));
end;
fMemorySize := TMemSize(Value) * fItemSize;
ReallocMem(fMemory,fMemorySize);
fCount := Value;
If Value > 0 then
PLLAItem(GetItemPtr_LL(HighArrayIndex))^.Next := -1;
// there is no free item anymore
fFirstFree := -1;
fLastFree := -1;
If Value <= 0 then
fFirstUsed := -1;
fLastUsed := HighArrayIndex; // -1 for empty array
DoChange;
end
else
begin
// removing only unused items
fMemorySize := TMemSize(Value) * fItemSize;
ReallocMem(fMemory,fMemorySize);
If Value > 0 then
PLLAItem(GetItemPtr_LL(HighArrayIndex))^.Next := -1;
If Value = fCount then
begin
fFirstFree := -1;
fLastFree := -1;
end
else fLastFree := HighArrayIndex;
end;
finally
EndUpdate;
end;
end;
end;
end
else raise ELLAInvalidValue.CreateFmt('TLinkedListArray.SetCapacity: Invalid capacity (%d).',[Value]);
end;
//------------------------------------------------------------------------------
Function TLinkedListArray.GetCount: Integer;
begin
Result := fCount;
end;
//------------------------------------------------------------------------------
procedure TLinkedListArray.SetCount(Value: Integer);
var
ListIndex: TLLAListIndex;
ArrayIndex: TLLAArrayIndex;
TempIndex: TLLAArrayIndex;
ItemPtr: PLLAItem;
begin
If Value >= 0 then
begin
If Value <> fCount then
begin
If Value > fCount then
begin
// new items will be added
If Value > Capacity then
SetCapacity(Value);
PLLAItem(GetItemPtr(fFirstFree))^.Prev := fLastUsed;
If CheckArrayIndex(fLastUsed) then
PLLAItem(GetItemPtr_LL(fLastUsed))^.Next := fFirstFree;
If not CheckArrayIndex(fFirstUsed) then
fFirstUsed := fFirstFree;
ListIndex := TLLAListIndex(fCount);
ArrayIndex := fFirstFree;
repeat
ItemPtr := PLLAItem(GetItemPtr_LL(ArrayIndex));
ItemPtr^.ListIndex := ListIndex;
PLLAItem(GetItemPtr_LL(TLLAArrayIndex(ListIndex)))^.ArrayIndex := ArrayIndex;
If not fLoading then
PayloadInit(Addr(ItemPtr^.Payload));
fLastUsed := ArrayIndex;
ArrayIndex := ItemPtr^.Next;
fFirstFree := ArrayIndex;
Inc(ListIndex);
until ListIndex >= Value;
PLLAItem(GetItemPtr(fLastUsed))^.Next := -1;
If CheckArrayIndex(fFirstFree) then
PLLAItem(GetItemPtr_LL(fFirstFree))^.Prev := -1
else
fLastFree := -1;
end
else
begin
// items will be removed
If CheckArrayIndex(fLastFree) then
PLLAItem(GetItemPtr_LL(fLastFree))^.Next := fLastUsed;
If not CheckArrayIndex(fFirstFree) then
fFirstFree := fLastUsed;
ListIndex := HighListIndex;
ArrayIndex := fLastUsed;
repeat
ItemPtr := PLLAItem(GetItemPtr_LL(ArrayIndex));
If not fLoading then
PayloadFinal(Addr(ItemPtr^.Payload));
PLLAItem(GetItemPtr_LL(TLLAArrayIndex(ListIndex)))^.ArrayIndex := -1;
ItemPtr^.ListIndex := -1;
TempIndex := fLastFree;
fLastFree := ArrayIndex;
ArrayIndex := ItemPtr^.Prev;
ItemPtr^.Prev := TempIndex;
ItemPtr^.Next := ArrayIndex;
fLastUsed := ArrayIndex;
Dec(ListIndex);
until ListIndex < Value;
PLLAItem(GetItemPtr(fLastFree))^.Next := -1;
If CheckArrayIndex(fLastUsed) then
PLLAItem(GetItemPtr_LL(fLastUsed))^.Next := -1
else
fFirstUsed := -1;
end;
fCount := Value;
DoChange;
end;
end
else raise ELLAInvalidValue.CreateFmt('TLinkedListArray.SetCount: Invalid count (%d).',[Value]);
end;
//------------------------------------------------------------------------------
procedure TLinkedListArray.PayloadInit(Payload: PLLAPayload);
begin
FillChar(Payload^,fPayloadSize,0);
end;
//------------------------------------------------------------------------------
{$IFDEF FPCDWM}{$PUSH}W5024{$ENDIF}
procedure TLinkedListArray.PayloadAdded(Payload: PLLAPayload);
begin
// nothing to do here
end;
{$IFDEF FPCDWM}{$POP}{$ENDIF}
//------------------------------------------------------------------------------
{$IFDEF FPCDWM}{$PUSH}W5024{$ENDIF}
procedure TLinkedListArray.PayloadFinal(Payload: PLLAPayload);
begin
// nothing to do here
end;
{$IFDEF FPCDWM}{$POP}{$ENDIF}
//------------------------------------------------------------------------------
procedure TLinkedListArray.PayloadCopy(SrcPayload,DstPayload: PLLAPayload);
begin
System.Move(SrcPayload^,DstPayload^,fPayloadSize);
end;
//------------------------------------------------------------------------------
Function TLinkedListArray.PayloadCompare(Payload1,Payload2: PLLAPayload): Integer;
begin
{$IFDEF FPCDWM}{$PUSH}W4055{$ENDIF}
If PtrUInt(Payload1) < PtrUInt(Payload2) then
Result := -1
else If PtrUInt(Payload1) > PtrUInt(Payload2) then
Result := +1
else
Result := 0;
{$IFDEF FPCDWM}{$POP}{$ENDIF}
end;
//------------------------------------------------------------------------------
Function TLinkedListArray.PayloadEquals(Payload1,Payload2: PLLAPayload): Boolean;
begin
Result := PayloadCompare(Payload1,Payload2) = 0;
end;
//------------------------------------------------------------------------------
procedure TLinkedListArray.PayloadWrite(Payload: PLLAPayload; Stream: TStream);
begin
Stream.WriteBuffer(Payload^,fPayloadSize);
end;
//------------------------------------------------------------------------------
procedure TLinkedListArray.PayloadRead(Payload: PLLAPayload; Stream: TStream);
begin
Stream.ReadBuffer(Payload^,fPayloadSize);
end;
//------------------------------------------------------------------------------
Function TLinkedListArray.SortCompare(ListIndex1,ListIndex2: Integer): Integer;
begin
Result := PayloadCompare(GetPayloadPtrByListIndex(TLLAListIndex(ListIndex1)),
GetPayloadPtrByListIndex(TLLAListIndex(ListIndex2)));
end;
//------------------------------------------------------------------------------
procedure TLinkedListArray.SortExchange(ListIndex1,ListIndex2: Integer);
begin
Exchange(TLLAListIndex(ListIndex1),TLLAListIndex(ListIndex2));
end;
//------------------------------------------------------------------------------
Function TLinkedListArray.DefragCompare(Index1,Index2: Integer): Integer;
var
Item1Ptr: PLLAItem;
Item2Ptr: PLLAItem;
begin
Item1Ptr := GetItemPtr_LL(TLLAArrayIndex(Index1));
Item2Ptr := GetItemPtr_LL(TLLAArrayIndex(Index2));
If Item1Ptr^.ListIndex < Item2Ptr^.ListIndex then
Result := -1
else If Item1Ptr^.ListIndex > Item2Ptr^.ListIndex then
Result := +1
else
Result := 0;
end;
//------------------------------------------------------------------------------
procedure TLinkedListArray.DefragExchange(Index1,Index2: Integer);
var
Item1Ptr,Item2Ptr: PLLAItem;
Temp: TLLAArrayIndex;
begin
If Index1 <> Index2 then
begin
Item1Ptr := GetItemPtr_LL(TLLAArrayIndex(Index1));
Item2Ptr := GetItemPtr_LL(TLLAArrayIndex(Index2));
// exchange indices
Temp := Item1Ptr^.ListIndex;
Item1Ptr^.ListIndex := Item2Ptr^.ListIndex;
Item2Ptr^.ListIndex := Temp;
// exchange data
System.Move(Item1Ptr^.Payload,fTempPayload^,fPayloadSize);
System.Move(Item2Ptr^.Payload,Item1Ptr^.Payload,fPayloadSize);
System.Move(fTempPayload^,Item2Ptr^.Payload,fPayloadSize);
end;
end;