File indexing completed on 2024-05-26 04:27:00
0001 /* 0002 * SPDX-FileCopyrightText: 2019 Dmitry Kazakov <dimula73@gmail.com> 0003 * 0004 * SPDX-License-Identifier: GPL-2.0-or-later 0005 */ 0006 #include "KisForestTest.h" 0007 0008 #include "KisCppQuirks.h" 0009 #include "KisForest.h" 0010 #include <vector> 0011 0012 struct IteratorToValue 0013 { 0014 using value_type = int; 0015 0016 template <typename Iterator> 0017 value_type operator() (Iterator it) const { 0018 return *it; 0019 } 0020 }; 0021 0022 template <typename Iterator, typename IteratorValuePolicy = IteratorToValue> 0023 bool testForestIteration(Iterator begin, Iterator end, 0024 std::vector<typename IteratorValuePolicy::value_type> reference, 0025 IteratorValuePolicy iteratorToValue = IteratorValuePolicy()) 0026 { 0027 using value_type = typename IteratorValuePolicy::value_type; 0028 0029 bool result = true; 0030 std::vector<value_type> values; 0031 0032 std::size_t index = 0; 0033 for (auto it = begin; it != end; ++it, ++index) { 0034 value_type value = iteratorToValue(it); 0035 0036 if (index >= reference.size() || value != reference[index]) { 0037 result = false; 0038 } 0039 values.push_back(value); 0040 0041 // emergency exit in case of infinite loop :) 0042 // "40 forest items must be enough for everyone!" (c) 0043 if (index > 40) { 0044 result = false; 0045 break; 0046 } 0047 } 0048 0049 result &= values.size() == reference.size(); 0050 0051 if (!result) { 0052 qDebug() << "Failed forest iteration:"; 0053 { 0054 QDebug deb = qDebug(); 0055 deb << " result:"; 0056 Q_FOREACH(value_type value, values) { 0057 deb << value; 0058 } 0059 } 0060 { 0061 QDebug deb = qDebug(); 0062 deb << " ref. :"; 0063 Q_FOREACH(value_type value, reference) { 0064 deb << value; 0065 } 0066 } 0067 } 0068 0069 return result; 0070 } 0071 0072 void KisForestTest::testAddToRoot() 0073 { 0074 KisForest<int> forest; 0075 0076 forest.insert(childBegin(forest), 2); 0077 forest.insert(childBegin(forest), 1); 0078 forest.insert(childBegin(forest), 0); 0079 forest.insert(childEnd(forest), 3); 0080 0081 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0,1,2,3})); 0082 0083 } 0084 0085 void KisForestTest::testAddToRootChained() 0086 { 0087 KisForest<int> forest; 0088 0089 auto it = forest.insert(childBegin(forest), 3); 0090 it = forest.insert(it, 2); 0091 it = forest.insert(it, 1); 0092 it = forest.insert(it, 0); 0093 0094 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0,1,2,3})); 0095 } 0096 0097 void KisForestTest::testAddToLeaf() 0098 { 0099 KisForest<int> forest; 0100 0101 auto root = forest.insert(childBegin(forest), 0); 0102 forest.insert(childBegin(root), 2); 0103 forest.insert(childBegin(root), 1); 0104 forest.insert(childEnd(root), 3); 0105 forest.insert(childEnd(root), 4); 0106 0107 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0})); 0108 QVERIFY(testForestIteration(childBegin(root), childEnd(root), {1,2,3,4})); 0109 0110 } 0111 0112 void KisForestTest::testAddToLeafChained() 0113 { 0114 KisForest<int> forest; 0115 0116 auto root = forest.insert(childBegin(forest), 0); 0117 auto it = forest.insert(childBegin(root), 4); 0118 it = forest.insert(it, 3); 0119 it = forest.insert(it, 2); 0120 it = forest.insert(it, 1); 0121 0122 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0})); 0123 QVERIFY(testForestIteration(childBegin(root), childEnd(root), {1,2,3,4})); 0124 0125 } 0126 0127 void KisForestTest::testDFSIteration() 0128 { 0129 KisForest<int> forest; 0130 0131 /** 0132 * 0 1 0133 * 2 0134 * 3 5 6 0135 * 7 0136 * 4 0137 * 8 9 0138 * 10 0139 **/ 0140 0141 0142 auto it0 = forest.insert(childBegin(forest), 0); 0143 auto it8 = forest.insert(childEnd(forest), 8); 0144 0145 auto it1 = forest.insert(childEnd(it0), 1); 0146 auto it2 = forest.insert(childEnd(it0), 2); 0147 auto it3 = forest.insert(childEnd(it0), 3); 0148 auto it4 = forest.insert(childEnd(it0), 4); 0149 0150 auto it5 = forest.insert(childEnd(it3), 5); 0151 0152 auto it6 = forest.insert(childEnd(it5), 6); 0153 auto it7 = forest.insert(childEnd(it5), 7); 0154 0155 auto it9 = forest.insert(childEnd(it8), 9); 0156 auto it10 = forest.insert(childEnd(it8), 10); 0157 0158 Q_UNUSED(it1); 0159 Q_UNUSED(it2); 0160 Q_UNUSED(it6); 0161 Q_UNUSED(it7); 0162 Q_UNUSED(it4); 0163 Q_UNUSED(it9); 0164 Q_UNUSED(it10); 0165 0166 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0, 8})); 0167 QVERIFY(testForestIteration(childBegin(it0), childEnd(it0), {1,2,3,4})); 0168 QVERIFY(testForestIteration(childBegin(it8), childEnd(it8), {9,10})); 0169 QVERIFY(testForestIteration(childBegin(it3), childEnd(it3), {5})); 0170 QVERIFY(testForestIteration(childBegin(it5), childEnd(it5), {6,7})); 0171 0172 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,6,7,4,8,9,10})); 0173 } 0174 0175 void KisForestTest::testHierarchyIteration() 0176 { 0177 KisForest<int> forest; 0178 0179 /** 0180 * 0 1 0181 * 2 0182 * 3 5 6 0183 * 7 0184 * 4 0185 * 8 9 0186 * 10 0187 **/ 0188 0189 0190 auto it0 = forest.insert(childBegin(forest), 0); 0191 auto it8 = forest.insert(childEnd(forest), 8); 0192 0193 auto it1 = forest.insert(childEnd(it0), 1); 0194 auto it2 = forest.insert(childEnd(it0), 2); 0195 auto it3 = forest.insert(childEnd(it0), 3); 0196 auto it4 = forest.insert(childEnd(it0), 4); 0197 0198 auto it5 = forest.insert(childEnd(it3), 5); 0199 0200 auto it6 = forest.insert(childEnd(it5), 6); 0201 auto it7 = forest.insert(childEnd(it5), 7); 0202 0203 auto it9 = forest.insert(childEnd(it8), 9); 0204 auto it10 = forest.insert(childEnd(it8), 10); 0205 0206 Q_UNUSED(it1); 0207 Q_UNUSED(it2); 0208 Q_UNUSED(it6); 0209 Q_UNUSED(it7); 0210 Q_UNUSED(it4); 0211 Q_UNUSED(it9); 0212 Q_UNUSED(it10); 0213 0214 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0, 8})); 0215 QVERIFY(testForestIteration(childBegin(it0), childEnd(it0), {1,2,3,4})); 0216 QVERIFY(testForestIteration(childBegin(it8), childEnd(it8), {9,10})); 0217 QVERIFY(testForestIteration(childBegin(it3), childEnd(it3), {5})); 0218 QVERIFY(testForestIteration(childBegin(it5), childEnd(it5), {6,7})); 0219 0220 QVERIFY(testForestIteration(hierarchyBegin(it0), hierarchyEnd(it0), {0})); 0221 QVERIFY(testForestIteration(hierarchyBegin(forest.end()), hierarchyEnd(forest.end()), {})); 0222 0223 QVERIFY(testForestIteration(hierarchyBegin(it7), hierarchyEnd(it7), {7,5,3,0})); 0224 QVERIFY(testForestIteration(hierarchyBegin(it5), hierarchyEnd(it5), {5,3,0})); 0225 QVERIFY(testForestIteration(hierarchyBegin(it4), hierarchyEnd(it4), {4,0})); 0226 QVERIFY(testForestIteration(hierarchyBegin(it10), hierarchyEnd(it10), {10,8})); 0227 } 0228 0229 void KisForestTest::testSiblingIteration() 0230 { 0231 KisForest<int> forest; 0232 0233 /** 0234 * 0 1 0235 * 2 0236 * 3 5 6 0237 * 7 0238 * 4 0239 * 8 9 0240 * 10 0241 **/ 0242 0243 0244 auto it0 = forest.insert(childBegin(forest), 0); 0245 auto it8 = forest.insert(childEnd(forest), 8); 0246 0247 auto it1 = forest.insert(childEnd(it0), 1); 0248 auto it2 = forest.insert(childEnd(it0), 2); 0249 auto it3 = forest.insert(childEnd(it0), 3); 0250 auto it4 = forest.insert(childEnd(it0), 4); 0251 0252 auto it5 = forest.insert(childEnd(it3), 5); 0253 0254 auto it6 = forest.insert(childEnd(it5), 6); 0255 auto it7 = forest.insert(childEnd(it5), 7); 0256 0257 auto it9 = forest.insert(childEnd(it8), 9); 0258 auto it10 = forest.insert(childEnd(it8), 10); 0259 0260 Q_UNUSED(it1); 0261 Q_UNUSED(it2); 0262 Q_UNUSED(it6); 0263 Q_UNUSED(it7); 0264 Q_UNUSED(it4); 0265 Q_UNUSED(it9); 0266 Q_UNUSED(it10); 0267 0268 /** 0269 * Test if all types of iterators are convertible into a child iterator 0270 */ 0271 QVERIFY(testForestIteration(siblingCurrent(it2), siblingEnd(it2), {2,3,4})); 0272 QVERIFY(testForestIteration(siblingCurrent(hierarchyBegin(it2)), siblingEnd(hierarchyBegin(it2)), {2,3,4})); 0273 QVERIFY(testForestIteration(siblingCurrent(subtreeBegin(it2)), siblingEnd(subtreeBegin(it2)), {2,3,4})); 0274 QVERIFY(testForestIteration(siblingCurrent(tailSubtreeBegin(it2)), siblingEnd(tailSubtreeBegin(it2)), {2,3,4})); 0275 QVERIFY(testForestIteration(siblingCurrent(compositionBegin(it2)), siblingEnd(compositionBegin(it2)), {2,3,4})); 0276 0277 // we cannot create a child iterator from an non-child end-iterator 0278 // QVERIFY(testForestIteration(siblingCurrent(compositionBegin(childEnd(it0))), 0279 // siblingEnd(compositionBegin(childEnd(it0))), {})); 0280 } 0281 0282 void KisForestTest::testCompositionIteration() 0283 { 0284 KisForest<int> forest; 0285 0286 /** 0287 * 0 1 0288 * 2 0289 * 3 5 6 0290 * 7 0291 * 4 0292 * 8 9 0293 * 10 0294 **/ 0295 0296 0297 auto it0 = forest.insert(childBegin(forest), 0); 0298 auto it8 = forest.insert(childEnd(forest), 8); 0299 0300 auto it1 = forest.insert(childEnd(it0), 1); 0301 auto it2 = forest.insert(childEnd(it0), 2); 0302 auto it3 = forest.insert(childEnd(it0), 3); 0303 auto it4 = forest.insert(childEnd(it0), 4); 0304 0305 auto it5 = forest.insert(childEnd(it3), 5); 0306 0307 auto it6 = forest.insert(childEnd(it5), 6); 0308 auto it7 = forest.insert(childEnd(it5), 7); 0309 0310 auto it9 = forest.insert(childEnd(it8), 9); 0311 auto it10 = forest.insert(childEnd(it8), 10); 0312 0313 Q_UNUSED(it1); 0314 Q_UNUSED(it2); 0315 Q_UNUSED(it6); 0316 Q_UNUSED(it7); 0317 Q_UNUSED(it4); 0318 Q_UNUSED(it9); 0319 Q_UNUSED(it10); 0320 0321 QVERIFY(testForestIteration(compositionBegin(forest), compositionEnd(forest), {0, 1, 1, 2, 2, 3, 5, 6, 6, 7, 7, 5, 3, 4, 4, 0, 8, 9, 9, 10, 10, 8})); 0322 0323 } 0324 0325 struct CompositionIteratorPairedValue 0326 { 0327 using value_type = std::pair<int, KisForest<int>::composition_iterator::traversal_state>; 0328 0329 template <typename Iterator> 0330 value_type operator() (Iterator it) const { 0331 return std::make_pair(*it, it.state()); 0332 } 0333 }; 0334 0335 void KisForestTest::testCompositionIterationSubtree() 0336 { 0337 KisForest<int> forest; 0338 0339 /** 0340 * 0 1 0341 * 2 0342 * 3 5 6 0343 * 7 0344 * 4 0345 * 8 9 0346 * 10 0347 **/ 0348 0349 0350 auto it0 = forest.insert(childBegin(forest), 0); 0351 auto it8 = forest.insert(childEnd(forest), 8); 0352 0353 auto it1 = forest.insert(childEnd(it0), 1); 0354 auto it2 = forest.insert(childEnd(it0), 2); 0355 auto it3 = forest.insert(childEnd(it0), 3); 0356 auto it4 = forest.insert(childEnd(it0), 4); 0357 0358 auto it5 = forest.insert(childEnd(it3), 5); 0359 0360 auto it6 = forest.insert(childEnd(it5), 6); 0361 auto it7 = forest.insert(childEnd(it5), 7); 0362 0363 auto it9 = forest.insert(childEnd(it8), 9); 0364 auto it10 = forest.insert(childEnd(it8), 10); 0365 0366 Q_UNUSED(it1); 0367 Q_UNUSED(it2); 0368 Q_UNUSED(it6); 0369 Q_UNUSED(it7); 0370 Q_UNUSED(it4); 0371 Q_UNUSED(it9); 0372 Q_UNUSED(it10); 0373 0374 QVERIFY(testForestIteration(compositionBegin(it3), compositionEnd(it3), {3, 5, 6, 6, 7, 7, 5, 3})); 0375 QVERIFY(testForestIteration(compositionBegin(it5), compositionEnd(it5), {5, 6, 6, 7, 7, 5})); 0376 QVERIFY(testForestIteration(compositionBegin(it8), compositionEnd(it8), {8, 9, 9, 10, 10, 8})); 0377 0378 using traversal_direction = KisForest<int>::composition_iterator::traversal_state; 0379 0380 std::vector<std::pair<int, traversal_direction>> references; 0381 0382 references = {{5, traversal_direction::Enter}, 0383 {6, traversal_direction::Enter}, 0384 {6, traversal_direction::Leave}, 0385 {7, traversal_direction::Enter}, 0386 {7, traversal_direction::Leave}, 0387 {5, traversal_direction::Leave}}; 0388 0389 QVERIFY(testForestIteration(compositionBegin(it5), compositionEnd(it5), 0390 references, CompositionIteratorPairedValue())); 0391 0392 references = {{3, traversal_direction::Enter}, 0393 {5, traversal_direction::Enter}, 0394 {6, traversal_direction::Enter}, 0395 {6, traversal_direction::Leave}, 0396 {7, traversal_direction::Enter}, 0397 {7, traversal_direction::Leave}, 0398 {5, traversal_direction::Leave}, 0399 {3, traversal_direction::Leave}}; 0400 0401 QVERIFY(testForestIteration(compositionBegin(it3), compositionEnd(it3), 0402 references, CompositionIteratorPairedValue())); 0403 0404 } 0405 0406 void KisForestTest::testSubtreeIteration() 0407 { 0408 KisForest<int> forest; 0409 0410 /** 0411 * 0 1 0412 * 2 0413 * 3 5 6 0414 * 7 0415 * 4 0416 * 8 9 0417 * 10 0418 **/ 0419 0420 0421 auto it0 = forest.insert(childBegin(forest), 0); 0422 auto it8 = forest.insert(childEnd(forest), 8); 0423 0424 auto it1 = forest.insert(childEnd(it0), 1); 0425 auto it2 = forest.insert(childEnd(it0), 2); 0426 auto it3 = forest.insert(childEnd(it0), 3); 0427 auto it4 = forest.insert(childEnd(it0), 4); 0428 0429 auto it5 = forest.insert(childEnd(it3), 5); 0430 0431 auto it6 = forest.insert(childEnd(it5), 6); 0432 auto it7 = forest.insert(childEnd(it5), 7); 0433 0434 auto it9 = forest.insert(childEnd(it8), 9); 0435 auto it10 = forest.insert(childEnd(it8), 10); 0436 0437 Q_UNUSED(it1); 0438 Q_UNUSED(it2); 0439 Q_UNUSED(it6); 0440 Q_UNUSED(it7); 0441 Q_UNUSED(it4); 0442 Q_UNUSED(it9); 0443 Q_UNUSED(it10); 0444 0445 0446 QVERIFY(testForestIteration(subtreeBegin(it3), subtreeEnd(it3), {3,5,6,7})); 0447 QVERIFY(testForestIteration(subtreeBegin(it0), subtreeEnd(it0), {0,1,2,3,5,6,7,4})); 0448 QVERIFY(testForestIteration(subtreeBegin(it8), subtreeEnd(it8), {8,9,10})); 0449 } 0450 0451 void KisForestTest::testSubtreeTailIteration() 0452 { 0453 KisForest<int> forest; 0454 0455 /** 0456 * 0 1 0457 * 2 0458 * 3 5 6 0459 * 7 0460 * 4 0461 * 8 9 0462 * 10 0463 **/ 0464 0465 0466 auto it0 = forest.insert(childBegin(forest), 0); 0467 auto it8 = forest.insert(childEnd(forest), 8); 0468 0469 auto it1 = forest.insert(childEnd(it0), 1); 0470 auto it2 = forest.insert(childEnd(it0), 2); 0471 auto it3 = forest.insert(childEnd(it0), 3); 0472 auto it4 = forest.insert(childEnd(it0), 4); 0473 0474 auto it5 = forest.insert(childEnd(it3), 5); 0475 0476 auto it6 = forest.insert(childEnd(it5), 6); 0477 auto it7 = forest.insert(childEnd(it5), 7); 0478 0479 auto it9 = forest.insert(childEnd(it8), 9); 0480 auto it10 = forest.insert(childEnd(it8), 10); 0481 0482 Q_UNUSED(it1); 0483 Q_UNUSED(it2); 0484 Q_UNUSED(it6); 0485 Q_UNUSED(it7); 0486 Q_UNUSED(it4); 0487 Q_UNUSED(it9); 0488 Q_UNUSED(it10); 0489 0490 0491 QVERIFY(testForestIteration(tailSubtreeBegin(it3), tailSubtreeEnd(it3), {6,7,5,3})); 0492 QVERIFY(testForestIteration(tailSubtreeBegin(it0), tailSubtreeEnd(it0), {1,2,6,7,5,3,4,0})); 0493 QVERIFY(testForestIteration(tailSubtreeBegin(it8), tailSubtreeEnd(it8), {9,10,8})); 0494 0495 QVERIFY(testForestIteration(tailSubtreeBegin(forest), tailSubtreeEnd(forest), {1,2,6,7,5,3,4,0,9,10,8})); 0496 } 0497 0498 void KisForestTest::testEraseNode() 0499 { 0500 KisForest<int> forest; 0501 0502 /** 0503 * 0 1 0504 * 2 0505 * 3 5 6 0506 * 7 0507 * 4 0508 * 8 9 0509 * 10 0510 **/ 0511 0512 0513 auto it0 = forest.insert(childBegin(forest), 0); 0514 auto it8 = forest.insert(childEnd(forest), 8); 0515 0516 auto it1 = forest.insert(childEnd(it0), 1); 0517 auto it2 = forest.insert(childEnd(it0), 2); 0518 auto it3 = forest.insert(childEnd(it0), 3); 0519 auto it4 = forest.insert(childEnd(it0), 4); 0520 0521 auto it5 = forest.insert(childEnd(it3), 5); 0522 0523 auto it6 = forest.insert(childEnd(it5), 6); 0524 auto it7 = forest.insert(childEnd(it5), 7); 0525 0526 auto it9 = forest.insert(childEnd(it8), 9); 0527 auto it10 = forest.insert(childEnd(it8), 10); 0528 0529 Q_UNUSED(it1); 0530 Q_UNUSED(it2); 0531 Q_UNUSED(it6); 0532 Q_UNUSED(it7); 0533 Q_UNUSED(it4); 0534 Q_UNUSED(it9); 0535 Q_UNUSED(it10); 0536 0537 0538 QCOMPARE(forest.erase(it6), it7); 0539 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,7,4,8,9,10})); 0540 0541 QCOMPARE(forest.erase(it7), childEnd(it5)); 0542 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4,8,9,10})); 0543 0544 QCOMPARE(forest.erase(it10), childEnd(it8)); 0545 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4,8,9})); 0546 0547 QCOMPARE(forest.erase(it9), childEnd(it8)); 0548 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4,8})); 0549 0550 QCOMPARE(forest.erase(it8), childEnd(forest)); 0551 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4})); 0552 } 0553 0554 void KisForestTest::testEraseSubtree() 0555 { 0556 KisForest<int> forest; 0557 0558 /** 0559 * 0 1 0560 * 2 0561 * 3 5 6 0562 * 7 0563 * 4 0564 * 8 9 0565 * 10 0566 **/ 0567 0568 0569 auto it0 = forest.insert(childBegin(forest), 0); 0570 auto it8 = forest.insert(childEnd(forest), 8); 0571 0572 auto it1 = forest.insert(childEnd(it0), 1); 0573 auto it2 = forest.insert(childEnd(it0), 2); 0574 auto it3 = forest.insert(childEnd(it0), 3); 0575 auto it4 = forest.insert(childEnd(it0), 4); 0576 0577 auto it5 = forest.insert(childEnd(it3), 5); 0578 0579 auto it6 = forest.insert(childEnd(it5), 6); 0580 auto it7 = forest.insert(childEnd(it5), 7); 0581 0582 auto it9 = forest.insert(childEnd(it8), 9); 0583 auto it10 = forest.insert(childEnd(it8), 10); 0584 0585 Q_UNUSED(it1); 0586 Q_UNUSED(it2); 0587 Q_UNUSED(it6); 0588 Q_UNUSED(it7); 0589 Q_UNUSED(it4); 0590 Q_UNUSED(it9); 0591 Q_UNUSED(it10); 0592 0593 0594 QCOMPARE(forest.erase(it3), it4); 0595 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,4,8,9,10})); 0596 0597 QCOMPARE(forest.erase(it8), childEnd(forest)); 0598 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,4})); 0599 0600 QCOMPARE(forest.erase(it0), childEnd(forest)); 0601 QVERIFY(testForestIteration(begin(forest), end(forest), {})); 0602 } 0603 0604 void KisForestTest::testEraseRange() 0605 { 0606 KisForest<int> forest; 0607 0608 /** 0609 * 0 1 0610 * 2 0611 * 3 5 6 0612 * 7 0613 * 4 0614 * 8 9 0615 * 10 0616 */ 0617 0618 0619 auto it0 = forest.insert(childBegin(forest), 0); 0620 auto it8 = forest.insert(childEnd(forest), 8); 0621 0622 auto it1 = forest.insert(childEnd(it0), 1); 0623 auto it2 = forest.insert(childEnd(it0), 2); 0624 auto it3 = forest.insert(childEnd(it0), 3); 0625 auto it4 = forest.insert(childEnd(it0), 4); 0626 0627 auto it5 = forest.insert(childEnd(it3), 5); 0628 0629 auto it6 = forest.insert(childEnd(it5), 6); 0630 auto it7 = forest.insert(childEnd(it5), 7); 0631 0632 auto it9 = forest.insert(childEnd(it8), 9); 0633 auto it10 = forest.insert(childEnd(it8), 10); 0634 0635 Q_UNUSED(it1); 0636 Q_UNUSED(it2); 0637 Q_UNUSED(it6); 0638 Q_UNUSED(it7); 0639 Q_UNUSED(it4); 0640 Q_UNUSED(it9); 0641 Q_UNUSED(it10); 0642 0643 0644 QCOMPARE(forest.erase(it1, it4), it4); 0645 QVERIFY(testForestIteration(begin(forest), end(forest), {0,4,8,9,10})); 0646 0647 QCOMPARE(forest.erase(it4, childEnd(it0)), childEnd(it0)); 0648 QVERIFY(testForestIteration(begin(forest), end(forest), {0,8,9,10})); 0649 } 0650 0651 void KisForestTest::testMoveSubtree() 0652 { 0653 KisForest<int> forest; 0654 0655 /** 0656 * 0 1 0657 * 2 0658 * 3 5 6 0659 * 7 0660 * 4 0661 * 8 9 0662 * 10 0663 */ 0664 0665 0666 auto it0 = forest.insert(childBegin(forest), 0); 0667 auto it8 = forest.insert(childEnd(forest), 8); 0668 0669 auto it1 = forest.insert(childEnd(it0), 1); 0670 auto it2 = forest.insert(childEnd(it0), 2); 0671 auto it3 = forest.insert(childEnd(it0), 3); 0672 auto it4 = forest.insert(childEnd(it0), 4); 0673 0674 auto it5 = forest.insert(childEnd(it3), 5); 0675 0676 auto it6 = forest.insert(childEnd(it5), 6); 0677 auto it7 = forest.insert(childEnd(it5), 7); 0678 0679 auto it9 = forest.insert(childEnd(it8), 9); 0680 auto it10 = forest.insert(childEnd(it8), 10); 0681 0682 Q_UNUSED(it1); 0683 Q_UNUSED(it2); 0684 Q_UNUSED(it6); 0685 Q_UNUSED(it7); 0686 Q_UNUSED(it4); 0687 Q_UNUSED(it9); 0688 Q_UNUSED(it10); 0689 0690 0691 auto newPos = forest.move(it3, it9); 0692 QCOMPARE(newPos, childBegin(it8)); 0693 0694 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,4,8,3,5,6,7,9,10})); 0695 0696 newPos = forest.move(it0, childEnd(it8)); 0697 QCOMPARE(newPos, std::prev(childEnd(it8))); 0698 0699 QVERIFY(testForestIteration(begin(forest), end(forest), {8,3,5,6,7,9,10,0,1,2,4})); 0700 } 0701 0702 void KisForestTest::testReversedChildIteration() 0703 { 0704 KisForest<int> forest; 0705 0706 /** 0707 * 0 1 0708 * 2 0709 * 3 5 6 0710 * 7 0711 * 4 0712 * 8 9 0713 * 10 0714 **/ 0715 0716 0717 auto it0 = forest.insert(childBegin(forest), 0); 0718 auto it8 = forest.insert(childEnd(forest), 8); 0719 0720 auto it1 = forest.insert(childEnd(it0), 1); 0721 auto it2 = forest.insert(childEnd(it0), 2); 0722 auto it3 = forest.insert(childEnd(it0), 3); 0723 auto it4 = forest.insert(childEnd(it0), 4); 0724 0725 auto it5 = forest.insert(childEnd(it3), 5); 0726 0727 auto it6 = forest.insert(childEnd(it5), 6); 0728 auto it7 = forest.insert(childEnd(it5), 7); 0729 0730 auto it9 = forest.insert(childEnd(it8), 9); 0731 auto it10 = forest.insert(childEnd(it8), 10); 0732 0733 Q_UNUSED(it1); 0734 Q_UNUSED(it2); 0735 Q_UNUSED(it6); 0736 Q_UNUSED(it7); 0737 Q_UNUSED(it4); 0738 Q_UNUSED(it9); 0739 Q_UNUSED(it10); 0740 0741 QVERIFY(testForestIteration(make_reverse_iterator(childEnd(forest)), 0742 make_reverse_iterator(childBegin(forest)), {8, 0})); 0743 0744 QVERIFY(testForestIteration(make_reverse_iterator(childEnd(it0)), 0745 make_reverse_iterator(childBegin(it0)), {4,3,2,1})); 0746 0747 QVERIFY(testForestIteration(make_reverse_iterator(childEnd(it3)), 0748 make_reverse_iterator(childBegin(it3)), {5})); 0749 } 0750 0751 void KisForestTest::testConversionsFromEnd() 0752 { 0753 KisForest<int> forest; 0754 0755 /** 0756 * 0 1 0757 * 2 0758 * 3 5 6 0759 * 7 0760 * 4 0761 * 8 9 0762 * 10 0763 **/ 0764 0765 0766 auto it0 = forest.insert(childBegin(forest), 0); 0767 auto it8 = forest.insert(childEnd(forest), 8); 0768 0769 auto it1 = forest.insert(childEnd(it0), 1); 0770 auto it2 = forest.insert(childEnd(it0), 2); 0771 auto it3 = forest.insert(childEnd(it0), 3); 0772 auto it4 = forest.insert(childEnd(it0), 4); 0773 0774 auto it5 = forest.insert(childEnd(it3), 5); 0775 0776 auto it6 = forest.insert(childEnd(it5), 6); 0777 auto it7 = forest.insert(childEnd(it5), 7); 0778 0779 auto it9 = forest.insert(childEnd(it8), 9); 0780 auto it10 = forest.insert(childEnd(it8), 10); 0781 0782 Q_UNUSED(it1); 0783 Q_UNUSED(it2); 0784 Q_UNUSED(it6); 0785 Q_UNUSED(it7); 0786 Q_UNUSED(it4); 0787 Q_UNUSED(it9); 0788 Q_UNUSED(it10); 0789 0790 /** 0791 * Currently, all operations on end-iterators are declared as "undefined behavior", 0792 * but, ideally, we should care about them. Like, it should be possible to get children 0793 * of the forest by calling childBegin/End(hierarchyEnd(it0)). I (DK) am not sure if 0794 * it is possible to implement without overhead. So I just added this test to document 0795 * "desired" behavior. But for now, no one should rely on this behavior, just consider 0796 * all operations with end-iterators as UB. 0797 */ 0798 0799 #define HIDE_UB_NOISE 0800 0801 QVERIFY(testForestIteration(childBegin(childEnd(it0)), 0802 childEnd(childEnd(it0)), {})); 0803 0804 #ifndef HIDE_UB_NOISE 0805 QEXPECT_FAIL("", "Fetching children of root node should return roots of the forest?", Continue); 0806 QVERIFY(testForestIteration(childBegin(hierarchyEnd(it0)), 0807 childEnd(hierarchyEnd(it0)), {0, 8})); 0808 QEXPECT_FAIL("", "End of composition should not (?) point to any existing node", Continue); 0809 QVERIFY(testForestIteration(childBegin(compositionEnd(it0)), 0810 childEnd(compositionEnd(it0)), {})); 0811 #endif 0812 0813 QVERIFY(testForestIteration(hierarchyBegin(childEnd(it0)), 0814 hierarchyEnd(childEnd(it0)), {})); 0815 QVERIFY(testForestIteration(hierarchyBegin(hierarchyEnd(it0)), 0816 hierarchyEnd(hierarchyEnd(it0)), {})); 0817 #ifndef HIDE_UB_NOISE 0818 QEXPECT_FAIL("", "End of composition should not (?) point to any existing node", Continue); 0819 QVERIFY(testForestIteration(hierarchyBegin(compositionEnd(it0)), 0820 hierarchyEnd(compositionEnd(it0)), {})); 0821 #endif 0822 0823 QVERIFY(testForestIteration(compositionBegin(childEnd(it0)), 0824 compositionEnd(childEnd(it0)), {})); 0825 #ifndef HIDE_UB_NOISE 0826 QEXPECT_FAIL("", "Starting composition on the root node should behave like we do it for the forest itself?", Continue); 0827 QVERIFY(testForestIteration(compositionBegin(hierarchyEnd(it0)), 0828 compositionEnd(hierarchyEnd(it0)), {0, 1, 1, 2, 2, 3, 5, 6, 6, 7, 7, 5, 3, 4, 4, 0, 8, 9, 9, 10, 10, 8})); 0829 QEXPECT_FAIL("", "End of composition should not (?) point to any existing node", Continue); 0830 QVERIFY(testForestIteration(compositionBegin(compositionEnd(it0)), 0831 compositionEnd(compositionEnd(it0)), {})); 0832 #endif 0833 0834 #ifndef HIDE_UB_NOISE 0835 QEXPECT_FAIL("", "Fetching siblings from child-end should work?", Continue); 0836 QVERIFY(testForestIteration(siblingBegin(childEnd(it0)), 0837 siblingEnd(childEnd(it0)), {1,2,3,4})); 0838 #endif 0839 0840 // TODO: we currently don't allow creation of child-iterators from end-non-child-iterators 0841 // QVERIFY(testForestIteration(siblingBegin(hierarchyEnd(it0)), 0842 // siblingEnd(hierarchyEnd(it0)), {})); 0843 // QVERIFY(testForestIteration(siblingBegin(compositionEnd(it0)), 0844 // siblingEnd(compositionEnd(it0)), {0,8})); 0845 0846 0847 0848 QVERIFY(testForestIteration(childBegin(childEnd(forest)), 0849 childEnd(childEnd(forest)), {})); 0850 // TODO: we currently don't allow creation of child-iterators from end-non-child-iterators 0851 // QVERIFY(testForestIteration(childBegin(compositionEnd(forest)), 0852 // childEnd(compositionEnd(forest)), {})); 0853 0854 QVERIFY(testForestIteration(hierarchyBegin(childEnd(forest)), 0855 hierarchyEnd(childEnd(forest)), {})); 0856 QVERIFY(testForestIteration(hierarchyBegin(compositionEnd(forest)), 0857 hierarchyEnd(compositionEnd(forest)), {})); 0858 0859 QVERIFY(testForestIteration(compositionBegin(childEnd(forest)), 0860 compositionEnd(childEnd(forest)), {})); 0861 QVERIFY(testForestIteration(compositionBegin(compositionEnd(forest)), 0862 compositionEnd(compositionEnd(forest)), {})); 0863 0864 #ifndef HIDE_UB_NOISE 0865 QEXPECT_FAIL("", "Fetching siblings from forest's child-end should work?", Continue); 0866 QVERIFY(testForestIteration(siblingBegin(childEnd(forest)), 0867 siblingEnd(childEnd(forest)), {0,8})); 0868 QEXPECT_FAIL("", "Fetching siblings from forest's composition-end should work?", Continue); 0869 QVERIFY(testForestIteration(siblingBegin(compositionEnd(forest)), 0870 siblingEnd(compositionEnd(forest)), {0,8})); 0871 #endif 0872 0873 #undef HIDE_UB_NOISE 0874 } 0875 0876 void KisForestTest::testCopyForest() 0877 { 0878 KisForest<int> forest; 0879 0880 /** 0881 * 0 1 0882 * 2 0883 * 3 5 6 0884 * 7 0885 * 4 0886 * 8 9 0887 * 10 0888 **/ 0889 0890 0891 auto it0 = forest.insert(childBegin(forest), 0); 0892 0893 auto it1 = forest.insert(childEnd(it0), 1); 0894 auto it2 = forest.insert(childEnd(it0), 2); 0895 auto it3 = forest.insert(childEnd(it0), 3); 0896 auto it4 = forest.insert(childEnd(it0), 4); 0897 auto it8 = forest.insert(childEnd(it0), 8); 0898 0899 auto it5 = forest.insert(childEnd(it3), 5); 0900 0901 auto it6 = forest.insert(childEnd(it5), 6); 0902 auto it7 = forest.insert(childEnd(it5), 7); 0903 0904 auto it9 = forest.insert(childEnd(it8), 9); 0905 auto it10 = forest.insert(childEnd(it8), 10); 0906 0907 Q_UNUSED(it1); 0908 Q_UNUSED(it2); 0909 Q_UNUSED(it6); 0910 Q_UNUSED(it7); 0911 Q_UNUSED(it4); 0912 Q_UNUSED(it9); 0913 Q_UNUSED(it10); 0914 0915 QVERIFY(testForestIteration(begin(forest), 0916 end(forest), 0917 {0, 1, 2, 3, 5, 6, 7, 4, 8, 9, 10})); 0918 0919 0920 { 0921 KisForest<int> clonedForest = forest; 0922 0923 QVERIFY(testForestIteration(begin(clonedForest), 0924 end(clonedForest), 0925 {0, 1, 2, 3, 5, 6, 7, 4, 8, 9, 10})); 0926 } 0927 0928 { 0929 const KisForest<int> &constForest = forest; 0930 KisForest<int> clonedForest = constForest; 0931 0932 QVERIFY(testForestIteration(begin(clonedForest), 0933 end(clonedForest), 0934 {0, 1, 2, 3, 5, 6, 7, 4, 8, 9, 10})); 0935 } 0936 0937 } 0938 0939 void KisForestTest::testSiblingsOnEndIterator() 0940 { 0941 KisForest<int> forest; 0942 0943 QVERIFY(childBegin(forest) == childEnd(forest)); 0944 0945 // toplevel **end** iterator on an empty forest 0946 { 0947 auto toplevelEndIt = childEnd(forest); 0948 0949 QVERIFY(toplevelEndIt == siblingBegin(toplevelEndIt)); 0950 QVERIFY(toplevelEndIt == siblingCurrent(toplevelEndIt)); 0951 QVERIFY(toplevelEndIt == siblingEnd(toplevelEndIt)); 0952 } 0953 0954 0955 auto it0 = forest.insert(childEnd(forest), 0); 0956 0957 // toplevel iterators on a non-empty forest 0958 { 0959 QVERIFY(it0 == siblingBegin(it0)); 0960 QVERIFY(it0 == siblingCurrent(it0)); 0961 QVERIFY(childEnd(forest) == siblingEnd(it0)); 0962 } 0963 0964 // toplevel **end** iterator on a non-empty forest 0965 { 0966 QVERIFY(it0 == siblingBegin(childEnd(forest))); 0967 QVERIFY(childEnd(forest) == siblingCurrent(childEnd(forest))); 0968 QVERIFY(childEnd(forest) == siblingEnd(childEnd(forest))); 0969 } 0970 0971 auto subordinateEnd = childEnd(it0); 0972 0973 // subordinate **end** iterators on an empty subtree 0974 { 0975 QVERIFY(subordinateEnd == siblingBegin(subordinateEnd)); 0976 QVERIFY(subordinateEnd == siblingCurrent(subordinateEnd)); 0977 QVERIFY(subordinateEnd == siblingEnd(subordinateEnd)); 0978 } 0979 0980 auto parentEnd = forest.parentEnd(); 0981 0982 // iterators on the parentEnd iterator 0983 { 0984 QVERIFY(parentEnd == siblingBegin(parentEnd)); 0985 QVERIFY(parentEnd == siblingCurrent(parentEnd)); 0986 QVERIFY(parentEnd == siblingEnd(parentEnd)); 0987 } 0988 } 0989 0990 void KisForestTest::testParentIterator() 0991 { 0992 KisForest<int> forest; 0993 0994 auto nonExistentEnd = childEnd(forest); 0995 QVERIFY(childBegin(nonExistentEnd) == childEnd(nonExistentEnd)); 0996 QVERIFY(forest.parentEnd() == KisForestDetail::parent(nonExistentEnd)); 0997 0998 // dig into hierarchy of non-existent nodes 0999 { 1000 auto childOfNonExistentEnd = childEnd(nonExistentEnd); 1001 1002 QVERIFY(nonExistentEnd == 1003 KisForestDetail::parent( 1004 childOfNonExistentEnd)); 1005 1006 QVERIFY(forest.parentEnd() == 1007 KisForestDetail::parent( 1008 KisForestDetail::parent( 1009 childOfNonExistentEnd))); 1010 1011 QVERIFY(childBegin(childOfNonExistentEnd) == childEnd(childOfNonExistentEnd)); 1012 1013 QVERIFY(nonExistentEnd != forest.parentEnd()); 1014 QVERIFY(nonExistentEnd != childOfNonExistentEnd); 1015 QVERIFY(KisForestDetail::parent(childOfNonExistentEnd) != forest.parentEnd()); 1016 } 1017 1018 auto it0 = forest.insert(childEnd(forest), 0); 1019 1020 // dig into hierarchy of an existent node 1021 { 1022 QVERIFY(forest.parentEnd() == KisForestDetail::parent(it0)); 1023 1024 QVERIFY(childBegin(it0) == childEnd(it0)); 1025 1026 auto childOfExistentNode = childEnd(it0); 1027 1028 QVERIFY(it0 == KisForestDetail::parent(childOfExistentNode)); 1029 QVERIFY(forest.parentEnd() == 1030 KisForestDetail::parent( 1031 KisForestDetail::parent( 1032 childOfExistentNode))); 1033 } 1034 } 1035 1036 void KisForestTest::testConstChildIterators() 1037 { 1038 KisForest<int> forest; 1039 1040 1041 const KisForest<int> &constForest = forest; 1042 1043 auto constBeginIt = constForest.constChildBegin(); 1044 auto constEndIt = constForest.constChildEnd(); 1045 1046 QVERIFY(constBeginIt == constEndIt); 1047 1048 QVERIFY(constBeginIt == forest.childBegin()); 1049 QVERIFY(constEndIt == forest.childEnd()); 1050 1051 forest.insert(forest.childEnd(), 10); 1052 1053 static_assert(std::is_same_v<decltype(*forest.childBegin()), int&>); 1054 static_assert(std::is_same_v<decltype(*forest.constChildBegin()), const int&>); 1055 1056 static_assert(std::is_same_v<decltype(*constForest.constChildBegin()), const int&>); 1057 static_assert(std::is_same_v<decltype(*constForest.childBegin()), const int&>); 1058 1059 static_assert(std::is_same_v<decltype(*forest.childEnd()), int&>); 1060 static_assert(std::is_same_v<decltype(*forest.constChildEnd()), const int&>); 1061 1062 static_assert(std::is_same_v<decltype(*constForest.constChildEnd()), const int&>); 1063 static_assert(std::is_same_v<decltype(*constForest.childEnd()), const int&>); 1064 1065 static_assert(std::is_same_v<decltype(*forest.parentEnd()), int&>); 1066 static_assert(std::is_same_v<decltype(*forest.constParentEnd()), const int&>); 1067 1068 static_assert(std::is_same_v<decltype(*constForest.constParentEnd()), const int&>); 1069 static_assert(std::is_same_v<decltype(*constForest.parentEnd()), const int&>); 1070 1071 } 1072 1073 void KisForestTest::testConstHierarchyIterators() 1074 { 1075 KisForest<int> forest; 1076 1077 // test on end-iterator 1078 { 1079 auto constIt = forest.constChildBegin(); 1080 auto it = forest.childBegin(); 1081 1082 auto hBegin = hierarchyBegin(it); 1083 auto hEnd = hierarchyBegin(it); 1084 1085 auto hConstBegin = hierarchyBegin(constIt); 1086 auto hConstEnd = hierarchyBegin(constIt); 1087 1088 QVERIFY(hEnd == hConstEnd); 1089 1090 static_assert(std::is_same_v<decltype(*hBegin), int&>); 1091 static_assert(std::is_same_v<decltype(*hEnd), int&>); 1092 1093 static_assert(std::is_same_v<decltype(*hConstBegin), const int&>); 1094 static_assert(std::is_same_v<decltype(*hConstEnd), const int&>); 1095 } 1096 1097 // test on a real element 1098 { 1099 forest.insert(forest.childEnd(), 10); 1100 1101 QVERIFY(forest.childBegin() != forest.childEnd()); 1102 1103 auto hBegin = hierarchyBegin(forest.childBegin()); 1104 auto hConstBegin = hierarchyBegin(forest.constChildBegin()); 1105 1106 QVERIFY(hBegin == hConstBegin); 1107 QVERIFY(*hBegin == *hConstBegin); 1108 } 1109 } 1110 1111 void KisForestTest::testConstSubtreeIterators() 1112 { 1113 KisForest<int> forest; 1114 1115 // test on end-iterator 1116 { 1117 auto constIt = forest.constBegin(); 1118 auto it = forest.begin(); 1119 1120 QVERIFY(it == constIt); 1121 1122 static_assert(std::is_same_v<decltype(*it), int&>); 1123 static_assert(std::is_same_v<decltype(*constIt), const int&>); 1124 } 1125 1126 // test on a real element 1127 { 1128 forest.insert(forest.childEnd(), 10); 1129 1130 QVERIFY(forest.begin() != forest.end()); 1131 1132 QVERIFY(forest.begin() == forest.constBegin()); 1133 QVERIFY(*forest.begin() == *forest.constBegin()); 1134 } 1135 } 1136 1137 void KisForestTest::testConstTailSubtreeIterators() 1138 { 1139 KisForest<int> forest; 1140 1141 // test on end-iterator 1142 { 1143 auto constIt = forest.constDepthFirstTailBegin(); 1144 auto it = forest.depthFirstTailBegin(); 1145 1146 QVERIFY(it == constIt); 1147 1148 static_assert(std::is_same_v<decltype(*it), int&>); 1149 static_assert(std::is_same_v<decltype(*constIt), const int&>); 1150 } 1151 1152 // test on a real element 1153 { 1154 forest.insert(forest.childEnd(), 10); 1155 1156 QVERIFY(forest.depthFirstTailBegin() != forest.depthFirstTailEnd()); 1157 1158 QVERIFY(forest.depthFirstTailBegin() == forest.constDepthFirstTailBegin()); 1159 QVERIFY(*forest.depthFirstTailBegin() == *forest.constDepthFirstTailBegin()); 1160 } 1161 } 1162 1163 1164 void KisForestTest::testConstTailFreeStandingForestFunctions() 1165 { 1166 KisForest<int> forest; 1167 forest.insert(forest.childEnd(), 10); 1168 1169 const KisForest<int> &constForest = forest; 1170 1171 auto comparePair = [] (auto beginIt, auto endIt) 1172 { 1173 static_assert(std::is_same_v<decltype(*beginIt), int&>); 1174 static_assert(std::is_same_v<decltype(*endIt), int&>); 1175 1176 QVERIFY(beginIt != endIt); 1177 QCOMPARE(*beginIt, 10); 1178 }; 1179 1180 auto compareConstPair = [] (auto beginIt, auto endIt) 1181 { 1182 static_assert(std::is_same_v<decltype(*beginIt), const int&>); 1183 static_assert(std::is_same_v<decltype(*endIt), const int&>); 1184 1185 QVERIFY(beginIt != endIt); 1186 QCOMPARE(*beginIt, 10); 1187 }; 1188 1189 1190 comparePair(childBegin(forest), childEnd(forest)); 1191 compareConstPair(childBegin(constForest), childEnd(constForest)); 1192 1193 comparePair(compositionBegin(forest), compositionEnd(forest)); 1194 compareConstPair(compositionBegin(constForest), compositionEnd(constForest)); 1195 1196 comparePair(tailSubtreeBegin(forest), tailSubtreeEnd(forest)); 1197 compareConstPair(tailSubtreeBegin(constForest), tailSubtreeEnd(constForest)); 1198 } 1199 1200 SIMPLE_TEST_MAIN(KisForestTest)