- Notifications
You must be signed in to change notification settings - Fork 19
Expand file tree
/
Copy pathStackSet.pas
More file actions
Latest commit
192 lines (169 loc) · 5.1 KB
/
Copy pathStackSet.pas
File metadata and controls
192 lines (169 loc) · 5.1 KB
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
unit StackSet;
interface
type
TSet<T: record> = record
privateconst
NoOfElements = ((SizeOf(T) shl8) div32);
publictype
TSetArray = array[0 .. 1] of integer;
TByteSet = setof byte;
private
FStorage: {packed}array[0 .. 31] of T;
{TODO -oJB -cGeneralization : Cater for SizeOf(T) = 3 etc}
functionGetItem(index: integer): integer; inline;
procedureSetItem(index: integer; constValue: integer); inline;
functionIndex(const A: T): integer; inline; //class functions don't get inlined
functionMask(const A: T): integer; inline;
property Item[index: integer]: integer read GetItem write SetItem;
public
classoperator NotEqual(const A, B: TSet<T>): boolean; inline;
classoperator LessThanOrEqual(const A, B: TSet<T>): boolean; inline;
classoperator Subtract(const A, B: TSet<T>): TSet<T>; inline;
classoperatorin (const A: T; const B: TSet<T>): boolean; inline;
classoperator Add(const A: TSet<T>; const B: T): TSet<T>;
classoperator Add(const A, B: TSet<T>): TSet<T>;
classoperator Subtract(const A: TSet<T>; const B: T): TSet<T>;
classoperator Multiply(const A, B: TSet<T>): TSet<T>;
classoperator Equal(const A, B: TSet<T>): boolean;
classoperator GreaterThanOrEqual(const A, B: TSet<T>): boolean;
classoperator Implicit(const [ref] A: TSetArray): TSet<T>;
classoperator Implicit(const A: TByteSet): TSet<T>;
classfunctionCreate<C>(const A: C): TSet<T>; inline; static;
end;
implementation
uses
SysUtils;
{ TSet<T> }
functionTSet<T>.GetItem(index: integer): integer;
begin
Result:= TSetArray((@Self.FStorage)^)[index];
end;
procedureTSet<T>.SetItem(index: integer; constValue: integer);
begin
TSetArray((@self.FStorage)^)[index]:= Value;
end;
functionTSet<T>.Index(const A: T): integer;
begin
if SizeOf(A) = SizeOf(byte) thenbegin
//256 elements, 32 bytes, 8 integers
Result:= byte((@A)^) div32;
endelseif SizeOf(A) = SizeOf(Word) thenbegin
//64K elements, 16 integers
Result:= word((@A)^) div32;
endelseif SizeOf(A) = 3thenbegin
Result:= (Integer((@A)^) and $00FFFFFF) div32;
endelseif SizeOf(A) = SizeOf(Integer) thenbegin
Result:= Integer((@A)^) div32;
endelseif SizeOf(A) = SizeOf(NativeInt) thenbegin
Result:= NativeInt((@A)^) div32;
end
else raise Exception.Create('Set to large');
end;
functionTSet<T>.Mask(const A: T): integer;
begin
if SizeOf(A) = SizeOf(byte) thenbegin
//256 elements, 32 bytes, 8 integers
Result:= byte((@A)^) and31;
endelseif SizeOf(A) = SizeOf(Word) thenbegin
//64K elements, 16 integers
Result:= word((@A)^) and31;
endelseif SizeOf(A) in [3,4] thenbegin
Result:= Integer((@A)^) and31
endelseif SizeOf(A) = SizeOf(NativeInt) thenbegin
Result:= NativeInt((@A)^) and31;
end
else raise Exception.Create('Set to large');
Result:= 1shl Result;
end;
classoperator TSet<T>.Subtract(const A, B: TSet<T>): TSet<T>;
begin
Result:= A * B;
end;
classoperator TSet<T>.NotEqual(const A, B: TSet<T>): boolean;
begin
Result:= not(A = B);
end;
classoperator TSet<T>.LessThanOrEqual(const A, B: TSet<T>): boolean;
begin
Result:= B >= A;
end;
classoperator TSet<T>.Add(const A: TSet<T>; const B: T): TSet<T>;
var
I, M: integer;
begin
I:= A.Index(B);
M:= A.Mask(B);
Move(A, Result, SizeOf(A));
Result.Item[i]:= Result.Item[i] or M;
end;
classoperator TSet<T>.Add(const A, B: TSet<T>): TSet<T>;
var
i: integer;
begin
for i:= 0to NoOfElements - 1dobegin
Result.Item[i]:= A.Item[i] or B.Item[i];
end;
end;
classfunctionTSet<T>.Create<C>(const A: C): TSet<T>;
begin
Assert(SizeOf(A) <= SizeOf(Result));
if SizeOf(A) < SizeOf(Result) then FillChar(Result, SizeOf(Result), #0);
Move(A, Result, SizeOf(A));
end;
classoperator TSet<T>.Equal(const A, B: TSet<T>): boolean;
var
i: integer;
begin
for i:= 0to NoOfElements - 1dobegin
Result:= A.Item[i] = B.Item[i];
ifnot(Result) then exit;
end;
end;
classoperator TSet<T>.GreaterThanOrEqual(const A, B: TSet<T>): boolean;
var
Sum: integer;
i: integer;
begin
//are all elements in B part of A?
//true if (B or A) = A
for i:= 1to NoOfElements - 1dobegin
Sum:= A.Item[i] or B.Item[i];
Result:= (Sum = A.Item[i]);
ifnot(Result) then exit;
end;
end;
classoperator TSet<T>.Implicit(const [ref] A: TSetArray): TSet<T>;
begin
Move(A, Result, SizeOf(A));
end;
classoperator TSet<T>.Implicit(const A: TByteSet): TSet<T>;
begin
if SizeOf(A) < SizeOf(Result) then FillChar(Result, SizeOf(Result),#0);
Move(A, Result, SizeOf(A));
end;
classoperator TSet<T>.in(const A: T; const B: TSet<T>): boolean;
var
I, M: integer;
begin
I:= B.Index(A);
M:= B.Mask(A);
Result:= (B.Item[i] and M) <> 0;
end;
classoperator TSet<T>.Multiply(const A, B: TSet<T>): TSet<T>;
var
i: integer;
begin
for i:= 0to NoOfElements - 1dobegin
Result.Item[i]:= A.Item[i] and B.Item[i];
end;
end;
classoperator TSet<T>.Subtract(const A: TSet<T>; const B: T): TSet<T>;
var
I, M: integer;
begin
I:= A.Index(B);
M:= A.Mask(B);
Move(A, Result, SizeOf(A));
Result.Item[i]:= Result.Item[i] andnot(M);
end;
end.