/builddir/build/BUILD/raul-0.4.0/raul/ListImpl.hpp

00001 /* This file is part of Raul.
00002  * Copyright (C) 2007 Dave 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 
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     // Appending to an empty list
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         // FIXME: atomicity an issue? _size < true size is probably fine...
00137         // no gurantee an iteration runs exactly size times though.  verify/document this.
00138         // assuming comment above that says tail is writer only, this is fine
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         // Removing the head (or the only element)
00186         if (n == _head.get())
00187             _head = next;
00188 
00189         // Removing the tail (or the only element)
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 } // namespace Raul
00380 
00381 
00382 #endif // RAUL_LIST_IMPL_HPP

Generated on Wed Apr 9 08:14:41 2008 for RAUL by  doxygen 1.5.1