1//! @file test_data_structure.cpp
2//! @author ryftchen
3//! @brief The definitions (test_data_structure) in the test module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2026 ryftchen. All rights reserved.
6
7#include <gtest/gtest.h>
8#include <syncstream>
9
10#include "application/example/include/apply_data_structure.hpp"
11
12//! @brief The test module.
13namespace test // NOLINT(modernize-concat-nested-namespaces)
14{
15//! @brief Data-structure-testing-related functions in the test module.
16namespace tst_ds
17{
18//! @brief Print the progress of the data structure task tests.
19//! @param title - task title
20//! @param state - task state
21//! @param align - alignment width
22static void printTaskProgress(const std::string_view title, const std::string_view state, const std::uint8_t align = 50)
23{
24 std::osyncstream(std::cout) << "TEST DATA STRUCTURE: " << std::setiosflags(std::ios_base::left) << std::setfill('.')
25 << std::setw(align) << title << state << std::resetiosflags(mask: std::ios_base::left)
26 << std::setfill(' ') << std::endl;
27}
28
29//! @brief Test base of cache.
30class CacheTestBase : public ::testing::Test
31{
32private:
33 //! @brief Alias for the showcase.
34 using Showcase = application::app_ds::cache::Showcase;
35
36protected:
37 //! @brief Set up the test case.
38 static void SetUpTestSuite() { printTaskProgress(title, state: "BEGIN"); }
39 //! @brief Tear down the test case.
40 static void TearDownTestSuite() { printTaskProgress(title, state: "END"); }
41
42 //! @brief Test title.
43 inline static const std::string_view title{data_structure::cache::description()};
44 //! @brief System under test.
45 [[no_unique_address]] const Showcase sut{};
46 // clang-format off
47 //! @brief Expected result 1.
48 static constexpr std::string_view expRes1
49 {
50 "insert {A: foo}\n"
51 "insert {B: bar}\n"
52 "insert {C: baz}\n"
53 "find A: true\n"
54 "find B: true\n"
55 "find B: true\n"
56 "find C: true\n"
57 "find A: true\n"
58 "erase D: false\n"
59 "insert {D: qux}\n"
60 "find range {A, B, C, D}: {A: ---}, {B: bar}, {C: baz}, {D: qux}\n"
61 "erase range {B, C}: 2\n"
62 "resolve range {A: ---}, {B: ---}, {C: ---}, {D: ---}: {A: ---}, {B: ---}, {C: ---}, {D: qux}\n"
63 "insert range {A: foo}, {B: bar}, {C: baz}, {D: qux}\n"
64 "whether it is empty: false\n"
65 "size: 3\n"
66 "capacity: 3\n"
67 "current status: {A: ---}, {B: bar}, {C: baz}, {D: qux}\n"
68 };
69 //! @brief Expected result 2.
70 static constexpr std::string_view expRes2
71 {
72 "insert {A: foo}\n"
73 "insert {B: bar}\n"
74 "insert {C: baz}\n"
75 "find A: true\n"
76 "find B: true\n"
77 "find B: true\n"
78 "find C: true\n"
79 "find A: true\n"
80 "erase D: false\n"
81 "insert {D: qux}\n"
82 "find range {A, B, C, D}: {A: foo}, {B: bar}, {C: ---}, {D: qux}\n"
83 "erase range {B, C}: 1\n"
84 "resolve range {A: ---}, {B: ---}, {C: ---}, {D: ---}: {A: foo}, {B: ---}, {C: ---}, {D: qux}\n"
85 "insert range {A: foo}, {B: bar}, {C: baz}, {D: qux}\n"
86 "whether it is empty: false\n"
87 "size: 3\n"
88 "capacity: 3\n"
89 "current status: {A: foo}, {B: ---}, {C: baz}, {D: qux}\n"
90 };
91 //! @brief Expected result 3.
92 static constexpr std::string_view expRes3
93 {
94 "insert {A: foo}\n"
95 "insert {B: bar}\n"
96 "insert {C: baz}\n"
97 "find A: true\n"
98 "find B: true\n"
99 "find B: true\n"
100 "find C: true\n"
101 "find A: true\n"
102 "erase D: false\n"
103 "insert {D: qux}\n"
104 "find range {A, B, C, D}: {A: foo}, {B: ---}, {C: baz}, {D: qux}\n"
105 "erase range {B, C}: 1\n"
106 "resolve range {A: ---}, {B: ---}, {C: ---}, {D: ---}: {A: foo}, {B: ---}, {C: ---}, {D: qux}\n"
107 "insert range {A: foo}, {B: bar}, {C: baz}, {D: qux}\n"
108 "whether it is empty: false\n"
109 "size: 3\n"
110 "capacity: 3\n"
111 "current status: {A: ---}, {B: bar}, {C: baz}, {D: qux}\n"
112 };
113 // clang-format on
114};
115
116//! @brief Test for the first in first out instance in the structure of cache.
117TEST_F(CacheTestBase, FIFOInstance)
118{
119 std::ostringstream result{};
120 ASSERT_NO_THROW(result = sut.fifo());
121 ASSERT_EQ(expRes1, result.str());
122}
123
124//! @brief Test for the least frequently used instance in the structure of cache.
125TEST_F(CacheTestBase, LFUInstance)
126{
127 std::ostringstream result{};
128 ASSERT_NO_THROW(result = sut.lfu());
129 ASSERT_EQ(expRes2, result.str());
130}
131
132//! @brief Test for the least recently used instance in the structure of cache.
133TEST_F(CacheTestBase, LRUInstance)
134{
135 std::ostringstream result{};
136 ASSERT_NO_THROW(result = sut.lru());
137 ASSERT_EQ(expRes3, result.str());
138}
139
140//! @brief Test base of filter.
141class FilterTestBase : public ::testing::Test
142{
143private:
144 //! @brief Alias for the showcase.
145 using Showcase = application::app_ds::filter::Showcase;
146
147protected:
148 //! @brief Set up the test case.
149 static void SetUpTestSuite() { printTaskProgress(title, state: "BEGIN"); }
150 //! @brief Tear down the test case.
151 static void TearDownTestSuite() { printTaskProgress(title, state: "END"); }
152
153 //! @brief Test title.
154 inline static const std::string_view title{data_structure::filter::description()};
155 //! @brief System under test.
156 [[no_unique_address]] const Showcase sut{};
157 // clang-format off
158 //! @brief Expected result 1.
159 static constexpr std::string_view expRes1
160 {
161 "insert {foo://bar/0/baz.qux ... foo://bar/999/baz.qux}: 1000\n"
162 "may contain {foo://bar/0/baz.qux ... foo://bar/999/baz.qux}: 1000\n"
163 "may not contain {foo://bar/1000/baz.qux ... foo://bar/1999/baz.qux}: 1000\n"
164 };
165 //! @brief Expected result 2.
166 static constexpr std::string_view expRes2
167 {
168 "A insert {foo://bar/0/baz.qux ... foo://bar/499/baz.qux}: 500\n"
169 "B insert {foo://bar/500/baz.qux ... foo://bar/999/baz.qux}: 500\n"
170 "C merge A and B: true\n"
171 "C remove {foo://bar/500/baz.qux ... foo://bar/999/baz.qux}: 500\n"
172 "C may contain {foo://bar/0/baz.qux ... foo://bar/499/baz.qux}: 500\n"
173 "C may not contain {foo://bar/500/baz.qux ... foo://bar/999/baz.qux}: 500\n"
174 };
175 // clang-format on
176};
177
178//! @brief Test for the Bloom instance in the structure of filter.
179TEST_F(FilterTestBase, BloomInstance)
180{
181 std::ostringstream result{};
182 ASSERT_NO_THROW(result = sut.bloom());
183 ASSERT_EQ(expRes1, result.str());
184}
185
186//! @brief Test for the quotient instance in the structure of filter.
187TEST_F(FilterTestBase, QuotientInstance)
188{
189 std::ostringstream result{};
190 ASSERT_NO_THROW(result = sut.quotient());
191 ASSERT_EQ(expRes2, result.str());
192}
193
194//! @brief Test base of graph.
195class GraphTestBase : public ::testing::Test
196{
197private:
198 //! @brief Alias for the showcase.
199 using Showcase = application::app_ds::graph::Showcase;
200
201protected:
202 //! @brief Set up the test case.
203 static void SetUpTestSuite() { printTaskProgress(title, state: "BEGIN"); }
204 //! @brief Tear down the test case.
205 static void TearDownTestSuite() { printTaskProgress(title, state: "END"); }
206
207 //! @brief Test title.
208 inline static const std::string_view title{data_structure::graph::description()};
209 //! @brief System under test.
210 [[no_unique_address]] const Showcase sut{};
211 // clang-format off
212 //! @brief Expected result 1.
213 static constexpr std::string_view expRes1
214 {
215 "add vertex A: true\n"
216 "add vertex B: true\n"
217 "add vertex C: true\n"
218 "add vertex D: true\n"
219 "add vertex E: true\n"
220 "add vertex F: true\n"
221 "add vertex G: true\n"
222 "add edge A-C: true\n"
223 "add edge A-D: true\n"
224 "add edge A-F: true\n"
225 "add edge B-C: true\n"
226 "add edge C-D: true\n"
227 "add edge E-G: true\n"
228 "add edge F-G: true\n"
229 "DFS traversal from A: A C B D F G E \n"
230 "BFS traversal from A: A C D F B G E \n"
231 "delete edge A-D: true\n"
232 "delete vertex A: true\n"
233 "DFS traversal from B: B C D \n"
234 "BFS traversal from B: B C D \n"
235 "DFS traversal from F: F G E \n"
236 "BFS traversal from F: F G E \n"
237 };
238 //! @brief Expected result 2.
239 static constexpr std::string_view expRes2
240 {
241 "add vertex A: true\n"
242 "add vertex B: true\n"
243 "add vertex C: true\n"
244 "add vertex D: true\n"
245 "add vertex E: true\n"
246 "add vertex F: true\n"
247 "add vertex G: true\n"
248 "add arc A-B: true\n"
249 "add arc B-C: true\n"
250 "add arc B-E: true\n"
251 "add arc B-F: true\n"
252 "add arc C-E: true\n"
253 "add arc D-C: true\n"
254 "add arc E-B: true\n"
255 "add arc E-D: true\n"
256 "add arc F-G: true\n"
257 "DFS traversal from A: A B C E D F G \n"
258 "BFS traversal from A: A B C E F D G \n"
259 "delete arc E-B: true\n"
260 "delete vertex B: true\n"
261 "DFS traversal from A: A \n"
262 "BFS traversal from A: A \n"
263 "DFS traversal from C: C E D \n"
264 "BFS traversal from C: C E D \n"
265 "DFS traversal from F: F G \n"
266 "BFS traversal from F: F G \n"
267 };
268 // clang-format on
269};
270
271//! @brief Test for the undirected instance in the structure of graph.
272TEST_F(GraphTestBase, UndirectedInstance)
273{
274 std::ostringstream result{};
275 ASSERT_NO_THROW(result = sut.undirected());
276 ASSERT_EQ(expRes1, result.str());
277}
278
279//! @brief Test for the directed instance in the structure of graph.
280TEST_F(GraphTestBase, DirectedInstance)
281{
282 std::ostringstream result{};
283 ASSERT_NO_THROW(result = sut.directed());
284 ASSERT_EQ(expRes2, result.str());
285}
286
287//! @brief Test base of heap.
288class HeapTestBase : public ::testing::Test
289{
290private:
291 //! @brief Alias for the showcase.
292 using Showcase = application::app_ds::heap::Showcase;
293
294protected:
295 //! @brief Set up the test case.
296 static void SetUpTestSuite() { printTaskProgress(title, state: "BEGIN"); }
297 //! @brief Tear down the test case.
298 static void TearDownTestSuite() { printTaskProgress(title, state: "END"); }
299
300 //! @brief Test title.
301 inline static const std::string_view title{data_structure::heap::description()};
302 //! @brief System under test.
303 [[no_unique_address]] const Showcase sut{};
304 // clang-format off
305 //! @brief Expected result 1.
306 static constexpr std::string_view expRes1
307 {
308 "insert 80, 40, 30, 60, 90, 70, 10, 50, 20\n"
309 "traversal: 10 ... 20 ... 30 ... 50 ... 90 ... 70 ... 40 ... 80 ... 60 ... \n"
310 "insert 15: true\n"
311 "traversal: 10 ... 15 ... 30 ... 50 ... 20 ... 70 ... 40 ... 80 ... 60 ... 90 ... \n"
312 "remove 10: true\n"
313 "traversal: 15 ... 20 ... 30 ... 50 ... 90 ... 70 ... 40 ... 80 ... 60 ... \n"
314 };
315 //! @brief Expected result 2.
316 static constexpr std::string_view expRes2
317 {
318 "A insert 10, 40, 24, 30, 36, 20, 12, 16\n"
319 "A all details:\n"
320 "+ 10(2) -> root\n"
321 "+ 24(1) -> 10's left child\n"
322 "+ 30(0) -> 24's left child\n"
323 "+ 36(0) -> 24's right child\n"
324 "+ 12(1) -> 10's right child\n"
325 "+ 20(0) -> 12's left child\n"
326 "+ 40(0) -> 20's left child\n"
327 "+ 16(0) -> 12's right child\n"
328 "B insert 17, 13, 11, 15, 19, 21, 23\n"
329 "B all details:\n"
330 "+ 11(2) -> root\n"
331 "+ 15(1) -> 11's left child\n"
332 "+ 19(0) -> 15's left child\n"
333 "+ 21(0) -> 15's right child\n"
334 "+ 13(1) -> 11's right child\n"
335 "+ 17(0) -> 13's left child\n"
336 "+ 23(0) -> 13's right child\n"
337 "A merge B\n"
338 "A pre-order traversal: 10 ... 11 ... 15 ... 19 ... 21 ... 12 ... 13 ... 17 ... 16 ... 23 ... 20 ... 40 ... 24 ... 30 ... 36 ... \n"
339 "A in-order traversal: 19 ... 15 ... 21 ... 11 ... 17 ... 13 ... 23 ... 16 ... 12 ... 40 ... 20 ... 10 ... 30 ... 24 ... 36 ... \n"
340 "A post-order traversal: 19 ... 21 ... 15 ... 17 ... 23 ... 16 ... 13 ... 40 ... 20 ... 12 ... 11 ... 30 ... 36 ... 24 ... 10 ... \n"
341 "A minimum: 10\n"
342 "A remove\n"
343 "A all details:\n"
344 "+ 11(2) -> root\n"
345 "+ 12(2) -> 11's left child\n"
346 "+ 13(1) -> 12's left child\n"
347 "+ 17(0) -> 13's left child\n"
348 "+ 16(0) -> 13's right child\n"
349 "+ 23(0) -> 16's left child\n"
350 "+ 20(1) -> 12's right child\n"
351 "+ 24(1) -> 20's left child\n"
352 "+ 30(0) -> 24's left child\n"
353 "+ 36(0) -> 24's right child\n"
354 "+ 40(0) -> 20's right child\n"
355 "+ 15(1) -> 11's right child\n"
356 "+ 19(0) -> 15's left child\n"
357 "+ 21(0) -> 15's right child\n"
358 };
359 //! @brief Expected result 3.
360 static constexpr std::string_view expRes3
361 {
362 "A insert 10, 40, 24, 30, 36, 20, 12, 16\n"
363 "A all details:\n"
364 "+ 10 -> root\n"
365 "+ 16 -> 10's left child\n"
366 "+ 20 -> 16's left child\n"
367 "+ 30 -> 20's left child\n"
368 "+ 40 -> 30's left child\n"
369 "+ 12 -> 10's right child\n"
370 "+ 24 -> 12's left child\n"
371 "+ 36 -> 24's left child\n"
372 "B insert 17, 13, 11, 15, 19, 21, 23\n"
373 "B all details:\n"
374 "+ 11 -> root\n"
375 "+ 13 -> 11's left child\n"
376 "+ 17 -> 13's left child\n"
377 "+ 23 -> 17's left child\n"
378 "+ 19 -> 13's right child\n"
379 "+ 15 -> 11's right child\n"
380 "+ 21 -> 15's left child\n"
381 "A merge B\n"
382 "A pre-order traversal: 10 ... 11 ... 12 ... 15 ... 21 ... 24 ... 36 ... 13 ... 17 ... 23 ... 19 ... 16 ... 20 ... 30 ... 40 ... \n"
383 "A in-order traversal: 21 ... 15 ... 12 ... 36 ... 24 ... 11 ... 23 ... 17 ... 13 ... 19 ... 10 ... 40 ... 30 ... 20 ... 16 ... \n"
384 "A post-order traversal: 21 ... 15 ... 36 ... 24 ... 12 ... 23 ... 17 ... 19 ... 13 ... 11 ... 40 ... 30 ... 20 ... 16 ... 10 ... \n"
385 "A minimum: 10\n"
386 "A remove\n"
387 "A all details:\n"
388 "+ 11 -> root\n"
389 "+ 13 -> 11's left child\n"
390 "+ 16 -> 13's left child\n"
391 "+ 19 -> 16's left child\n"
392 "+ 20 -> 16's right child\n"
393 "+ 30 -> 20's left child\n"
394 "+ 40 -> 30's left child\n"
395 "+ 17 -> 13's right child\n"
396 "+ 23 -> 17's left child\n"
397 "+ 12 -> 11's right child\n"
398 "+ 15 -> 12's left child\n"
399 "+ 21 -> 15's left child\n"
400 "+ 24 -> 12's right child\n"
401 "+ 36 -> 24's left child\n"
402 };
403 // clang-format on
404};
405
406//! @brief Test for the binary instance in the structure of heap.
407TEST_F(HeapTestBase, BinaryInstance)
408{
409 std::ostringstream result{};
410 ASSERT_NO_THROW(result = sut.binary());
411 ASSERT_EQ(expRes1, result.str());
412}
413
414//! @brief Test for the leftist instance in the structure of heap.
415TEST_F(HeapTestBase, LeftistInstance)
416{
417 std::ostringstream result{};
418 ASSERT_NO_THROW(result = sut.leftist());
419 ASSERT_EQ(expRes2, result.str());
420}
421
422//! @brief Test for the skew instance in the structure of heap.
423TEST_F(HeapTestBase, SkewInstance)
424{
425 std::ostringstream result{};
426 ASSERT_NO_THROW(result = sut.skew());
427 ASSERT_EQ(expRes3, result.str());
428}
429
430//! @brief Test base of linear.
431class LinearTestBase : public ::testing::Test
432{
433private:
434 //! @brief Alias for the showcase.
435 using Showcase = application::app_ds::linear::Showcase;
436
437protected:
438 //! @brief Set up the test case.
439 static void SetUpTestSuite() { printTaskProgress(title, state: "BEGIN"); }
440 //! @brief Tear down the test case.
441 static void TearDownTestSuite() { printTaskProgress(title, state: "END"); }
442
443 //! @brief Test title.
444 inline static const std::string_view title{data_structure::linear::description()};
445 //! @brief System under test.
446 [[no_unique_address]] const Showcase sut{};
447 // clang-format off
448 //! @brief Expected result 1.
449 static constexpr std::string_view expRes1
450 {
451 "insert (0) 97: true\n"
452 "insert (0) 98: true\n"
453 "insert (0) 99: true\n"
454 "insert (0) 100: true\n"
455 "traversal: 100 ... 99 ... 98 ... 97 ... \n"
456 "remove (1): true\n"
457 "insert (2) 99: true\n"
458 "insert first 97: true\n"
459 "insert last 100: true\n"
460 "get first: 97\n"
461 "get last: 100\n"
462 "remove first: true\n"
463 "remove last: true\n"
464 "whether it is empty: false\n"
465 "size: 4\n"
466 "all details: HEAD -> 100 <-> 98 <-> 99 <-> 97 <- TAIL\n"
467 };
468 //! @brief Expected result 2.
469 static constexpr std::string_view expRes2
470 {
471 "push 97: true\n"
472 "push 98: true\n"
473 "push 99: true\n"
474 "push 100: true\n"
475 "traversal: 100 ... 99 ... 98 ... 97 ... \n"
476 "pop: 100\n"
477 "top: 99\n"
478 "push 100: true\n"
479 "whether it is empty: false\n"
480 "size: 4\n"
481 "all details: TOP [ 100 | 99 | 98 | 97 ] BOTTOM\n"
482 };
483 //! @brief Expected result 3.
484 static constexpr std::string_view expRes3
485 {
486 "push 97: true\n"
487 "push 98: true\n"
488 "push 99: true\n"
489 "push 100: true\n"
490 "traversal: 97 ... 98 ... 99 ... 100 ... \n"
491 "pop: 97\n"
492 "front: 98\n"
493 "push 97: true\n"
494 "whether it is empty: false\n"
495 "size: 4\n"
496 "all details: FRONT [ 98 | 99 | 100 | 97 ] REAR\n"
497 };
498 // clang-format on
499};
500
501//! @brief Test for the doubly linked list instance in the structure of linear.
502TEST_F(LinearTestBase, DLLInstance)
503{
504 std::ostringstream result{};
505 ASSERT_NO_THROW(result = sut.dll());
506 ASSERT_EQ(expRes1, result.str());
507}
508
509//! @brief Test for the stack instance in the structure of linear.
510TEST_F(LinearTestBase, StackInstance)
511{
512 std::ostringstream result{};
513 ASSERT_NO_THROW(result = sut.stack());
514 ASSERT_EQ(expRes2, result.str());
515}
516
517//! @brief Test for the queue instance in the structure of linear.
518TEST_F(LinearTestBase, QueueInstance)
519{
520 std::ostringstream result{};
521 ASSERT_NO_THROW(result = sut.queue());
522 ASSERT_EQ(expRes3, result.str());
523}
524
525//! @brief Test base of tree.
526class TreeTestBase : public ::testing::Test
527{
528private:
529 //! @brief Alias for the showcase.
530 using Showcase = application::app_ds::tree::Showcase;
531
532protected:
533 //! @brief Set up the test case.
534 static void SetUpTestSuite() { printTaskProgress(title, state: "BEGIN"); }
535 //! @brief Tear down the test case.
536 static void TearDownTestSuite() { printTaskProgress(title, state: "END"); }
537
538 //! @brief Test title.
539 inline static const std::string_view title{data_structure::tree::description()};
540 //! @brief System under test.
541 [[no_unique_address]] const Showcase sut{};
542 // clang-format off
543 //! @brief Expected result 1.
544 static constexpr std::string_view expRes1
545 {
546 "insert 1, 5, 4, 3, 2, 6\n"
547 "pre-order traversal: 1 ... 5 ... 4 ... 3 ... 2 ... 6 ... \n"
548 "in-order traversal: 1 ... 2 ... 3 ... 4 ... 5 ... 6 ... \n"
549 "post-order traversal: 2 ... 3 ... 4 ... 6 ... 5 ... 1 ... \n"
550 "minimum: 1\n"
551 "maximum: 6\n"
552 "all details:\n"
553 "+ 1 -> root\n"
554 "+ 5 -> 1's right child\n"
555 "+ 4 -> 5's left child\n"
556 "+ 3 -> 4's left child\n"
557 "+ 2 -> 3's left child\n"
558 "+ 6 -> 5's right child\n"
559 "search 3: true\n"
560 "predecessor of 3: 2\n"
561 "successor of 3: 4\n"
562 "remove 3\n"
563 "in-order traversal: 1 ... 2 ... 4 ... 5 ... 6 ... \n"
564 "all details:\n"
565 "+ 1 -> root\n"
566 "+ 5 -> 1's right child\n"
567 "+ 4 -> 5's left child\n"
568 "+ 2 -> 4's left child\n"
569 "+ 6 -> 5's right child\n"
570 };
571 //! @brief Expected result 2.
572 static constexpr std::string_view expRes2
573 {
574 "height: 0\n"
575 "insert 3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9\n"
576 "pre-order traversal: 7 ... 4 ... 2 ... 1 ... 3 ... 6 ... 5 ... 13 ... 11 ... 9 ... 8 ... 10 ... 12 ... 15 ... 14 ... 16 ... \n"
577 "in-order traversal: 1 ... 2 ... 3 ... 4 ... 5 ... 6 ... 7 ... 8 ... 9 ... 10 ... 11 ... 12 ... 13 ... 14 ... 15 ... 16 ... \n"
578 "post-order traversal: 1 ... 3 ... 2 ... 5 ... 6 ... 4 ... 8 ... 10 ... 9 ... 12 ... 11 ... 14 ... 16 ... 15 ... 13 ... 7 ... \n"
579 "height: 5\n"
580 "minimum: 1\n"
581 "maximum: 16\n"
582 "all details:\n"
583 "+ 7 -> root\n"
584 "+ 4 -> 7's left child\n"
585 "+ 2 -> 4's left child\n"
586 "+ 1 -> 2's left child\n"
587 "+ 3 -> 2's right child\n"
588 "+ 6 -> 4's right child\n"
589 "+ 5 -> 6's left child\n"
590 "+ 13 -> 7's right child\n"
591 "+ 11 -> 13's left child\n"
592 "+ 9 -> 11's left child\n"
593 "+ 8 -> 9's left child\n"
594 "+ 10 -> 9's right child\n"
595 "+ 12 -> 11's right child\n"
596 "+ 15 -> 13's right child\n"
597 "+ 14 -> 15's left child\n"
598 "+ 16 -> 15's right child\n"
599 "search 13: true\n"
600 "remove 13\n"
601 "height: 5\n"
602 "in-order traversal: 1 ... 2 ... 3 ... 4 ... 5 ... 6 ... 7 ... 8 ... 9 ... 10 ... 11 ... 12 ... 14 ... 15 ... 16 ... \n"
603 "all details:\n"
604 "+ 7 -> root\n"
605 "+ 4 -> 7's left child\n"
606 "+ 2 -> 4's left child\n"
607 "+ 1 -> 2's left child\n"
608 "+ 3 -> 2's right child\n"
609 "+ 6 -> 4's right child\n"
610 "+ 5 -> 6's left child\n"
611 "+ 12 -> 7's right child\n"
612 "+ 9 -> 12's left child\n"
613 "+ 8 -> 9's left child\n"
614 "+ 11 -> 9's right child\n"
615 "+ 10 -> 11's left child\n"
616 "+ 15 -> 12's right child\n"
617 "+ 14 -> 15's left child\n"
618 "+ 16 -> 15's right child\n"
619 };
620 //! @brief Expected result 3.
621 static constexpr std::string_view expRes3
622 {
623 "insert 10, 50, 40, 70, 30, 20, 60\n"
624 "pre-order traversal: 60 ... 30 ... 20 ... 10 ... 50 ... 40 ... 70 ... \n"
625 "in-order traversal: 10 ... 20 ... 30 ... 40 ... 50 ... 60 ... 70 ... \n"
626 "post-order traversal: 10 ... 20 ... 40 ... 50 ... 30 ... 70 ... 60 ... \n"
627 "minimum: 10\n"
628 "maximum: 70\n"
629 "all details:\n"
630 "+ 60 -> root\n"
631 "+ 30 -> 60's left child\n"
632 "+ 20 -> 30's left child\n"
633 "+ 10 -> 20's left child\n"
634 "+ 50 -> 30's right child\n"
635 "+ 40 -> 50's left child\n"
636 "+ 70 -> 60's right child\n"
637 "search 70: true\n"
638 "remove 70\n"
639 "in-order traversal: 10 ... 20 ... 30 ... 40 ... 50 ... 60 ... \n"
640 "all details:\n"
641 "+ 60 -> root\n"
642 "+ 30 -> 60's left child\n"
643 "+ 20 -> 30's left child\n"
644 "+ 10 -> 20's left child\n"
645 "+ 50 -> 30's right child\n"
646 "+ 40 -> 50's left child\n"
647 "splay 30\n"
648 "all details:\n"
649 "+ 30 -> root\n"
650 "+ 20 -> 30's left child\n"
651 "+ 10 -> 20's left child\n"
652 "+ 60 -> 30's right child\n"
653 "+ 50 -> 60's left child\n"
654 "+ 40 -> 50's left child\n"
655 };
656 // clang-format on
657};
658
659//! @brief Test for the binary search instance in the structure of tree.
660TEST_F(TreeTestBase, BSInstance)
661{
662 std::ostringstream result{};
663 ASSERT_NO_THROW(result = sut.bs());
664 ASSERT_EQ(expRes1, result.str());
665}
666
667//! @brief Test for the Adelson-Velsky-Landis instance in the structure of tree.
668TEST_F(TreeTestBase, AVLInstance)
669{
670 std::ostringstream result{};
671 ASSERT_NO_THROW(result = sut.avl());
672 ASSERT_EQ(expRes2, result.str());
673}
674
675//! @brief Test for the splay instance in the structure of tree.
676TEST_F(TreeTestBase, SplayInstance)
677{
678 std::ostringstream result{};
679 ASSERT_NO_THROW(result = sut.splay());
680 ASSERT_EQ(expRes3, result.str());
681}
682} // namespace tst_ds
683} // namespace test
684