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
00118 template <typename T>
00119 void
00120 List<T>::append(List<T>& list)
00121 {
00122 Node* const my_head = _head.get();
00123 Node* const my_tail = _tail.get();
00124 Node* const other_head = list._head.get();
00125 Node* const other_tail = list._tail.get();
00126
00127
00128 if (my_head == NULL && my_tail == NULL) {
00129 _head = other_head;
00130 _tail = other_tail;
00131 _size = list._size;
00132 } else if (other_head != NULL && other_tail != NULL) {
00133
00134 other_head->prev(my_tail);
00135
00136
00137
00138
00139 my_tail->next(other_head);
00140 _tail = other_tail;
00141 _size += list.size();
00142 }
00143
00144 list._head = NULL;
00145 list._tail = NULL;
00146 list._size = 0;
00147 }
00148
00149
00155 template <typename T>
00156 typename List<T>::iterator
00157 List<T>::find(const T& val)
00158 {
00159 for (iterator i = begin(); i != end(); ++i)
00160 if (*i == val)
00161 return i;
00162
00163 return end();
00164 }
00165
00166
00174 template <typename T>
00175 typename List<T>::Node*
00176 List<T>::erase(const iterator iter)
00177 {
00178 Node* const n = iter._listnode;
00179
00180 if (n) {
00181
00182 Node* const prev = n->prev();
00183 Node* const next = n->next();
00184
00185
00186 if (n == _head.get())
00187 _head = next;
00188
00189
00190 if (n == _tail.get())
00191 _tail = _tail.get()->prev();
00192
00193 if (prev)
00194 n->prev()->next(next);
00195
00196 if (next)
00197 n->next()->prev(prev);
00198
00199 --_size;
00200 }
00201
00202 return n;
00203 }
00204
00205
00207
00208 template <typename T>
00209 List<T>::iterator::iterator(List<T>* list)
00210 : _list(list),
00211 _listnode(NULL)
00212 {
00213 }
00214
00215
00216 template <typename T>
00217 T&
00218 List<T>::iterator::operator*()
00219 {
00220 assert(_listnode);
00221 return _listnode->elem();
00222 }
00223
00224
00225 template <typename T>
00226 T*
00227 List<T>::iterator::operator->()
00228 {
00229 assert(_listnode);
00230 return &_listnode->elem();
00231 }
00232
00233
00234 template <typename T>
00235 inline typename List<T>::iterator&
00236 List<T>::iterator::operator++()
00237 {
00238 assert(_listnode);
00239 _listnode = _listnode->next();
00240
00241 return *this;
00242 }
00243
00244
00245 template <typename T>
00246 inline bool
00247 List<T>::iterator::operator!=(const iterator& iter) const
00248 {
00249 return (_listnode != iter._listnode);
00250 }
00251
00252
00253 template <typename T>
00254 inline bool
00255 List<T>::iterator::operator!=(const const_iterator& iter) const
00256 {
00257 return (_listnode != iter._listnode);
00258 }
00259
00260
00261 template <typename T>
00262 inline bool
00263 List<T>::iterator::operator==(const iterator& iter) const
00264 {
00265 return (_listnode == iter._listnode);
00266 }
00267
00268
00269 template <typename T>
00270 inline bool
00271 List<T>::iterator::operator==(const const_iterator& iter) const
00272 {
00273 return (_listnode == iter._listnode);
00274 }
00275
00276
00277 template <typename T>
00278 inline typename List<T>::iterator
00279 List<T>::begin()
00280 {
00281 typename List<T>::iterator iter(this);
00282
00283 iter._listnode = _head.get();
00284
00285 return iter;
00286 }
00287
00288
00289 template <typename T>
00290 inline const typename List<T>::iterator
00291 List<T>::end() const
00292 {
00293 return _end_iter;
00294 }
00295
00296
00297
00299
00300
00301 template <typename T>
00302 List<T>::const_iterator::const_iterator(const List<T>* const list)
00303 : _list(list),
00304 _listnode(NULL)
00305 {
00306 }
00307
00308
00309 template <typename T>
00310 const T&
00311 List<T>::const_iterator::operator*()
00312 {
00313 assert(_listnode);
00314 return _listnode->elem();
00315 }
00316
00317
00318 template <typename T>
00319 const T*
00320 List<T>::const_iterator::operator->()
00321 {
00322 assert(_listnode);
00323 return &_listnode->elem();
00324 }
00325
00326
00327 template <typename T>
00328 inline typename List<T>::const_iterator&
00329 List<T>::const_iterator::operator++()
00330 {
00331 assert(_listnode);
00332 _listnode = _listnode->next();
00333
00334 return *this;
00335 }
00336
00337
00338 template <typename T>
00339 inline bool
00340 List<T>::const_iterator::operator!=(const const_iterator& iter) const
00341 {
00342 return (_listnode != iter._listnode);
00343 }
00344
00345
00346 template <typename T>
00347 inline bool
00348 List<T>::const_iterator::operator!=(const iterator& iter) const
00349 {
00350 return (_listnode != iter._listnode);
00351 }
00352
00353
00354 template <typename T>
00355 inline bool
00356 List<T>::const_iterator::operator==(const const_iterator& iter) const
00357 {
00358 return (_listnode == iter._listnode);
00359 }
00360
00361
00362 template <typename T>
00363 inline bool
00364 List<T>::const_iterator::operator==(const iterator& iter) const
00365 {
00366 return (_listnode == iter._listnode);
00367 }
00368
00369 template <typename T>
00370 inline typename List<T>::const_iterator
00371 List<T>::begin() const
00372 {
00373 typename List<T>::const_iterator iter(this);
00374 iter._listnode = _head.get();
00375 return iter;
00376 }
00377
00378
00379 }
00380
00381
00382 #endif // RAUL_LIST_IMPL_HPP