1//! @file linear.hpp
2//! @author ryftchen
3//! @brief The declarations (linear) in the data structure module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2026 ryftchen. All rights reserved.
6
7#pragma once
8
9#include <functional>
10#include <ostream>
11
12//! @brief The data structure module.
13namespace data_structure // NOLINT(modernize-concat-nested-namespaces)
14{
15//! @brief Linear-related functions in the data structure module.
16namespace linear
17{
18//! @brief Brief function description.
19//! @return function description (module_function)
20inline static const char* description() noexcept
21{
22 return "DS_LINEAR";
23}
24extern const char* version() noexcept;
25
26#ifdef __cplusplus
27extern "C"
28{
29#endif
30#pragma pack(push, 8)
31 //! @brief The node of the linear structure.
32 typedef struct Node
33 {
34 //! @brief Pointer to the previous node.
35 struct Node* prev;
36 //! @brief Pointer to the next node.
37 struct Node* next;
38 //! @brief Node value.
39 void* value;
40 }* Linear;
41#pragma pack(pop)
42#ifdef __cplusplus
43}
44#endif
45
46//! @brief The doubly linked list structure.
47namespace dll
48{
49//! @brief Alias for the linear structure. Used for the doubly linked list.
50using DLL = Linear;
51
52extern bool create(DLL* const dll);
53extern bool destroy(DLL* const dll);
54extern int size(const DLL head);
55extern bool empty(const DLL head);
56extern void* get(const DLL head, const int index);
57extern void* getFirst(const DLL head);
58extern void* getLast(const DLL head);
59extern bool insert(const DLL head, const int index, const void* const value);
60extern bool insertFirst(const DLL head, const void* const value);
61extern bool insertLast(const DLL head, const void* const value);
62extern bool remove(const DLL head, const int index);
63extern bool removeFirst(const DLL head);
64extern bool removeLast(const DLL head);
65
66//! @brief Print the doubly linked list.
67//! @tparam Value - type of node value
68template <typename Value>
69class Printer
70{
71public:
72 //! @brief Construct a new Printer object.
73 //! @param dll - doubly linked list to print
74 explicit Printer(const DLL* const dll) : dll{dll} {}
75
76private:
77 //! @brief The doubly linked list to print.
78 const DLL* const dll{nullptr};
79
80protected:
81 template <typename NV>
82 friend std::ostream& operator<<(std::ostream&, const Printer<NV>&);
83};
84
85//! @brief The operator (<<) overloading of the Printer class.
86//! @tparam NV - type of node value
87//! @param os - output stream object
88//! @param printer - specific Printer object
89//! @return reference of the output stream object
90template <typename NV>
91std::ostream& operator<<(std::ostream& os, const Printer<NV>& printer)
92{
93 if (printer.dll && *(printer.dll))
94 {
95 const auto& dll = *(printer.dll);
96 const int size = dll::size(head: dll);
97 os << "HEAD -> ";
98 for (int i = 0; i < size; ++i)
99 {
100 if (const auto* const value = dll::get(head: dll, index: i); value)
101 {
102 os << *static_cast<const NV*>(value);
103 }
104 else
105 {
106 os << "<null>";
107 }
108 if (i < (size - 1))
109 {
110 os << " <-> ";
111 }
112 }
113 os << " <- TAIL";
114 }
115 return os;
116}
117} // namespace dll
118
119//! @brief The stack structure (FILO/LIFO).
120namespace stack
121{
122//! @brief Alias for the linear structure. Used for the stack.
123using Stack = Linear;
124
125extern bool create(Stack* const stk);
126extern bool destroy(Stack* const stk);
127extern int size(const Stack head);
128extern bool empty(const Stack head);
129extern bool push(const Stack head, const void* const value);
130extern void* top(const Stack head);
131extern void* pop(const Stack head);
132
133//! @brief Print the stack.
134//! @tparam Value - type of node value
135template <typename Value>
136class Printer
137{
138public:
139 //! @brief Construct a new Printer object.
140 //! @param stk - stack to print
141 explicit Printer(const Stack* const stk) : stk{stk} {}
142
143private:
144 //! @brief The stack to print.
145 const Stack* const stk{nullptr};
146
147protected:
148 template <typename NV>
149 friend std::ostream& operator<<(std::ostream&, const Printer<NV>&);
150};
151
152//! @brief The operator (<<) overloading of the Printer class.
153//! @tparam NV - type of node value
154//! @param os - output stream object
155//! @param printer - specific Printer object
156//! @return reference of the output stream object
157template <typename NV>
158std::ostream& operator<<(std::ostream& os, const Printer<NV>& printer)
159{
160 if (printer.stk && *(printer.stk))
161 {
162 const auto& stk = *(printer.stk);
163 const int size = dll::size(head: stk);
164 os << "TOP [ ";
165 for (int i = 0; i < size; ++i)
166 {
167 if (const auto* const value = dll::get(head: stk, index: i); value)
168 {
169 os << *static_cast<const NV*>(value);
170 }
171 else
172 {
173 os << "<null>";
174 }
175 if (i < (size - 1))
176 {
177 os << " | ";
178 }
179 }
180 os << " ] BOTTOM";
181 }
182 return os;
183}
184} // namespace stack
185
186//! @brief The queue structure (FIFO/LILO).
187namespace queue
188{
189//! @brief Alias for the linear structure. Used for the queue.
190using Queue = Linear;
191
192extern bool create(Queue* const que);
193extern bool destroy(Queue* const que);
194extern int size(const Queue head);
195extern bool empty(const Queue head);
196extern bool push(const Queue head, const void* const value);
197extern void* front(const Queue head);
198extern void* pop(const Queue head);
199
200//! @brief Print the queue.
201//! @tparam Value - type of node value
202template <typename Value>
203class Printer
204{
205public:
206 //! @brief Construct a new Printer object.
207 //! @param que - queue to print
208 explicit Printer(const Queue* const que) : que{que} {}
209
210private:
211 //! @brief The queue to print.
212 const Queue* const que{nullptr};
213
214protected:
215 template <typename NV>
216 friend std::ostream& operator<<(std::ostream&, const Printer<NV>&);
217};
218
219//! @brief The operator (<<) overloading of the Printer class.
220//! @tparam NV - type of node value
221//! @param os - output stream object
222//! @param printer - specific Printer object
223//! @return reference of the output stream object
224template <typename NV>
225std::ostream& operator<<(std::ostream& os, const Printer<NV>& printer)
226{
227 if (printer.que && *(printer.que))
228 {
229 const auto& que = *(printer.que);
230 const int size = dll::size(head: que);
231 os << "FRONT [ ";
232 for (int i = 0; i < size; ++i)
233 {
234 if (const auto* const value = dll::get(head: que, index: i); value)
235 {
236 os << *static_cast<const NV*>(value);
237 }
238 else
239 {
240 os << "<null>";
241 }
242 if (i < (size - 1))
243 {
244 os << " | ";
245 }
246 }
247 os << " ] REAR";
248 }
249 return os;
250}
251} // namespace queue
252
253//! @brief Do traversing.
254class Traverse
255{
256public:
257 //! @brief Construct a new Traverse object.
258 //! @param linear - linear structure for traversing
259 explicit Traverse(const dll::DLL* const linear) : linear{linear} {}
260
261 //! @brief Alias for the operation when traversing.
262 using Operation = std::function<void(const void* const)>;
263 //! @brief Perform a order traversal starting from head.
264 //! @param op - operation on each node
265 void order(const Operation& op) const;
266
267private:
268 //! @brief The linear structure for traversing.
269 const dll::DLL* const linear{nullptr};
270};
271} // namespace linear
272} // namespace data_structure
273