edelib
2.0.0
|
00001 /* 00002 * $Id: List.h 3250 2012-04-15 15:26:53Z karijes $ 00003 * 00004 * STL-like list class 00005 * Copyright (c) 2005-2007 edelib authors 00006 * 00007 * This library is free software; you can redistribute it and/or 00008 * modify it under the terms of the GNU Lesser General Public 00009 * License as published by the Free Software Foundation; either 00010 * version 2 of the License, or (at your option) any later version. 00011 * 00012 * This library is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00015 * Lesser General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU Lesser General Public License 00018 * along with this library. If not, see <http://www.gnu.org/licenses/>. 00019 */ 00020 00021 #ifndef __EDELIB_LIST_H__ 00022 #define __EDELIB_LIST_H__ 00023 00024 #include "Debug.h" 00025 00026 EDELIB_NS_BEGIN 00027 00028 #ifndef SKIP_DOCS 00029 00030 struct ListNode { 00031 void* value; 00032 ListNode* next; 00033 ListNode* prev; 00034 ListNode() : value(0), next(0), prev(0) { } 00035 }; 00036 00037 template <typename T> 00038 struct ListIterator { 00039 typedef ListNode NodeType; 00040 NodeType* node; 00041 00042 ListIterator(NodeType* n) : node(n) { } 00043 ListIterator() : node(0) { } 00044 00045 T& operator*(void) const { 00046 E_ASSERT(node != 0 && "Bad code! Access to zero node!!!"); 00047 E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!"); 00048 return *(T*)node->value; 00049 } 00050 00051 T* operator->(void) const { 00052 E_ASSERT(node != 0 && "Bad code! Access to zero node!!!"); 00053 E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!"); 00054 return (T*)node->value; 00055 } 00056 00057 bool operator!=(const ListIterator& other) const { return node != other.node; } 00058 bool operator==(const ListIterator& other) const { return node == other.node; } 00059 ListIterator& operator++(void) { node = node->next; return *this; } 00060 ListIterator& operator--(void) { node = node->prev; return *this; } 00061 }; 00062 00063 #ifndef USE_SMALL_LIST 00064 template <typename T> 00065 struct ListConstIterator { 00066 typedef ListNode NodeType; 00067 NodeType* node; 00068 00069 ListConstIterator(NodeType* n) : node(n) { } 00070 ListConstIterator() : node(0) { } 00071 00072 // stupid language constructs !!! 00073 ListConstIterator(const ListIterator<T>& i) : node(i.node) { } 00074 00075 const T& operator*(void) const { 00076 E_ASSERT(node != 0 && "Bad code! Access to zero node!!!"); 00077 E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!"); 00078 return *(T*)node->value; 00079 } 00080 00081 const T* operator->(void) const { 00082 E_ASSERT(node != 0 && "Bad code! Access to zero node!!!"); 00083 E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!"); 00084 return (T*)node->value; 00085 } 00086 00087 bool operator!=(const ListConstIterator& other) const { return node != other.node; } 00088 bool operator==(const ListConstIterator& other) const { return node == other.node; } 00089 ListConstIterator& operator++(void) { node = node->next; return *this; } 00090 ListConstIterator& operator--(void) { node = node->prev; return *this; } 00091 }; 00092 #endif 00093 00094 #endif 00095 00159 template <typename T> 00160 class list { 00161 public: 00162 #ifndef SKIP_DOCS 00163 typedef unsigned int size_type; 00164 #endif 00165 private: 00166 typedef ListNode Node; 00167 typedef bool (SortCmp)(const T& val1, const T& val2); 00168 00169 size_type sz; 00170 Node* tail; 00171 00172 E_DISABLE_CLASS_COPY(list) 00173 00174 static bool default_sort_cmp(const T& val1, const T& val2) { return val1 < val2; } 00175 00176 Node* merge_nodes(Node* a, Node* b, SortCmp* cmp) { 00177 Node head; 00178 Node* c = &head; 00179 Node* cprev = 0; 00180 00181 while(a != 0 && b != 0) { 00182 // compare values 00183 if(cmp(*(T*)a->value, *(T*)b->value)) { 00184 c->next = a; 00185 a = a->next; 00186 } else { 00187 c->next = b; 00188 b = b->next; 00189 } 00190 00191 c = c->next; 00192 c->prev = cprev; 00193 cprev = c; 00194 } 00195 00196 if(a == 0) 00197 c->next = b; 00198 else 00199 c->next = a; 00200 00201 c->next->prev = c; 00202 return head.next; 00203 } 00204 00205 Node* mergesort(Node* c, SortCmp* cmp) { 00206 Node* a, *b; 00207 if(c->next == 0) 00208 return c; 00209 a = c; 00210 b = c->next; 00211 00212 while((b != 0) && (b->next != 0)) { 00213 c = c->next; 00214 b = b->next->next; 00215 } 00216 00217 b = c->next; 00218 c->next = 0; 00219 return merge_nodes(mergesort(a, cmp), mergesort(b, cmp), cmp); 00220 } 00221 00222 public: 00223 /* 00224 * This comment is not part of documentation, and in short explains 00225 * implementation details. 00226 * 00227 * List is implemented as circular doubly linked list, which means 00228 * that last node is pointing back to the first one (and reverse). 00229 * Due the nature of traversing in circular lists, additional node 00230 * (dummy node) is created so traversal (first != last) can be done. 00231 * 00232 * As you can see, only one node (tail) is used; it always pointing 00233 * to dummy node (which is always latest node). To get first element node, 00234 * tail->first is used, and to get last (user visible), tail->prev is used. 00235 * This implementation is needed so cases like --end() can return valid 00236 * iterator to last element in the list. 00237 * 00238 * I tried to avoid dummy node creation, but implementing circular list 00239 * will be pain in the ass. Also, contrary popular std::list implementations I could 00240 * find, this node will be created only when insert()/push_back()/push_front() 00241 * are called; without those calls, list will not allocate it. 00242 */ 00243 #ifndef SKIP_DOCS 00244 typedef ListIterator<T> iterator; 00245 #ifndef USE_SMALL_LIST 00246 typedef ListConstIterator<T> const_iterator; 00247 #else 00248 typedef ListIterator<T> const_iterator; 00249 #endif 00250 #endif 00251 00255 list() : sz(0), tail(0) { } 00256 00260 ~list() { clear(); } 00261 00265 void clear(void) { 00266 if(!tail) { 00267 E_ASSERT(sz == 0 && "Internal error! size() != 0, but list is empty !?!!"); 00268 return; 00269 } 00270 00271 Node* p = tail->next; 00272 Node* t; 00273 while(p != tail) { 00274 t = p->next; 00275 delete (T*)p->value; 00276 delete p; 00277 p = t; 00278 } 00279 00280 // delete dummy node 00281 delete tail; 00282 00283 tail = 0; 00284 sz = 0; 00285 } 00286 00295 iterator insert(iterator it, const T& val) { 00296 // [23.2.2.3] insert() does not affect validity of iterators 00297 Node* tmp = new Node; 00298 tmp->value = new T(val); 00299 00300 if(!tail) { 00301 // dummy node first 00302 tail = new Node; 00303 tail->next = tail->prev = tmp; 00304 tmp->next = tmp->prev = tail; 00305 } else { 00306 tmp->next = it.node; 00307 tmp->prev = it.node->prev; 00308 it.node->prev->next = tmp; 00309 it.node->prev = tmp; 00310 } 00311 00312 sz++; 00313 return iterator(tmp); 00314 } 00315 00322 iterator erase(iterator it) { 00323 // do not allow erase(l.end()) 00324 E_ASSERT(it.node != tail && "Bad code! erase() on end()!!!"); 00325 00326 // [23.2.2.3] erase() invalidates only the iterators 00327 it.node->prev->next = it.node->next; 00328 it.node->next->prev = it.node->prev; 00329 00330 iterator ret(it.node); 00331 ++ret; 00332 sz--; 00333 00334 delete (T*)it.node->value; 00335 delete it.node; 00336 00337 return ret; 00338 } 00339 00344 void push_back(const T& val) { insert(end(), val); } 00345 00350 void push_front(const T& val) { insert(begin(), val); } 00351 00355 iterator begin(void) { return iterator(tail ? tail->next : 0); } 00356 00360 const_iterator begin(void) const { return const_iterator(tail ? tail->next : 0); } 00361 00367 iterator end(void) { return iterator(tail); } 00368 00374 const_iterator end(void) const { return const_iterator(tail); } 00375 00379 T& front(void) { return *(begin()); } 00380 00384 const T& front(void) const { return *(begin()); } 00385 00389 T& back(void) { return *(--end()); } 00390 00394 const T& back(void) const { return *(--end()); } 00395 00399 size_type size(void) const { return sz; } 00400 00404 bool empty(void) const { return sz == 0; } 00405 00409 bool operator==(list<T>& other) { 00410 if(size() != other.size()) 00411 return false; 00412 00413 iterator it = begin(), it_end = end(), it2 = other.begin(); 00414 for(; it != it_end; ++it, ++it2) { 00415 if((*it) != (*it2)) 00416 return false; 00417 } 00418 00419 return true; 00420 } 00421 00425 bool operator!=(list<T>& other) { return !operator==(other); } 00426 00431 void sort(SortCmp* cmp = default_sort_cmp) { 00432 if(size() <= 1) 00433 return; 00434 00435 // unlink nodes first making first->prev and last->next zero 00436 tail->prev->next = 0; 00437 00438 Node* nn = mergesort(tail->next, cmp); 00439 00440 tail->next = nn; 00441 nn->prev = tail; 00442 00443 /* 00444 * Search last node and let tail points to it. 00445 * Althought this looks like overhead, this sort is still twice faster that std::list sort. 00446 * Alternative optimization would be that __mergesort() returns end node. 00447 */ 00448 while(1) { 00449 if(nn->next) 00450 nn = nn->next; 00451 else { 00452 nn->next = tail; 00453 tail->prev = nn; 00454 break; 00455 } 00456 } 00457 } 00458 }; 00459 00460 #if 0 00461 // list specialization for pointers 00462 #ifndef SKIP_DOCS 00463 #ifndef NO_LIST_SPECIALIZATION 00464 00465 // explicit instantation 00466 template class list<void*>; 00467 template class ListIterator<void*>; 00468 00469 template <typename T> 00470 struct ListIterator<T*> { 00471 private: 00472 ListIterator<void*> impl; 00473 00474 public: 00475 // implicit conversion; some magic. Yuck ! 00476 operator ListIterator<void*> () { return impl; } 00477 00478 ListIterator(const ListIterator<void*>& b) : impl(b) { } 00479 typedef ListNode NodeType; 00480 00481 ListIterator() { } 00482 ListIterator(NodeType* n) : impl(n) { } 00483 00484 T* operator*(void) const { return (T*)*impl; } 00485 00486 bool operator!=(const ListIterator& other) const { return impl != other.impl; } 00487 bool operator==(const ListIterator& other) const { return impl == other.impl; } 00488 00489 ListIterator& operator++(void) { ++impl; return *this; } 00490 ListIterator& operator--(void) { --impl; return *this; } 00491 }; 00492 00493 template <typename T> 00494 class list<T*> { 00495 private: 00496 list<void*> impl; 00497 static bool default_sort_cmp(const T* val1, const T* val2) { return *val1 < *val2; } 00498 00499 public: 00500 typedef unsigned int size_type; 00501 00502 typedef T* value_type; 00503 typedef const value_type& const_reference; 00504 typedef value_type& reference; 00505 typedef value_type* pointer; 00506 typedef const value_type* const_pointer; 00507 00508 typedef bool (SortCmp)(const_reference val1, const_reference val2); 00509 00510 typedef ListIterator<T*> iterator; 00511 typedef ListIterator<T*> const_iterator; 00512 00513 void clear(void) { impl.clear(); } 00514 00515 iterator insert(iterator it, const_reference val) { return impl.insert(it, val); } 00516 iterator erase(iterator it) { return impl.erase(it); } 00517 00518 void push_back(const_reference val) { impl.push_back((void*)val); } 00519 void push_front(const_reference val) { impl.push_front((void*)val); } 00520 00521 iterator begin(void) { return impl.begin(); } 00522 const_iterator begin(void) const { return impl.begin(); } 00523 00524 iterator end(void) { return impl.end(); } 00525 const_iterator end(void) const { return impl.end(); } 00526 00527 pointer front(void) { return impl.front(); } 00528 const_pointer front(void) const { return impl.front(); } 00529 00530 pointer back(void) { return impl.back(); } 00531 const_pointer back(void) const { return impl.back(); } 00532 00533 size_type size(void) const { return impl.size(); } 00534 bool empty(void) const { return impl.empty(); } 00535 00536 bool operator==(list<T*>& other) { return impl.operator==(other); } 00537 bool operator!=(list<T*>& other) { return impl.operator!=(other); } 00538 00539 //void sort(SortCmp* cmp = default_sort_cmp) { impl.sort( (bool (*)(void* const&, void* const&)) cmp); } 00540 void sort(SortCmp* cmp) { impl.sort((bool (*)(void* const&, void* const&)) cmp); } 00541 }; 00542 00543 #endif // NO_LIST_SPECIALIZATION 00544 #endif // SKIP_DOCS 00545 #endif 00546 00547 EDELIB_NS_END 00548 #endif