RAUL
0.8.0
|
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