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 os << *static_cast<const NV*>(get(dll, i));
101 if (i < (size - 1))
102 {
103 os << " <-> ";
104 }
105 }
106 os << " <- TAIL";
107 }
108 return os;
109}
110} // namespace dll
111
112//! @brief The stack structure (FILO/LIFO).
113namespace stack
114{
115//! @brief Alias for the linear structure. Used for the stack.
116using Stack = Linear;
117
118extern bool create(Stack* const stk);
119extern bool destroy(Stack* const stk);
120extern int size(const Stack head);
121extern bool empty(const Stack head);
122extern bool push(const Stack head, const void* const value);
123extern void* top(const Stack head);
124extern void* pop(const Stack head);
125
126//! @brief Print the stack.
127//! @tparam Value - type of node value
128template <typename Value>
129class Printer
130{
131public:
132 //! @brief Construct a new Printer object.
133 //! @param stk - stack to print
134 explicit Printer(const Stack* const stk) : stk{stk} {}
135
136private:
137 //! @brief The stack to print.
138 const Stack* const stk{nullptr};
139
140protected:
141 template <typename NV>
142 friend std::ostream& operator<<(std::ostream&, const Printer<NV>&);
143};
144
145//! @brief The operator (<<) overloading of the Printer class.
146//! @tparam NV - type of node value
147//! @param os - output stream object
148//! @param printer - specific Printer object
149//! @return reference of the output stream object
150template <typename NV>
151std::ostream& operator<<(std::ostream& os, const Printer<NV>& printer)
152{
153 if (printer.stk && *(printer.stk))
154 {
155 const auto& stk = *(printer.stk);
156 const int size = dll::size(head: stk);
157 os << "TOP [ ";
158 for (int i = 0; i < size; ++i)
159 {
160 os << *static_cast<const NV*>(dll::get(head: stk, index: i));
161 if (i < (size - 1))
162 {
163 os << " | ";
164 }
165 }
166 os << " ] BOTTOM";
167 }
168 return os;
169}
170} // namespace stack
171
172//! @brief The queue structure (FIFO/LILO).
173namespace queue
174{
175//! @brief Alias for the linear structure. Used for the queue.
176using Queue = Linear;
177
178extern bool create(Queue* const que);
179extern bool destroy(Queue* const que);
180extern int size(const Queue head);
181extern bool empty(const Queue head);
182extern bool push(const Queue head, const void* const value);
183extern void* front(const Queue head);
184extern void* pop(const Queue head);
185
186//! @brief Print the queue.
187//! @tparam Value - type of node value
188template <typename Value>
189class Printer
190{
191public:
192 //! @brief Construct a new Printer object.
193 //! @param que - queue to print
194 explicit Printer(const Queue* const que) : que{que} {}
195
196private:
197 //! @brief The queue to print.
198 const Queue* const que{nullptr};
199
200protected:
201 template <typename NV>
202 friend std::ostream& operator<<(std::ostream&, const Printer<NV>&);
203};
204
205//! @brief The operator (<<) overloading of the Printer class.
206//! @tparam NV - type of node value
207//! @param os - output stream object
208//! @param printer - specific Printer object
209//! @return reference of the output stream object
210template <typename NV>
211std::ostream& operator<<(std::ostream& os, const Printer<NV>& printer)
212{
213 if (printer.que && *(printer.que))
214 {
215 const auto& que = *(printer.que);
216 const int size = dll::size(head: que);
217 os << "FRONT [ ";
218 for (int i = 0; i < size; ++i)
219 {
220 os << *static_cast<const NV*>(dll::get(head: que, index: i));
221 if (i < (size - 1))
222 {
223 os << " | ";
224 }
225 }
226 os << " ] REAR";
227 }
228 return os;
229}
230} // namespace queue
231
232//! @brief Do traversing.
233class Traverse
234{
235public:
236 //! @brief Construct a new Traverse object.
237 //! @param linear - linear structure for traversing
238 explicit Traverse(const dll::DLL* const linear) : linear{linear} {}
239
240 //! @brief Alias for the operation when traversing.
241 using Operation = std::function<void(const void* const)>;
242 //! @brief Perform a order traversal starting from head.
243 //! @param op - operation on each node
244 void order(const Operation& op) const;
245
246private:
247 //! @brief The linear structure for traversing.
248 const dll::DLL* const linear{nullptr};
249};
250} // namespace linear
251} // namespace data_structure
252