1// SPDX-License-Identifier: GPL-3.0-or-later
2#pragma once
3
4#include <mos/allocator.hpp>
5
6namespace mos
7{
8 template<typename T>
9 class list
10 {
11 public:
12 list() = default;
13 list(const list &other) = default;
14 list(list &&other) noexcept = default;
15 list &operator=(const list &other) = default;
16 list &operator=(list &&other) noexcept = default;
17 ~list() = default;
18
19 void push_back(const T &value)
20 {
21 if (head == nullptr)
22 {
23 head = mos::create<node>(value);
24 tail = head;
25 }
26 else
27 {
28 tail->next = mos::create<node>(value);
29 tail = tail->next;
30 }
31 }
32
33 void push_front(const T &value)
34 {
35 if (head == nullptr)
36 {
37 head = mos::create<node>(value);
38 tail = head;
39 }
40 else
41 {
42 node *new_head = mos::create<node>(value);
43 new_head->next = head;
44 head = new_head;
45 }
46 }
47
48 void pop_back()
49 {
50 if (head == nullptr)
51 return;
52
53 if (head == tail)
54 {
55 delete head;
56 head = nullptr;
57 tail = nullptr;
58 return;
59 }
60
61 node *current = head;
62 while (current->next != tail)
63 current = current->next;
64
65 delete tail;
66 tail = current;
67 tail->next = nullptr;
68 }
69
70 void pop_front()
71 {
72 if (head == nullptr)
73 return;
74
75 if (head == tail)
76 {
77 delete head;
78 head = nullptr;
79 tail = nullptr;
80 return;
81 }
82
83 node *new_head = head->next;
84 delete head;
85 head = new_head;
86 }
87
88 T &front()
89 {
90 return head->value;
91 }
92
93 T &back()
94 {
95 return tail->value;
96 }
97
98 bool empty() const
99 {
100 return head == nullptr;
101 }
102
103 private:
104 struct node : mos::NamedType<"List.Node">
105 {
106 T value;
107 node *next = nullptr;
108
109 node(const T &value) : value(value) {};
110 };
111
112 public:
113 class iterator
114 {
115 public:
116 iterator(node *current) : current(current)
117 {
118 }
119
120 T &operator*()
121 {
122 return current->value;
123 }
124
125 iterator &operator++()
126 {
127 current = current->next;
128 return *this;
129 }
130
131 bool operator==(const iterator &other) const
132 {
133 return current == other.current;
134 }
135
136 bool operator!=(const iterator &other) const
137 {
138 return current != other.current;
139 }
140
141 private:
142 node *current;
143 };
144
145 iterator begin()
146 {
147 return iterator(head);
148 }
149
150 iterator end()
151 {
152 return iterator(nullptr);
153 }
154
155 const iterator begin() const
156 {
157 return iterator(head);
158 }
159
160 const iterator end() const
161 {
162 return iterator(nullptr);
163 }
164
165 const iterator cbegin() const
166 {
167 return iterator(head);
168 }
169
170 const iterator cend() const
171 {
172 return iterator(nullptr);
173 }
174
175 iterator erase(iterator it)
176 {
177 if (it.current == head)
178 {
179 pop_front();
180 return iterator(head);
181 }
182
183 node *current = head;
184 while (current->next != it.current)
185 current = current->next;
186
187 current->next = it.current->next;
188 delete it.current;
189 return iterator(current->next);
190 }
191
192 void insert(iterator it, const T &value)
193 {
194 if (it.current == head)
195 {
196 push_front(value);
197 return;
198 }
199
200 node *current = head;
201 while (current->next != it.current)
202 current = current->next;
203
204 node *new_node = mos::create<node>(value);
205 new_node->next = current->next;
206 current->next = new_node;
207 }
208
209 void clear()
210 {
211 while (head != nullptr)
212 {
213 node *next = head->next;
214 delete head;
215 head = next;
216 }
217 }
218
219 private:
220 node *head = nullptr;
221 node *tail = nullptr;
222 };
223} // namespace mos
224