1 {
2  Test all with:
3      ./runtests --format=plain --suite=TTest_AvgLvlTree
4      ./runtests --format=plain --suite=TTest_AVLTree
5 
6  Test specific with:
7      ./runtests --format=plain --suite=TestAvgLvlTreeAddsDeletes
8      ./runtests --format=plain --suite=TestIndexedAVLTreeAddsDeletes
9      ./runtests --format=plain --suite=TestAVLTreeAddsDeletes
10 }
11 unit TestAvgLvlTree;
12 
13 {$mode objfpc}{$H+}
14 
15 { $DEFINE VerboseTestSequence}
16 
17 interface
18 
19 uses
20   Classes, SysUtils, fpcunit, testglobals, LazLogger,
21   AVL_Tree, // the unit from FPC
22   // Laz_AVL_Tree, the unit copied from FPC when compiling Lazarus for older compilers
23   AvgLvlTree // unit from LazUtils, an extended version
24   ;
25 
26 type
27   { TTest_AvgLvlTree - the LazUtils extensions }
28 
29   TTest_AvgLvlTree = class(TTestCase)
30   private
31     fTreeClass: AvgLvlTree.TAvgLvlTreeClass;
CreateTreenull32     function CreateTree(Args: array of const): AvgLvlTree.TAvgLvlTree;
33     procedure TestSequence(Args: array of const);
34     procedure TestAscendingSequence(InitArgs: array of const; AscSeq: array of const);
35     procedure TestAvgLvlTree;
36   published
37     procedure TestAvgLvlTreeAddsDeletes;
38     procedure TestIndexedAVLTreeAddsDeletes;
39   end;
40 
41   {$IF FPC_FULLVERSION<30101}
42   TAVLTreeClass = class of TAVLTree;
43   {$ENDIF}
44 
45   { TTest_AVLTree - the FPC unit}
46 
47   TTest_AVLTree = class(TTestCase)
48   private
49     fTreeClass: TAVLTreeClass;
CreateTreenull50     function CreateTree(Args: array of const): TAVLTree;
51     procedure TestSequence(Args: array of const);
52     {$IF FPC_FULLVERSION>=30101}
53     procedure TestAscendingSequence(InitArgs: array of const; AscSeq: array of const);
54     {$ENDIF}
55     procedure TestAVLTree;
56   published
57     procedure TestAVLTreeAddsDeletes;
58   end;
59 
60 implementation
61 
62 { TTest_AVLTree }
63 
CreateTreenull64 function TTest_AVLTree.CreateTree(Args: array of const): TAVLTree;
65 var
66   i: Integer;
67   Value: LongInt;
68 begin
69   Result:=fTreeClass.Create;
70   //DebugLn(Result.ReportAsString);
71   Result.ConsistencyCheck;
72 
73   for i:=Low(Args) to high(Args) do begin
74     if Args[i].VType<>vtInteger then continue;
75     Value:=Args[i].vinteger;
76     if Value>0 then begin
77       {$IFDEF VerboseTestSequence}
78       DebugLn(['  add value ',Value]);
79       {$ENDIF}
80       Result.Add({%H-}Pointer(Value));
81     end else begin
82       Value:=-Value;
83       {$IFDEF VerboseTestSequence}
84       debugln(['  remove value ',Value]);
85       {$ENDIF}
86       Result.Remove({%H-}Pointer(Value));
87     end;
88     {$IFDEF VerboseTestSequence}
89     DebugLn(Result.ReportAsString);
90     {$ENDIF}
91     Result.ConsistencyCheck;
92   end;
93 end;
94 
95 procedure TTest_AVLTree.TestSequence(Args: array of const);
96 var
97   Tree: AVL_Tree.TAVLTree;
98 begin
99   Tree:=CreateTree(Args);
100   Tree.Clear;
101   //DebugLn(Tree.ReportAsString);
102   Tree.ConsistencyCheck;
103   Tree.Free;
104 end;
105 
106 {$IF FPC_FULLVERSION>=30101}
107 procedure TTest_AVLTree.TestAscendingSequence(InitArgs: array of const;
108   AscSeq: array of const);
109 var
110   Tree: AVL_Tree.TAVLTree;
111   LastAdded, Succesor: AVL_Tree.TAVLTreeNode;
112   i: Integer;
113   Value: LongInt;
114 begin
115   Tree:=CreateTree(InitArgs);
116 
117   LastAdded:=nil;
118   Succesor:=nil;
119   for i:=Low(AscSeq) to high(AscSeq) do begin
120     if AscSeq[i].VType<>vtInteger then continue;
121     Value:=AscSeq[i].vinteger;
122     {$IFDEF VerboseTestSequence}
123     DebugLn(['  add ascending value ',Value]);
124     {$ENDIF}
125     LastAdded:=Tree.AddAscendingSequence({%H-}Pointer(Value),LastAdded,Succesor);
126     {$IFDEF VerboseTestSequence}
127     DebugLn(Tree.ReportAsString);
128     {$ENDIF}
129     Tree.ConsistencyCheck;
130   end;
131 
132   Tree.Clear;
133   //DebugLn(Tree.ReportAsString);
134   Tree.ConsistencyCheck;
135   Tree.Free;
136 end;
137 {$ENDIF}
138 
139 procedure TTest_AVLTree.TestAVLTree;
140 begin
141   // rotate left
142   TestSequence([]);
143   TestSequence([1]);
144   TestSequence([1,2]);
145   TestSequence([1,2,3]);
146   TestSequence([1,2,3,4]);
147   TestSequence([1,2,3,4,5]);
148   TestSequence([1,2,3,4,5,6]);
149   TestSequence([1,2,3,4,5,6,7,8,9,10]);
150 
151   // rotate right
152   TestSequence([10,9,8,7,6,5,4,3,2,1]);
153 
154   // double rotate right, left
155   TestSequence([5,7,6]);
156 
157   // double rotate left, right
158   TestSequence([5,3,4]);
159 
160   // test deletes
161   TestSequence([1,2,3,-1,-2,-3]);
162   TestSequence([1,2,3,-1,-3,-2]);
163   TestSequence([1,2,3,-2,-1,-3]);
164   TestSequence([1,2,3,-2,-3,-1]);
165   TestSequence([1,2,3,-3,-1,-2]);
166   TestSequence([1,2,3,-3,-2,-1]);
167 
168   {$IF FPC_FULLVERSION>=30101}
169   // test AddAscendingSequence
170   TestAscendingSequence([],[1]);
171   TestAscendingSequence([],[1,2]);
172   TestAscendingSequence([],[1,2,3]);
173   TestAscendingSequence([],[2,1]);
174   TestAscendingSequence([],[3,2,1]);
175   TestAscendingSequence([1],[2,3,4,5]);
176   TestAscendingSequence([2],[1,3,4,5]);
177   TestAscendingSequence([3],[1,2,4,5,6]);
178   TestAscendingSequence([3,4],[1,2,5,6,7]);
179   {$ENDIF}
180 end;
181 
182 procedure TTest_AVLTree.TestAVLTreeAddsDeletes;
183 begin
184   fTreeClass:=AVL_Tree.TAVLTree;
185   TestAVLTree;
186 end;
187 
188 { TTest_AvgLvlTree }
189 
CreateTreenull190 function TTest_AvgLvlTree.CreateTree(Args: array of const): AvgLvlTree.TAvgLvlTree;
191 var
192   i: Integer;
193   Value: LongInt;
194 begin
195   Result:=fTreeClass.Create;
196   //DebugLn(Result.ReportAsString);
197   Result.ConsistencyCheck;
198 
199   for i:=Low(Args) to high(Args) do begin
200     if Args[i].VType<>vtInteger then continue;
201     Value:=Args[i].vinteger;
202     if Value>0 then begin
203       {$IFDEF VerboseTestSequence}
204       DebugLn(['  add value ',Value]);
205       {$ENDIF}
206       Result.Add({%H-}Pointer(Value));
207     end else begin
208       Value:=-Value;
209       {$IFDEF VerboseTestSequence}
210       debugln(['  remove value ',Value]);
211       {$ENDIF}
212       Result.Remove({%H-}Pointer(Value));
213     end;
214     {$IFDEF VerboseTestSequence}
215     DebugLn(Result.ReportAsString);
216     {$ENDIF}
217     Result.ConsistencyCheck;
218   end;
219 end;
220 
221 procedure TTest_AvgLvlTree.TestSequence(Args: array of const);
222 var
223   Tree: AvgLvlTree.TAvgLvlTree;
224 begin
225   Tree:=CreateTree(Args);
226   Tree.Clear;
227   //DebugLn(Tree.ReportAsString);
228   Tree.ConsistencyCheck;
229   Tree.Free;
230 end;
231 
232 procedure TTest_AvgLvlTree.TestAscendingSequence(InitArgs: array of const;
233   AscSeq: array of const);
234 var
235   Tree: AvgLvlTree.TAvgLvlTree;
236   LastAdded, Succesor: AvgLvlTree.TAvgLvlTreeNode;
237   i: Integer;
238   Value: LongInt;
239 begin
240   Tree:=CreateTree(InitArgs);
241 
242   LastAdded:=nil;
243   Succesor:=nil;
244   for i:=Low(AscSeq) to high(AscSeq) do begin
245     if AscSeq[i].VType<>vtInteger then continue;
246     Value:=AscSeq[i].vinteger;
247     {$IFDEF VerboseTestSequence}
248     DebugLn(['  add ascending value ',Value]);
249     {$ENDIF}
250     LastAdded:=Tree.AddAscendingSequence({%H-}Pointer(Value),LastAdded,Succesor);
251     {$IFDEF VerboseTestSequence}
252     DebugLn(Tree.ReportAsString);
253     {$ENDIF}
254     Tree.ConsistencyCheck;
255   end;
256 
257   Tree.Clear;
258   //DebugLn(Tree.ReportAsString);
259   Tree.ConsistencyCheck;
260   Tree.Free;
261 end;
262 
263 procedure TTest_AvgLvlTree.TestAvgLvlTree;
264 begin
265   // rotate left
266   TestSequence([]);
267   TestSequence([1]);
268   TestSequence([1,2]);
269   TestSequence([1,2,3]);
270   TestSequence([1,2,3,4]);
271   TestSequence([1,2,3,4,5]);
272   TestSequence([1,2,3,4,5,6]);
273   TestSequence([1,2,3,4,5,6,7,8,9,10]);
274 
275   // rotate right
276   TestSequence([10,9,8,7,6,5,4,3,2,1]);
277 
278   // double rotate right, left
279   TestSequence([5,7,6]);
280 
281   // double rotate left, right
282   TestSequence([5,3,4]);
283 
284   // test deletes
285   TestSequence([1,2,3,-1,-2,-3]);
286   TestSequence([1,2,3,-1,-3,-2]);
287   TestSequence([1,2,3,-2,-1,-3]);
288   TestSequence([1,2,3,-2,-3,-1]);
289   TestSequence([1,2,3,-3,-1,-2]);
290   TestSequence([1,2,3,-3,-2,-1]);
291 
292   // test AddAscendingSequence
293   TestAscendingSequence([],[1]);
294   TestAscendingSequence([],[1,2]);
295   TestAscendingSequence([],[1,2,3]);
296   TestAscendingSequence([],[2,1]);
297   TestAscendingSequence([],[3,2,1]);
298   TestAscendingSequence([1],[2,3,4,5]);
299   TestAscendingSequence([2],[1,3,4,5]);
300   TestAscendingSequence([3],[1,2,4,5,6]);
301   TestAscendingSequence([3,4],[1,2,5,6,7]);
302 end;
303 
304 procedure TTest_AvgLvlTree.TestAvgLvlTreeAddsDeletes;
305 begin
306   fTreeClass:=AvgLvlTree.TAvgLvlTree;
307   TestAvgLvlTree;
308 end;
309 
310 procedure TTest_AvgLvlTree.TestIndexedAVLTreeAddsDeletes;
311 begin
312   fTreeClass:=AvgLvlTree.TIndexedAVLTree;
313   TestAvgLvlTree;
314 end;
315 
316 initialization
317   AddToLazUtilsTestSuite(TTest_AvgLvlTree);
318   AddToLazUtilsTestSuite(TTest_AVLTree);
319 
320 end.
321 
322