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