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