RAUL: ListImpl.hpp Source File

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