RAUL 0.8.0

- Main Page
- Modules
- Namespaces
- Classes
- Files

- File List

ListImpl.hpp

    00001 /* This file is part of Raul.
    00002  * Copyright (C) 2007-2009 David Robillard <http://drobilla.net>
    00003  *
    00004  * Raul is free software; you can redistribute it and/or modify it under the
    00005  * terms of the GNU General Public License as published by the Free Software
    00006  * Foundation; either version 2 of the License, or (at your option) any later
    00007  * version.
    00008  *
    00009  * Raul is distributed in the hope that it will be useful, but WITHOUT ANY
    00010  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    00011  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for details.
    00012  *
    00013  * You should have received a copy of the GNU General Public License along
    00014  * with this program; if not, write to the Free Software Foundation, Inc.,
    00015  * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
    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()) { // empty
    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()) { // empty
    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     // Appending to an empty list
    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         // FIXME: atomicity an issue? _size < true size is probably fine...
    00139         // no guarantee an iteration runs exactly size times though.  verify/document this.
    00140         // assuming comment above that says tail is writer only, this is fine
    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         // Removing the head (or the only element)
    00188         if (n == _head.get())
    00189             _head = next;
    00190
    00191         // Removing the tail (or the only element)
    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         // FIXME: race?
    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 } // namespace Raul
    00409
    00410
    00411 #endif // RAUL_LIST_IMPL_HPP