1 /*
2 * Copyright (c) 2019 Dmitry Kazakov <dimula73@gmail.com>
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 */
18 #include "KisForestTest.h"
19
20 #include "KisCppQuirks.h"
21 #include "KisForest.h"
22 #include <vector>
23
24 struct IteratorToValue
25 {
26 using value_type = int;
27
28 template <typename Iterator>
operator ()IteratorToValue29 value_type operator() (Iterator it) const {
30 return *it;
31 }
32 };
33
34 template <typename Iterator, typename IteratorValuePolicy = IteratorToValue>
testForestIteration(Iterator begin,Iterator end,std::vector<typename IteratorValuePolicy::value_type> reference,IteratorValuePolicy iteratorToValue=IteratorValuePolicy ())35 bool testForestIteration(Iterator begin, Iterator end,
36 std::vector<typename IteratorValuePolicy::value_type> reference,
37 IteratorValuePolicy iteratorToValue = IteratorValuePolicy())
38 {
39 using value_type = typename IteratorValuePolicy::value_type;
40
41 bool result = true;
42 std::vector<value_type> values;
43
44 std::size_t index = 0;
45 for (auto it = begin; it != end; ++it, ++index) {
46 value_type value = iteratorToValue(it);
47
48 if (index >= reference.size() || value != reference[index]) {
49 result = false;
50 }
51 values.push_back(value);
52
53 // emergency exit in case of infinite loop :)
54 // "40 forest items must be enough for everyone!" (c)
55 if (index > 40) {
56 result = false;
57 break;
58 }
59 }
60
61 result &= values.size() == reference.size();
62
63 if (!result) {
64 qDebug() << "Failed forest iteration:";
65 {
66 QDebug deb = qDebug();
67 deb << " result:";
68 Q_FOREACH(value_type value, values) {
69 deb << value;
70 }
71 }
72 {
73 QDebug deb = qDebug();
74 deb << " ref. :";
75 Q_FOREACH(value_type value, reference) {
76 deb << value;
77 }
78 }
79 }
80
81 return result;
82 }
83
testAddToRoot()84 void KisForestTest::testAddToRoot()
85 {
86 KisForest<int> forest;
87
88 forest.insert(childBegin(forest), 2);
89 forest.insert(childBegin(forest), 1);
90 forest.insert(childBegin(forest), 0);
91 forest.insert(childEnd(forest), 3);
92
93 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0,1,2,3}));
94
95 }
96
testAddToRootChained()97 void KisForestTest::testAddToRootChained()
98 {
99 KisForest<int> forest;
100
101 auto it = forest.insert(childBegin(forest), 3);
102 it = forest.insert(it, 2);
103 it = forest.insert(it, 1);
104 it = forest.insert(it, 0);
105
106 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0,1,2,3}));
107 }
108
testAddToLeaf()109 void KisForestTest::testAddToLeaf()
110 {
111 KisForest<int> forest;
112
113 auto root = forest.insert(childBegin(forest), 0);
114 forest.insert(childBegin(root), 2);
115 forest.insert(childBegin(root), 1);
116 forest.insert(childEnd(root), 3);
117 forest.insert(childEnd(root), 4);
118
119 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0}));
120 QVERIFY(testForestIteration(childBegin(root), childEnd(root), {1,2,3,4}));
121
122 }
123
testAddToLeafChained()124 void KisForestTest::testAddToLeafChained()
125 {
126 KisForest<int> forest;
127
128 auto root = forest.insert(childBegin(forest), 0);
129 auto it = forest.insert(childBegin(root), 4);
130 it = forest.insert(it, 3);
131 it = forest.insert(it, 2);
132 it = forest.insert(it, 1);
133
134 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0}));
135 QVERIFY(testForestIteration(childBegin(root), childEnd(root), {1,2,3,4}));
136
137 }
138
testDFSIteration()139 void KisForestTest::testDFSIteration()
140 {
141 KisForest<int> forest;
142
143 /**
144 * 0 1
145 * 2
146 * 3 5 6
147 * 7
148 * 4
149 * 8 9
150 * 10
151 **/
152
153
154 auto it0 = forest.insert(childBegin(forest), 0);
155 auto it8 = forest.insert(childEnd(forest), 8);
156
157 auto it1 = forest.insert(childEnd(it0), 1);
158 auto it2 = forest.insert(childEnd(it0), 2);
159 auto it3 = forest.insert(childEnd(it0), 3);
160 auto it4 = forest.insert(childEnd(it0), 4);
161
162 auto it5 = forest.insert(childEnd(it3), 5);
163
164 auto it6 = forest.insert(childEnd(it5), 6);
165 auto it7 = forest.insert(childEnd(it5), 7);
166
167 auto it9 = forest.insert(childEnd(it8), 9);
168 auto it10 = forest.insert(childEnd(it8), 10);
169
170 Q_UNUSED(it1);
171 Q_UNUSED(it2);
172 Q_UNUSED(it6);
173 Q_UNUSED(it7);
174 Q_UNUSED(it4);
175 Q_UNUSED(it9);
176 Q_UNUSED(it10);
177
178 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0, 8}));
179 QVERIFY(testForestIteration(childBegin(it0), childEnd(it0), {1,2,3,4}));
180 QVERIFY(testForestIteration(childBegin(it8), childEnd(it8), {9,10}));
181 QVERIFY(testForestIteration(childBegin(it3), childEnd(it3), {5}));
182 QVERIFY(testForestIteration(childBegin(it5), childEnd(it5), {6,7}));
183
184 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,6,7,4,8,9,10}));
185 }
186
testHierarchyIteration()187 void KisForestTest::testHierarchyIteration()
188 {
189 KisForest<int> forest;
190
191 /**
192 * 0 1
193 * 2
194 * 3 5 6
195 * 7
196 * 4
197 * 8 9
198 * 10
199 **/
200
201
202 auto it0 = forest.insert(childBegin(forest), 0);
203 auto it8 = forest.insert(childEnd(forest), 8);
204
205 auto it1 = forest.insert(childEnd(it0), 1);
206 auto it2 = forest.insert(childEnd(it0), 2);
207 auto it3 = forest.insert(childEnd(it0), 3);
208 auto it4 = forest.insert(childEnd(it0), 4);
209
210 auto it5 = forest.insert(childEnd(it3), 5);
211
212 auto it6 = forest.insert(childEnd(it5), 6);
213 auto it7 = forest.insert(childEnd(it5), 7);
214
215 auto it9 = forest.insert(childEnd(it8), 9);
216 auto it10 = forest.insert(childEnd(it8), 10);
217
218 Q_UNUSED(it1);
219 Q_UNUSED(it2);
220 Q_UNUSED(it6);
221 Q_UNUSED(it7);
222 Q_UNUSED(it4);
223 Q_UNUSED(it9);
224 Q_UNUSED(it10);
225
226 QVERIFY(testForestIteration(childBegin(forest), childEnd(forest), {0, 8}));
227 QVERIFY(testForestIteration(childBegin(it0), childEnd(it0), {1,2,3,4}));
228 QVERIFY(testForestIteration(childBegin(it8), childEnd(it8), {9,10}));
229 QVERIFY(testForestIteration(childBegin(it3), childEnd(it3), {5}));
230 QVERIFY(testForestIteration(childBegin(it5), childEnd(it5), {6,7}));
231
232 QVERIFY(testForestIteration(hierarchyBegin(it0), hierarchyEnd(it0), {0}));
233 QVERIFY(testForestIteration(hierarchyBegin(forest.end()), hierarchyEnd(forest.end()), {}));
234
235 QVERIFY(testForestIteration(hierarchyBegin(it7), hierarchyEnd(it7), {7,5,3,0}));
236 QVERIFY(testForestIteration(hierarchyBegin(it5), hierarchyEnd(it5), {5,3,0}));
237 QVERIFY(testForestIteration(hierarchyBegin(it4), hierarchyEnd(it4), {4,0}));
238 QVERIFY(testForestIteration(hierarchyBegin(it10), hierarchyEnd(it10), {10,8}));
239 }
240
testSiblingIteration()241 void KisForestTest::testSiblingIteration()
242 {
243 KisForest<int> forest;
244
245 /**
246 * 0 1
247 * 2
248 * 3 5 6
249 * 7
250 * 4
251 * 8 9
252 * 10
253 **/
254
255
256 auto it0 = forest.insert(childBegin(forest), 0);
257 auto it8 = forest.insert(childEnd(forest), 8);
258
259 auto it1 = forest.insert(childEnd(it0), 1);
260 auto it2 = forest.insert(childEnd(it0), 2);
261 auto it3 = forest.insert(childEnd(it0), 3);
262 auto it4 = forest.insert(childEnd(it0), 4);
263
264 auto it5 = forest.insert(childEnd(it3), 5);
265
266 auto it6 = forest.insert(childEnd(it5), 6);
267 auto it7 = forest.insert(childEnd(it5), 7);
268
269 auto it9 = forest.insert(childEnd(it8), 9);
270 auto it10 = forest.insert(childEnd(it8), 10);
271
272 Q_UNUSED(it1);
273 Q_UNUSED(it2);
274 Q_UNUSED(it6);
275 Q_UNUSED(it7);
276 Q_UNUSED(it4);
277 Q_UNUSED(it9);
278 Q_UNUSED(it10);
279
280 /**
281 * Test if all types of iterators are convertible into a child iterator
282 */
283 QVERIFY(testForestIteration(siblingCurrent(it2), siblingEnd(it2), {2,3,4}));
284 QVERIFY(testForestIteration(siblingCurrent(hierarchyBegin(it2)), siblingEnd(hierarchyBegin(it2)), {2,3,4}));
285 QVERIFY(testForestIteration(siblingCurrent(subtreeBegin(it2)), siblingEnd(subtreeBegin(it2)), {2,3,4}));
286 QVERIFY(testForestIteration(siblingCurrent(tailSubtreeBegin(it2)), siblingEnd(tailSubtreeBegin(it2)), {2,3,4}));
287 QVERIFY(testForestIteration(siblingCurrent(compositionBegin(it2)), siblingEnd(compositionBegin(it2)), {2,3,4}));
288
289 QVERIFY(testForestIteration(siblingCurrent(compositionBegin(childEnd(it0))),
290 siblingEnd(compositionBegin(childEnd(it0))), {}));
291 }
292
testCompositionIteration()293 void KisForestTest::testCompositionIteration()
294 {
295 KisForest<int> forest;
296
297 /**
298 * 0 1
299 * 2
300 * 3 5 6
301 * 7
302 * 4
303 * 8 9
304 * 10
305 **/
306
307
308 auto it0 = forest.insert(childBegin(forest), 0);
309 auto it8 = forest.insert(childEnd(forest), 8);
310
311 auto it1 = forest.insert(childEnd(it0), 1);
312 auto it2 = forest.insert(childEnd(it0), 2);
313 auto it3 = forest.insert(childEnd(it0), 3);
314 auto it4 = forest.insert(childEnd(it0), 4);
315
316 auto it5 = forest.insert(childEnd(it3), 5);
317
318 auto it6 = forest.insert(childEnd(it5), 6);
319 auto it7 = forest.insert(childEnd(it5), 7);
320
321 auto it9 = forest.insert(childEnd(it8), 9);
322 auto it10 = forest.insert(childEnd(it8), 10);
323
324 Q_UNUSED(it1);
325 Q_UNUSED(it2);
326 Q_UNUSED(it6);
327 Q_UNUSED(it7);
328 Q_UNUSED(it4);
329 Q_UNUSED(it9);
330 Q_UNUSED(it10);
331
332 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}));
333
334 }
335
336 struct CompositonIteratorPairedValue
337 {
338 using value_type = std::pair<int, KisForest<int>::composition_iterator::traversal_state>;
339
340 template <typename Iterator>
operator ()CompositonIteratorPairedValue341 value_type operator() (Iterator it) const {
342 return std::make_pair(*it, it.state());
343 }
344 };
345
testCompositionIterationSubtree()346 void KisForestTest::testCompositionIterationSubtree()
347 {
348 KisForest<int> forest;
349
350 /**
351 * 0 1
352 * 2
353 * 3 5 6
354 * 7
355 * 4
356 * 8 9
357 * 10
358 **/
359
360
361 auto it0 = forest.insert(childBegin(forest), 0);
362 auto it8 = forest.insert(childEnd(forest), 8);
363
364 auto it1 = forest.insert(childEnd(it0), 1);
365 auto it2 = forest.insert(childEnd(it0), 2);
366 auto it3 = forest.insert(childEnd(it0), 3);
367 auto it4 = forest.insert(childEnd(it0), 4);
368
369 auto it5 = forest.insert(childEnd(it3), 5);
370
371 auto it6 = forest.insert(childEnd(it5), 6);
372 auto it7 = forest.insert(childEnd(it5), 7);
373
374 auto it9 = forest.insert(childEnd(it8), 9);
375 auto it10 = forest.insert(childEnd(it8), 10);
376
377 Q_UNUSED(it1);
378 Q_UNUSED(it2);
379 Q_UNUSED(it6);
380 Q_UNUSED(it7);
381 Q_UNUSED(it4);
382 Q_UNUSED(it9);
383 Q_UNUSED(it10);
384
385 QVERIFY(testForestIteration(compositionBegin(it3), compositionEnd(it3), {3, 5, 6, 6, 7, 7, 5, 3}));
386 QVERIFY(testForestIteration(compositionBegin(it5), compositionEnd(it5), {5, 6, 6, 7, 7, 5}));
387 QVERIFY(testForestIteration(compositionBegin(it8), compositionEnd(it8), {8, 9, 9, 10, 10, 8}));
388
389 using traversal_direction = KisForest<int>::composition_iterator::traversal_state;
390
391 std::vector<std::pair<int, traversal_direction>> references;
392
393 references = {{5, traversal_direction::Enter},
394 {6, traversal_direction::Enter},
395 {6, traversal_direction::Leave},
396 {7, traversal_direction::Enter},
397 {7, traversal_direction::Leave},
398 {5, traversal_direction::Leave}};
399
400 QVERIFY(testForestIteration(compositionBegin(it5), compositionEnd(it5),
401 references, CompositonIteratorPairedValue()));
402
403 references = {{3, traversal_direction::Enter},
404 {5, traversal_direction::Enter},
405 {6, traversal_direction::Enter},
406 {6, traversal_direction::Leave},
407 {7, traversal_direction::Enter},
408 {7, traversal_direction::Leave},
409 {5, traversal_direction::Leave},
410 {3, traversal_direction::Leave}};
411
412 QVERIFY(testForestIteration(compositionBegin(it3), compositionEnd(it3),
413 references, CompositonIteratorPairedValue()));
414
415 }
416
testSubtreeIteration()417 void KisForestTest::testSubtreeIteration()
418 {
419 KisForest<int> forest;
420
421 /**
422 * 0 1
423 * 2
424 * 3 5 6
425 * 7
426 * 4
427 * 8 9
428 * 10
429 **/
430
431
432 auto it0 = forest.insert(childBegin(forest), 0);
433 auto it8 = forest.insert(childEnd(forest), 8);
434
435 auto it1 = forest.insert(childEnd(it0), 1);
436 auto it2 = forest.insert(childEnd(it0), 2);
437 auto it3 = forest.insert(childEnd(it0), 3);
438 auto it4 = forest.insert(childEnd(it0), 4);
439
440 auto it5 = forest.insert(childEnd(it3), 5);
441
442 auto it6 = forest.insert(childEnd(it5), 6);
443 auto it7 = forest.insert(childEnd(it5), 7);
444
445 auto it9 = forest.insert(childEnd(it8), 9);
446 auto it10 = forest.insert(childEnd(it8), 10);
447
448 Q_UNUSED(it1);
449 Q_UNUSED(it2);
450 Q_UNUSED(it6);
451 Q_UNUSED(it7);
452 Q_UNUSED(it4);
453 Q_UNUSED(it9);
454 Q_UNUSED(it10);
455
456
457 QVERIFY(testForestIteration(subtreeBegin(it3), subtreeEnd(it3), {3,5,6,7}));
458 QVERIFY(testForestIteration(subtreeBegin(it0), subtreeEnd(it0), {0,1,2,3,5,6,7,4}));
459 QVERIFY(testForestIteration(subtreeBegin(it8), subtreeEnd(it8), {8,9,10}));
460 }
461
testSubtreeTailIteration()462 void KisForestTest::testSubtreeTailIteration()
463 {
464 KisForest<int> forest;
465
466 /**
467 * 0 1
468 * 2
469 * 3 5 6
470 * 7
471 * 4
472 * 8 9
473 * 10
474 **/
475
476
477 auto it0 = forest.insert(childBegin(forest), 0);
478 auto it8 = forest.insert(childEnd(forest), 8);
479
480 auto it1 = forest.insert(childEnd(it0), 1);
481 auto it2 = forest.insert(childEnd(it0), 2);
482 auto it3 = forest.insert(childEnd(it0), 3);
483 auto it4 = forest.insert(childEnd(it0), 4);
484
485 auto it5 = forest.insert(childEnd(it3), 5);
486
487 auto it6 = forest.insert(childEnd(it5), 6);
488 auto it7 = forest.insert(childEnd(it5), 7);
489
490 auto it9 = forest.insert(childEnd(it8), 9);
491 auto it10 = forest.insert(childEnd(it8), 10);
492
493 Q_UNUSED(it1);
494 Q_UNUSED(it2);
495 Q_UNUSED(it6);
496 Q_UNUSED(it7);
497 Q_UNUSED(it4);
498 Q_UNUSED(it9);
499 Q_UNUSED(it10);
500
501
502 QVERIFY(testForestIteration(tailSubtreeBegin(it3), tailSubtreeEnd(it3), {6,7,5,3}));
503 QVERIFY(testForestIteration(tailSubtreeBegin(it0), tailSubtreeEnd(it0), {1,2,6,7,5,3,4,0}));
504 QVERIFY(testForestIteration(tailSubtreeBegin(it8), tailSubtreeEnd(it8), {9,10,8}));
505
506 QVERIFY(testForestIteration(tailSubtreeBegin(forest), tailSubtreeEnd(forest), {1,2,6,7,5,3,4,0,9,10,8}));
507 }
508
testEraseNode()509 void KisForestTest::testEraseNode()
510 {
511 KisForest<int> forest;
512
513 /**
514 * 0 1
515 * 2
516 * 3 5 6
517 * 7
518 * 4
519 * 8 9
520 * 10
521 **/
522
523
524 auto it0 = forest.insert(childBegin(forest), 0);
525 auto it8 = forest.insert(childEnd(forest), 8);
526
527 auto it1 = forest.insert(childEnd(it0), 1);
528 auto it2 = forest.insert(childEnd(it0), 2);
529 auto it3 = forest.insert(childEnd(it0), 3);
530 auto it4 = forest.insert(childEnd(it0), 4);
531
532 auto it5 = forest.insert(childEnd(it3), 5);
533
534 auto it6 = forest.insert(childEnd(it5), 6);
535 auto it7 = forest.insert(childEnd(it5), 7);
536
537 auto it9 = forest.insert(childEnd(it8), 9);
538 auto it10 = forest.insert(childEnd(it8), 10);
539
540 Q_UNUSED(it1);
541 Q_UNUSED(it2);
542 Q_UNUSED(it6);
543 Q_UNUSED(it7);
544 Q_UNUSED(it4);
545 Q_UNUSED(it9);
546 Q_UNUSED(it10);
547
548
549 QCOMPARE(forest.erase(it6), it7);
550 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,7,4,8,9,10}));
551
552 QCOMPARE(forest.erase(it7), childEnd(it5));
553 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4,8,9,10}));
554
555 QCOMPARE(forest.erase(it10), childEnd(it8));
556 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4,8,9}));
557
558 QCOMPARE(forest.erase(it9), childEnd(it8));
559 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4,8}));
560
561 QCOMPARE(forest.erase(it8), childEnd(forest));
562 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,3,5,4}));
563 }
564
testEraseSubtree()565 void KisForestTest::testEraseSubtree()
566 {
567 KisForest<int> forest;
568
569 /**
570 * 0 1
571 * 2
572 * 3 5 6
573 * 7
574 * 4
575 * 8 9
576 * 10
577 **/
578
579
580 auto it0 = forest.insert(childBegin(forest), 0);
581 auto it8 = forest.insert(childEnd(forest), 8);
582
583 auto it1 = forest.insert(childEnd(it0), 1);
584 auto it2 = forest.insert(childEnd(it0), 2);
585 auto it3 = forest.insert(childEnd(it0), 3);
586 auto it4 = forest.insert(childEnd(it0), 4);
587
588 auto it5 = forest.insert(childEnd(it3), 5);
589
590 auto it6 = forest.insert(childEnd(it5), 6);
591 auto it7 = forest.insert(childEnd(it5), 7);
592
593 auto it9 = forest.insert(childEnd(it8), 9);
594 auto it10 = forest.insert(childEnd(it8), 10);
595
596 Q_UNUSED(it1);
597 Q_UNUSED(it2);
598 Q_UNUSED(it6);
599 Q_UNUSED(it7);
600 Q_UNUSED(it4);
601 Q_UNUSED(it9);
602 Q_UNUSED(it10);
603
604
605 QCOMPARE(forest.erase(it3), it4);
606 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,4,8,9,10}));
607
608 QCOMPARE(forest.erase(it8), childEnd(forest));
609 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,4}));
610
611 QCOMPARE(forest.erase(it0), childEnd(forest));
612 QVERIFY(testForestIteration(begin(forest), end(forest), {}));
613 }
614
testEraseRange()615 void KisForestTest::testEraseRange()
616 {
617 KisForest<int> forest;
618
619 /**
620 * 0 1
621 * 2
622 * 3 5 6
623 * 7
624 * 4
625 * 8 9
626 * 10
627 */
628
629
630 auto it0 = forest.insert(childBegin(forest), 0);
631 auto it8 = forest.insert(childEnd(forest), 8);
632
633 auto it1 = forest.insert(childEnd(it0), 1);
634 auto it2 = forest.insert(childEnd(it0), 2);
635 auto it3 = forest.insert(childEnd(it0), 3);
636 auto it4 = forest.insert(childEnd(it0), 4);
637
638 auto it5 = forest.insert(childEnd(it3), 5);
639
640 auto it6 = forest.insert(childEnd(it5), 6);
641 auto it7 = forest.insert(childEnd(it5), 7);
642
643 auto it9 = forest.insert(childEnd(it8), 9);
644 auto it10 = forest.insert(childEnd(it8), 10);
645
646 Q_UNUSED(it1);
647 Q_UNUSED(it2);
648 Q_UNUSED(it6);
649 Q_UNUSED(it7);
650 Q_UNUSED(it4);
651 Q_UNUSED(it9);
652 Q_UNUSED(it10);
653
654
655 QCOMPARE(forest.erase(it1, it4), it4);
656 QVERIFY(testForestIteration(begin(forest), end(forest), {0,4,8,9,10}));
657
658 QCOMPARE(forest.erase(it4, childEnd(it0)), childEnd(it0));
659 QVERIFY(testForestIteration(begin(forest), end(forest), {0,8,9,10}));
660 }
661
testMoveSubtree()662 void KisForestTest::testMoveSubtree()
663 {
664 KisForest<int> forest;
665
666 /**
667 * 0 1
668 * 2
669 * 3 5 6
670 * 7
671 * 4
672 * 8 9
673 * 10
674 */
675
676
677 auto it0 = forest.insert(childBegin(forest), 0);
678 auto it8 = forest.insert(childEnd(forest), 8);
679
680 auto it1 = forest.insert(childEnd(it0), 1);
681 auto it2 = forest.insert(childEnd(it0), 2);
682 auto it3 = forest.insert(childEnd(it0), 3);
683 auto it4 = forest.insert(childEnd(it0), 4);
684
685 auto it5 = forest.insert(childEnd(it3), 5);
686
687 auto it6 = forest.insert(childEnd(it5), 6);
688 auto it7 = forest.insert(childEnd(it5), 7);
689
690 auto it9 = forest.insert(childEnd(it8), 9);
691 auto it10 = forest.insert(childEnd(it8), 10);
692
693 Q_UNUSED(it1);
694 Q_UNUSED(it2);
695 Q_UNUSED(it6);
696 Q_UNUSED(it7);
697 Q_UNUSED(it4);
698 Q_UNUSED(it9);
699 Q_UNUSED(it10);
700
701
702 auto newPos = forest.move(it3, it9);
703 QCOMPARE(newPos, childBegin(it8));
704
705 QVERIFY(testForestIteration(begin(forest), end(forest), {0,1,2,4,8,3,5,6,7,9,10}));
706
707 newPos = forest.move(it0, childEnd(it8));
708 QCOMPARE(newPos, std::prev(childEnd(it8)));
709
710 QVERIFY(testForestIteration(begin(forest), end(forest), {8,3,5,6,7,9,10,0,1,2,4}));
711 }
712
testReversedChildIteration()713 void KisForestTest::testReversedChildIteration()
714 {
715 KisForest<int> forest;
716
717 /**
718 * 0 1
719 * 2
720 * 3 5 6
721 * 7
722 * 4
723 * 8 9
724 * 10
725 **/
726
727
728 auto it0 = forest.insert(childBegin(forest), 0);
729 auto it8 = forest.insert(childEnd(forest), 8);
730
731 auto it1 = forest.insert(childEnd(it0), 1);
732 auto it2 = forest.insert(childEnd(it0), 2);
733 auto it3 = forest.insert(childEnd(it0), 3);
734 auto it4 = forest.insert(childEnd(it0), 4);
735
736 auto it5 = forest.insert(childEnd(it3), 5);
737
738 auto it6 = forest.insert(childEnd(it5), 6);
739 auto it7 = forest.insert(childEnd(it5), 7);
740
741 auto it9 = forest.insert(childEnd(it8), 9);
742 auto it10 = forest.insert(childEnd(it8), 10);
743
744 Q_UNUSED(it1);
745 Q_UNUSED(it2);
746 Q_UNUSED(it6);
747 Q_UNUSED(it7);
748 Q_UNUSED(it4);
749 Q_UNUSED(it9);
750 Q_UNUSED(it10);
751
752 QVERIFY(testForestIteration(make_reverse_iterator(childEnd(forest)),
753 make_reverse_iterator(childBegin(forest)), {8, 0}));
754
755 QVERIFY(testForestIteration(make_reverse_iterator(childEnd(it0)),
756 make_reverse_iterator(childBegin(it0)), {4,3,2,1}));
757
758 QVERIFY(testForestIteration(make_reverse_iterator(childEnd(it3)),
759 make_reverse_iterator(childBegin(it3)), {5}));
760 }
761
testConversionsFromEnd()762 void KisForestTest::testConversionsFromEnd()
763 {
764 KisForest<int> forest;
765
766 /**
767 * 0 1
768 * 2
769 * 3 5 6
770 * 7
771 * 4
772 * 8 9
773 * 10
774 **/
775
776
777 auto it0 = forest.insert(childBegin(forest), 0);
778 auto it8 = forest.insert(childEnd(forest), 8);
779
780 auto it1 = forest.insert(childEnd(it0), 1);
781 auto it2 = forest.insert(childEnd(it0), 2);
782 auto it3 = forest.insert(childEnd(it0), 3);
783 auto it4 = forest.insert(childEnd(it0), 4);
784
785 auto it5 = forest.insert(childEnd(it3), 5);
786
787 auto it6 = forest.insert(childEnd(it5), 6);
788 auto it7 = forest.insert(childEnd(it5), 7);
789
790 auto it9 = forest.insert(childEnd(it8), 9);
791 auto it10 = forest.insert(childEnd(it8), 10);
792
793 Q_UNUSED(it1);
794 Q_UNUSED(it2);
795 Q_UNUSED(it6);
796 Q_UNUSED(it7);
797 Q_UNUSED(it4);
798 Q_UNUSED(it9);
799 Q_UNUSED(it10);
800
801 /**
802 * Currently, all operations on end-iterators are declared as "undefined behavior",
803 * but, ideally, we should care about them. Like, it should be possible to get children
804 * of the forest by calling childBegin/End(hierarchyEnd(it0)). I (DK) am not sure if
805 * it is possible to implement without overhead. So I just added this test to document
806 * "desired" behavior. But for now, noone should rely on this behavior, just consider
807 * all operations with end-iterators as UB.
808 */
809
810 #define HIDE_UB_NOISE
811
812 QVERIFY(testForestIteration(childBegin(childEnd(it0)),
813 childEnd(childEnd(it0)), {}));
814
815 #ifndef HIDE_UB_NOISE
816 QEXPECT_FAIL("", "Fetching children of root node should return roots of the forest?", Continue);
817 QVERIFY(testForestIteration(childBegin(hierarchyEnd(it0)),
818 childEnd(hierarchyEnd(it0)), {0, 8}));
819 QEXPECT_FAIL("", "End of composition should not (?) point to any existing node", Continue);
820 QVERIFY(testForestIteration(childBegin(compositionEnd(it0)),
821 childEnd(compositionEnd(it0)), {}));
822 #endif
823
824 QVERIFY(testForestIteration(hierarchyBegin(childEnd(it0)),
825 hierarchyEnd(childEnd(it0)), {}));
826 QVERIFY(testForestIteration(hierarchyBegin(hierarchyEnd(it0)),
827 hierarchyEnd(hierarchyEnd(it0)), {}));
828 #ifndef HIDE_UB_NOISE
829 QEXPECT_FAIL("", "End of composition should not (?) point to any existing node", Continue);
830 QVERIFY(testForestIteration(hierarchyBegin(compositionEnd(it0)),
831 hierarchyEnd(compositionEnd(it0)), {}));
832 #endif
833
834 QVERIFY(testForestIteration(compositionBegin(childEnd(it0)),
835 compositionEnd(childEnd(it0)), {}));
836 #ifndef HIDE_UB_NOISE
837 QEXPECT_FAIL("", "Starting composition on the root node should behave like we do it for the forest itself?", Continue);
838 QVERIFY(testForestIteration(compositionBegin(hierarchyEnd(it0)),
839 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}));
840 QEXPECT_FAIL("", "End of composition should not (?) point to any existing node", Continue);
841 QVERIFY(testForestIteration(compositionBegin(compositionEnd(it0)),
842 compositionEnd(compositionEnd(it0)), {}));
843 #endif
844
845 #ifndef HIDE_UB_NOISE
846 QEXPECT_FAIL("", "Fetching siblings from child-end should work?", Continue);
847 QVERIFY(testForestIteration(siblingBegin(childEnd(it0)),
848 siblingEnd(childEnd(it0)), {1,2,3,4}));
849 #endif
850 QVERIFY(testForestIteration(siblingBegin(hierarchyEnd(it0)),
851 siblingEnd(hierarchyEnd(it0)), {}));
852 QVERIFY(testForestIteration(siblingBegin(compositionEnd(it0)),
853 siblingEnd(compositionEnd(it0)), {0,8}));
854
855
856
857 QVERIFY(testForestIteration(childBegin(childEnd(forest)),
858 childEnd(childEnd(forest)), {}));
859 QVERIFY(testForestIteration(childBegin(compositionEnd(forest)),
860 childEnd(compositionEnd(forest)), {}));
861
862 QVERIFY(testForestIteration(hierarchyBegin(childEnd(forest)),
863 hierarchyEnd(childEnd(forest)), {}));
864 QVERIFY(testForestIteration(hierarchyBegin(compositionEnd(forest)),
865 hierarchyEnd(compositionEnd(forest)), {}));
866
867 QVERIFY(testForestIteration(compositionBegin(childEnd(forest)),
868 compositionEnd(childEnd(forest)), {}));
869 QVERIFY(testForestIteration(compositionBegin(compositionEnd(forest)),
870 compositionEnd(compositionEnd(forest)), {}));
871
872 #ifndef HIDE_UB_NOISE
873 QEXPECT_FAIL("", "Fetching siblings from forest's child-end should work?", Continue);
874 QVERIFY(testForestIteration(siblingBegin(childEnd(forest)),
875 siblingEnd(childEnd(forest)), {0,8}));
876 QEXPECT_FAIL("", "Fetching siblings from forest's composition-end should work?", Continue);
877 QVERIFY(testForestIteration(siblingBegin(compositionEnd(forest)),
878 siblingEnd(compositionEnd(forest)), {0,8}));
879 #endif
880
881 #undef HIDE_UB_NOISE
882 }
883
884 QTEST_MAIN(KisForestTest)
885