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;
191 fixture = std::make_unique<InputBuilder>(
192 args: SphericalBessel{}, args: SphericalBessel::range1, args: SphericalBessel::range2, args: SphericalBessel::funcDescr);
193 sut.clear();
194 sut["Gradient"] = std::make_unique<algorithm::optimal::Gradient>(args: fixture->getFunction());
195 sut["Tabu"] = std::make_unique<algorithm::optimal::Tabu>(args: fixture->getFunction());
196 sut["Annealing"] = std::make_unique<algorithm::optimal::Annealing>(args: fixture->getFunction());
197 sut["Particle"] = std::make_unique<algorithm::optimal::Particle>(args: fixture->getFunction());
198 sut["Ant"] = std::make_unique<algorithm::optimal::Ant>(args: fixture->getFunction());
199 sut["Genetic"] = std::make_unique<algorithm::optimal::Genetic>(args: fixture->getFunction());
200 }
201 //! @brief Reset scenario.
202 static void resetScenario()
203 {
204 fixture.reset();
205 sut.clear();
206 }
207
208protected:
209 //! @brief Set up the test case.
210 static void SetUpTestSuite()
211 {
212 printTaskProgress(title, state: "BEGIN");
213 prepareScenario();
214 }
215 //! @brief Tear down the test case.
216 static void TearDownTestSuite()
217 {
218 printTaskProgress(title, state: "END");
219 resetScenario();
220 }
221
222 //! @brief Test title.
223 inline static const std::string_view title{algorithm::optimal::description()};
224 //! @brief System under test.
225 inline static std::unordered_map<std::string, std::unique_ptr<algorithm::optimal::Optimal>> sut{};
226 //! @brief Fixture data.
227 inline static std::unique_ptr<InputBuilder> fixture{};
228 //! @brief Expected result.
229 static constexpr double expRes{-0.21723};
230 //! @brief Allowable absolute error.
231 static constexpr double absErr{0.1 * ((expRes < 0.0) ? -expRes : expRes)};
232 //! @brief Default precision.
233 static constexpr double defPrec{algorithm::optimal::epsilon};
234};
235
236// NOLINTBEGIN(bugprone-unchecked-optional-access)
237//! @brief Test for the gradient descent method in the solution of optimal.
238TEST_F(OptimalTestBase, GradientDescentMethod)
239{
240 auto& gradient = *sut.at(k: "Gradient");
241 const auto result = gradient(fixture->getRanges().first, fixture->getRanges().second, defPrec);
242 ASSERT_TRUE(result.has_value());
243 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
244 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
245}
246
247//! @brief Test for the tabu method in the solution of optimal.
248TEST_F(OptimalTestBase, TabuMethod)
249{
250 auto& tabu = *sut.at(k: "Tabu");
251 const auto result = tabu(fixture->getRanges().first, fixture->getRanges().second, defPrec);
252 ASSERT_TRUE(result.has_value());
253 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
254 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
255}
256
257//! @brief Test for the simulated annealing method in the solution of optimal.
258TEST_F(OptimalTestBase, SimulatedAnnealingMethod)
259{
260 auto& annealing = *sut.at(k: "Annealing");
261 const auto result = annealing(fixture->getRanges().first, fixture->getRanges().second, defPrec);
262 ASSERT_TRUE(result.has_value());
263 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
264 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
265}
266
267//! @brief Test for the particle swarm method in the solution of optimal.
268TEST_F(OptimalTestBase, ParticleSwarmMethod)
269{
270 auto& particle = *sut.at(k: "Particle");
271 const auto result = particle(fixture->getRanges().first, fixture->getRanges().second, defPrec);
272 ASSERT_TRUE(result.has_value());
273 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
274 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
275}
276
277//! @brief Test for the ant colony method in the solution of optimal.
278TEST_F(OptimalTestBase, AntColonyMethod)
279{
280 auto& ant = *sut.at(k: "Ant");
281 const auto result = ant(fixture->getRanges().first, fixture->getRanges().second, defPrec);
282 ASSERT_TRUE(result.has_value());
283 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
284 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
285}
286
287//! @brief Test for the genetic method in the solution of optimal.
288TEST_F(OptimalTestBase, GeneticMethod)
289{
290 auto& genetic = *sut.at(k: "Genetic");
291 const auto result = genetic(fixture->getRanges().first, fixture->getRanges().second, defPrec);
292 ASSERT_TRUE(result.has_value());
293 EXPECT_GT(std::get<0>(result.value()), expRes - absErr);
294 EXPECT_LT(std::get<0>(result.value()), expRes + absErr);
295}
296// NOLINTEND(bugprone-unchecked-optional-access)
297
298//! @brief Test base of search.
299class SearchTestBase : public ::testing::Test
300{
301private:
302 //! @brief Alias for the input builder.
303 using InputBuilder = application::app_algo::search::InputBuilder<float>;
304 //! @brief Prepare scenario.
305 static void prepareScenario()
306 {
307 namespace input = application::app_algo::search::input;
308 fixture = std::make_unique<InputBuilder>(args: input::arrayLength, args: input::arrayRangeMin, args: input::arrayRangeMax);
309 expRes.clear();
310 const std::span<const float> orderedArray{fixture->getOrderedArray().get(), fixture->getLength()};
311 const float searchKey = fixture->getSearchKey();
312 const auto range = std::ranges::equal_range(orderedArray, searchKey);
313 for (auto iterator = range.begin(); iterator != range.end(); ++iterator)
314 {
315 expRes.emplace(args: std::distance(first: orderedArray.begin(), last: iterator));
316 }
317 }
318 //! @brief Reset scenario.
319 static void resetScenario()
320 {
321 fixture.reset();
322 expRes.clear();
323 }
324
325protected:
326 //! @brief Set up the test case.
327 static void SetUpTestSuite()
328 {
329 printTaskProgress(title, state: "BEGIN");
330 prepareScenario();
331 }
332 //! @brief Tear down the test case.
333 static void TearDownTestSuite()
334 {
335 printTaskProgress(title, state: "END");
336 resetScenario();
337 }
338
339 //! @brief Test title.
340 inline static const std::string_view title{algorithm::search::description()};
341 //! @brief System under test.
342 [[no_unique_address]] const algorithm::search::Search<float> sut{};
343 //! @brief Fixture data.
344 inline static std::unique_ptr<InputBuilder> fixture{};
345 //! @brief Expected result.
346 inline static std::set<std::int64_t> expRes{};
347};
348
349//! @brief Test for the binary method in the solution of search.
350TEST_F(SearchTestBase, BinaryMethod)
351{
352 ASSERT_TRUE(
353 expRes.contains(sut.binary(fixture->getOrderedArray().get(), fixture->getLength(), fixture->getSearchKey())));
354}
355
356//! @brief Test for the interpolation method in the solution of search.
357TEST_F(SearchTestBase, InterpolationMethod)
358{
359 ASSERT_TRUE(expRes.contains(
360 sut.interpolation(fixture->getOrderedArray().get(), fixture->getLength(), fixture->getSearchKey())));
361}
362
363//! @brief Test for the Fibonacci method in the solution of search.
364TEST_F(SearchTestBase, FibonacciMethod)
365{
366 ASSERT_TRUE(expRes.contains(
367 sut.fibonacci(fixture->getOrderedArray().get(), fixture->getLength(), fixture->getSearchKey())));
368}
369
370//! @brief Test base of sort.
371class SortTestBase : public ::testing::Test
372{
373private:
374 //! @brief Alias for the input builder.
375 using InputBuilder = application::app_algo::sort::InputBuilder<std::int32_t>;
376 //! @brief Prepare scenario.
377 static void prepareScenario()
378 {
379 namespace input = application::app_algo::sort::input;
380 fixture = std::make_unique<InputBuilder>(args: input::arrayLength, args: input::arrayRangeMin, args: input::arrayRangeMax);
381 expRes = std::vector<std::int32_t>{
382 fixture->getRandomArray().get(), fixture->getRandomArray().get() + fixture->getLength()};
383 std::ranges::sort(expRes);
384 }
385 //! @brief Reset scenario.
386 static void resetScenario()
387 {
388 fixture.reset();
389 expRes.clear();
390 }
391
392protected:
393 //! @brief Set up the test case.
394 static void SetUpTestSuite()
395 {
396 printTaskProgress(title, state: "BEGIN");
397 prepareScenario();
398 }
399 //! @brief Tear down the test case.
400 static void TearDownTestSuite()
401 {
402 printTaskProgress(title, state: "END");
403 resetScenario();
404 }
405
406 //! @brief Test title.
407 inline static const std::string_view title{algorithm::sort::description()};
408 //! @brief System under test.
409 [[no_unique_address]] algorithm::sort::Sort<std::int32_t> sut{};
410 //! @brief Fixture data.
411 inline static std::unique_ptr<InputBuilder> fixture{};
412 //! @brief Expected result.
413 inline static std::vector<std::int32_t> expRes{};
414};
415
416//! @brief Test for the bubble method in the solution of sort.
417TEST_F(SortTestBase, BubbleMethod)
418{
419 ASSERT_EQ(expRes, sut.bubble(fixture->getRandomArray().get(), fixture->getLength()));
420}
421
422//! @brief Test for the selection method in the solution of sort.
423TEST_F(SortTestBase, SelectionMethod)
424{
425 ASSERT_EQ(expRes, sut.selection(fixture->getRandomArray().get(), fixture->getLength()));
426}
427
428//! @brief Test for the insertion method in the solution of sort.
429TEST_F(SortTestBase, InsertionMethod)
430{
431 ASSERT_EQ(expRes, sut.insertion(fixture->getRandomArray().get(), fixture->getLength()));
432}
433
434//! @brief Test for the shell method in the solution of sort.
435TEST_F(SortTestBase, ShellMethod)
436{
437 ASSERT_EQ(expRes, sut.shell(fixture->getRandomArray().get(), fixture->getLength()));
438}
439
440//! @brief Test for the merge method in the solution of sort.
441TEST_F(SortTestBase, MergeMethod)
442{
443 ASSERT_EQ(expRes, sut.merge(fixture->getRandomArray().get(), fixture->getLength()));
444}
445
446//! @brief Test for the quick method in the solution of sort.
447TEST_F(SortTestBase, QuickMethod)
448{
449 ASSERT_EQ(expRes, sut.quick(fixture->getRandomArray().get(), fixture->getLength()));
450}
451
452//! @brief Test for the heap method in the solution of sort.
453TEST_F(SortTestBase, HeapMethod)
454{
455 ASSERT_EQ(expRes, sut.heap(fixture->getRandomArray().get(), fixture->getLength()));
456}
457
458//! @brief Test for the counting method in the solution of sort.
459TEST_F(SortTestBase, CountingMethod)
460{
461 ASSERT_EQ(expRes, sut.counting(fixture->getRandomArray().get(), fixture->getLength()));
462}
463
464//! @brief Test for the bucket method in the solution of sort.
465TEST_F(SortTestBase, BucketMethod)
466{
467 ASSERT_EQ(expRes, sut.bucket(fixture->getRandomArray().get(), fixture->getLength()));
468}
469
470//! @brief Test for the radix method in the solution of sort.
471TEST_F(SortTestBase, RadixMethod)
472{
473 ASSERT_EQ(expRes, sut.radix(fixture->getRandomArray().get(), fixture->getLength()));
474}
475} // namespace tst_algo
476} // namespace test
477