Atoms Crowd  7.0.0
List.impl.h
1 #pragma once
2 
3 namespace ToolchefsSTL
4 {
5  template<typename T>
6  List<T>::List(Allocator* allocator) noexcept:
7  m_allocator(allocator),
8  m_head(nullptr),
9  m_tail(nullptr)
10  {
11 
12  }
13 
14  template<typename T>
15  List<T>::~List() noexcept
16  {
17  clear();
18  }
19 
20 
21  template<typename T>
22  List<T>::List(const List& rhs) noexcept:
23  m_allocator(rhs.m_allocator),
24  m_head(nullptr),
25  m_tail(nullptr)
26  {
27  for (auto it=rhs.cbegin(); it!= rhs.cend(); ++it)
28  {
29  push_back(*it);
30  }
31  }
32 
33  template<typename T>
34  List<T>& List<T>::operator=(const List<T>& rhs) noexcept
35  {
36  for (auto it = rhs.cbegin(); it != rhs.cend(); ++it)
37  {
38  push_back(*it);
39  }
40  return *this;
41  }
42 
43  template<typename T>
44  List<T>::List(List&& rhs) noexcept:
45  m_head(rhs.m_head),
46  m_tail(rhs.m_tail),
47  m_allocator(rhs.m_allocator)
48  {
49  rhs.m_head = nullptr;
50  rhs.m_tail = nullptr;
51  }
52 
53  template<typename T>
54  List<T>& List<T>::operator=(List<T>&& rhs) noexcept
55  {
56  m_head = rhs.m_head;
57  m_tail = rhs.m_tail;
58  m_allocator = rhs.m_allocator;
59  rhs.m_head = nullptr;
60  rhs.m_tail = nullptr;
61  return *this;
62  }
63 
64  template<typename T>
65  void List<T>::clear() noexcept
66  {
67  Node* _currNode = m_tail;
68  while (_currNode)
69  {
70  Node* prev = _currNode->_prev;
71  _currNode->~Node();
72  m_allocator->free(_currNode);
73  _currNode = prev;
74  }
75  m_head = nullptr;
76  m_tail = nullptr;
77  }
78 
79  template<typename T>
80  size_t List<T>::size() const noexcept
81  {
82  size_t counter = 0;
83  Node* _currNode = m_head;
84  while(_currNode)
85  {
86  counter++;
87  _currNode = _currNode->_next;
88  }
89  return counter;
90  }
91 
92  template<typename T>
93  size_t List<T>::length() const noexcept
94  {
95  return size();
96  }
97 
98  template<typename T>
99  typename List<T>::iterator List<T>::begin() noexcept
100  {
101  return iterator(m_head);
102  }
103 
104  template<typename T>
105  typename List<T>::iterator List<T>::end() noexcept
106  {
107  return iterator(nullptr);
108  }
109 
110  template<typename T>
111  typename List<T>::const_iterator List<T>::cbegin() const noexcept
112  {
113  return const_iterator(m_head);
114  }
115 
116  template<typename T>
117  typename List<T>::const_iterator List<T>::cend() const noexcept
118  {
119  return const_iterator(nullptr);
120  }
121 
122  template<typename T>
123  typename List<T>::reverse_iterator List<T>::rbegin() noexcept
124  {
125  return reverse_iterator(m_tail);
126  }
127 
128  template<typename T>
129  typename List<T>::reverse_iterator List<T>::rend() noexcept
130  {
131  return reverse_iterator(nullptr);
132  }
133 
134  template<typename T>
135  typename List<T>::const_reverse_iterator List<T>::crbegin() const noexcept
136  {
137  return const_reverse_iterator(m_tail);
138  }
139 
140  template<typename T>
141  typename List<T>::const_reverse_iterator List<T>::crend() const noexcept
142  {
143  return const_reverse_iterator(nullptr);
144  }
145 
146  template<typename T>
147  T& List<T>::back() noexcept
148  {
149  return m_tail->data;
150  }
151 
152  template<typename T>
153  const T& List<T>::back() const noexcept
154  {
155  return m_tail->data;
156  }
157 
158  template<typename T>
159  T& List<T>::front() noexcept
160  {
161  return m_head->data;
162  }
163 
164  template<typename T>
165  const T& List<T>::front() const noexcept
166  {
167  return m_head->data;
168  }
169 
170  template<typename T>
171  void List<T>::push_back(const T& element) noexcept
172  {
173  Node* value = static_cast<Node*>(m_allocator->malloc(sizeof(Node)));
174  new (value) Node(element);
175  if (!m_head)
176  {
177  m_head = value;
178  m_tail = m_head;
179  return;
180  }
181 
182  m_tail->_next = value;
183  value->_prev = m_tail;
184  m_tail = value;
185 
186  }
187 
188  template<typename T>
189  void List<T>::pop_back() noexcept
190  {
191  if (!m_tail) return;
192  Node* node = m_tail;
193  if (node->_prev)
194  {
195  m_tail = node->_prev;
196  m_tail->_next = nullptr;
197  }
198  else
199  {
200  m_tail = nullptr;
201  m_head = nullptr;
202  }
203  node->~Node();
204  m_allocator->free(node);
205  }
206 
207  template<typename T>
208  void List<T>::push_front(const T& element) noexcept
209  {
210  Node* value = static_cast<Node*>(m_allocator->malloc(sizeof(Node)));
211  new (value) Node(element);
212  if (!m_head)
213  {
214  m_head = value;
215  m_tail = m_head;
216  return;
217  }
218 
219  value->_next = m_head;
220  m_head = value;
221  }
222 
223  template<typename T>
224  void List<T>::pop_front() noexcept
225  {
226  if (!m_head) return;
227  Node* node = m_head;
228  if (node->_next)
229  {
230  m_head = node->_next;
231  m_head->_prev = nullptr;
232  }
233  else
234  {
235  m_head = nullptr;
236  m_tail = nullptr;
237  }
238  node->~Node();
239  m_allocator->free(node);
240  }
241 
242  template<typename T>
243  typename List<T>::iterator List<T>::insert(const_iterator pos, const T& value) noexcept
244  {
245  if (pos == cend() || !pos.m_ptr) return end();
246  Node* node = const_cast<Node*>(pos.m_ptr);
247 
248  Node* new_node = static_cast<Node*>(m_allocator->malloc(sizeof(Node)));
249  new (new_node) Node(value);
250  Node* prevNode = node->_prev;
251  node->_prev = new_node;
252  new_node->_next = node;
253 
254 
255  if (prevNode)
256  {
257  prevNode->_next = new_node;
258  new_node->_prev = prevNode;
259  }
260  return iterator(new_node);
261  }
262 
263  template<typename T>
264  typename List<T>::iterator List<T>::insert(iterator pos, const T& value) noexcept
265  {
266  if (pos == end() || !pos.m_ptr) return end();
267  Node* node = pos.m_ptr;
268 
269  Node* new_node = static_cast<Node*>(m_allocator->malloc(sizeof(Node)));
270  new (new_node) Node(value);
271  Node* prevNode = node->_prev;
272  node->_prev = new_node;
273  new_node->_next = node;
274 
275 
276  if (prevNode)
277  {
278  prevNode->_next = new_node;
279  new_node->_prev = prevNode;
280  }
281  return iterator(new_node);
282  }
283 
284  template<typename T>
285  typename List<T>::iterator List<T>::erase(const_iterator pos) noexcept
286  {
287  if (pos == cend() || !pos.m_ptr) return end();
288  Node* node = const_cast<Node*>(pos.m_ptr);
289  Node* prev = node->_prev;
290  Node* next = node->_next;
291 
292  node->~Node();
293  m_allocator->free(node);
294  if (prev)
295  {
296  prev->_next = next;
297  }
298  else
299  {
300  m_head = next;
301  }
302  if (next)
303  {
304  next->_prev = prev;
305  }
306  else
307  {
308  m_tail = prev;
309  }
310 
311 
312  return iterator(next);
313  }
314 
315  template<typename T>
316  typename List<T>::iterator List<T>::erase(iterator pos) noexcept
317  {
318  if (pos == end() || !pos.m_ptr) return end();
319  Node* node = pos.m_ptr;
320  Node* prev = node->_prev;
321  Node* next = node->_next;
322 
323  node->~Node();
324  m_allocator->free(node);
325  if (prev)
326  {
327  prev->_next = next;
328  }
329  else
330  {
331  m_head = next;
332  }
333  if (next)
334  {
335  next->_prev = prev;
336  }
337  else
338  {
339  m_tail = prev;
340  }
341 
342 
343  return iterator(next);
344  }
345 
346  template<typename T>
347  typename List<T>::iterator List<T>::find(const T& element) noexcept
348  {
349  auto end_it = end();
350  for (auto it = begin(); it != end_it; ++it)
351  {
352  if (*it == element) return it;
353  }
354  return end();
355  }
356 
357  template<typename T>
358  typename List<T>::const_iterator List<T>::find(const T& element) const noexcept
359  {
360  auto end_it = cend();
361  for (auto it = cbegin(); it != end_it; ++it)
362  {
363  if (*it == element) return it;
364  }
365  return cend();
366  }
367 
368 }
ToolchefsSTL::List::Node
Definition: List.h:12
ToolchefsSTL::List
Definition: List.h:8
ToolchefsSTL::List::push_back
void push_back(const T &element) noexcept
Insert element.
Definition: List.impl.h:171
ToolchefsSTL::List::back
T & back() noexcept
Direct access.
Definition: List.impl.h:147
ToolchefsSTL::List::begin
iterator begin() noexcept
Iterators.
Definition: List.impl.h:99
ToolchefsSTL::List::push_front
void push_front(const T &element) noexcept
Insert element.
Definition: List.impl.h:208