1 {
2     This file is part of the Free Pascal/NewPascal run time library.
3     Copyright (c) 2018 by Maciej Izak (hnb),
4     member of the NewPascal development team (http://newpascal.org)
5 
6     Copyright(c) 2004-2018 DaThoX
7 
8     It contains tests for the Free Pascal generics library
9 
10     See the file COPYING.FPC, included in this distribution,
11     for details about the copyright.
12 
13     This program is distributed in the hope that it will be useful,
14     but WITHOUT ANY WARRANTY; without even the implied warranty of
15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16 
17     Acknowledgment
18 
19     Thanks to Sphere 10 Software (http://sphere10.com) for sponsoring
20     many new types, tests and major refactoring of entire library
21 
22  **********************************************************************}
23 
24 unit tests.generics.trees;
25 
26 {$mode delphi}
27 
28 interface
29 
30 uses
31   fpcunit, testregistry, testutils, tests.generics.utils,
32   Classes, SysUtils, Generics.Collections;
33 
34 type
35 
36   { TTestArrayHelper }
37 
38   { TTestTrees }
39 
40   TTestTrees = class(TTestCollections)
41   published
42     procedure Test_IndexedAVLTree_Add_General;
43     procedure Test_IndexedAVLTree_Add;
44     procedure Test_IndexedAVLTree_Delete;
45     procedure Test_IndexedAVLTree_Items;
46 
47     procedure Test_TAVLTreeMap_Notification;
48   end;
49 
50 implementation
51 
52 type
53   TStringsTree = TIndexedAVLTree<string>;
54   TMapTree = TAVLTreeMap<string, Integer>;
55 
56 { TTestTrees }
57 
58 procedure TTestTrees.Test_IndexedAVLTree_Add_General;
59 const
60   _COUNT = 999;
61 var
62   LNumbers: THashSet<Integer>;
63   i, j: Integer;
64   LTree: TStringsTree;
65   LNodes: TList<TStringsTree.PNode>;
66   n: TStringsTree.PNode;
67 begin
68   LNumbers := THashSet<Integer>.Create;
69   LTree := TStringsTree.Create;
70   LNodes := TList<TStringsTree.PNode>.Create;
71 
72   try
73     // check consistency of adding new nodes to Indexed AVL
74     for i := 0 to _COUNT do
75     begin
76       LNodes.Add(LTree.Add('0'+i.ToString));
77       LNumbers.Clear;
78       for n in LTree.Nodes do
79         Check(LNumbers.Add(LTree.NodeToIndex(n)), 'Wrong index (duplicate) of '+ i.ToString + ' for node ' + n.Key);
80       for j := 0 to LNodes.Count - 1 do
81         Check(LNumbers.Contains(j), 'Missing index ' + j.ToString + ' for i = ' + i.ToString);
82       LTree.ConsistencyCheck;
83       CheckEquals(i+1, LTree.Count, 'Wrong tree count');
84     end;
85   finally
86     LNodes.Free;
87     LTree.Free;
88     LNumbers.Free;
89   end;
90 end;
91 
92 procedure TTestTrees.Test_IndexedAVLTree_Add;
93 var
94   LTree: TStringsTree;
95 begin
96   LTree := TStringsTree.Create;
97 
98   try
99     LTree.Duplicates:=dupAccept;
100     LTree.Add('Aaa');
101   finally
102     LTree.Free;
103   end;
104 end;
105 
106 procedure TTestTrees.Test_IndexedAVLTree_Delete;
107 const
108   _COUNT = 999;
109 var
110   LNumbers: THashSet<Integer>;
111   i, j: Integer;
112   LTree: TStringsTree;
113   LNodes: TList<TStringsTree.PNode>;
114   n: TStringsTree.PNode;
115 begin
116   LNumbers := THashSet<Integer>.Create;
117   LTree := TStringsTree.Create;
118   LNodes := TList<TStringsTree.PNode>.Create;
119 
120   try
121     for i := 0 to _COUNT do
122       LNodes.Add(LTree.Add('0'+i.ToString));
123 
124     // check consistency of deleting nodes from Indexed AVL
125     for i := 0 to _COUNT do
126     begin
127       LTree.Delete(LNodes.ExtractIndex(Random(LNodes.count)));
128       LNumbers.Clear;
129       for n in LTree.Nodes do
130         Check(LNumbers.Add(LTree.NodeToIndex(n)), 'Wrong index (duplicate) of '+ i.ToString + ' for node ' + n.Key);
131       for j := 0 to LNodes.Count - 1 do
132         Check(LNumbers.Contains(j), 'Missing index ' + j.ToString + ' for i = ' + i.ToString);
133       LTree.ConsistencyCheck;
134       CheckEquals(_COUNT-i, LTree.Count, 'Wrong tree count');
135     end;
136   finally
137     LNodes.Free;
138     LTree.Free;
139     LNumbers.Free;
140   end;
141 end;
142 
143 procedure TTestTrees.Test_IndexedAVLTree_Items;
144 var
145   LTree: TMapTree;
146 begin
147   LTree := TMapTree.Create;
148   try
149     Check(LTree.Add('A', 1)<>nil);
150     Check(LTree.Add('B', 2)<>nil);
151     Check(LTree.Add('C', 3)<>nil);
152     CheckEquals(LTree.Items['A'], 1);
153     CheckEquals(LTree.Items['B'], 2);
154     CheckEquals(LTree.Items['C'], 3);
155     LTree.Items['A'] := 4;
156     LTree.Items['B'] := 5;
157     LTree.Items['C'] := 6;
158     CheckEquals(LTree.Items['A'], 4);
159     CheckEquals(LTree.Items['B'], 5);
160     CheckEquals(LTree.Items['C'], 6);
161   finally
162     LTree.Free;
163   end;
164 end;
165 
166 procedure TTestTrees.Test_TAVLTreeMap_Notification;
167 var
168   LTree: TAVLTreeMap<string, string>;
169   LNode, LA, LC: TAVLTreeMap<string, string>.PNode;
170 begin
171   LTree := TAVLTreeMap<string, string>.Create;
172   LTree.OnKeyNotify := NotifyTestStr;
173   LTree.OnValueNotify := NotifyTestStr;
174   LTree.OnNodeNotify := NotifyTestNodeStr;
175   try
176     // simple add
177     NotificationAdd(LTree, ['Aaa', 'Bbb'], cnAdded);
178     NotificationAdd(LTree, 'Aaa', 'Bbb', nil, cnAdded, false, true);
179     LA := LTree.Add('Aaa', 'Bbb');
180     AssertNotificationsExecutedNodeStr;
181     AssertNotificationsExecutedStr;
182 
183     // pair add
184     NotificationAdd(LTree, ['Ccc', 'Ddd'], cnAdded);
185     NotificationAdd(LTree, 'Ccc', 'Ddd', nil, cnAdded, false, true);
186     LC := LTree.Add(TAVLTreeMap<string, string>.TTreePair.Create('Ccc', 'Ddd'));
187     AssertNotificationsExecutedNodeStr;
188     AssertNotificationsExecutedStr;
189 
190     // AddNode;
191     LNode := LTree.NewNode;
192     LNode.Key := 'Eee';
193     LNode.Value := 'Fff';
194     NotificationAdd(LTree, ['Eee', 'Fff'], cnAdded);
195     NotificationAdd(LTree, 'Eee', 'Fff', LNode, cnAdded, false, false);
196     AssertTrue(LTree.AddNode(LNode));
197     AssertNotificationsExecutedNodeStr;
198     AssertNotificationsExecutedStr;
199 
200     // Delete
201     NotificationAdd(LTree, ['Eee', 'Fff'], cnRemoved);
202     NotificationAdd(LTree, 'Eee', 'Fff', LNode, cnRemoved, false, false);
203     LTree.Delete(LNode, false);
204     AssertNotificationsExecutedNodeStr;
205     AssertNotificationsExecutedStr;
206     LTree.DisposeNode(LNode);
207 
208     // remove
209     NotificationAdd(LTree, ['Aaa', 'Bbb'], cnRemoved);
210     NotificationAdd(LTree, 'Aaa', 'Bbb', LA, cnRemoved, true, false);
211     LTree.Remove('Aaa');
212     AssertNotificationsExecutedNodeStr;
213     AssertNotificationsExecutedStr;
214 
215 
216     // free
217     NotificationAdd(LTree, ['Ccc', 'Ddd'], cnRemoved);
218     NotificationAdd(LTree, 'Ccc', 'Ddd', LC, cnRemoved, true, false);
219   finally
220     LTree.Free;
221     AssertNotificationsExecutedNodeStr;
222     AssertNotificationsExecutedStr;
223   end;
224 end;
225 
226 begin
227   RegisterTest(TTestTrees);
228 end.
229 
230