edelib 2.1.0
List.h
1/*
2 * $Id: List.h 3250 2012-04-15 15:26:53Z karijes $
3 *
4 * STL-like list class
5 * Copyright (c) 2005-2007 edelib authors
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with this library. If not, see <http://www.gnu.org/licenses/>.
19 */
20
21#ifndef __EDELIB_LIST_H__
22#define __EDELIB_LIST_H__
23
24#include "Debug.h"
25
26EDELIB_NS_BEGIN
27
28#ifndef SKIP_DOCS
29
30struct ListNode {
31 void* value;
32 ListNode* next;
33 ListNode* prev;
34 ListNode() : value(0), next(0), prev(0) { }
35};
36
37template <typename T>
38struct ListIterator {
39 typedef ListNode NodeType;
40 NodeType* node;
41
42 ListIterator(NodeType* n) : node(n) { }
43 ListIterator() : node(0) { }
44
45 T& operator*(void) const {
46 E_ASSERT(node != 0 && "Bad code! Access to zero node!!!");
47 E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!");
48 return *(T*)node->value;
49 }
50
51 T* operator->(void) const {
52 E_ASSERT(node != 0 && "Bad code! Access to zero node!!!");
53 E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!");
54 return (T*)node->value;
55 }
56
57 bool operator!=(const ListIterator& other) const { return node != other.node; }
58 bool operator==(const ListIterator& other) const { return node == other.node; }
59 ListIterator& operator++(void) { node = node->next; return *this; }
60 ListIterator& operator--(void) { node = node->prev; return *this; }
61};
62
63#ifndef USE_SMALL_LIST
64template <typename T>
65struct ListConstIterator {
66 typedef ListNode NodeType;
67 NodeType* node;
68
69 ListConstIterator(NodeType* n) : node(n) { }
70 ListConstIterator() : node(0) { }
71
72 // stupid language constructs !!!
73 ListConstIterator(const ListIterator<T>& i) : node(i.node) { }
74
75 const T& operator*(void) const {
76 E_ASSERT(node != 0 && "Bad code! Access to zero node!!!");
77 E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!");
78 return *(T*)node->value;
79 }
80
81 const T* operator->(void) const {
82 E_ASSERT(node != 0 && "Bad code! Access to zero node!!!");
83 E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!");
84 return (T*)node->value;
85 }
86
87 bool operator!=(const ListConstIterator& other) const { return node != other.node; }
88 bool operator==(const ListConstIterator& other) const { return node == other.node; }
89 ListConstIterator& operator++(void) { node = node->next; return *this; }
90 ListConstIterator& operator--(void) { node = node->prev; return *this; }
91};
92#endif
93
94#endif
95
159template <typename T>
160class list {
161public:
162#ifndef SKIP_DOCS
163 typedef unsigned int size_type;
164#endif
165private:
166 typedef ListNode Node;
167 typedef bool (SortCmp)(const T& val1, const T& val2);
168
169 size_type sz;
170 Node* tail;
171
173
174 static bool default_sort_cmp(const T& val1, const T& val2) { return val1 < val2; }
175
176 Node* merge_nodes(Node* a, Node* b, SortCmp* cmp) {
177 Node head;
178 Node* c = &head;
179 Node* cprev = 0;
180
181 while(a != 0 && b != 0) {
182 // compare values
183 if(cmp(*(T*)a->value, *(T*)b->value)) {
184 c->next = a;
185 a = a->next;
186 } else {
187 c->next = b;
188 b = b->next;
189 }
190
191 c = c->next;
192 c->prev = cprev;
193 cprev = c;
194 }
195
196 if(a == 0)
197 c->next = b;
198 else
199 c->next = a;
200
201 c->next->prev = c;
202 return head.next;
203 }
204
205 Node* mergesort(Node* c, SortCmp* cmp) {
206 Node* a, *b;
207 if(c->next == 0)
208 return c;
209 a = c;
210 b = c->next;
211
212 while((b != 0) && (b->next != 0)) {
213 c = c->next;
214 b = b->next->next;
215 }
216
217 b = c->next;
218 c->next = 0;
219 return merge_nodes(mergesort(a, cmp), mergesort(b, cmp), cmp);
220 }
221
222public:
223 /*
224 * This comment is not part of documentation, and in short explains
225 * implementation details.
226 *
227 * List is implemented as circular doubly linked list, which means
228 * that last node is pointing back to the first one (and reverse).
229 * Due the nature of traversing in circular lists, additional node
230 * (dummy node) is created so traversal (first != last) can be done.
231 *
232 * As you can see, only one node (tail) is used; it always pointing
233 * to dummy node (which is always latest node). To get first element node,
234 * tail->first is used, and to get last (user visible), tail->prev is used.
235 * This implementation is needed so cases like --end() can return valid
236 * iterator to last element in the list.
237 *
238 * I tried to avoid dummy node creation, but implementing circular list
239 * will be pain in the ass. Also, contrary popular std::list implementations I could
240 * find, this node will be created only when insert()/push_back()/push_front()
241 * are called; without those calls, list will not allocate it.
242 */
243#ifndef SKIP_DOCS
244 typedef ListIterator<T> iterator;
245#ifndef USE_SMALL_LIST
246 typedef ListConstIterator<T> const_iterator;
247#else
248 typedef ListIterator<T> const_iterator;
249#endif
250#endif
251
255 list() : sz(0), tail(0) { }
256
260 ~list() { clear(); }
261
265 void clear(void) {
266 if(!tail) {
267 E_ASSERT(sz == 0 && "Internal error! size() != 0, but list is empty !?!!");
268 return;
269 }
270
271 Node* p = tail->next;
272 Node* t;
273 while(p != tail) {
274 t = p->next;
275 delete (T*)p->value;
276 delete p;
277 p = t;
278 }
279
280 // delete dummy node
281 delete tail;
282
283 tail = 0;
284 sz = 0;
285 }
286
295 iterator insert(iterator it, const T& val) {
296 // [23.2.2.3] insert() does not affect validity of iterators
297 Node* tmp = new Node;
298 tmp->value = new T(val);
299
300 if(!tail) {
301 // dummy node first
302 tail = new Node;
303 tail->next = tail->prev = tmp;
304 tmp->next = tmp->prev = tail;
305 } else {
306 tmp->next = it.node;
307 tmp->prev = it.node->prev;
308 it.node->prev->next = tmp;
309 it.node->prev = tmp;
310 }
311
312 sz++;
313 return iterator(tmp);
314 }
315
322 iterator erase(iterator it) {
323 // do not allow erase(l.end())
324 E_ASSERT(it.node != tail && "Bad code! erase() on end()!!!");
325
326 // [23.2.2.3] erase() invalidates only the iterators
327 it.node->prev->next = it.node->next;
328 it.node->next->prev = it.node->prev;
329
330 iterator ret(it.node);
331 ++ret;
332 sz--;
333
334 delete (T*)it.node->value;
335 delete it.node;
336
337 return ret;
338 }
339
344 void push_back(const T& val) { insert(end(), val); }
345
350 void push_front(const T& val) { insert(begin(), val); }
351
355 iterator begin(void) { return iterator(tail ? tail->next : 0); }
356
360 const_iterator begin(void) const { return const_iterator(tail ? tail->next : 0); }
361
367 iterator end(void) { return iterator(tail); }
368
374 const_iterator end(void) const { return const_iterator(tail); }
375
379 T& front(void) { return *(begin()); }
380
384 const T& front(void) const { return *(begin()); }
385
389 T& back(void) { return *(--end()); }
390
394 const T& back(void) const { return *(--end()); }
395
399 size_type size(void) const { return sz; }
400
404 bool empty(void) const { return sz == 0; }
405
409 bool operator==(list<T>& other) {
410 if(size() != other.size())
411 return false;
412
413 iterator it = begin(), it_end = end(), it2 = other.begin();
414 for(; it != it_end; ++it, ++it2) {
415 if((*it) != (*it2))
416 return false;
417 }
418
419 return true;
420 }
421
425 bool operator!=(list<T>& other) { return !operator==(other); }
426
431 void sort(SortCmp* cmp = default_sort_cmp) {
432 if(size() <= 1)
433 return;
434
435 // unlink nodes first making first->prev and last->next zero
436 tail->prev->next = 0;
437
438 Node* nn = mergesort(tail->next, cmp);
439
440 tail->next = nn;
441 nn->prev = tail;
442
443 /*
444 * Search last node and let tail points to it.
445 * Althought this looks like overhead, this sort is still twice faster that std::list sort.
446 * Alternative optimization would be that __mergesort() returns end node.
447 */
448 while(1) {
449 if(nn->next)
450 nn = nn->next;
451 else {
452 nn->next = tail;
453 tail->prev = nn;
454 break;
455 }
456 }
457 }
458};
459
460#if 0
461// list specialization for pointers
462#ifndef SKIP_DOCS
463#ifndef NO_LIST_SPECIALIZATION
464
465// explicit instantation
466template class list<void*>;
467template class ListIterator<void*>;
468
469template <typename T>
470struct ListIterator<T*> {
471private:
472 ListIterator<void*> impl;
473
474public:
475 // implicit conversion; some magic. Yuck !
476 operator ListIterator<void*> () { return impl; }
477
478 ListIterator(const ListIterator<void*>& b) : impl(b) { }
479 typedef ListNode NodeType;
480
481 ListIterator() { }
482 ListIterator(NodeType* n) : impl(n) { }
483
484 T* operator*(void) const { return (T*)*impl; }
485
486 bool operator!=(const ListIterator& other) const { return impl != other.impl; }
487 bool operator==(const ListIterator& other) const { return impl == other.impl; }
488
489 ListIterator& operator++(void) { ++impl; return *this; }
490 ListIterator& operator--(void) { --impl; return *this; }
491};
492
493template <typename T>
494class list<T*> {
495private:
496 list<void*> impl;
497 static bool default_sort_cmp(const T* val1, const T* val2) { return *val1 < *val2; }
498
499public:
500 typedef unsigned int size_type;
501
502 typedef T* value_type;
503 typedef const value_type& const_reference;
504 typedef value_type& reference;
505 typedef value_type* pointer;
506 typedef const value_type* const_pointer;
507
508 typedef bool (SortCmp)(const_reference val1, const_reference val2);
509
510 typedef ListIterator<T*> iterator;
511 typedef ListIterator<T*> const_iterator;
512
513 void clear(void) { impl.clear(); }
514
515 iterator insert(iterator it, const_reference val) { return impl.insert(it, val); }
516 iterator erase(iterator it) { return impl.erase(it); }
517
518 void push_back(const_reference val) { impl.push_back((void*)val); }
519 void push_front(const_reference val) { impl.push_front((void*)val); }
520
521 iterator begin(void) { return impl.begin(); }
522 const_iterator begin(void) const { return impl.begin(); }
523
524 iterator end(void) { return impl.end(); }
525 const_iterator end(void) const { return impl.end(); }
526
527 pointer front(void) { return impl.front(); }
528 const_pointer front(void) const { return impl.front(); }
529
530 pointer back(void) { return impl.back(); }
531 const_pointer back(void) const { return impl.back(); }
532
533 size_type size(void) const { return impl.size(); }
534 bool empty(void) const { return impl.empty(); }
535
536 bool operator==(list<T*>& other) { return impl.operator==(other); }
537 bool operator!=(list<T*>& other) { return impl.operator!=(other); }
538
539 //void sort(SortCmp* cmp = default_sort_cmp) { impl.sort( (bool (*)(void* const&, void* const&)) cmp); }
540 void sort(SortCmp* cmp) { impl.sort((bool (*)(void* const&, void* const&)) cmp); }
541};
542
543#endif // NO_LIST_SPECIALIZATION
544#endif // SKIP_DOCS
545#endif
546
547EDELIB_NS_END
548#endif
bool operator!=(const String &str1, const char *str2)
Definition String.h:359
bool operator==(const String &str1, const char *str2)
Definition String.h:353
Linked list class.
Definition List.h:160
bool operator==(list< T > &other)
Definition List.h:409
bool empty(void) const
Definition List.h:404
const_iterator end(void) const
Definition List.h:374
iterator begin(void)
Definition List.h:355
T & back(void)
Definition List.h:389
size_type size(void) const
Definition List.h:399
bool operator!=(list< T > &other)
Definition List.h:425
list()
Definition List.h:255
void sort(SortCmp *cmp=default_sort_cmp)
Definition List.h:431
T & front(void)
Definition List.h:379
void push_back(const T &val)
Definition List.h:344
const T & front(void) const
Definition List.h:384
const_iterator begin(void) const
Definition List.h:360
void push_front(const T &val)
Definition List.h:350
~list()
Definition List.h:260
iterator erase(iterator it)
Definition List.h:322
const T & back(void) const
Definition List.h:394
void clear(void)
Definition List.h:265
iterator end(void)
Definition List.h:367
iterator insert(iterator it, const T &val)
Definition List.h:295
#define E_ASSERT(expr)
Definition Debug.h:117
#define E_DISABLE_CLASS_COPY(klass)
Definition edelib-global.h:161