RAUL
0.7.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 _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