-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathtpl_coll_vector.inc
390 lines (339 loc) · 13.4 KB
/
tpl_coll_vector.inc
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
(*
Template vector collection
(C) George Bakhtadze
Usage:
uses template;
type
_VectorValueType = <some type>;
// Optional search type if Find() method is needed
[_VectorSearchType = <some type>;]
{$MESSAGE 'Instantiating TIntegerVector interface'}
{$I tpl_coll_vector.inc}
T<xxx>Vector = _GenVector;
implementation
// Optional equals function:
[function _VectorEquals(const v1, v2: _VectorValueType): Boolean;
begin
Result := v1 = v2;
end;]
// Search function if search type was specified:
[function _VectorFound(const v: _VectorValueType; const Pattern: _VectorSearchType): Boolean;
begin
Result := ...
end;]
// a compiler message with explanation which type is being instantiated would be very helpful:
{$MESSAGE 'Instantiating TIntegerVector'}
{$I tpl_coll_vector.inc}
Some options can be specified in _VectorOptions. See template.TDataStructureOption documentaion.
*)
{$IFNDEF _VECTORIMPL} // Interface
{$IFDEF _IDE_PARSER_}
unit tpl_coll_vector;
interface
uses template;
type
{$ENDIF}
{$IF Declared(_VectorOptions)}
{$I tpl_coll_vector_opt.inc}
{$IFEND}
{$IF not Declared(__CollectionIndexType)}
__CollectionIndexType = Integer;
{$IFEND}
{$I _T.inc} = _VectorValueType;
{$IF not Declared(_PVectorValueType)}
_PVectorValueType = ^_VectorValueType;
{$IFEND}
_VectorValueArray = array[0..0] of _VectorValueType;
_PVectorValuesType = ^_VectorValueArray;
// Vector for each delegate
_VectorDelegate = function(const e: _VectorValueType; Data: Pointer): Boolean of object;
{$I _Dg.inc} = _VectorDelegate;
// Vector for each delegate
_VectorCallback = function(const e: _VectorValueType; Data: Pointer): Boolean;
{$I _Cb.inc} = _VectorCallback;
_IGenVector = interface
{$IFDEF TPL_HINTS}{$MESSAGE 'Instantiating _IGenVector interface for a template vector type'}{$ENDIF}
{$I tpl_coll_list.inc}
end;
// Advance template type instance counter to reuse it in other template collection classes
{$DEFINE _GEN_CNT_ADV}
{$I _T.inc}
// Generic vector template. Unit which use this inclde should use template unit also.
_GenVector = class {$IF Declared(TTemplateInterface)}(TTemplateInterface, _IGenVector){$IFEND}
{$IFDEF HAS_STRICT}strict{$ENDIF} protected
// Values container
FValues: _PVectorValuesType;
// Current capacity of the vector
FCapacity,
// Number of entries
FSize: __CollectionIndexType;
procedure SetValue(const Index: __CollectionIndexType; const e: _VectorValueType); {$I inline.inc}
procedure SetCapacity(const ACapacity: __CollectionIndexType);
public
constructor Create(); overload;
constructor Create(const Capacity: __CollectionIndexType); overload;
constructor Create(const arr: array of _VectorValueType); overload;
destructor Destroy(); override;
// Increases the capacity of the list to ensure that it can hold at least the number of elements specified
procedure EnsureCapacity(const ASize: __CollectionIndexType); {$I inline.inc}
{ Collection interface }
// Returns the number of elements in the collection
function GetSize(): __CollectionIndexType; {$I inline.inc}
// Sets the number of elements in the collection
procedure SetSize(const ASize: __CollectionIndexType);
// Returns True if the collection contains no elements
function IsEmpty(): Boolean; {$I inline.inc}
// Returns True if the collection contains the specified element
function Contains(const e: _VectorValueType): Boolean;
// Calls the delegate for each element in the collection
procedure ForEach(Delegate: _VectorDelegate; Data: Pointer); overload;
// Calls the delegate for each element in the collection
procedure ForEach(Callback: _VectorCallback; Data: Pointer); overload;
{$IF Declared(_VectorSearchType)}
// Searches for element which satisfies the condition _VectorFound(element, Pattern) and returns its index or -1 if no such element.
function Find(const Pattern: _VectorSearchType): __CollectionIndexType;
// Searches for element which satisfies the condition _VectorFound(element, Pattern) starting from last one and returns its index or -1 if no such element.
function FindLast(const Pattern: _VectorSearchType): __CollectionIndexType;
{$IFEND}
// Appends the element as the last element of the vector and returns True
function Add(const e: _VectorValueType): Boolean; {$I inline.inc}
{/ Removes the specified element from the collection.
Returns True if the collection contained the element./}
function Remove(const e: _VectorValueType): Boolean;
// Removes all elements from the collection
procedure Clear(); {$I inline.inc}
// Number of elements
property Size: __CollectionIndexType read FSize write SetSize;
{ List interface }
{/ Returns the element at the specified position in the list.
Throws an error on invalid index if dsRangeCheck was included in the list options before instantiation. }
function Get(const Index: __CollectionIndexType): _VectorValueType; {$I inline.inc}
{/ Returns the address of the element at the specified position in the list.
Throws an error on invalid index if dsRangeCheck was included in the list options before instantiation. }
function GetPtr(const Index: __CollectionIndexType): _PVectorValueType; {$I inline.inc}
{/ Replaces the element at the specified position in the list with the specified element.
Returns the element previously at the specified position.
Throws an error on invalid index if dsRangeCheck was included in the list options when instantiation. }
function Put(const Index: __CollectionIndexType; const e: _VectorValueType): _VectorValueType; {$I inline.inc}
{/ Inserts the element at the specified position in the list shifting the element currently at that
position (if any) and any subsequent elements to the right.
Throws an error on invalid index if dsRangeCheck was included in the list options when instantiation. }
procedure Insert(const Index: __CollectionIndexType; const e: _VectorValueType);
{/ Removes the element at the specified position in the list shifting any subsequent elements
to the left.
Returns the element that was removed from the list. }
function RemoveBy(const Index: __CollectionIndexType): _VectorValueType; {$I inline.inc}
{/ Returns the index of the first occurrence of the specified element in the list,
or -1 if the list does not contain the element. }
function IndexOf(const e: _VectorValueType): __CollectionIndexType; {$I inline.inc}
{/ Returns the index of the last occurrence of the specified element in the list,
or -1 if the list does not contain the element. }
function LastIndexOf(const e: _VectorValueType): __CollectionIndexType; {$I inline.inc}
// Values retrieved by index
property Values[const Index: __CollectionIndexType]: _VectorValueType read Get write SetValue; default;
// Pointer to values retrieved by index
property ValuesPtr[const Index: __CollectionIndexType]: _PVectorValueType read GetPtr;
// Number of elements which the collection able to hold without memory allocations
property Capacity: __CollectionIndexType read FCapacity write SetCapacity;
end;
{$DEFINE _VECTORIMPL}
{$IFDEF _IDE_PARSER_}{$DEFINE _IDE_DISABLE_CONDITIONALS_}{$ENDIF}
{$ELSE _VECTORIMPL}
{$IFDEF _IDE_PARSER_}{$UNDEF _IDE_DISABLE_CONDITIONALS_}{$ENDIF}
{$IFDEF _IDE_PARSER_}
implementation
{$ENDIF _IDE_PARSER_}
{$Q-}
{$R-}
{$IF not Declared(_VectorDefaultCapacity)}
const _VectorDefaultCapacity = 16;
{$IFEND}
{$IF not Declared(_VectorCapacityStep)}
const _VectorCapacityStep = 16;
{$IFEND}
procedure _GenVector.SetValue(const Index: __CollectionIndexType; const e: _VectorValueType);
begin
{$IFDEF _RANGECHECK}
if (Index < 0) or (Index >= FSize) then Assert(False, 'Range check error');
{$ENDIF}
FValues^[Index] := e;
end;
procedure _GenVector.SetCapacity(const ACapacity: __CollectionIndexType);
{$IFNDEF _NO_INIT_NEEDED}
var OldCapacity: __CollectionIndexType;
{$ENDIF}
begin
{$IFNDEF _NO_INIT_NEEDED}
OldCapacity := FCapacity;
{$ENDIF}
FCapacity := ACapacity;
{$IFNDEF _NO_INIT_NEEDED}
if OldCapacity > FCapacity then
Finalize(FValues^[FCapacity], OldCapacity - FCapacity);
{$ENDIF}
ReallocMem(FValues, Ord(FCapacity) * SizeOf(_VectorValueType));
{$IFNDEF _NO_INIT_NEEDED}
if OldCapacity < FCapacity then
FillChar(FValues^[OldCapacity], (FCapacity - OldCapacity) * SizeOf(_VectorValueType), 0);
{$ENDIF}
if FSize > FCapacity then
FSize := FCapacity;
end;
constructor _GenVector.Create();
begin
Create(_VectorDefaultCapacity);
end;
constructor _GenVector.Create(const Capacity: __CollectionIndexType);
begin
inherited Create();
SetCapacity(Capacity);
end;
constructor _GenVector.Create(const arr: array of _VectorValueType);
var i: Integer;
begin
FSize := Length(arr);
SetCapacity(FSize);
for i := 0 to FCapacity-1 do
FValues^[i] := arr[i];
end;
destructor _GenVector.Destroy();
begin
SetCapacity(0);
FValues := nil;
inherited;
end;
function __MaxI(const V1, V2: __CollectionIndexType): __CollectionIndexType; {$I inline.inc}
begin
Result := V1 * Ord(V1 >= V2) + V2 * Ord(V1 < V2);
end;
procedure _GenVector.EnsureCapacity(const ASize: __CollectionIndexType);
begin
if ASize > FCapacity then SetCapacity(__MaxI(ASize, FCapacity + _VectorCapacityStep));
Assert(FCapacity >= ASize, 'Capacity low');
end;
function _GenVector.GetSize(): __CollectionIndexType;
begin
Result := FSize;
end;
procedure _GenVector.SetSize(const ASize: __CollectionIndexType);
begin
EnsureCapacity(ASize);
FSize := ASize;
end;
function _GenVector.IsEmpty(): Boolean;
begin
Result := FSize = 0;
end;
function _GenVector.Contains(const e: _VectorValueType): Boolean;
begin
Result := IndexOf(e) >= 0;
end;
procedure _GenVector.ForEach(Delegate: _VectorDelegate; Data: Pointer);
var i: Integer;
begin
for i := 0 to FSize-1 do Delegate(FValues^[i], Data);
end;
procedure _GenVector.ForEach(Callback: _VectorCallback; Data: Pointer);
var i: Integer;
begin
for i := 0 to FSize-1 do Callback(FValues^[i], Data);
end;
{$IF Declared(_VectorSearchType)}
function _GenVector.Find(const Pattern: _VectorSearchType): __CollectionIndexType;
begin
Result := 0;
while (Result < FSize) do
if _VectorFound(FValues^[Result], Pattern) then Break else Inc(Result);
if Result >= FSize then Result := -1;
end;
function _GenVector.FindLast(const Pattern: _VectorSearchType): __CollectionIndexType;
begin
Result := FSize-1;
while (Result >= 0) do
if _VectorFound(FValues^[Result], Pattern) then Break else Dec(Result);
end;
{$IFEND}
function _GenVector.Add(const e: _VectorValueType): Boolean;
begin
EnsureCapacity(FSize+1);
FValues^[FSize] := e;
Result := True;
Inc(FSize);
end;
function _GenVector.Remove(const e: _VectorValueType): Boolean;
var ind: __CollectionIndexType;
begin
ind := IndexOf(e);
Result := ind >= 0;
if Result then RemoveBy(ind);
end;
// Removes all elements from the collection
procedure _GenVector.Clear();
begin
FSize := 0;
end;
function _GenVector.Get(const Index: __CollectionIndexType): _VectorValueType;
begin
{$IFDEF _RANGECHECK}
if (Index < 0) or (Index >= FSize) then Assert(False, 'Range check error');
{$ENDIF}
Result := FValues^[Index];
end;
function _GenVector.GetPtr(const Index: __CollectionIndexType): _PVectorValueType;
begin
{$IFDEF _RANGECHECK}
if (Index < 0) or (Index >= FSize) then Assert(False, 'Range check error');
{$ENDIF}
Result := @FValues^[Index];
end;
function _GenVector.Put(const Index: __CollectionIndexType; const e: _VectorValueType): _VectorValueType;
begin
Result := Get(Index);
SetValue(index, e);
end;
procedure _GenVector.Insert(const Index: __CollectionIndexType; const e: _VectorValueType);
var i: __CollectionIndexType;
begin
{$IFDEF _RANGECHECK}
if (Index < 0) or (Index >= FSize) then Assert(False, 'Range check error');
{$ENDIF}
EnsureCapacity(FSize+1);
for i := FSize-1 downto Index+1 do
FValues^[i] := FValues^[i-1];
FValues[Index] := e;
Inc(FSize);
end;
function _GenVector.RemoveBy(const Index: __CollectionIndexType): _VectorValueType;
var i: __CollectionIndexType;
begin
{$IFDEF _RANGECHECK}
if (Index < 0) or (Index >= FSize) then Assert(False, 'Range check error');
{$ENDIF}
Result := FValues^[Index];
for i := Index to FSize-2 do
FValues^[i] := FValues^[i+1];
Dec(FSize);
end;
function _GenVector.IndexOf(const e: _VectorValueType): __CollectionIndexType;
begin
Result := 0;
while (Result < FSize) do
{$IF Declared(_VectorEquals)}
if _VectorEquals(FValues^[Result], e) then Break else Inc(Result);
{$ELSE}
if (FValues^[Result] = e) then Break else Inc(Result);
{$IFEND}
if Result >= FSize then Result := -1;
end;
function _GenVector.LastIndexOf(const e: _VectorValueType): __CollectionIndexType;
begin
Result := FSize-1;
while (Result >= 0) do
{$IF Declared(_VectorEquals)}
if _VectorEquals(FValues^[Result], e) then Break else Dec(Result);
{$ELSE}
if (FValues^[Result] = e) then Break else Dec(Result);
{$IFEND}
end;
{$UNDEF _VECTORIMPL}
{$ENDIF _VECTORIMPL}