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 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
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
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
00225
00226
00227
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
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
00281 delete tail;
00282
00283 tail = 0;
00284 sz = 0;
00285 }
00286
00295 iterator insert(iterator it, const T& val) {
00296
00297 Node* tmp = new Node;
00298 tmp->value = new T(val);
00299
00300 if(!tail) {
00301
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
00324 E_ASSERT(it.node != tail && "Bad code! erase() on end()!!!");
00325
00326
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
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
00445
00446
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
00462 #ifndef SKIP_DOCS
00463 #ifndef NO_LIST_SPECIALIZATION
00464
00465
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
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
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