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 _tail = other_tail;
00132 _head = other_head;
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
00156 template <typename T>
00157 typename List<T>::iterator
00158 List<T>::find(const T& val)
00159 {
00160 for (iterator i = begin(); i != end(); ++i)
00161 if (*i == val)
00162 return i;
00163
00164 return end();
00165 }
00166
00167
00175 template <typename T>
00176 typename List<T>::Node*
00177 List<T>::erase(const iterator iter)
00178 {
00179 assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
00180
00181 Node* const n = iter._listnode;
00182
00183 if (n) {
00184 Node* const prev = n->prev();
00185 Node* const next = n->next();
00186
00187
00188 if (n == _head.get())
00189 _head = next;
00190
00191
00192 if (n == _tail.get())
00193 _tail = _tail.get()->prev();
00194
00195 if (prev)
00196 n->prev()->next(next);
00197
00198 if (next)
00199 n->next()->prev(prev);
00200
00201 --_size;
00202 }
00203
00204 assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
00205 return n;
00206 }
00207
00208
00209 template <typename T>
00210 void
00211 List<T>::chop_front(List<T>& front, size_t front_size, Node* front_tail)
00212 {
00213 assert(front_tail);
00214 assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get()));
00215 assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
00216 front._size = front_size;
00217 front._head = _head;
00218 front._tail = front_tail;
00219 Node* new_head = front_tail->next();
00220 if (new_head) {
00221 new_head->prev(NULL);
00222 _head = new_head;
00223 } else {
00224
00225 _head = NULL;
00226 _tail = NULL;
00227 }
00228 _size -= front_size;
00229 front_tail->next(NULL);
00230 assert((front._head.get() && front._tail.get()) || (!front._head.get() && !front._tail.get()));
00231 assert((_head.get() && _tail.get()) || (!_head.get() && !_tail.get()));
00232 }
00233
00234
00236
00237 template <typename T>
00238 List<T>::iterator::iterator(List<T>* list)
00239 : _list(list),
00240 _listnode(NULL)
00241 {
00242 }
00243
00244
00245 template <typename T>
00246 T&
00247 List<T>::iterator::operator*()
00248 {
00249 assert(_listnode);
00250 return _listnode->elem();
00251 }
00252
00253
00254 template <typename T>
00255 T*
00256 List<T>::iterator::operator->()
00257 {
00258 assert(_listnode);
00259 return &_listnode->elem();
00260 }
00261
00262
00263 template <typename T>
00264 inline typename List<T>::iterator&
00265 List<T>::iterator::operator++()
00266 {
00267 assert(_listnode);
00268 _listnode = _listnode->next();
00269
00270 return *this;
00271 }
00272
00273
00274 template <typename T>
00275 inline bool
00276 List<T>::iterator::operator!=(const iterator& iter) const
00277 {
00278 return (_listnode != iter._listnode);
00279 }
00280
00281
00282 template <typename T>
00283 inline bool
00284 List<T>::iterator::operator!=(const const_iterator& iter) const
00285 {
00286 return (_listnode != iter._listnode);
00287 }
00288
00289
00290 template <typename T>
00291 inline bool
00292 List<T>::iterator::operator==(const iterator& iter) const
00293 {
00294 return (_listnode == iter._listnode);
00295 }
00296
00297
00298 template <typename T>
00299 inline bool
00300 List<T>::iterator::operator==(const const_iterator& iter) const
00301 {
00302 return (_listnode == iter._listnode);
00303 }
00304
00305
00306 template <typename T>
00307 inline typename List<T>::iterator
00308 List<T>::begin()
00309 {
00310 typename List<T>::iterator iter(this);
00311
00312 iter._listnode = _head.get();
00313
00314 return iter;
00315 }
00316
00317
00318 template <typename T>
00319 inline const typename List<T>::iterator
00320 List<T>::end() const
00321 {
00322 return _end_iter;
00323 }
00324
00325
00326
00328
00329
00330 template <typename T>
00331 List<T>::const_iterator::const_iterator(const List<T>* const list)
00332 : _list(list),
00333 _listnode(NULL)
00334 {
00335 }
00336
00337
00338 template <typename T>
00339 const T&
00340 List<T>::const_iterator::operator*()
00341 {
00342 assert(_listnode);
00343 return _listnode->elem();
00344 }
00345
00346
00347 template <typename T>
00348 const T*
00349 List<T>::const_iterator::operator->()
00350 {
00351 assert(_listnode);
00352 return &_listnode->elem();
00353 }
00354
00355
00356 template <typename T>
00357 inline typename List<T>::const_iterator&
00358 List<T>::const_iterator::operator++()
00359 {
00360 assert(_listnode);
00361 _listnode = _listnode->next();
00362
00363 return *this;
00364 }
00365
00366
00367 template <typename T>
00368 inline bool
00369 List<T>::const_iterator::operator!=(const const_iterator& iter) const
00370 {
00371 return (_listnode != iter._listnode);
00372 }
00373
00374
00375 template <typename T>
00376 inline bool
00377 List<T>::const_iterator::operator!=(const iterator& iter) const
00378 {
00379 return (_listnode != iter._listnode);
00380 }
00381
00382
00383 template <typename T>
00384 inline bool
00385 List<T>::const_iterator::operator==(const const_iterator& iter) const
00386 {
00387 return (_listnode == iter._listnode);
00388 }
00389
00390
00391 template <typename T>
00392 inline bool
00393 List<T>::const_iterator::operator==(const iterator& iter) const
00394 {
00395 return (_listnode == iter._listnode);
00396 }
00397
00398 template <typename T>
00399 inline typename List<T>::const_iterator
00400 List<T>::begin() const
00401 {
00402 typename List<T>::const_iterator iter(this);
00403 iter._listnode = _head.get();
00404 return iter;
00405 }
00406
00407
00408 }
00409
00410
00411 #endif // RAUL_LIST_IMPL_HPP