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