1 // Copyright Jean Pierre Cimalando 2018.
2 // Distributed under the Boost Software License, Version 1.0.
3 // (See accompanying file LICENSE or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
5
6 #include "pl_list.hpp"
7
8 template <class Cell>
pl_iterator(Cell * cell)9 pl_iterator<Cell>::pl_iterator(Cell *cell)
10 : cell_(cell)
11 {
12 }
13
14 template <class Cell>
is_end() const15 bool pl_iterator<Cell>::is_end() const
16 {
17 return cell_->next == NULL;
18 }
19
20 template <class Cell>
operator *() const21 Cell &pl_iterator<Cell>::operator*() const
22 {
23 return *cell_;
24 }
25
26 template <class Cell>
operator ->() const27 Cell *pl_iterator<Cell>::operator->() const
28 {
29 return cell_;
30 }
31
32 template <class T>
operator ==(const pl_iterator & i) const33 bool pl_iterator<T>::operator==(const pl_iterator &i) const
34 {
35 return cell_ == i.cell_;
36 }
37
38 template <class T>
operator !=(const pl_iterator & i) const39 bool pl_iterator<T>::operator!=(const pl_iterator &i) const
40 {
41 return cell_ != i.cell_;
42 }
43
44 template <class T>
operator ++()45 pl_iterator<T> &pl_iterator<T>::operator++()
46 {
47 cell_ = cell_->next;
48 return *this;
49 }
50
51 template <class T>
operator ++(int)52 pl_iterator<T> pl_iterator<T>::operator++(int)
53 {
54 pl_iterator i(cell_);
55 cell_ = cell_->next;
56 return i;
57 }
58
59 template <class T>
operator --()60 pl_iterator<T> &pl_iterator<T>::operator--()
61 {
62 cell_ = cell_->prev;
63 return *this;
64 }
65
66 template <class T>
operator --(int)67 pl_iterator<T> pl_iterator<T>::operator--(int)
68 {
69 pl_iterator i(cell_);
70 cell_ = cell_->prev;
71 return i;
72 }
73
74 template <class T>
pl_list(std::size_t capacity)75 pl_list<T>::pl_list(std::size_t capacity)
76 {
77 initialize(capacity);
78 }
79
80 template <class T>
~pl_list()81 pl_list<T>::~pl_list()
82 {
83 if (cells_allocd_)
84 delete[] cells_;
85 }
86
87 template <class T>
pl_list(pl_cell<T> * cells,std::size_t ncells,external_storage_policy)88 pl_list<T>::pl_list(pl_cell<T> *cells, std::size_t ncells, external_storage_policy)
89 {
90 initialize(ncells, cells);
91 }
92
93 template <class T>
pl_list(const pl_list & other)94 pl_list<T>::pl_list(const pl_list &other)
95 {
96 initialize(other.capacity());
97 for(const_iterator i = other.end(), b = other.begin(); i-- != b;)
98 push_front(i->value);
99 }
100
101 template <class T>
operator =(const pl_list & other)102 pl_list<T> &pl_list<T>::operator=(const pl_list &other)
103 {
104 if(this != &other)
105 {
106 std::size_t size = other.size();
107 if(size > capacity())
108 {
109 pl_cell<T> *oldcells = cells_;
110 bool allocd = cells_allocd_;
111 initialize(other.capacity());
112 if (allocd)
113 delete[] oldcells;
114 }
115 clear();
116 for(const_iterator i = other.end(), b = other.begin(); i-- != b;)
117 push_front(i->value);
118 }
119 return *this;
120 }
121
122 template <class T>
size() const123 std::size_t pl_list<T>::size() const
124 {
125 return size_;
126 }
127
128 template <class T>
capacity() const129 std::size_t pl_list<T>::capacity() const
130 {
131 return capacity_;
132 }
133
134 template <class T>
empty() const135 bool pl_list<T>::empty() const
136 {
137 return size_ == 0;
138 }
139
140 template <class T>
begin()141 typename pl_list<T>::iterator pl_list<T>::begin()
142 {
143 return iterator(first_);
144 }
145
146 template <class T>
end()147 typename pl_list<T>::iterator pl_list<T>::end()
148 {
149 return iterator(reinterpret_cast<pl_cell<T> *>(&endcell_));
150 }
151
152 template <class T>
begin() const153 typename pl_list<T>::const_iterator pl_list<T>::begin() const
154 {
155 return const_iterator(first_);
156 }
157
158 template <class T>
end() const159 typename pl_list<T>::const_iterator pl_list<T>::end() const
160 {
161 return const_iterator(reinterpret_cast<const pl_cell<T> *>(&endcell_));
162 }
163
164 template <class T>
clear()165 void pl_list<T>::clear()
166 {
167 std::size_t capacity = capacity_;
168 pl_cell<T> *cells = cells_;
169 pl_cell<T> *endcell = &*end();
170 size_ = 0;
171 first_ = endcell;
172 free_ = cells;
173 endcell->prev = NULL;
174 for(std::size_t i = 0; i < capacity; ++i)
175 {
176 cells[i].prev = (i > 0) ? &cells[i - 1] : NULL;
177 cells[i].next = (i + 1 < capacity) ? &cells[i + 1] : NULL;
178 cells[i].value = T();
179 }
180 }
181
182 template <class T>
front()183 pl_cell<T> &pl_list<T>::front()
184 {
185 return *first_;
186 }
187
188 template <class T>
front() const189 const pl_cell<T> &pl_list<T>::front() const
190 {
191 return *first_;
192 }
193
194 template <class T>
back()195 pl_cell<T> &pl_list<T>::back()
196 {
197 iterator i = end();
198 return *--i;
199 }
200
201 template <class T>
back() const202 const pl_cell<T> &pl_list<T>::back() const
203 {
204 const_iterator i = end();
205 return *--i;
206 }
207
208 template <class T>
insert(iterator pos,const T & x)209 typename pl_list<T>::iterator pl_list<T>::insert(iterator pos, const T &x)
210 {
211 pl_cell<T> *cell = allocate(&*pos);
212 if (!cell)
213 throw std::bad_alloc();
214 cell->value = x;
215 return iterator(cell);
216 }
217
218 template <class T>
erase(iterator pos)219 typename pl_list<T>::iterator pl_list<T>::erase(iterator pos)
220 {
221 deallocate(&*(pos++));
222 return pos;
223 }
224
225 template <class T>
push_front(const T & x)226 void pl_list<T>::push_front(const T &x)
227 {
228 insert(begin(), x);
229 }
230
231 template <class T>
push_back(const T & x)232 void pl_list<T>::push_back(const T &x)
233 {
234 insert(end(), x);
235 }
236
237 template <class T>
pop_front()238 void pl_list<T>::pop_front()
239 {
240 deallocate(first_);
241 }
242
243 template <class T>
pop_back()244 void pl_list<T>::pop_back()
245 {
246 iterator i(&*end());
247 deallocate(&*--i);
248 }
249
250 template <class T>
find(const T & x)251 typename pl_list<T>::iterator pl_list<T>::find(const T &x)
252 {
253 const_iterator i = const_cast<const pl_list<T> *>(this)->find(x);
254 return iterator(&const_cast<reference>(*i));
255 }
256
257 template <class T>
find(const T & x) const258 typename pl_list<T>::const_iterator pl_list<T>::find(const T &x) const
259 {
260 const_iterator e = end();
261 for (const_iterator i = begin(); i != e; ++i)
262 {
263 if(i->value == x)
264 return i;
265 }
266 return e;
267 }
268
269 template <class T>
270 template <class Pred>
find_if(const Pred & p)271 typename pl_list<T>::iterator pl_list<T>::find_if(const Pred &p)
272 {
273 const_iterator i = const_cast<const pl_list<T> *>(this)->find_if(p);
274 return iterator(&const_cast<reference>(*i));
275 }
276
277 template <class T>
278 template <class Pred>
find_if(const Pred & p) const279 typename pl_list<T>::const_iterator pl_list<T>::find_if(const Pred &p) const
280 {
281 const_iterator e = end();
282 for (const_iterator i = begin(); i != e; ++i)
283 {
284 if(p(i->value))
285 return i;
286 }
287 return e;
288 }
289
290 template <class T>
initialize(std::size_t capacity,pl_cell<T> * extcells)291 void pl_list<T>::initialize(std::size_t capacity, pl_cell<T> *extcells)
292 {
293 cells_ = extcells ? extcells : new pl_cell<T>[capacity];
294 cells_allocd_ = extcells ? false : true;
295 capacity_ = capacity;
296 endcell_.next = NULL;
297 clear();
298 }
299
300 template <class T>
allocate(pl_cell<T> * pos)301 pl_cell<T> *pl_list<T>::allocate(pl_cell<T> *pos)
302 {
303 // remove free cells front
304 pl_cell<T> *cell = free_;
305 if(!cell)
306 return NULL;
307 free_ = cell->next;
308 if(free_)
309 free_->prev = NULL;
310
311 // insert at position
312 if (pos == first_)
313 first_ = cell;
314 cell->prev = pos->prev;
315 if (cell->prev)
316 cell->prev->next = cell;
317 cell->next = pos;
318 pos->prev = cell;
319
320 ++size_;
321 return cell;
322 }
323
324 template <class T>
deallocate(pl_cell<T> * cell)325 void pl_list<T>::deallocate(pl_cell<T> *cell)
326 {
327 if(cell->prev)
328 cell->prev->next = cell->next;
329 if(cell->next)
330 cell->next->prev = cell->prev;
331 if(cell == first_)
332 first_ = cell->next;
333 cell->prev = NULL;
334 cell->next = free_;
335 cell->value = T();
336 free_ = cell;
337 --size_;
338 }
339