• 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         _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         // FIXME: atomicity an issue? _size < true size is probably fine...
00139         // no gurantee 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 
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         // Removing the head (or the only element)
00187         if (n == _head.get())
00188             _head = next;
00189 
00190         // Removing the tail (or the only element)
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 } // namespace Raul
00412 
00413 
00414 #endif // RAUL_LIST_IMPL_HPP

Generated on Wed Oct 6 2010 for RAUL by  doxygen 1.7.1