1 /** 2 * 3 * Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU) 4 * info_at_agrum_dot_org 5 * 6 * This library is free software: you can redistribute it and/or modify 7 * it under the terms of the GNU Lesser General Public License as published by 8 * the Free Software Foundation, either version 3 of the License, or 9 * (at your option) any later version. 10 * 11 * This library is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public License 17 * along with this library. If not, see <http://www.gnu.org/licenses/>. 18 * 19 */ 20 21 22 #include <gumtest/AgrumTestSuite.h> 23 #include <gumtest/testsuite_utils.h> 24 25 #include <agrum/tools/graphs/parts/nodeGraphPart.h> 26 27 namespace gum_tests { 28 29 class NodeGraphPartTestSuite: public CxxTest::TestSuite { 30 public: testConstructor()31 void testConstructor() { TS_GUM_ASSERT_THROWS_NOTHING(gum::NodeGraphPart ngp); } 32 testInsertion()33 void testInsertion() { 34 gum::NodeGraphPart ngp; 35 TS_ASSERT_EQUALS(ngp.size(), (gum::Size)0) 36 TS_ASSERT(ngp.empty()) 37 38 gum::NodeId firstId = ngp.addNode(); 39 TS_ASSERT(!ngp.empty()) 40 TS_ASSERT_EQUALS(ngp.size(), (gum::Size)1) 41 TS_ASSERT_EQUALS(firstId, (gum::NodeId)0) 42 43 ngp.addNode(); 44 TS_ASSERT_EQUALS(ngp.size(), (gum::Size)2) 45 46 ngp.addNode(); 47 TS_ASSERT_EQUALS(ngp.size(), (gum::Size)3) 48 49 gum::NodeId next = ngp.nextNodeId(); 50 gum::NodeId next2 = ngp.addNode(); 51 TS_ASSERT_EQUALS(next, next2) 52 53 TS_GUM_ASSERT_THROWS_NOTHING(ngp.addNodeWithId(next2 + 1)); 54 TS_ASSERT_THROWS(ngp.addNodeWithId(next2 + 1), gum::DuplicateElement) 55 } 56 testSuppression()57 void testSuppression() { 58 gum::NodeGraphPart ngp; 59 ngp.addNode(); 60 ngp.addNode(); 61 gum::NodeId id3 = ngp.addNode(); 62 ngp.addNode(); 63 64 ngp.eraseNode(id3); 65 TS_GUM_ASSERT_THROWS_NOTHING(ngp.eraseNode(id3)); 66 TS_ASSERT_EQUALS(ngp.size(), (gum::Size)3) 67 68 TS_GUM_ASSERT_THROWS_NOTHING(ngp.addNodeWithId(id3)); 69 TS_ASSERT_THROWS(ngp.addNodeWithId(id3), gum::DuplicateElement) 70 TS_ASSERT_EQUALS(ngp.size(), (gum::Size)4) 71 72 ngp.clear(); 73 TS_ASSERT_EQUALS(ngp.size(), (gum::Size)0) 74 } 75 testAdd2()76 void testAdd2() { 77 gum::NodeGraphPart ngp; 78 ngp.addNodeWithId(gum::NodeId(3)); 79 TS_ASSERT_EQUALS(ngp._sizeHoles_(), (gum::Size)3) 80 ngp.addNodeWithId(gum::NodeId(2)); 81 ngp.addNodeWithId(gum::NodeId(1)); 82 ngp.addNodeWithId(gum::NodeId(0)); 83 TS_ASSERT_EQUALS(ngp._sizeHoles_(), (gum::Size)0) 84 85 gum::NodeGraphPart ngp2; 86 ngp2.addNodeWithId(gum::NodeId(0)); 87 ngp2.addNodeWithId(gum::NodeId(1)); 88 ngp2.addNodeWithId(gum::NodeId(2)); 89 ngp2.addNodeWithId(gum::NodeId(3)); 90 91 TS_ASSERT_EQUALS(ngp, ngp2) 92 } 93 testCopy()94 void testCopy() { 95 gum::NodeGraphPart ngp; 96 ngp.addNode(); 97 ngp.addNode(); 98 _ForTestCopy_(ngp); 99 TS_ASSERT_EQUALS(ngp._sizeHoles_(), (gum::Size)0) 100 gum::NodeId id3 = ngp.addNode(); 101 gum::NodeId id4 = ngp.addNode(); 102 ngp.eraseNode(id3); 103 _ForTestCopy_(ngp); 104 TS_ASSERT_EQUALS(ngp._sizeHoles_(), (gum::Size)1) 105 ngp.eraseNode(id4); 106 _ForTestCopy_(ngp); 107 TS_ASSERT_EQUALS(ngp._sizeHoles_(), 108 (gum::Size)0); // 2 last hole has vanished 109 } 110 testInsertionForcee()111 void testInsertionForcee() { 112 gum::NodeGraphPart ngp; 113 gum::NodeId a = 1; 114 gum::NodeId b = 2; 115 gum::NodeId c = 3; 116 gum::NodeId d = 4; 117 gum::NodeId e = 5; 118 gum::NodeId f = 6; 119 gum::NodeId g = 7; 120 121 ngp.addNodeWithId(c); 122 TS_ASSERT(ngp._inHoles_(a)) 123 TS_ASSERT(ngp._inHoles_(b)) 124 TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)3)) 125 TS_ASSERT_EQUALS(ngp.bound(), c + 1) 126 127 ngp.addNodeWithId(a); 128 TS_ASSERT(ngp._inHoles_(b)) 129 TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)2)) 130 TS_ASSERT_EQUALS(ngp.bound(), c + 1) 131 132 ngp.addNodeWithId(f); 133 TS_ASSERT(ngp._inHoles_(b)) 134 TS_ASSERT(ngp._inHoles_(d)) 135 TS_ASSERT(ngp._inHoles_(e)) 136 TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)4)) 137 TS_ASSERT_EQUALS(ngp.bound(), f + 1) 138 139 ngp.addNodeWithId(e); 140 TS_ASSERT(ngp._inHoles_(b)) 141 TS_ASSERT(ngp._inHoles_(d)) 142 TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)3)) 143 TS_ASSERT_EQUALS(ngp.bound(), f + 1) 144 145 ngp.addNodeWithId(b); 146 TS_ASSERT(ngp._inHoles_(d)) 147 TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)2)) 148 TS_ASSERT_EQUALS(ngp.bound(), f + 1) 149 150 ngp.addNodeWithId(d); 151 TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)1)) 152 TS_ASSERT_EQUALS(ngp.bound(), f + 1) 153 154 ngp.addNodeWithId(g); 155 TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)1)) 156 TS_ASSERT_EQUALS(ngp.bound(), g + 1) 157 158 ngp.addNodeWithId(gum::NodeId(0)); 159 TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)0)) 160 TS_ASSERT_EQUALS(ngp.bound(), g + 1) 161 162 TS_ASSERT_THROWS(ngp.addNodeWithId(f), gum::DuplicateElement) 163 } 164 testGarbageCollecting()165 void testGarbageCollecting() { 166 gum::NodeGraphPart ngp; 167 gum::NodeId node = 6; 168 169 TS_ASSERT_EQUALS(ngp.bound(), (gum::NodeId)(0)) 170 TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)0)) 171 TS_ASSERT_EQUALS(ngp.nextNodeId(), ((gum::Size)0)) 172 ngp.addNodeWithId(node); 173 TS_ASSERT_EQUALS(ngp.bound(), (gum::NodeId)(node + 1)) 174 TS_ASSERT_EQUALS(ngp._sizeHoles_(), (gum::Size(node))) 175 TS_ASSERT(ngp.nextNodeId() < node); // we fill one of the holes 176 ngp.eraseNode(node); 177 TS_ASSERT_EQUALS(ngp._sizeHoles_(), ((gum::Size)0)) 178 TS_ASSERT_EQUALS(ngp.nextNodeId(), ((gum::Size)0)) 179 TS_ASSERT_EQUALS(ngp.bound(), (gum::NodeId)(0)) 180 181 // do we fill all the holes? 182 gum::NodeGraphPart ngp2; 183 ngp2.addNodeWithId(node); 184 185 for (gum::Size i = 1; i < node; i++) { 186 TS_ASSERT_EQUALS(ngp2._sizeHoles_(), (gum::Size(node) + 1 - i)) 187 TS_ASSERT(ngp2.addNode() < node) 188 } 189 190 TS_ASSERT_EQUALS(ngp2._sizeHoles_(), (gum::Size)1) 191 192 TS_ASSERT_EQUALS(ngp2.nextNodeId(), gum::NodeId(node - 1)) 193 194 ngp2.addNode(); 195 196 TS_ASSERT_EQUALS(ngp2._sizeHoles_(), (gum::Size)0) 197 TS_ASSERT_EQUALS(ngp2.nextNodeId(), gum::NodeId(node + 1)) 198 } 199 testUnsafeIterator()200 void testUnsafeIterator() { 201 gum::NodeGraphPart ngp; 202 203 for (gum::NodeId i = 0; i < 20; ++i) { 204 ngp.addNodeWithId(i); 205 } 206 207 for (gum::NodeId i = 0; i < 20; ++i) { 208 if (i % 3 == 0) { ngp.eraseNode(i); } 209 } 210 211 gum::NodeGraphPartIteratorSafe safe_iter = ngp.beginSafe(); // safe iterator needed here 212 213 for (gum::NodeGraphPartIterator iter = ngp.begin(); iter != ngp.end(); ++iter, ++safe_iter) { 214 TS_ASSERT_EQUALS(*iter, *safe_iter) 215 } 216 217 gum::Size nb = 0, nb2 = 0; 218 219 for (auto x: ngp) { 220 ++nb; 221 nb2 += x; 222 } 223 224 TS_ASSERT_EQUALS(nb, (gum::Size)13) 225 } 226 testBigNodeGraphPart()227 void testBigNodeGraphPart() { TS_GUM_ASSERT_THROWS_NOTHING(_privateTestBigNodeGraphPart_()); } 228 testIteratorEnd()229 void testIteratorEnd() { 230 gum::NodeGraphPart nodeset; 231 nodeset.addNode(); 232 gum::Size cpt = 0; 233 234 for (gum::NodeGraphPartIteratorSafe iter = nodeset.beginSafe(); // safe iterator needed here 235 iter != nodeset.endSafe(); 236 ++iter) { 237 if (cpt == 0) { 238 nodeset.eraseNode(*iter); 239 cpt++; 240 } else { 241 // If false : infinite loop spotted 242 TS_ASSERT(false) 243 break; 244 } 245 } 246 } 247 testIteratorEraseNode()248 void testIteratorEraseNode() { 249 gum::NodeGraphPart nodeset; 250 const gum::Size max_cpt = 100; 251 252 for (gum::NodeId i = 0; i < max_cpt; ++i) { 253 nodeset.addNode(); 254 } 255 256 gum::Size cpt = 0; 257 258 for (gum::NodeGraphPartIteratorSafe iter = nodeset.beginSafe(); // safe iterator needed here 259 iter != nodeset.endSafe(); 260 ++iter, ++cpt) { 261 TS_GUM_ASSERT_THROWS_NOTHING(nodeset.eraseNode(*iter)); 262 263 if (cpt > max_cpt) { 264 // If false : infinite loop spotted 265 TS_ASSERT(false) 266 break; 267 } 268 } 269 270 TS_ASSERT_EQUALS(cpt, max_cpt) 271 } 272 testIteratorAddNodes()273 void testIteratorAddNodes() { 274 gum::NodeGraphPart nodeset; 275 276 auto v = nodeset.addNodes(100); 277 for (gum::NodeId i = 0; i < 100; i++) 278 TS_ASSERT_EQUALS(v[i], i) 279 280 for (int i = 0; i < 5; i++) 281 nodeset.eraseNode(2 + i * 19); 282 283 nodeset.addNodes(5); 284 285 TS_ASSERT_EQUALS(nodeset.size(), (gum::Size)100) 286 287 gum::NodeId i = 0; 288 for (auto n: nodeset.nodes()) 289 TS_ASSERT_EQUALS(n, i++) 290 291 gum::NodeGraphPart nodeset2; 292 nodeset2.addNodes(10); 293 gum::NodeGraphPart futureIds; 294 295 nodeset2.eraseNode(1); 296 futureIds.addNodeWithId(1); 297 nodeset2.eraseNode(3); 298 futureIds.addNodeWithId(3); 299 nodeset2.eraseNode(5); 300 futureIds.addNodeWithId(5); 301 302 auto v2 = nodeset2.addNodes(4); 303 futureIds.addNodeWithId(10); // the 4th added node as 10 for id 304 305 for (auto n: v2) { 306 TS_GUM_ASSERT_THROWS_NOTHING(futureIds.eraseNode(n)); 307 } 308 TS_ASSERT(futureIds.empty()) 309 } 310 311 private: 312 #define NBR_PROFILING_NODES 50000 _privateTestBigNodeGraphPart_()313 void _privateTestBigNodeGraphPart_() { 314 { 315 gum::NodeGraphPart ngp; 316 // direct 317 318 for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) { 319 ngp.addNode(); 320 } 321 322 for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) { 323 ngp.eraseNode(node); 324 } 325 } 326 327 { 328 gum::NodeGraphPart ngp; 329 // reverse 330 331 for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) { 332 ngp.addNode(); 333 } 334 335 for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) { 336 ngp.eraseNode(NBR_PROFILING_NODES - node); 337 } 338 } 339 340 { 341 gum::NodeGraphPart ngp; 342 343 // direct with id 344 345 for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) { 346 ngp.addNodeWithId(node); 347 } 348 349 for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) { 350 ngp.eraseNode(node); 351 } 352 } 353 354 { 355 gum::NodeGraphPart ngp; 356 357 // reverse with id 358 359 for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) { 360 ngp.addNodeWithId(NBR_PROFILING_NODES - node); 361 } 362 363 for (gum::NodeId node = 1; node < NBR_PROFILING_NODES; node++) { 364 ngp.eraseNode(10000 - node); 365 } 366 } 367 } 368 _ForTestCopy_(gum::NodeGraphPart & ngp)369 void _ForTestCopy_(gum::NodeGraphPart& ngp) { 370 gum::NodeGraphPart ngp2(ngp); 371 TS_ASSERT_EQUALS(ngp.toString(), ngp2.toString()) 372 373 gum::NodeGraphPart ngp3 = ngp; 374 TS_ASSERT_EQUALS(ngp.toString(), ngp3.toString()) 375 376 gum::NodeGraphPart ngp4; 377 TS_ASSERT(ngp4.empty()) 378 ngp4 = ngp; 379 TS_ASSERT_EQUALS(ngp.toString(), ngp3.toString()) 380 } 381 }; 382 } // namespace gum_tests 383