edelib  2.0.0
edelib/List.h
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