1//! @file linear.cpp
2//! @author ryftchen
3//! @brief The definitions (linear) in the data structure module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2025 ryftchen. All rights reserved.
6
7#include "linear.hpp"
8
9namespace data_structure::linear
10{
11//! @brief Function version number.
12//! @return version number (major.minor.patch)
13const char* version() noexcept
14{
15 static const char* const ver = "0.1.0";
16 return ver;
17}
18
19// NOLINTBEGIN(cppcoreguidelines-owning-memory, cppcoreguidelines-pro-type-const-cast)
20namespace dll
21{
22//! @brief Create the node of the doubly linked list.
23//! @param value - value of the target node
24//! @return new node
25static Node* createNode(const void* const value)
26{
27 Node* const newNode = ::new (std::nothrow) Node;
28 if (!newNode)
29 {
30 return nullptr;
31 }
32
33 newNode->prev = newNode->next = newNode;
34 newNode->value = const_cast<void*>(value);
35 return newNode;
36}
37
38//! @brief Get the node of the doubly linked list by index.
39//! @param head - head of the list
40//! @param index - target index
41//! @return node at the index
42static Node* getNode(const DLL head, const int index)
43{
44 if (!head || (index < 0))
45 {
46 return nullptr;
47 }
48
49 Node* nNext = head->next;
50 int counter = 0;
51 while (nNext != head)
52 {
53 ++counter;
54 nNext = nNext->next;
55 }
56 if (index >= counter)
57 {
58 return nullptr;
59 }
60
61 if (index <= (counter / 2))
62 {
63 nNext = head->next;
64 int i = 0;
65 while ((i++) < index)
66 {
67 nNext = nNext->next;
68 }
69 return nNext;
70 }
71
72 Node* pNode = head->prev;
73 const int rIdx = counter - index - 1;
74 int j = 0;
75 while ((j++) < rIdx)
76 {
77 pNode = pNode->prev;
78 }
79 return pNode;
80}
81
82//! @brief Create the doubly linked list.
83//! @param dll - doubly linked list
84//! @return success or failure
85bool create(DLL* const dll)
86{
87 return dll && ((*dll = createNode(value: nullptr)) != nullptr);
88}
89
90//! @brief Destroy the doubly linked list.
91//! @param dll - doubly linked list
92//! @return success or failure
93bool destroy(DLL* const dll)
94{
95 if (!dll || !*dll)
96 {
97 return false;
98 }
99
100 const Node* nNode = (*dll)->next;
101 const Node* temp = nullptr;
102 while (nNode != *dll)
103 {
104 temp = nNode;
105 nNode = nNode->next;
106 ::delete temp;
107 temp = nullptr;
108 }
109
110 ::delete *dll;
111 *dll = nullptr;
112 return true;
113}
114
115//! @brief Get the size of the doubly linked list.
116//! @param head - head of the list
117//! @return size of the doubly linked list
118int size(const DLL head)
119{
120 if (!head)
121 {
122 return 0;
123 }
124
125 const Node* nNode = head->next;
126 int counter = 0;
127 while (nNode != head)
128 {
129 ++counter;
130 nNode = nNode->next;
131 }
132 return counter;
133}
134
135//! @brief Check whether any nodes do not exist in the doubly linked list.
136//! @param head - head of the list
137//! @return any nodes do not exist or exist
138bool empty(const DLL head)
139{
140 return size(head) == 0;
141}
142
143//! @brief Get the node value of the doubly linked list by index.
144//! @param head - head of the list
145//! @param index - target index
146//! @return node value
147void* get(const DLL head, const int index)
148{
149 const Node* const iNode = getNode(head, index);
150 return iNode ? iNode->value : nullptr;
151}
152
153//! @brief Get the first node value of the doubly linked list.
154//! @param head - head of the list
155//! @return first node value
156void* getFirst(const DLL head)
157{
158 return get(head, index: 0);
159}
160
161//! @brief Get the last node value of the doubly linked list.
162//! @param head - head of the list
163//! @return last node value
164void* getLast(const DLL head)
165{
166 return get(head, index: size(head) - 1);
167}
168
169//! @brief Insert the node into the doubly linked list by index.
170//! @param head - head of the list
171//! @param index - target index
172//! @param value - value of the target node
173//! @return success or failure
174bool insert(const DLL head, const int index, const void* const value)
175{
176 if (index == 0)
177 {
178 return insertFirst(head, value);
179 }
180
181 Node* const iNode = getNode(head, index);
182 if (!iNode)
183 {
184 return false;
185 }
186
187 Node* const newNode = createNode(value);
188 if (!newNode)
189 {
190 return false;
191 }
192
193 newNode->prev = iNode->prev;
194 newNode->next = iNode;
195 iNode->prev->next = newNode;
196 iNode->prev = newNode;
197 return true;
198}
199
200//! @brief Insert the node into the doubly linked list as the first node.
201//! @param head - head of the list
202//! @param value - value of the target node
203//! @return success or failure
204bool insertFirst(const DLL head, const void* const value)
205{
206 if (!head)
207 {
208 return false;
209 }
210
211 Node* const newNode = createNode(value);
212 if (!newNode)
213 {
214 return false;
215 }
216
217 newNode->prev = head;
218 newNode->next = head->next;
219 head->next->prev = newNode;
220 head->next = newNode;
221 return true;
222}
223
224//! @brief Insert the node into the doubly linked list as the last node.
225//! @param head - head of the list
226//! @param value - value of the target node
227//! @return success or failure
228bool insertLast(const DLL head, const void* const value)
229{
230 if (!head)
231 {
232 return false;
233 }
234
235 Node* const newNode = createNode(value);
236 if (!newNode)
237 {
238 return false;
239 }
240
241 newNode->next = head;
242 newNode->prev = head->prev;
243 head->prev->next = newNode;
244 head->prev = newNode;
245 return true;
246}
247
248//! @brief Remove the node from the doubly linked list by index.
249//! @param head - head of the list
250//! @param index - target index
251//! @return success or failure
252bool remove(const DLL head, const int index)
253{
254 const Node* iNode = getNode(head, index);
255 if (!iNode)
256 {
257 return false;
258 }
259
260 iNode->next->prev = iNode->prev;
261 iNode->prev->next = iNode->next;
262 ::delete iNode;
263 iNode = nullptr;
264 return true;
265}
266
267//! @brief Remove the first node from the doubly linked list.
268//! @param head - head of the list
269//! @return success or failure
270bool removeFirst(const DLL head)
271{
272 return remove(head, index: 0);
273}
274
275//! @brief Remove the last node from the doubly linked list.
276//! @param head - head of the list
277//! @return success or failure
278bool removeLast(const DLL head)
279{
280 return remove(head, index: size(head) - 1);
281}
282} // namespace dll
283
284namespace stack
285{
286//! @brief Create the stack.
287//! @param stk - stack
288//! @return success or failure
289bool create(Stack* const stk)
290{
291 return dll::create(dll: stk);
292}
293
294//! @brief Destroy the stack.
295//! @param stk - stack
296//! @return success or failure
297bool destroy(Stack* const stk)
298{
299 return dll::destroy(dll: stk);
300}
301
302//! @brief Get the size of the stack.
303//! @param head - head of the stack
304//! @return size of the stack
305int size(const Stack head)
306{
307 return dll::size(head);
308}
309
310//! @brief Check whether any nodes do not exist in the stack.
311//! @param head - head of the stack
312//! @return any nodes do not exist or exist
313bool empty(const Stack head)
314{
315 return dll::empty(head);
316}
317
318//! @brief Push operation of the stack.
319//! @param head - head of the stack
320//! @param value - value of the target node
321//! @return success or failure
322bool push(const Stack head, const void* const value)
323{
324 return dll::insertFirst(head, value);
325}
326
327//! @brief Top operation of the stack.
328//! @param head - head of the stack
329//! @return node value
330void* top(const Stack head)
331{
332 return dll::getFirst(head);
333}
334
335//! @brief Pop operation of the stack.
336//! @param head - head of the stack
337//! @return node value
338void* pop(const Stack head)
339{
340 void* const value = top(head);
341 dll::removeFirst(head);
342 return value;
343}
344} // namespace stack
345
346namespace queue
347{
348//! @brief Create the queue.
349//! @param que - queue
350//! @return success or failure
351bool create(Queue* const que)
352{
353 return dll::create(dll: que);
354}
355
356//! @brief Destroy the queue.
357//! @param que - queue
358//! @return success or failure
359bool destroy(Queue* const que)
360{
361 return dll::destroy(dll: que);
362}
363
364//! @brief Get the size of the queue.
365//! @param head - head of the queue
366//! @return size of the queue
367int size(const Queue head)
368{
369 return dll::size(head);
370}
371
372//! @brief Check whether any nodes do not exist in the queue.
373//! @param head - head of the queue
374//! @return any nodes do not exist or exist
375bool empty(const Queue head)
376{
377 return dll::empty(head);
378}
379
380//! @brief Push operation of the queue.
381//! @param head - head of the queue
382//! @param value - value of the target node
383//! @return success or failure
384bool push(const Queue head, const void* const value)
385{
386 return dll::insertLast(head, value);
387}
388
389//! @brief Front operation of the queue.
390//! @param head - head of the queue
391//! @return node value
392void* front(const Queue head)
393{
394 return dll::getFirst(head);
395}
396
397//! @brief Pop operation of the queue.
398//! @param head - head of the queue
399//! @return node value
400void* pop(const Queue head)
401{
402 void* const value = dll::getFirst(head);
403 dll::removeFirst(head);
404 return value;
405}
406} // namespace queue
407// NOLINTEND(cppcoreguidelines-owning-memory, cppcoreguidelines-pro-type-const-cast)
408
409void Traverse::order(const Operation& op) const
410{
411 if (!linear || !*linear || !op)
412 {
413 return;
414 }
415
416 for (int i = 0; i < dll::size(head: *linear); ++i)
417 {
418 op(dll::get(head: *linear, index: i));
419 }
420}
421} // namespace data_structure::linear
422