00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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 bool operator!=(const ListIterator& other) const { return node != other.node; }
00052 bool operator==(const ListIterator& other) const { return node == other.node; }
00053 ListIterator& operator++(void) { node = node->next; return *this; }
00054 ListIterator& operator--(void) { node = node->prev; return *this; }
00055 };
00056
00057 #ifndef USE_SMALL_LIST
00058 template <typename T>
00059 struct ListConstIterator {
00060 typedef ListNode NodeType;
00061 NodeType* node;
00062
00063 ListConstIterator(NodeType* n) : node(n) { }
00064 ListConstIterator() : node(0) { }
00065
00066
00067 ListConstIterator(const ListIterator<T>& i) : node(i.node) { }
00068
00069 const T& operator*(void) const {
00070 E_ASSERT(node != 0 && "Bad code! Access to zero node!!!");
00071 E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!");
00072 return *(T*)node->value;
00073 }
00074
00075 bool operator!=(const ListConstIterator& other) const { return node != other.node; }
00076 bool operator==(const ListConstIterator& other) const { return node == other.node; }
00077 ListConstIterator& operator++(void) { node = node->next; return *this; }
00078 ListConstIterator& operator--(void) { node = node->prev; return *this; }
00079 };
00080 #endif
00081
00082 #endif
00083
00147 template <typename T>
00148 class list {
00149 public:
00150 #ifndef SKIP_DOCS
00151 typedef unsigned int size_type;
00152 #endif
00153 private:
00154 typedef ListNode Node;
00155 typedef bool (SortCmp)(const T& val1, const T& val2);
00156
00157 size_type sz;
00158 Node* tail;
00159
00160 E_DISABLE_CLASS_COPY(list)
00161
00162 static bool default_sort_cmp(const T& val1, const T& val2) { return val1 < val2; }
00163
00164 Node* merge_nodes(Node* a, Node* b, SortCmp* cmp) {
00165 Node head;
00166 Node* c = &head;
00167 Node* cprev = 0;
00168
00169 while(a != 0 && b != 0) {
00170
00171 if(cmp(*(T*)a->value, *(T*)b->value)) {
00172 c->next = a;
00173 a = a->next;
00174 } else {
00175 c->next = b;
00176 b = b->next;
00177 }
00178
00179 c = c->next;
00180 c->prev = cprev;
00181 cprev = c;
00182 }
00183
00184 if(a == 0)
00185 c->next = b;
00186 else
00187 c->next = a;
00188
00189 c->next->prev = c;
00190 return head.next;
00191 }
00192
00193 Node* mergesort(Node* c, SortCmp* cmp) {
00194 Node* a, *b;
00195 if(c->next == 0)
00196 return c;
00197 a = c;
00198 b = c->next;
00199
00200 while((b != 0) && (b->next != 0)) {
00201 c = c->next;
00202 b = b->next->next;
00203 }
00204
00205 b = c->next;
00206 c->next = 0;
00207 return merge_nodes(mergesort(a, cmp), mergesort(b, cmp), cmp);
00208 }
00209
00210 public:
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231 #ifndef SKIP_DOCS
00232 typedef ListIterator<T> iterator;
00233 #ifndef USE_SMALL_LIST
00234 typedef ListConstIterator<T> const_iterator;
00235 #else
00236 typedef ListIterator<T> const_iterator;
00237 #endif
00238 #endif
00239
00243 list() : sz(0), tail(0) { }
00244
00248 ~list() { clear(); }
00249
00253 void clear(void) {
00254 if(!tail) {
00255 E_ASSERT(sz == 0 && "Internal error! size() != 0, but list is empty !?!!");
00256 return;
00257 }
00258
00259 Node* p = tail->next;
00260 Node* t;
00261 while(p != tail) {
00262 t = p->next;
00263 delete (T*)p->value;
00264 delete p;
00265 p = t;
00266 }
00267
00268
00269 delete tail;
00270
00271 tail = 0;
00272 sz = 0;
00273 }
00274
00283 iterator insert(iterator it, const T& val) {
00284
00285 Node* tmp = new Node;
00286 tmp->value = new T(val);
00287
00288 if(!tail) {
00289
00290 tail = new Node;
00291 tail->next = tail->prev = tmp;
00292 tmp->next = tmp->prev = tail;
00293 } else {
00294 tmp->next = it.node;
00295 tmp->prev = it.node->prev;
00296 it.node->prev->next = tmp;
00297 it.node->prev = tmp;
00298 }
00299
00300 sz++;
00301 return iterator(tmp);
00302 }
00303
00310 iterator erase(iterator it) {
00311
00312 E_ASSERT(it.node != tail && "Bad code! erase() on end()!!!");
00313
00314
00315 it.node->prev->next = it.node->next;
00316 it.node->next->prev = it.node->prev;
00317
00318 iterator ret(it.node);
00319 ++ret;
00320 sz--;
00321
00322 delete (T*)it.node->value;
00323 delete it.node;
00324
00325 return ret;
00326 }
00327
00332 void push_back(const T& val) { insert(end(), val); }
00333
00338 void push_front(const T& val) { insert(begin(), val); }
00339
00343 iterator begin(void) { return iterator(tail ? tail->next : 0); }
00344
00348 const_iterator begin(void) const { return const_iterator(tail ? tail->next : 0); }
00349
00355 iterator end(void) { return iterator(tail); }
00356
00362 const_iterator end(void) const { return const_iterator(tail); }
00363
00367 T& front(void) { return *(begin()); }
00368
00372 const T& front(void) const { return *(begin()); }
00373
00377 T& back(void) { return *(--end()); }
00378
00382 const T& back(void) const { return *(--end()); }
00383
00387 size_type size(void) const { return sz; }
00388
00392 bool empty(void) const { return sz == 0; }
00393
00397 bool operator==(list<T>& other) {
00398 if(size() != other.size())
00399 return false;
00400
00401 iterator it = begin(), it_end = end(), it2 = other.begin();
00402 for(; it != it_end; ++it, ++it2) {
00403 if((*it) != (*it2))
00404 return false;
00405 }
00406
00407 return true;
00408 }
00409
00413 bool operator!=(list<T>& other) { return !operator==(other); }
00414
00419 void sort(SortCmp* cmp = default_sort_cmp) {
00420 if(size() <= 1)
00421 return;
00422
00423
00424 tail->prev->next = 0;
00425
00426 Node* nn = mergesort(tail->next, cmp);
00427
00428 tail->next = nn;
00429 nn->prev = tail;
00430
00431
00432
00433
00434
00435
00436 while(1) {
00437 if(nn->next)
00438 nn = nn->next;
00439 else {
00440 nn->next = tail;
00441 tail->prev = nn;
00442 break;
00443 }
00444 }
00445 }
00446 };
00447
00448 #if 0
00449
00450 #ifndef SKIP_DOCS
00451 #ifndef NO_LIST_SPECIALIZATION
00452
00453
00454 template class list<void*>;
00455 template class ListIterator<void*>;
00456
00457 template <typename T>
00458 struct ListIterator<T*> {
00459 private:
00460 ListIterator<void*> impl;
00461
00462 public:
00463
00464 operator ListIterator<void*> () { return impl; }
00465
00466 ListIterator(const ListIterator<void*>& b) : impl(b) { }
00467 typedef ListNode NodeType;
00468
00469 ListIterator() { }
00470 ListIterator(NodeType* n) : impl(n) { }
00471
00472 T* operator*(void) const { return (T*)*impl; }
00473
00474 bool operator!=(const ListIterator& other) const { return impl != other.impl; }
00475 bool operator==(const ListIterator& other) const { return impl == other.impl; }
00476
00477 ListIterator& operator++(void) { ++impl; return *this; }
00478 ListIterator& operator--(void) { --impl; return *this; }
00479 };
00480
00481 template <typename T>
00482 class list<T*> {
00483 private:
00484 list<void*> impl;
00485 static bool default_sort_cmp(const T* val1, const T* val2) { return *val1 < *val2; }
00486
00487 public:
00488 typedef unsigned int size_type;
00489
00490 typedef T* value_type;
00491 typedef const value_type& const_reference;
00492 typedef value_type& reference;
00493 typedef value_type* pointer;
00494 typedef const value_type* const_pointer;
00495
00496 typedef bool (SortCmp)(const_reference val1, const_reference val2);
00497
00498 typedef ListIterator<T*> iterator;
00499 typedef ListIterator<T*> const_iterator;
00500
00501 void clear(void) { impl.clear(); }
00502
00503 iterator insert(iterator it, const_reference val) { return impl.insert(it, val); }
00504 iterator erase(iterator it) { return impl.erase(it); }
00505
00506 void push_back(const_reference val) { impl.push_back((void*)val); }
00507 void push_front(const_reference val) { impl.push_front((void*)val); }
00508
00509 iterator begin(void) { return impl.begin(); }
00510 const_iterator begin(void) const { return impl.begin(); }
00511
00512 iterator end(void) { return impl.end(); }
00513 const_iterator end(void) const { return impl.end(); }
00514
00515 pointer front(void) { return impl.front(); }
00516 const_pointer front(void) const { return impl.front(); }
00517
00518 pointer back(void) { return impl.back(); }
00519 const_pointer back(void) const { return impl.back(); }
00520
00521 size_type size(void) const { return impl.size(); }
00522 bool empty(void) const { return impl.empty(); }
00523
00524 bool operator==(list<T*>& other) { return impl.operator==(other); }
00525 bool operator!=(list<T*>& other) { return impl.operator!=(other); }
00526
00527
00528 void sort(SortCmp* cmp) { impl.sort((bool (*)(void* const&, void* const&)) cmp); }
00529 };
00530
00531 #endif // NO_LIST_SPECIALIZATION
00532 #endif // SKIP_DOCS
00533 #endif
00534
00535 EDELIB_NS_END
00536 #endif