1//! @file test_algorithm.cpp
2//! @author ryftchen
3//! @brief The definitions (test_algorithm) 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_algorithm.hpp"
11
12//! @brief The test module.
13namespace test // NOLINT(modernize-concat-nested-namespaces)
14{
15//! @brief Algorithm-testing-related functions in the test module.
16namespace tst_algo
17{
18//! @brief Print the progress of the algorithm 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 ALGORITHM: " << 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 match.
30class MatchTestBase : public ::testing::Test
31{
32private:
33 //! @brief Alias for the input builder.
34 using InputBuilder = application::app_algo::match::InputBuilder;
35 //! @brief Prepare scenario.
36 static void prepareScenario()
37 {
38 namespace input = application::app_algo::match::input;
39 fixture = std::make_unique<InputBuilder>(args: input::patternString);
40 }
41 //! @brief Reset scenario.
42 static void resetScenario() { fixture.reset(); }
43
44protected:
45 //! @brief Set up the test case.
46 static void SetUpTestSuite()
47 {
48 printTaskProgress(title, state: "BEGIN");
49 prepareScenario();
50 }
51 //! @brief Tear down the test case.
52 static void TearDownTestSuite()
53 {
54 printTaskProgress(title, state: "END");
55 resetScenario();
56 }
57
58 //! @brief Test title.
59 inline static const std::string_view title{algorithm::match::description()};
60 //! @brief System under test.
61 [[no_unique_address]] const algorithm::match::Match sut{};
62 //! @brief Fixture data.
63 inline static std::unique_ptr<InputBuilder> fixture{};
64 //! @brief Expected result.
65 static constexpr std::int64_t expRes{49702};
66};
67
68//! @brief Test for the Rabin-Karp method in the solution of match.
69TEST_F(MatchTestBase, RKMethod)
70{
71 ASSERT_EQ(
72 expRes,
73 sut.rk(
74 fixture->getMatchingText().get(),
75 fixture->getSinglePattern().get(),
76 fixture->getTextLength(),
77 fixture->getPatternLength()));
78}
79
80//! @brief Test for the Knuth-Morris-Pratt method in the solution of match.
81TEST_F(MatchTestBase, KMPMethod)
82{
83 ASSERT_EQ(
84 expRes,
85 sut.kmp(
86 fixture->getMatchingText().get(),
87 fixture->getSinglePattern().get(),
88 fixture->getTextLength(),
89 fixture->getPatternLength()));
90}
91
92//! @brief Test for the Boyer-Moore method in the solution of match.
93TEST_F(MatchTestBase, BMMethod)
94{
95 ASSERT_EQ(
96 expRes,
97 sut.bm(
98 fixture->getMatchingText().get(),
99 fixture->getSinglePattern().get(),
100 fixture->getTextLength(),
101 fixture->getPatternLength()));
102}
103
104//! @brief Test for the Horspool method in the solution of match.
105TEST_F(MatchTestBase, HorspoolMethod)
106{
107 ASSERT_EQ(
108 expRes,
109 sut.horspool(
110 fixture->getMatchingText().get(),
111 fixture->getSinglePattern().get(),
112 fixture->getTextLength(),
113 fixture->getPatternLength()));
114}
115
116//! @brief Test for the Sunday method in the solution of match.
117TEST_F(MatchTestBase, SundayMethod)
118{
119 ASSERT_EQ(
120 expRes,
121 sut.sunday(
122 fixture->getMatchingText().get(),
123 fixture->getSinglePattern().get(),
124 fixture->getTextLength(),
125 fixture->getPatternLength()));
126}
127
128//! @brief Test base of notation.
129class NotationTestBase : public ::testing::Test
130{
131private:
132 //! @brief Alias for the input builder.
133 using InputBuilder = application::app_algo::notation::InputBuilder;
134 //! @brief Prepare scenario.
135 static void prepareScenario()
136 {
137 namespace input = application::app_algo::notation::input;
138 fixture = std::make_unique<InputBuilder>(args: input::infixString);
139 }
140 //! @brief Reset scenario.
141 static void resetScenario() { fixture.reset(); }
142
143protected:
144 //! @brief Set up the test case.
145 static void SetUpTestSuite()
146 {
147 printTaskProgress(title, state: "BEGIN");
148 prepareScenario();
149 }
150 //! @brief Tear down the test case.
151 static void TearDownTestSuite()
152 {
153 printTaskProgress(title, state: "END");
154 resetScenario();
155 }
156
157 //! @brief Test title.
158 inline static const std::string_view title{algorithm::notation::description()};
159 //! @brief System under test.
160 [[no_unique_address]] const algorithm::notation::Notation sut{};
161 //! @brief Fixture data.
162 inline static std::unique_ptr<InputBuilder> fixture{};
163 //! @brief Expected result 1.
164 static constexpr std::string_view expRes1{"+a-*b^-^cde+f*ghi"};
165 //! @brief Expected result 2.
166 static constexpr std::string_view expRes2{"abcd^e-fgh*+^*+i-"};
167};
168
169//! @brief Test for the prefix method in the solution of notation.
170TEST_F(NotationTestBase, PrefixMethod)
171{
172 ASSERT_EQ(expRes1, sut.prefix(fixture->getInfixNotation()));
173}
174
175//! @brief Test for the postfix method in the solution of notation.
176TEST_F(NotationTestBase, PostfixMethod)
177{
178 ASSERT_EQ(expRes2, sut.postfix(fixture->getInfixNotation()));
179}
180
181//! @brief Test base of optimal.
182class OptimalTestBase : public ::testing::Test
183{
184private:
185 //! @brief Alias for the input builder.
186 using InputBuilder = application::app_algo::optimal::InputBuilder;
187 //! @brief Prepare scenario.
188 static void prepareScenario()
189 {
190 using application::app_algo::optimal::input::SphericalBessel, algorithm::optimal::Gradient,
191 algorithm::optimal::Tabu, algorithm::optimal::Annealing, algorithm::optimal::Particle,
192 algorithm::optimal::Ant, algorithm::optimal::Genetic;
193 fixture = std::make_unique<InputBuilder>(
194 args: SphericalBessel{}, args: SphericalBessel::range1, args: SphericalBessel::range2, args: SphericalBessel::funcDescr);
195 sut.clear();
196 const auto function = fixture->getFunction();
197 sut["Gradient"] = std::make_unique<Gradient>(args: function);
198 sut["Tabu"] = std::make_unique<Tabu>(args: function);
199 sut["Annealing"] = std::make_unique<Annealing>(args: function);
200 sut["Particle"] = std::make_unique<Particle>(args: function);
201 sut["Ant"] = std::make_unique<Ant>(args: function);
202 sut["Genetic"] = std::make_unique<Genetic>(args: function);
203 }
204 //! @brief Reset scenario.
205 static void resetScenario()
206 {
207 fixture.reset();
208 sut.clear();
209 }
210
211protected:
212 //! @brief Set up the test case.
213 static void SetUpTestSuite()
214 {
215 printTaskProgress(title, state: "BEGIN");
216 prepareScenario();
217 }
218 //! @brief Tear down the test case.
219 static void TearDownTestSuite()
220 {
221 printTaskProgress(title, state: "END");
222 resetScenario();
223 }
224
225 //! @brief Test title.
226 inline static const std::string_view title{algorithm::optimal::description()};
227 //! @brief System under test.
228 inline static std::unordered_map<std::string, std::unique_ptr<algorithm::optimal::Optimal>> sut{};
229 //! @brief Fixture data.
230 inline static std::unique_ptr<InputBuilder> fixture{};
231 //! @brief Expected result.
232 static constexpr double expRes{-0.21723};
233 //! @brief Allowable absolute error.
234 static constexpr double absErr{0.1 * ((expRes < 0.0) ? -expRes : expRes)};
235 //! @brief Default precision.
236 static constexpr double defPrec{algorithm::optimal::epsilon};
237};
238
239// NOLINTBEGIN(bugprone-unchecked-optional-access)
240//! @brief Test for the gradient descent method in the solution of optimal.
241TEST_F(OptimalTestBase, GradientDescentMethod)
242{
243 auto& gradient = *sut.at(k: "Gradient");
244 const auto result = gradient(fixture->getRanges().first, fixture->getRanges().second, defPrec);
245 ASSERT_TRUE(result.has_value());
246 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
247 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
248}
249
250//! @brief Test for the tabu method in the solution of optimal.
251TEST_F(OptimalTestBase, TabuMethod)
252{
253 auto& tabu = *sut.at(k: "Tabu");
254 const auto result = tabu(fixture->getRanges().first, fixture->getRanges().second, defPrec);
255 ASSERT_TRUE(result.has_value());
256 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
257 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
258}
259
260//! @brief Test for the simulated annealing method in the solution of optimal.
261TEST_F(OptimalTestBase, SimulatedAnnealingMethod)
262{
263 auto& annealing = *sut.at(k: "Annealing");
264 const auto result = annealing(fixture->getRanges().first, fixture->getRanges().second, defPrec);
265 ASSERT_TRUE(result.has_value());
266 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
267 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
268}
269
270//! @brief Test for the particle swarm method in the solution of optimal.
271TEST_F(OptimalTestBase, ParticleSwarmMethod)
272{
273 auto& particle = *sut.at(k: "Particle");
274 const auto result = particle(fixture->getRanges().first, fixture->getRanges().second, defPrec);
275 ASSERT_TRUE(result.has_value());
276 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
277 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
278}
279
280//! @brief Test for the ant colony method in the solution of optimal.
281TEST_F(OptimalTestBase, AntColonyMethod)
282{
283 auto& ant = *sut.at(k: "Ant");
284 const auto result = ant(fixture->getRanges().first, fixture->getRanges().second, defPrec);
285 ASSERT_TRUE(result.has_value());
286 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
287 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
288}
289
290//! @brief Test for the genetic method in the solution of optimal.
291TEST_F(OptimalTestBase, GeneticMethod)
292{
293 auto& genetic = *sut.at(k: "Genetic");
294 const auto result = genetic(fixture->getRanges().first, fixture->getRanges().second, defPrec);
295 ASSERT_TRUE(result.has_value());
296 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
297 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
298}
299// NOLINTEND(bugprone-unchecked-optional-access)
300
301//! @brief Test base of search.
302class SearchTestBase : public ::testing::Test
303{
304private:
305 //! @brief Alias for the input builder.
306 using InputBuilder = application::app_algo::search::InputBuilder<float>;
307 //! @brief Prepare scenario.
308 static void prepareScenario()
309 {
310 namespace input = application::app_algo::search::input;
311 fixture = std::make_unique<InputBuilder>(args: input::arrayLength, args: input::arrayRangeMin, args: input::arrayRangeMax);
312 expRes.clear();
313 const std::span<const float> orderedArray{fixture->getOrderedArray().get(), fixture->getLength()};
314 const float searchKey = fixture->getSearchKey();
315 const auto range = std::ranges::equal_range(orderedArray, searchKey);
316 for (auto iterator = range.begin(); iterator != range.end(); ++iterator)
317 {
318 expRes.emplace(args: std::distance(first: orderedArray.begin(), last: iterator));
319 }
320 }
321 //! @brief Reset scenario.
322 static void resetScenario()
323 {
324 fixture.reset();
325 expRes.clear();
326 }
327
328protected:
329 //! @brief Set up the test case.
330 static void SetUpTestSuite()
331 {
332 printTaskProgress(title, state: "BEGIN");
333 prepareScenario();
334 }
335 //! @brief Tear down the test case.
336 static void TearDownTestSuite()
337 {
338 printTaskProgress(title, state: "END");
339 resetScenario();
340 }
341
342 //! @brief Test title.
343 inline static const std::string_view title{algorithm::search::description()};
344 //! @brief System under test.
345 [[no_unique_address]] const algorithm::search::Search<float> sut{};
346 //! @brief Fixture data.
347 inline static std::unique_ptr<InputBuilder> fixture{};
348 //! @brief Expected result.
349 inline static std::set<std::int64_t> expRes{};
350};
351
352//! @brief Test for the binary method in the solution of search.
353TEST_F(SearchTestBase, BinaryMethod)
354{
355 ASSERT_TRUE(
356 expRes.contains(sut.binary(fixture->getOrderedArray().get(), fixture->getLength(), fixture->getSearchKey())));
357}
358
359//! @brief Test for the interpolation method in the solution of search.
360TEST_F(SearchTestBase, InterpolationMethod)
361{
362 ASSERT_TRUE(expRes.contains(
363 sut.interpolation(fixture->getOrderedArray().get(), fixture->getLength(), fixture->getSearchKey())));
364}
365
366//! @brief Test for the Fibonacci method in the solution of search.
367TEST_F(SearchTestBase, FibonacciMethod)
368{
369 ASSERT_TRUE(expRes.contains(
370 sut.fibonacci(fixture->getOrderedArray().get(), fixture->getLength(), fixture->getSearchKey())));
371}
372
373//! @brief Test base of sort.
374class SortTestBase : public ::testing::Test
375{
376private:
377 //! @brief Alias for the input builder.
378 using InputBuilder = application::app_algo::sort::InputBuilder<std::int32_t>;
379 //! @brief Prepare scenario.
380 static void prepareScenario()
381 {
382 namespace input = application::app_algo::sort::input;
383 fixture = std::make_unique<InputBuilder>(args: input::arrayLength, args: input::arrayRangeMin, args: input::arrayRangeMax);
384 expRes = std::vector<std::int32_t>{
385 fixture->getRandomArray().get(), fixture->getRandomArray().get() + fixture->getLength()};
386 std::ranges::sort(expRes);
387 }
388 //! @brief Reset scenario.
389 static void resetScenario()
390 {
391 fixture.reset();
392 expRes.clear();
393 }
394
395protected:
396 //! @brief Set up the test case.
397 static void SetUpTestSuite()
398 {
399 printTaskProgress(title, state: "BEGIN");
400 prepareScenario();
401 }
402 //! @brief Tear down the test case.
403 static void TearDownTestSuite()
404 {
405 printTaskProgress(title, state: "END");
406 resetScenario();
407 }
408
409 //! @brief Test title.
410 inline static const std::string_view title{algorithm::sort::description()};
411 //! @brief System under test.
412 [[no_unique_address]] algorithm::sort::Sort<std::int32_t> sut{};
413 //! @brief Fixture data.
414 inline static std::unique_ptr<InputBuilder> fixture{};
415 //! @brief Expected result.
416 inline static std::vector<std::int32_t> expRes{};
417};
418
419//! @brief Test for the bubble method in the solution of sort.
420TEST_F(SortTestBase, BubbleMethod)
421{
422 ASSERT_EQ(expRes, sut.bubble(fixture->getRandomArray().get(), fixture->getLength()));
423}
424
425//! @brief Test for the selection method in the solution of sort.
426TEST_F(SortTestBase, SelectionMethod)
427{
428 ASSERT_EQ(expRes, sut.selection(fixture->getRandomArray().get(), fixture->getLength()));
429}
430
431//! @brief Test for the insertion method in the solution of sort.
432TEST_F(SortTestBase, InsertionMethod)
433{
434 ASSERT_EQ(expRes, sut.insertion(fixture->getRandomArray().get(), fixture->getLength()));
435}
436
437//! @brief Test for the shell method in the solution of sort.
438TEST_F(SortTestBase, ShellMethod)
439{
440 ASSERT_EQ(expRes, sut.shell(fixture->getRandomArray().get(), fixture->getLength()));
441}
442
443//! @brief Test for the merge method in the solution of sort.
444TEST_F(SortTestBase, MergeMethod)
445{
446 ASSERT_EQ(expRes, sut.merge(fixture->getRandomArray().get(), fixture->getLength()));
447}
448
449//! @brief Test for the quick method in the solution of sort.
450TEST_F(SortTestBase, QuickMethod)
451{
452 ASSERT_EQ(expRes, sut.quick(fixture->getRandomArray().get(), fixture->getLength()));
453}
454
455//! @brief Test for the heap method in the solution of sort.
456TEST_F(SortTestBase, HeapMethod)
457{
458 ASSERT_EQ(expRes, sut.heap(fixture->getRandomArray().get(), fixture->getLength()));
459}
460
461//! @brief Test for the counting method in the solution of sort.
462TEST_F(SortTestBase, CountingMethod)
463{
464 ASSERT_EQ(expRes, sut.counting(fixture->getRandomArray().get(), fixture->getLength()));
465}
466
467//! @brief Test for the bucket method in the solution of sort.
468TEST_F(SortTestBase, BucketMethod)
469{
470 ASSERT_EQ(expRes, sut.bucket(fixture->getRandomArray().get(), fixture->getLength()));
471}
472
473//! @brief Test for the radix method in the solution of sort.
474TEST_F(SortTestBase, RadixMethod)
475{
476 ASSERT_EQ(expRes, sut.radix(fixture->getRandomArray().get(), fixture->getLength()));
477}
478} // namespace tst_algo
479} // namespace test
480