1//! @file apply_data_structure.hpp
2//! @author ryftchen
3//! @brief The declarations (apply_data_structure) in the application module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2026 ryftchen. All rights reserved.
6
7#pragma once
8
9#ifndef _PRECOMPILED_HEADER
10#include <sstream>
11#else
12#include "application/pch/precompiled_header.hpp"
13#endif
14
15#include "data_structure/include/cache.hpp"
16#include "data_structure/include/filter.hpp"
17#include "data_structure/include/graph.hpp"
18#include "data_structure/include/heap.hpp"
19#include "data_structure/include/linear.hpp"
20#include "data_structure/include/tree.hpp"
21
22//! @brief The application module.
23namespace application // NOLINT(modernize-concat-nested-namespaces)
24{
25//! @brief Data-structure-applying-related functions in the application module.
26namespace app_ds
27{
28//! @brief Apply cache.
29namespace cache
30{
31//! @brief The version used to apply.
32const char* const version = data_structure::cache::version();
33
34//! @brief Separator for each KeyValue or KeyOptValue.
35static constexpr std::string_view separator = ", ";
36//! @brief Alias for the key.
37using Key = char;
38//! @brief Alias for the value.
39using Value = std::string;
40//! @brief Alias for the pair of key and value.
41using KeyValue = std::pair<Key, Value>;
42//! @brief The operator (<<) overloading of the KeyValue type.
43//! @param os - output stream object
44//! @param keyValue - specific KeyValue object
45//! @return reference of the output stream object
46static std::ostream& operator<<(std::ostream& os, const KeyValue& keyValue)
47{
48 os << '{' << keyValue.first << ": " << keyValue.second << '}';
49 return os;
50}
51//! @brief Alias for the range of KeyValue.
52using KeyValueRange = std::vector<KeyValue>;
53//! @brief The operator (<<) overloading of the KeyValueRange type.
54//! @param os - output stream object
55//! @param keyValueRange - specific KeyValueRange object
56//! @return reference of the output stream object
57static std::ostream& operator<<(std::ostream& os, const KeyValueRange& keyValueRange)
58{
59 for (const auto& keyValue : keyValueRange)
60 {
61 os << keyValue << separator;
62 }
63 return os;
64}
65//! @brief Alias for the pair of key and optional value.
66using KeyOptValue = std::pair<Key, std::optional<Value>>;
67//! @brief The operator (<<) overloading of the KeyOptValue type.
68//! @param os - output stream object
69//! @param keyOptValue - specific KeyOptValue object
70//! @return reference of the output stream object
71static std::ostream& operator<<(std::ostream& os, const KeyOptValue& keyOptValue)
72{
73 os << '{' << keyOptValue.first << ": " << (keyOptValue.second.has_value() ? *keyOptValue.second : "---") << '}';
74 return os;
75}
76//! @brief Alias for the range of KeyOptValue.
77using KeyOptValueRange = std::vector<KeyOptValue>;
78//! @brief The operator (<<) overloading of the KeyOptValueRange type.
79//! @param os - output stream object
80//! @param keyOptValueRange - specific KeyOptValueRange object
81//! @return reference of the output stream object
82static std::ostream& operator<<(std::ostream& os, const KeyOptValueRange& keyOptValueRange)
83{
84 for (const auto& keyOptValue : keyOptValueRange)
85 {
86 os << keyOptValue << separator;
87 }
88 return os;
89}
90
91//! @brief Showcase for cache instances.
92class Showcase
93{
94public:
95 //! @brief First in first out.
96 //! @return procedure output
97 static std::ostringstream fifo()
98 {
99 const KeyValue keyValueA = {'A', "foo"};
100 const KeyValue keyValueB = {'B', "bar"};
101 const KeyValue keyValueC = {'C', "baz"};
102 const KeyValue keyValueD = {'D', "qux"};
103 std::ostringstream process{};
104
105 data_structure::cache::FIFO<Key, Value> fifoCache{3};
106 process << std::boolalpha;
107 process << "insert " << keyValueA << '\n';
108 fifoCache.insert(key: 'A', value: "foo");
109 process << "insert " << keyValueB << '\n';
110 fifoCache.insert(key: 'B', value: "bar");
111 process << "insert " << keyValueC << '\n';
112 fifoCache.insert(key: 'C', value: "baz");
113 process << "find A: " << fifoCache.find(key: 'A').has_value() << '\n';
114 process << "find B: " << fifoCache.find(key: 'B').has_value() << '\n';
115 process << "find B: " << fifoCache.find(key: 'B').has_value() << '\n';
116 process << "find C: " << fifoCache.find(key: 'C').has_value() << '\n';
117 process << "find A: " << fifoCache.find(key: 'A').has_value() << '\n';
118 process << "erase D: " << fifoCache.erase(key: 'D') << '\n';
119 process << "insert " << keyValueD << '\n';
120 fifoCache.insert(key: 'D', value: "qux");
121 process << "find range {A, B, C, D}: " << fifoCache.findRange(keyRange: std::vector<Key>{'A', 'B', 'C', 'D'});
122 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
123
124 process << "\nerase range {B, C}: " << fifoCache.eraseRange(keyRange: std::vector<Key>{'B', 'C'}) << '\n';
125 auto resolvedRange =
126 KeyOptValueRange{{'A', std::nullopt}, {'B', std::nullopt}, {'C', std::nullopt}, {'D', std::nullopt}};
127 process << "resolve range " << resolvedRange;
128 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
129 process << ": ";
130 fifoCache.resolveRange(keyOptValueRange&: resolvedRange);
131 process << resolvedRange;
132 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
133
134 auto insertedRange = KeyValueRange{keyValueA, keyValueB, keyValueC, keyValueD};
135 process << "\ninsert range " << insertedRange;
136 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
137 fifoCache.insertRange(keyValueRange: std::move(insertedRange));
138
139 process << "\nwhether it is empty: " << fifoCache.empty() << '\n';
140 process << "size: " << fifoCache.size() << '\n';
141 process << "capacity: " << fifoCache.capacity() << '\n';
142 process << "current status: " << fifoCache.findRange(keyRange: std::vector<Key>{'A', 'B', 'C', 'D'});
143 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
144 return std::ostringstream{process.str().substr(pos: 0, n: process.tellp()) + '\n'};
145 }
146
147 //! @brief Least frequently used.
148 //! @return procedure output
149 static std::ostringstream lfu()
150 {
151 const KeyValue keyValueA = {'A', "foo"};
152 const KeyValue keyValueB = {'B', "bar"};
153 const KeyValue keyValueC = {'C', "baz"};
154 const KeyValue keyValueD = {'D', "qux"};
155 std::ostringstream process{};
156
157 data_structure::cache::LFU<Key, Value> lfuCache{3};
158 process << std::boolalpha;
159 process << "insert " << keyValueA << '\n';
160 lfuCache.insert(key: 'A', value: "foo");
161 process << "insert " << keyValueB << '\n';
162 lfuCache.insert(key: 'B', value: "bar");
163 process << "insert " << keyValueC << '\n';
164 lfuCache.insert(key: 'C', value: "baz");
165 process << "find A: " << lfuCache.find(key: 'A').has_value() << '\n';
166 process << "find B: " << lfuCache.find(key: 'B').has_value() << '\n';
167 process << "find B: " << lfuCache.find(key: 'B').has_value() << '\n';
168 process << "find C: " << lfuCache.find(key: 'C').has_value() << '\n';
169 process << "find A: " << lfuCache.find(key: 'A').has_value() << '\n';
170 process << "erase D: " << lfuCache.erase(key: 'D') << '\n';
171 process << "insert " << keyValueD << '\n';
172 lfuCache.insert(key: 'D', value: "qux");
173 process << "find range {A, B, C, D}: " << lfuCache.findRange(keyRange: std::vector<Key>{'A', 'B', 'C', 'D'});
174 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
175
176 process << "\nerase range {B, C}: " << lfuCache.eraseRange(keyRange: std::vector<Key>{'B', 'C'}) << '\n';
177 auto resolvedRange =
178 KeyOptValueRange{{'A', std::nullopt}, {'B', std::nullopt}, {'C', std::nullopt}, {'D', std::nullopt}};
179 process << "resolve range " << resolvedRange;
180 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
181 process << ": ";
182 lfuCache.resolveRange(keyOptValueRange&: resolvedRange);
183 process << resolvedRange;
184 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
185
186 auto insertedRange = KeyValueRange{keyValueA, keyValueB, keyValueC, keyValueD};
187 process << "\ninsert range " << insertedRange;
188 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
189 lfuCache.insertRange(keyValueRange: std::move(insertedRange));
190
191 process << "\nwhether it is empty: " << lfuCache.empty() << '\n';
192 process << "size: " << lfuCache.size() << '\n';
193 process << "capacity: " << lfuCache.capacity() << '\n';
194 process << "current status: " << lfuCache.findRange(keyRange: std::vector<Key>{'A', 'B', 'C', 'D'});
195 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
196 return std::ostringstream{process.str().substr(pos: 0, n: process.tellp()) + '\n'};
197 }
198
199 //! @brief Least recently used.
200 //! @return procedure output
201 static std::ostringstream lru()
202 {
203 const KeyValue keyValueA = {'A', "foo"};
204 const KeyValue keyValueB = {'B', "bar"};
205 const KeyValue keyValueC = {'C', "baz"};
206 const KeyValue keyValueD = {'D', "qux"};
207 std::ostringstream process{};
208
209 data_structure::cache::LRU<Key, Value> lruCache{3};
210 process << std::boolalpha;
211 process << "insert " << keyValueA << '\n';
212 lruCache.insert(key: 'A', value: "foo");
213 process << "insert " << keyValueB << '\n';
214 lruCache.insert(key: 'B', value: "bar");
215 process << "insert " << keyValueC << '\n';
216 lruCache.insert(key: 'C', value: "baz");
217 process << "find A: " << lruCache.find(key: 'A').has_value() << '\n';
218 process << "find B: " << lruCache.find(key: 'B').has_value() << '\n';
219 process << "find B: " << lruCache.find(key: 'B').has_value() << '\n';
220 process << "find C: " << lruCache.find(key: 'C').has_value() << '\n';
221 process << "find A: " << lruCache.find(key: 'A').has_value() << '\n';
222 process << "erase D: " << lruCache.erase(key: 'D') << '\n';
223 process << "insert " << keyValueD << '\n';
224 lruCache.insert(key: 'D', value: "qux");
225 process << "find range {A, B, C, D}: " << lruCache.findRange(keyRange: std::vector<Key>{'A', 'B', 'C', 'D'});
226 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
227
228 process << "\nerase range {B, C}: " << lruCache.eraseRange(keyRange: std::vector<Key>{'B', 'C'}) << '\n';
229 auto resolvedRange =
230 KeyOptValueRange{{'A', std::nullopt}, {'B', std::nullopt}, {'C', std::nullopt}, {'D', std::nullopt}};
231 process << "resolve range " << resolvedRange;
232 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
233 process << ": ";
234 lruCache.resolveRange(keyOptValueRange&: resolvedRange);
235 process << resolvedRange;
236 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
237
238 auto insertedRange = KeyValueRange{keyValueA, keyValueB, keyValueC, keyValueD};
239 process << "\ninsert range " << insertedRange;
240 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
241 lruCache.insertRange(keyValueRange: std::move(insertedRange));
242
243 process << "\nwhether it is empty: " << lruCache.empty() << '\n';
244 process << "size: " << lruCache.size() << '\n';
245 process << "capacity: " << lruCache.capacity() << '\n';
246 process << "current status: " << lruCache.findRange(keyRange: std::vector<Key>{'A', 'B', 'C', 'D'});
247 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
248 return std::ostringstream{process.str().substr(pos: 0, n: process.tellp()) + '\n'};
249 }
250};
251} // namespace cache
252extern void applyingCache(const std::vector<std::string>& candidates);
253
254//! @brief Apply filter.
255namespace filter
256{
257//! @brief The version used to apply.
258const char* const version = data_structure::filter::version();
259
260//! @brief Showcase for filter instances.
261class Showcase
262{
263public:
264 //! @brief Bloom.
265 //! @return procedure output
266 static std::ostringstream bloom()
267 {
268 constexpr std::uint32_t totalSize = 1000;
269 const std::string keyPart1 = "foo://bar/";
270 const std::string keyPart2 = "/baz.qux";
271 std::ostringstream process{};
272 std::vector<std::string> urls1{};
273 std::vector<std::string> urls2{};
274 urls1.reserve(n: totalSize);
275 urls1.reserve(n: totalSize);
276 for (std::uint32_t i = 0; i < totalSize; ++i)
277 {
278 auto url1 = keyPart1;
279 url1 += std::to_string(val: i);
280 url1 += keyPart2;
281 urls1.emplace_back(args: std::move(url1));
282
283 auto url2 = keyPart1;
284 url2 += std::to_string(val: i + totalSize);
285 url2 += keyPart2;
286 urls2.emplace_back(args: std::move(url2));
287 }
288
289 data_structure::filter::Bloom bf(1e5, 1e-5, 0);
290 process << std::boolalpha;
291 const std::uint32_t inserted = std::accumulate(
292 first: urls1.cbegin(),
293 last: urls1.cend(),
294 init: 0,
295 binary_op: [&bf](const auto acc, const auto& url) { return acc + (bf.insert(key: url.c_str(), length: url.length()) ? 1 : 0); });
296 process << "insert {" << urls1.at(n: 0) << " ... " << urls1.at(n: urls1.size() - 1) << "}: " << inserted << '\n';
297
298 const std::uint32_t mayContained = std::accumulate(
299 first: urls1.cbegin(),
300 last: urls1.cend(),
301 init: 0,
302 binary_op: [&bf](const auto acc, const auto& url)
303 { return acc + (bf.mayContain(key: url.c_str(), length: url.length()) ? 1 : 0); });
304 process << "may contain {" << urls1.at(n: 0) << " ... " << urls1.at(n: urls1.size() - 1) << "}: " << mayContained
305 << '\n';
306 const std::uint32_t mayNotContained = std::accumulate(
307 first: urls2.cbegin(),
308 last: urls2.cend(),
309 init: 0,
310 binary_op: [&bf](const auto acc, const auto& url)
311 { return acc + (!bf.mayContain(key: url.c_str(), length: url.length()) ? 1 : 0); });
312 process << "may not contain {" << urls2.at(n: 0) << " ... " << urls2.at(n: urls2.size() - 1)
313 << "}: " << mayNotContained << '\n';
314 bf.clear();
315 return process;
316 }
317
318 //! @brief Quotient.
319 //! @return procedure output
320 static std::ostringstream quotient()
321 {
322 constexpr std::uint32_t totalSize = 500;
323 const std::string keyPart1 = "foo://bar/";
324 const std::string keyPart2 = "/baz.qux";
325 std::ostringstream process{};
326 std::vector<std::string> urls1{};
327 std::vector<std::string> urls2{};
328 urls1.reserve(n: totalSize);
329 urls1.reserve(n: totalSize);
330 for (std::uint32_t i = 0; i < totalSize; ++i)
331 {
332 auto url1 = keyPart1;
333 url1 += std::to_string(val: i);
334 url1 += keyPart2;
335 urls1.emplace_back(args: std::move(url1));
336
337 auto url2 = keyPart1;
338 url2 += std::to_string(val: i + totalSize);
339 url2 += keyPart2;
340 urls2.emplace_back(args: std::move(url2));
341 }
342
343 data_structure::filter::Quotient qfA(16, 8, 0);
344 data_structure::filter::Quotient qfB(16, 8, 0);
345 data_structure::filter::Quotient qfC(16, 8, 0);
346 process << std::boolalpha;
347 const std::uint32_t insertedA = std::accumulate(
348 first: urls1.cbegin(),
349 last: urls1.cend(),
350 init: 0,
351 binary_op: [&qfA](const auto acc, const auto& url) { return acc + (qfA.insert(url.c_str(), url.length()) ? 1 : 0); });
352 process << "A insert {" << urls1.at(n: 0) << " ... " << urls1.at(n: urls1.size() - 1) << "}: " << insertedA << '\n';
353 const std::uint32_t insertedB = std::accumulate(
354 first: urls2.cbegin(),
355 last: urls2.cend(),
356 init: 0,
357 binary_op: [&qfB](const auto acc, const auto& url) { return acc + (qfB.insert(url.c_str(), url.length()) ? 1 : 0); });
358 process << "B insert {" << urls2.at(n: 0) << " ... " << urls2.at(n: urls2.size() - 1) << "}: " << insertedB << '\n';
359
360 process << "C merge A and B: " << qfC.merge(qf: qfA, others: qfB) << '\n';
361 qfA.clear();
362 qfB.clear();
363
364 const std::uint32_t removedC = std::accumulate(
365 first: urls2.cbegin(),
366 last: urls2.cend(),
367 init: 0,
368 binary_op: [&qfC](const auto acc, const auto& url) { return acc + (qfC.remove(url.c_str(), url.length()) ? 1 : 0); });
369 process << "C remove {" << urls2.at(n: 0) << " ... " << urls2.at(n: urls2.size() - 1) << "}: " << removedC << '\n';
370 const std::uint32_t mayContainedC = std::accumulate(
371 first: urls1.cbegin(),
372 last: urls1.cend(),
373 init: 0,
374 binary_op: [&qfC](const auto acc, const auto& url)
375 { return acc + (qfC.mayContain(url.c_str(), url.length()) ? 1 : 0); });
376 process << "C may contain {" << urls1.at(n: 0) << " ... " << urls1.at(n: urls1.size() - 1) << "}: " << mayContainedC
377 << '\n';
378 const std::uint32_t mayNotContainedC = std::accumulate(
379 first: urls2.cbegin(),
380 last: urls2.cend(),
381 init: 0,
382 binary_op: [&qfC](const auto acc, const auto& url)
383 { return acc + (!qfC.mayContain(url.c_str(), url.length()) ? 1 : 0); });
384 process << "C may not contain {" << urls2.at(n: 0) << " ... " << urls2.at(n: urls2.size() - 1)
385 << "}: " << mayNotContainedC << '\n';
386 qfC.clear();
387 return process;
388 }
389};
390} // namespace filter
391extern void applyingFilter(const std::vector<std::string>& candidates);
392
393//! @brief Apply graph.
394namespace graph
395{
396//! @brief The version used to apply.
397const char* const version = data_structure::graph::version();
398
399//! @brief Alias for the data.
400using Data = char;
401//! @brief Compare function for the data.
402//! @param a - first data
403//! @param b - second data
404//! @return a is less than b if returns -1, a is greater than b if returns 1, and a is equal to b if returns 0
405static int compareData(const void* const a, const void* const b)
406{
407 const auto l = *static_cast<const Data*>(a);
408 const auto r = *static_cast<const Data*>(b);
409 return static_cast<int>(l > r) - static_cast<int>(l < r);
410}
411
412//! @brief Showcase for graph instances.
413class Showcase
414{
415public:
416 // NOLINTBEGIN(readability-magic-numbers)
417 //! @brief Undirected.
418 //! @return procedure output
419 static std::ostringstream undirected()
420 {
421 namespace undirected = data_structure::graph::undirected;
422 using undirected::Traverse;
423 constexpr std::array<Data, 7> vertices = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
424 constexpr std::array<std::array<Data, 2>, 7> edges = {
425 ._M_elems: {{._M_elems: {'A', 'C'}}, {._M_elems: {'A', 'D'}}, {._M_elems: {'A', 'F'}}, {._M_elems: {'B', 'C'}}, {._M_elems: {'C', 'D'}}, {._M_elems: {'E', 'G'}}, {._M_elems: {'F', 'G'}}}};
426 std::ostringstream process{};
427 const auto opInTraversal = [&process](const void* const data)
428 { process << *static_cast<const Data*>(data) << ' '; };
429
430 undirected::AMLGraph* const graph = undirected::create(cmp: compareData);
431 const auto traverse = Traverse(graph);
432 process << std::boolalpha;
433 for (const auto& vertex : vertices)
434 {
435 process << "add vertex " << vertex << ": " << undirected::addVertex(graph, vert: &vertex) << '\n';
436 }
437 for (const auto& edge : edges)
438 {
439 process << "add edge " << edge[0] << '-' << edge[1] << ": "
440 << undirected::addEdge(graph, vert1: edge.data(), vert2: &edge[1]) << '\n';
441 }
442
443 process << "DFS traversal from " << vertices[0] << ": ";
444 traverse.dfs(vert: vertices.data(), op: opInTraversal);
445 process << "\nBFS traversal from " << vertices[0] << ": ";
446 traverse.bfs(vert: vertices.data(), op: opInTraversal);
447
448 process << "\ndelete edge " << edges[1][0] << '-' << edges[1][1] << ": "
449 << undirected::deleteEdge(graph, vert1: edges[1].data(), vert2: &edges[1][1]) << '\n';
450 process << "delete vertex " << vertices[0] << ": " << undirected::deleteVertex(graph, vert: vertices.data()) << '\n';
451
452 process << "DFS traversal from " << vertices[1] << ": ";
453 traverse.dfs(vert: &vertices[1], op: opInTraversal);
454 process << "\nBFS traversal from " << vertices[1] << ": ";
455 traverse.bfs(vert: &vertices[1], op: opInTraversal);
456
457 process << "\nDFS traversal from " << vertices[5] << ": ";
458 traverse.dfs(vert: &vertices[5], op: opInTraversal);
459 process << "\nBFS traversal from " << vertices[5] << ": ";
460 traverse.bfs(vert: &vertices[5], op: opInTraversal);
461 process << '\n';
462 undirected::destroy(graph);
463 return std::ostringstream{process.str()};
464 }
465
466 //! @brief Directed.
467 //! @return procedure output
468 static std::ostringstream directed()
469 {
470 namespace directed = data_structure::graph::directed;
471 using directed::Traverse;
472 constexpr std::array<Data, 7> vertices = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
473 constexpr std::array<std::array<Data, 2>, 9> edges = {
474 ._M_elems: {{._M_elems: {'A', 'B'}},
475 {._M_elems: {'B', 'C'}},
476 {._M_elems: {'B', 'E'}},
477 {._M_elems: {'B', 'F'}},
478 {._M_elems: {'C', 'E'}},
479 {._M_elems: {'D', 'C'}},
480 {._M_elems: {'E', 'B'}},
481 {._M_elems: {'E', 'D'}},
482 {._M_elems: {'F', 'G'}}}};
483 std::ostringstream process{};
484 const auto opInTraversal = [&process](const void* const data)
485 { process << *static_cast<const Data*>(data) << ' '; };
486
487 directed::OLGraph* const graph = directed::create(cmp: compareData);
488 const auto traverse = Traverse(graph);
489 process << std::boolalpha;
490 for (const auto& vertex : vertices)
491 {
492 process << "add vertex " << vertex << ": " << directed::addVertex(graph, vert: &vertex) << '\n';
493 }
494 for (const auto& edge : edges)
495 {
496 process << "add arc " << edge[0] << '-' << edge[1] << ": " << directed::addArc(graph, vert1: edge.data(), vert2: &edge[1])
497 << '\n';
498 }
499
500 process << "DFS traversal from " << vertices[0] << ": ";
501 traverse.dfs(vert: vertices.data(), op: opInTraversal);
502 process << "\nBFS traversal from " << vertices[0] << ": ";
503 traverse.bfs(vert: vertices.data(), op: opInTraversal);
504
505 process << "\ndelete arc " << edges[6][0] << '-' << edges[6][1] << ": "
506 << directed::deleteArc(graph, vert1: edges[6].data(), vert2: &edges[6][1]) << '\n';
507 process << "delete vertex " << vertices[1] << ": " << directed::deleteVertex(graph, vert: &vertices[1]) << '\n';
508
509 process << "DFS traversal from " << vertices[0] << ": ";
510 traverse.dfs(vert: vertices.data(), op: opInTraversal);
511 process << "\nBFS traversal from " << vertices[0] << ": ";
512 traverse.bfs(vert: vertices.data(), op: opInTraversal);
513
514 process << "\nDFS traversal from " << vertices[2] << ": ";
515 traverse.dfs(vert: &vertices[2], op: opInTraversal);
516 process << "\nBFS traversal from " << vertices[2] << ": ";
517 traverse.bfs(vert: &vertices[2], op: opInTraversal);
518
519 process << "\nDFS traversal from " << vertices[5] << ": ";
520 traverse.dfs(vert: &vertices[5], op: opInTraversal);
521 process << "\nBFS traversal from " << vertices[5] << ": ";
522 traverse.bfs(vert: &vertices[5], op: opInTraversal);
523 process << '\n';
524 directed::destroy(graph);
525 return std::ostringstream{process.str()};
526 }
527 // NOLINTEND(readability-magic-numbers)
528};
529} // namespace graph
530extern void applyingGraph(const std::vector<std::string>& candidates);
531
532//! @brief Apply heap.
533namespace heap
534{
535//! @brief The version used to apply.
536const char* const version = data_structure::heap::version();
537
538//! @brief Separator for each Key.
539static constexpr std::string_view separator = ", ";
540//! @brief Alias for the key.
541using Key = std::int16_t;
542//! @brief Compare function for the key.
543//! @param a - first key
544//! @param b - second key
545//! @return a is less than b if returns -1, a is greater than b if returns 1, and a is equal to b if returns 0
546static int compareKey(const void* const a, const void* const b)
547{
548 const auto l = *static_cast<const Key*>(a);
549 const auto r = *static_cast<const Key*>(b);
550 return static_cast<int>(l > r) - static_cast<int>(l < r);
551}
552
553//! @brief Showcase for heap instances.
554class Showcase
555{
556public:
557 //! @brief Binary.
558 //! @return procedure output
559 static std::ostringstream binary()
560 {
561 namespace binary = data_structure::heap::binary;
562 constexpr std::array<Key, 9> keys = {80, 40, 30, 60, 90, 70, 10, 50, 20};
563 constexpr int capacity = 30;
564 std::ostringstream process{};
565 const auto opInTraversal = [&process](const void* const key)
566 { process << *static_cast<const Key*>(key) << " ... "; };
567
568 binary::BinaryHeap* const heap = binary::create(cap: capacity, cmp: compareKey);
569 const auto traverse = binary::Traverse(heap);
570 process << std::boolalpha;
571 process << "insert ";
572 for (const auto& key : keys)
573 {
574 process << key << separator;
575 binary::insert(heap, key: &key);
576 }
577 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
578 process << "\ntraversal: ";
579 traverse.order(op: opInTraversal);
580
581 constexpr Key insertKey = 15;
582 process << "\ninsert " << insertKey << ": " << binary::insert(heap, key: &insertKey) << '\n';
583 process << "traversal: ";
584 traverse.order(op: opInTraversal);
585
586 constexpr Key removeKey = 10;
587 process << "\nremove " << removeKey << ": " << binary::remove(heap, key: &removeKey) << '\n';
588 process << "traversal: ";
589 traverse.order(op: opInTraversal);
590 process << '\n';
591 binary::destroy(heap);
592 return std::ostringstream{process.str()};
593 }
594
595 //! @brief Leftist.
596 //! @return procedure output
597 static std::ostringstream leftist()
598 {
599 namespace leftist = data_structure::heap::leftist;
600 using Traverse = data_structure::heap::Traverse<leftist::LeftistHeap, leftist::Node>;
601 using Printer = data_structure::heap::Printer<leftist::Node, Key>;
602 constexpr std::array<Key, 8> keys1 = {10, 40, 24, 30, 36, 20, 12, 16};
603 constexpr std::array<Key, 7> keys2 = {17, 13, 11, 15, 19, 21, 23};
604 std::ostringstream process{};
605 const auto opInTraversal = [&process](const void* const key)
606 { process << *static_cast<const Key*>(key) << " ... "; };
607
608 leftist::LeftistHeap* const heapA = leftist::create(cmp: compareKey);
609 const auto traverseA = Traverse(heapA);
610 process << std::boolalpha;
611 process << "A insert ";
612 for (const auto& key : keys1)
613 {
614 process << key << separator;
615 leftist::insert(heap: heapA, key: &key);
616 }
617 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
618 process << "\nA all details:\n" << Printer(heapA->root);
619
620 leftist::LeftistHeap* const heapB = leftist::create(cmp: compareKey);
621 process << "B insert ";
622 for (const auto& key : keys2)
623 {
624 process << key << separator;
625 leftist::insert(heap: heapB, key: &key);
626 }
627 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
628 process << "\nB all details:\n" << Printer(heapB->root);
629
630 process << "A merge B\n";
631 leftist::merge(dst: heapA, src: heapB);
632 process << "A pre-order traversal: ";
633 traverseA.preOrder(op: opInTraversal);
634 process << "\nA in-order traversal: ";
635 traverseA.inOrder(op: opInTraversal);
636 process << "\nA post-order traversal: ";
637 traverseA.postOrder(op: opInTraversal);
638
639 process << "\nA minimum: " << *static_cast<Key*>(leftist::getMinimum(heap: heapA)) << '\n';
640 process << "A remove\n";
641 remove(heap: heapA);
642 process << "A all details:\n" << Printer(heapA->root);
643 leftist::destroy(heap: heapA);
644 leftist::destroy(heap: heapB);
645 return std::ostringstream{process.str()};
646 }
647
648 //! @brief Skew.
649 //! @return procedure output
650 static std::ostringstream skew()
651 {
652 namespace skew = data_structure::heap::skew;
653 using Traverse = data_structure::heap::Traverse<skew::SkewHeap, skew::Node>;
654 using Printer = data_structure::heap::Printer<skew::Node, Key>;
655 constexpr std::array<Key, 8> keys1 = {10, 40, 24, 30, 36, 20, 12, 16};
656 constexpr std::array<Key, 7> keys2 = {17, 13, 11, 15, 19, 21, 23};
657 std::ostringstream process{};
658 const auto opInTraversal = [&process](const void* const key)
659 { process << *static_cast<const Key*>(key) << " ... "; };
660
661 skew::SkewHeap* const heapA = skew::create(cmp: compareKey);
662 const auto traverseA = Traverse(heapA);
663 process << std::boolalpha;
664 process << "A insert ";
665 for (const auto& key : keys1)
666 {
667 process << key << separator;
668 skew::insert(heap: heapA, key: &key);
669 }
670 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
671 process << "\nA all details:\n" << Printer(heapA->root);
672
673 skew::SkewHeap* const heapB = skew::create(cmp: compareKey);
674 process << "B insert ";
675 for (const auto& key : keys2)
676 {
677 process << key << separator;
678 skew::insert(heap: heapB, key: &key);
679 }
680 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
681 process << "\nB all details:\n" << Printer(heapB->root);
682
683 process << "A merge B\n";
684 skew::merge(dst: heapA, src: heapB);
685 process << "A pre-order traversal: ";
686 traverseA.preOrder(op: opInTraversal);
687 process << "\nA in-order traversal: ";
688 traverseA.inOrder(op: opInTraversal);
689 process << "\nA post-order traversal: ";
690 traverseA.postOrder(op: opInTraversal);
691
692 process << "\nA minimum: " << *static_cast<Key*>(skew::getMinimum(heap: heapA)) << '\n';
693 process << "A remove\n";
694 remove(heap: heapA);
695 process << "A all details:\n" << Printer(heapA->root);
696 skew::destroy(heap: heapA);
697 skew::destroy(heap: heapB);
698 return std::ostringstream{process.str()};
699 }
700};
701} // namespace heap
702extern void applyingHeap(const std::vector<std::string>& candidates);
703
704//! @brief Apply linear.
705namespace linear
706{
707//! @brief The version used to apply.
708const char* const version = data_structure::linear::version();
709
710//! @brief Alias for the value.
711using Value = std::int16_t;
712
713//! @brief Showcase for linear instances.
714class Showcase
715{
716public:
717 //! @brief Doubly linked list.
718 //! @return procedure output
719 static std::ostringstream dll()
720 {
721 namespace dll = data_structure::linear::dll;
722 using data_structure::linear::Traverse;
723 using Printer = dll::Printer<Value>;
724 constexpr std::array<Value, 4> values = {'a', 'b', 'c', 'd'};
725 std::ostringstream process{};
726
727 dll::DLL linear{};
728 dll::create(dll: &linear);
729 process << std::boolalpha;
730 for (const auto& value : values)
731 {
732 process << "insert (0) " << value << ": " << dll::insert(head: linear, index: 0, value: &value) << '\n';
733 }
734 process << "traversal: ";
735 Traverse(&linear).order(op: [&process](const void* const value)
736 { process << *static_cast<const Value*>(value) << " ... "; });
737
738 process << "\nremove (1): " << dll::remove(head: linear, index: 1) << '\n';
739 process << "insert (2) " << values[2] << ": " << dll::insert(head: linear, index: 2, value: &values[2]) << '\n';
740
741 process << "insert first " << values[0] << ": " << dll::insertFirst(head: linear, value: values.data()) << '\n';
742 process << "insert last " << values[3] << ": " << dll::insertLast(head: linear, value: &values[3]) << '\n';
743 process << "get first: " << *static_cast<Value*>(dll::getFirst(head: linear)) << '\n';
744 process << "get last: " << *static_cast<Value*>(dll::getLast(head: linear)) << '\n';
745 process << "remove first: " << dll::removeFirst(head: linear) << '\n';
746 process << "remove last: " << dll::removeLast(head: linear) << '\n';
747
748 process << "whether it is empty: " << dll::empty(head: linear) << '\n';
749 process << "size: " << dll::size(head: linear) << '\n';
750 process << "all details: " << Printer(&linear) << '\n';
751 dll::destroy(dll: &linear);
752 return std::ostringstream{process.str()};
753 }
754 //! @brief Stack.
755 //! @return procedure output
756 static std::ostringstream stack()
757 {
758 namespace stack = data_structure::linear::stack;
759 using data_structure::linear::Traverse;
760 using Printer = stack::Printer<Value>;
761 constexpr std::array<Value, 4> values = {'a', 'b', 'c', 'd'};
762 std::ostringstream process{};
763
764 stack::Stack linear{};
765 stack::create(stk: &linear);
766 process << std::boolalpha;
767 for (const auto& value : values)
768 {
769 process << "push " << value << ": " << stack::push(head: linear, value: &value) << '\n';
770 }
771 process << "traversal: ";
772 Traverse(&linear).order(op: [&process](const void* const value)
773 { process << *static_cast<const Value*>(value) << " ... "; });
774
775 process << "\npop: " << *static_cast<Value*>(stack::pop(head: linear)) << '\n';
776 process << "top: " << *static_cast<Value*>(stack::top(head: linear)) << '\n';
777 process << "push " << values[3] << ": " << stack::push(head: linear, value: &values[3]) << '\n';
778
779 process << "whether it is empty: " << stack::empty(head: linear) << '\n';
780 process << "size: " << stack::size(head: linear) << '\n';
781 process << "all details: " << Printer(&linear) << '\n';
782 stack::destroy(stk: &linear);
783 return std::ostringstream{process.str()};
784 }
785 //! @brief Queue.
786 //! @return procedure output
787 static std::ostringstream queue()
788 {
789 namespace queue = data_structure::linear::queue;
790 using data_structure::linear::Traverse;
791 using Printer = queue::Printer<Value>;
792 constexpr std::array<Value, 4> values = {'a', 'b', 'c', 'd'};
793 std::ostringstream process{};
794
795 queue::Queue linear{};
796 queue::create(que: &linear);
797 process << std::boolalpha;
798 for (const auto& value : values)
799 {
800 process << "push " << value << ": " << queue::push(head: linear, value: &value) << '\n';
801 }
802 process << "traversal: ";
803 Traverse(&linear).order(op: [&process](const void* const value)
804 { process << *static_cast<const Value*>(value) << " ... "; });
805
806 process << "\npop: " << *static_cast<Value*>(queue::pop(head: linear)) << '\n';
807 process << "front: " << *static_cast<Value*>(queue::front(head: linear)) << '\n';
808 process << "push " << values[0] << ": " << queue::push(head: linear, value: values.data()) << '\n';
809
810 process << "whether it is empty: " << queue::empty(head: linear) << '\n';
811 process << "size: " << queue::size(head: linear) << '\n';
812 process << "all details: " << Printer(&linear) << '\n';
813 queue::destroy(que: &linear);
814 return std::ostringstream{process.str()};
815 }
816};
817} // namespace linear
818extern void applyingLinear(const std::vector<std::string>& candidates);
819
820//! @brief Apply tree.
821namespace tree
822{
823//! @brief The version used to apply.
824const char* const version = data_structure::tree::version();
825
826//! @brief Separator for each Key.
827static constexpr std::string_view separator = ", ";
828//! @brief Alias for the key.
829using Key = std::int16_t;
830//! @brief Compare function for the key.
831//! @param a - first key
832//! @param b - second key
833//! @return a is less than b if returns -1, a is greater than b if returns 1, and a is equal to b if returns 0
834static int compareKey(const void* const a, const void* const b)
835{
836 const auto l = *static_cast<const Key*>(a);
837 const auto r = *static_cast<const Key*>(b);
838 return static_cast<int>(l > r) - static_cast<int>(l < r);
839}
840
841//! @brief Showcase for tree instances.
842class Showcase
843{
844public:
845 //! @brief Binary search.
846 //! @return procedure output
847 static std::ostringstream bs()
848 {
849 namespace bs = data_structure::tree::bs;
850 using Traverse = data_structure::tree::Traverse<bs::BSTree, bs::Node>;
851 using Printer = data_structure::tree::Printer<bs::Node, Key>;
852 constexpr std::array<Key, 6> keys = {1, 5, 4, 3, 2, 6};
853 std::ostringstream process{};
854 const auto opInTraversal = [&process](const void* const key)
855 { process << *static_cast<const Key*>(key) << " ... "; };
856
857 bs::BSTree* const tree = bs::create(cmp: compareKey);
858 const auto traverse = Traverse(tree);
859 process << std::boolalpha;
860 process << "insert ";
861 for (const auto& key : keys)
862 {
863 process << key << separator;
864 bs::insert(tree, key: &key);
865 }
866 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
867
868 process << "\npre-order traversal: ";
869 traverse.preOrder(op: opInTraversal);
870 process << "\nin-order traversal: ";
871 traverse.inOrder(op: opInTraversal);
872 process << "\npost-order traversal: ";
873 traverse.postOrder(op: opInTraversal);
874
875 process << "\nminimum: " << *static_cast<Key*>(bs::getMinimum(tree)->key) << '\n';
876 process << "maximum: " << *static_cast<Key*>(bs::getMaximum(tree)->key) << '\n';
877 process << "all details:\n" << Printer(tree->root);
878
879 constexpr Key searchKey = 3;
880 const auto* const searchNode = bs::search(tree, key: &searchKey);
881 process << "search " << searchKey << ": " << static_cast<bool>(searchNode) << '\n';
882 process << "predecessor of " << searchKey << ": " << *static_cast<Key*>(bs::getPredecessor(x: searchNode)->key)
883 << '\n';
884 process << "successor of " << searchKey << ": " << *static_cast<Key*>(bs::getSuccessor(x: searchNode)->key)
885 << '\n';
886 process << "remove " << searchKey << '\n';
887 bs::remove(tree, key: &searchKey);
888
889 process << "in-order traversal: ";
890 traverse.inOrder(op: opInTraversal);
891 process << "\nall details:\n" << Printer(tree->root);
892 bs::destroy(tree);
893 return std::ostringstream{process.str()};
894 }
895 //! @brief Adelson-Velsky-Landis.
896 //! @return procedure output
897 static std::ostringstream avl()
898 {
899 namespace avl = data_structure::tree::avl;
900 using Traverse = data_structure::tree::Traverse<avl::AVLTree, avl::Node>;
901 using Printer = data_structure::tree::Printer<avl::Node, Key>;
902 constexpr std::array<Key, 16> keys = {3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};
903 std::ostringstream process{};
904 const auto opInTraversal = [&process](const void* const key)
905 { process << *static_cast<const Key*>(key) << " ... "; };
906
907 avl::AVLTree* const tree = avl::create(cmp: compareKey);
908 const auto traverse = Traverse(tree);
909 process << std::boolalpha;
910 process << "height: " << avl::getHeight(tree) << '\n';
911 process << "insert ";
912 for (const auto& key : keys)
913 {
914 process << key << separator;
915 avl::insert(tree, key: &key);
916 }
917 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
918
919 process << "\npre-order traversal: ";
920 traverse.preOrder(op: opInTraversal);
921 process << "\nin-order traversal: ";
922 traverse.inOrder(op: opInTraversal);
923 process << "\npost-order traversal: ";
924 traverse.postOrder(op: opInTraversal);
925
926 process << "\nheight: " << avl::getHeight(tree) << '\n';
927 process << "minimum: " << *static_cast<Key*>(avl::getMinimum(tree)->key) << '\n';
928 process << "maximum: " << *static_cast<Key*>(avl::getMaximum(tree)->key) << '\n';
929 process << "all details:\n" << Printer(tree->root);
930 constexpr Key searchKey = 13;
931 const auto* const searchNode = avl::search(tree, key: &searchKey);
932 process << "search " << searchKey << ": " << static_cast<bool>(searchNode) << '\n';
933 process << "remove " << searchKey << '\n';
934 avl::remove(tree, key: &searchKey);
935
936 process << "height: " << avl::getHeight(tree) << '\n';
937 process << "in-order traversal: ";
938 traverse.inOrder(op: opInTraversal);
939 process << "\nall details:\n" << Printer(tree->root);
940 avl::destroy(tree);
941 return std::ostringstream{process.str()};
942 }
943 //! @brief Splay.
944 //! @return procedure output
945 static std::ostringstream splay()
946 {
947 namespace splay = data_structure::tree::splay;
948 using Traverse = data_structure::tree::Traverse<splay::SplayTree, splay::Node>;
949 using Printer = data_structure::tree::Printer<splay::Node, Key>;
950 constexpr std::array<Key, 7> keys = {10, 50, 40, 70, 30, 20, 60};
951 std::ostringstream process{};
952 const auto opInTraversal = [&process](const void* const key)
953 { process << *static_cast<const Key*>(key) << " ... "; };
954
955 splay::SplayTree* const tree = splay::create(cmp: compareKey);
956 const auto traverse = Traverse(tree);
957 process << std::boolalpha;
958 process << "insert ";
959 for (const auto& key : keys)
960 {
961 process << key << separator;
962 splay::insert(tree, key: &key);
963 }
964 process.seekp(static_cast<std::streamoff>(process.str().length() - separator.length()));
965
966 process << "\npre-order traversal: ";
967 traverse.preOrder(op: opInTraversal);
968 process << "\nin-order traversal: ";
969 traverse.inOrder(op: opInTraversal);
970 process << "\npost-order traversal: ";
971 traverse.postOrder(op: opInTraversal);
972
973 process << "\nminimum: " << *static_cast<Key*>(splay::getMinimum(tree)->key) << '\n';
974 process << "maximum: " << *static_cast<Key*>(splay::getMaximum(tree)->key) << '\n';
975 process << "all details:\n" << Printer(tree->root);
976
977 constexpr Key searchKey = 70;
978 const auto* const searchNode = splay::search(tree, key: &searchKey);
979 process << "search " << searchKey << ": " << static_cast<bool>(searchNode) << '\n';
980 process << "remove " << searchKey << '\n';
981 splay::remove(tree, key: &searchKey);
982
983 process << "in-order traversal: ";
984 traverse.inOrder(op: opInTraversal);
985 process << "\nall details:\n" << Printer(tree->root);
986
987 constexpr Key splayKey = 30;
988 process << "splay " << splayKey << '\n';
989 splay::splay(tree, key: &splayKey);
990
991 process << "all details:\n" << Printer(tree->root);
992 splay::destroy(tree);
993 return std::ostringstream{process.str()};
994 }
995};
996} // namespace tree
997extern void applyingTree(const std::vector<std::string>& candidates);
998} // namespace app_ds
999} // namespace application
1000