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