00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef RAUL_LIST_IMPL_HPP
00019 #define RAUL_LIST_IMPL_HPP
00020
00021 namespace Raul {
00022
00023
00024 template <typename T>
00025 List<T>::~List<T>()
00026 {
00027 clear();
00028 }
00029
00030
00035 template <typename T>
00036 void
00037 List<T>::clear()
00038 {
00039 Node* node = _head.get();
00040 Node* next = NULL;
00041
00042 while (node) {
00043 next = node->next();
00044 delete node;
00045 node = next;
00046 }
00047
00048 _head = 0;
00049 _tail = 0;
00050 _size = 0;
00051 }
00052
00053
00059 template <typename T>
00060 void
00061 List<T>::push_back(Node* const ln)
00062 {
00063 assert(ln);
00064
00065 ln->next(NULL);
00066
00067 if ( ! _head.get()) {
00068 ln->prev(NULL);
00069 _tail = ln;
00070 _head = ln;
00071 } else {
00072 ln->prev(_tail.get());
00073 _tail.get()->next(ln);
00074 _tail = ln;
00075 }
00076 ++_size;
00077 }
00078
00079
00085 template <typename T>
00086 void
00087 List<T>::push_back(T& elem)
00088 {
00089 Node* const ln = new Node(elem);
00090
00091 assert(ln);
00092
00093 ln->next(NULL);
00094
00095 if ( ! _head.get()) {
00096 ln->prev(NULL);
00097 _tail = ln;
00098 _head = ln;
00099 } else {
00100 ln->prev(_tail.get());
00101 _tail.get()->next(ln);
00102 _tail = ln;
00103 }
00104 ++_size;
00105 }
00106
00107
00117 template <typename T>
00118 void
00119 List<T>::append(List<T>& list)
00120 {
00121 Node* const my_head = _head.get();
00122 Node* const my_tail = _tail.get();
00123 Node* const other_head = list._head.get();
00124 Node* const other_tail = list._tail.get();
00125
00126 assert((my_head && my_tail) || (!my_head && !my_tail));
00127 assert((other_head && other_tail) || (!other_head && !other_tail));
00128
00129
00130 if (my_head == NULL && my_tail == NULL) {
00131 _head = other_head;
00132 _tail = other_tail;
00133 _size = list._size;
00134 } else if (other_head != NULL && other_tail != NULL) {
00135
00136 other_head->prev(my_tail);
00137
00138
00139
00140
00141 my_tail->next(other_head);
00142 _tail = other_tail;
00143 _size += list.size();
00144 }
00145
00146 list._head = NULL;
00147 list._tail = NULL;
00148 list._size = 0;
00149 }
00150
00151
00157 template <typename T>
00158 typename List<T>::iterator
00159 List<T>::find(const T& val)
00160 {
00161 for (iterator i = begin(); i != end(); ++i)
00162 if (*i == val)
00163 return i;
00164
00165 return end();
00166 }
00167
00168
00176 template <typename T>
00177 typename List<T>::Node*
00178 List<T>::erase(const iterator iter)
00179 {
00180 Node* const n = iter._listnode;
00181
00182 if (n) {
00183 Node* const prev = n->prev();
00184 Node* const next = n->next();
00185
00186
00187 if (n == _head.get())
00188 _head = next;
00189
00190
00191 if (n == _tail.get())
00192 _tail = _tail.get()->prev();
00193
00194 if (prev)
00195 n->prev()->next(next);
00196
00197 if (next)
00198 n->next()->prev(prev);
00199
00200 --_size;
00201 }
00202
00203 assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
00204 return n;
00205 }
00206
00207
00208 template <typename T>
00209 void
00210 List<T>::chop_front(List<T>& front, size_t front_size, Node* new_head)
00211 {
00212 assert(new_head != _head.get());
00213 assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get()));
00214 assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
00215 if (!new_head) {
00216 assert(front_size == static_cast<size_t>(_size.get()));
00217 front._size = _size;
00218 front._head = _head;
00219 front._tail = _tail;
00220 _size = 0;
00221 _head = NULL;
00222 _tail = NULL;
00223 } else {
00224 front._size = front_size;
00225 front._head = _head;
00226 front._tail = new_head->prev();
00227 if (new_head->prev())
00228 new_head->prev()->next(NULL);
00229 _head = new_head;
00230 new_head->prev(NULL);
00231 _size -= front_size;
00232 }
00233 assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get()));
00234 assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
00235 }
00236
00237
00239
00240 template <typename T>
00241 List<T>::iterator::iterator(List<T>* list)
00242 : _list(list),
00243 _listnode(NULL)
00244 {
00245 }
00246
00247
00248 template <typename T>
00249 T&
00250 List<T>::iterator::operator*()
00251 {
00252 assert(_listnode);
00253 return _listnode->elem();
00254 }
00255
00256
00257 template <typename T>
00258 T*
00259 List<T>::iterator::operator->()
00260 {
00261 assert(_listnode);
00262 return &_listnode->elem();
00263 }
00264
00265
00266 template <typename T>
00267 inline typename List<T>::iterator&
00268 List<T>::iterator::operator++()
00269 {
00270 assert(_listnode);
00271 _listnode = _listnode->next();
00272
00273 return *this;
00274 }
00275
00276
00277 template <typename T>
00278 inline bool
00279 List<T>::iterator::operator!=(const iterator& iter) const
00280 {
00281 return (_listnode != iter._listnode);
00282 }
00283
00284
00285 template <typename T>
00286 inline bool
00287 List<T>::iterator::operator!=(const const_iterator& iter) const
00288 {
00289 return (_listnode != iter._listnode);
00290 }
00291
00292
00293 template <typename T>
00294 inline bool
00295 List<T>::iterator::operator==(const iterator& iter) const
00296 {
00297 return (_listnode == iter._listnode);
00298 }
00299
00300
00301 template <typename T>
00302 inline bool
00303 List<T>::iterator::operator==(const const_iterator& iter) const
00304 {
00305 return (_listnode == iter._listnode);
00306 }
00307
00308
00309 template <typename T>
00310 inline typename List<T>::iterator
00311 List<T>::begin()
00312 {
00313 typename List<T>::iterator iter(this);
00314
00315 iter._listnode = _head.get();
00316
00317 return iter;
00318 }
00319
00320
00321 template <typename T>
00322 inline const typename List<T>::iterator
00323 List<T>::end() const
00324 {
00325 return _end_iter;
00326 }
00327
00328
00329
00331
00332
00333 template <typename T>
00334 List<T>::const_iterator::const_iterator(const List<T>* const list)
00335 : _list(list),
00336 _listnode(NULL)
00337 {
00338 }
00339
00340
00341 template <typename T>
00342 const T&
00343 List<T>::const_iterator::operator*()
00344 {
00345 assert(_listnode);
00346 return _listnode->elem();
00347 }
00348
00349
00350 template <typename T>
00351 const T*
00352 List<T>::const_iterator::operator->()
00353 {
00354 assert(_listnode);
00355 return &_listnode->elem();
00356 }
00357
00358
00359 template <typename T>
00360 inline typename List<T>::const_iterator&
00361 List<T>::const_iterator::operator++()
00362 {
00363 assert(_listnode);
00364 _listnode = _listnode->next();
00365
00366 return *this;
00367 }
00368
00369
00370 template <typename T>
00371 inline bool
00372 List<T>::const_iterator::operator!=(const const_iterator& iter) const
00373 {
00374 return (_listnode != iter._listnode);
00375 }
00376
00377
00378 template <typename T>
00379 inline bool
00380 List<T>::const_iterator::operator!=(const iterator& iter) const
00381 {
00382 return (_listnode != iter._listnode);
00383 }
00384
00385
00386 template <typename T>
00387 inline bool
00388 List<T>::const_iterator::operator==(const const_iterator& iter) const
00389 {
00390 return (_listnode == iter._listnode);
00391 }
00392
00393
00394 template <typename T>
00395 inline bool
00396 List<T>::const_iterator::operator==(const iterator& iter) const
00397 {
00398 return (_listnode == iter._listnode);
00399 }
00400
00401 template <typename T>
00402 inline typename List<T>::const_iterator
00403 List<T>::begin() const
00404 {
00405 typename List<T>::const_iterator iter(this);
00406 iter._listnode = _head.get();
00407 return iter;
00408 }
00409
00410
00411 }
00412
00413
00414 #endif // RAUL_LIST_IMPL_HPP