1 // Doubly linked list class. 2 // 3 // Inserts new entries at the *end* of the list -- so add_entry() 4 // followed by delete_last_entry() will do nothing. 5 // 6 // 7 // Usage: 8 // 9 // List<Thing> l; creates an empty list. 10 // Thing a; List<Thing> l(a); creates a list containing a. 11 // 12 // void l.add_entry(Thing a); adds an entry. 13 // void l.delete_entry(Thing a); removes `a' from the list if it's there, 14 // aborts if it's not. 15 // void l.delete_{first,last}_entry deletes the first/last entry. 16 // Thing l.{first,last}_entry returns the first/last entry. 17 // bool l.contains(Thing a) is a in the list? 18 #ifndef list_template_hpp 19 #define list_template_hpp 20 21 //#pragma once 22 23 #include <stdio.h> 24 25 #ifdef _CPPRTTI // run time type information available 26 #include <typeinfo.h> 27 #define LIST_TEM_TYPEID_THIS typeid(*this).name() 28 #else 29 #define LIST_TEM_TYPEID_THIS "?" 30 #endif 31 32 #include "mem3dc.h" 33 34 #ifdef NDEBUG fail(...)35 static void fail(...) {} 36 #define list_fail_get_data_from_sentinel NULL 37 #define list_fail_add_entry_after NULL 38 #define list_fail_add_entry_before NULL 39 #define list_fail_delete_entry NULL 40 #define list_fail_delete_entry_by_pointer NULL 41 #define list_fail_alter_entry NULL 42 #define list_fail_next_entry_nonexist NULL 43 #define list_fail_next_entry_sentinel NULL 44 #define list_fail_prev_entry_nonexist NULL 45 #define list_fail_prev_entry_sentinel NULL 46 #define list_fail_last_entry NULL 47 #define list_fail_first_entry NULL 48 #define list_fail_similar_entry NULL 49 #define list_fail_delete_last_entry NULL 50 #define list_fail_delete_first_entry NULL 51 #define list_fail_operator NULL 52 #define lit_fail_next NULL 53 #define lit_fail_operator NULL 54 #define lit_fail_delete_current NULL 55 #define lit_fail_change_current NULL 56 #else 57 #include "fail.h" 58 extern char const * list_fail_get_data_from_sentinel; 59 extern char const * list_fail_add_entry_after; 60 extern char const * list_fail_add_entry_before; 61 extern char const * list_fail_delete_entry; 62 extern char const * list_fail_delete_entry_by_pointer; 63 extern char const * list_fail_alter_entry; 64 extern char const * list_fail_next_entry_nonexist; 65 extern char const * list_fail_next_entry_sentinel; 66 extern char const * list_fail_prev_entry_nonexist; 67 extern char const * list_fail_prev_entry_sentinel; 68 extern char const * list_fail_last_entry; 69 extern char const * list_fail_first_entry; 70 extern char const * list_fail_similar_entry; 71 extern char const * list_fail_delete_last_entry; 72 extern char const * list_fail_delete_first_entry; 73 extern char const * list_fail_operator; 74 extern char const * lit_fail_next; 75 extern char const * lit_fail_operator; 76 extern char const * lit_fail_delete_current; 77 extern char const * lit_fail_change_current; 78 #endif 79 80 // The first declaration of these class templates was previously as friends 81 // of List. However, Visual C++ 5 can't parse them unless we give a 82 // forward declaration first - I think this is a compiler bug - Garry. 83 template<class T> 84 class List_Iterator_Forward; 85 template<class T> 86 class ConstList_Iterator_Forward; 87 template<class T> 88 class List_Iterator_Backward; 89 template<class T> 90 class ConstList_Iterator_Backward; 91 template<class T> 92 class List_Iterator_Loop; 93 94 template<class T> 95 struct List_Member; 96 97 template<class T> 98 struct List_Member_Base 99 { 100 union 101 { 102 List_Member_Base<T> *prev; 103 List_Member<T> *prev_debug; // encourage the debugger to display the list members data 104 // hopefully casting from base to derived class would not 105 // cause the actual value of the ptr to change, so the debugger 106 // will display the information correctly, and this union 107 // won't cause any kind of performance hit 108 }; 109 union 110 { 111 List_Member_Base<T> *next; 112 List_Member<T> *next_debug; 113 }; ~List_Member_BaseList_Member_Base114 virtual ~List_Member_Base() {} 115 }; 116 117 template<class T> 118 struct List_Member : public List_Member_Base<T> 119 { 120 T data; 121 List_Member<T>(const T& n) : data(n) {} 122 }; 123 124 template<class T> 125 class List { 126 private: 127 List_Member_Base<T> *sentinel; 128 int n_entries; 129 mutable T **entry_pointers; 130 mutable bool calculated_indices; 131 data(List_Member_Base<T> * e) const132 T& data(List_Member_Base<T>* e) const 133 { 134 if (e == sentinel) 135 fail(list_fail_get_data_from_sentinel,LIST_TEM_TYPEID_THIS); 136 return ((List_Member<T>*)e)->data; 137 } 138 139 public: List()140 List() { 141 sentinel = new List_Member_Base<T>; 142 143 sentinel->next = sentinel; 144 sentinel->prev = sentinel; 145 146 n_entries = 0; 147 entry_pointers = 0; 148 calculated_indices = false; 149 } 150 List(const T & n)151 List(const T& n) { 152 sentinel = new List_Member_Base<T>; 153 sentinel->next = sentinel; 154 sentinel->prev = sentinel; 155 n_entries = 0; 156 entry_pointers = 0; 157 calculated_indices = false; 158 159 add_entry(n); 160 } 161 List(const List<T> & l)162 List(const List<T>& l) { 163 sentinel = new List_Member_Base<T>; 164 165 sentinel->next = sentinel; 166 sentinel->prev = sentinel; 167 n_entries = 0; 168 169 entry_pointers = 0; 170 calculated_indices = false; 171 172 List_Member_Base<T>* m = l.sentinel->next; 173 while (m != l.sentinel) { 174 add_entry(data(m)); 175 m = m->next; 176 } 177 178 } 179 operator =(const List<T> & l)180 List<T>& operator= (const List<T>& l) { 181 while(n_entries != 0) delete_last_entry(); 182 if (entry_pointers != 0) 183 delete[] entry_pointers; 184 185 List_Member_Base<T>* m = l.sentinel->next; 186 while (m != l.sentinel) { 187 add_entry(data(m)); 188 m = m->next; 189 } 190 calculated_indices = false; 191 entry_pointers = 0; 192 return *this; 193 } 194 ~List()195 ~List() { 196 while (n_entries != 0) delete_last_entry(); 197 delete sentinel; 198 delete[] entry_pointers; 199 } 200 add_entry(const T & n)201 void add_entry(const T& n) { 202 add_entry_end(n); 203 } 204 add_entry_end(const T & n)205 void add_entry_end(const T& n) { 206 List_Member<T> *e = new List_Member<T>(n); 207 e->next = sentinel; 208 e->prev = sentinel->prev; 209 sentinel->prev->next = e; 210 sentinel->prev = e; 211 n_entries++; 212 cleanup(); 213 } 214 add_entry_start(const T & n)215 void add_entry_start(const T& n) { 216 List_Member<T> *e = new List_Member<T>(n); 217 e->prev = sentinel; 218 e->next = sentinel->next; 219 sentinel->next->prev = e; 220 sentinel->next = e; 221 n_entries++; 222 cleanup(); 223 } 224 add_entry_after(const T & n,const T & d)225 void add_entry_after(const T& n, const T& d) { 226 List_Member_Base<T> *f = sentinel->next; 227 while (f != sentinel && data(f) != d) { 228 f = f->next; 229 } 230 if (f == sentinel) { 231 fail(list_fail_add_entry_after,LIST_TEM_TYPEID_THIS); 232 } else { 233 List_Member<T> *e = new List_Member<T>(n); 234 e->next = f->next; 235 e->prev = f; 236 e->next->prev = e; 237 f->next = e; 238 n_entries++; 239 } 240 cleanup(); 241 } 242 add_entry_before(const T & n,const T & d)243 void add_entry_before(const T& n, const T& d) { 244 List_Member_Base<T> *f = sentinel->next; 245 while (f != sentinel && data(f) != d) { 246 f = f->next; 247 } 248 if (f == sentinel) { 249 fail(list_fail_add_entry_before,LIST_TEM_TYPEID_THIS); 250 } else { 251 List_Member<T> *e = new List_Member<T>(n); 252 e->prev = f->prev; 253 e->next = f; 254 e->prev->next = e; 255 f->prev = e; 256 n_entries++; 257 } 258 cleanup(); 259 } 260 delete_entry(const T & d)261 void delete_entry(const T& d) { 262 List_Member_Base<T> *e = sentinel->next; 263 while (e != sentinel && data(e) != d && e != sentinel) { 264 e = e->next; 265 } 266 if (e == sentinel) { 267 fail(list_fail_delete_entry,LIST_TEM_TYPEID_THIS); 268 } else { 269 e->prev->next = e->next; 270 e->next->prev = e->prev; 271 delete e; 272 } 273 n_entries--; 274 cleanup(); 275 } 276 delete_entry_backward(const T & d)277 void delete_entry_backward(const T& d) { 278 List_Member_Base<T> *e = sentinel->prev; 279 while (e != sentinel && data(e) != d && e != sentinel) { 280 e = e->prev; 281 } 282 if (e == sentinel) { 283 fail(list_fail_delete_entry,LIST_TEM_TYPEID_THIS); 284 } else { 285 e->prev->next = e->next; 286 e->next->prev = e->prev; 287 delete e; 288 } 289 n_entries--; 290 cleanup(); 291 } 292 delete_entry_by_pointer(List_Member_Base<T> * l)293 void delete_entry_by_pointer(List_Member_Base<T>* l) { 294 if (l == sentinel) 295 fail(list_fail_delete_entry_by_pointer,LIST_TEM_TYPEID_THIS); 296 l->next->prev = l->prev; 297 l->prev->next = l->next; 298 delete l; 299 l = 0; // so we get a seg if we try and reuse it 300 n_entries--; 301 cleanup(); 302 } 303 alter_entry(const T & od,const T & nd)304 void alter_entry(const T& od, const T& nd) { 305 List_Member_Base<T> *e = sentinel->next; 306 while (e != sentinel && data(e) != od) { 307 e = e->next; 308 } 309 if (e == sentinel) { 310 fail(list_fail_alter_entry,LIST_TEM_TYPEID_THIS); 311 } else { 312 // Remove this entry, and put a new one in it's place. We can't 313 // just do e->data = nd, because that's assignment, and we don't 314 // want to require an assignment operator to be defined for 315 // every thing that we put on a list. 316 List_Member<T> * n = new List_Member<T>(nd); 317 e->prev->next = n; 318 e->next->prev = n; 319 n->next = e->next; 320 n->prev = e->prev; 321 delete e; 322 } 323 cleanup(); 324 } 325 next_entry(const T & d) const326 T next_entry(const T& d) const { 327 List_Member_Base<T> *e = sentinel->next; 328 while (e != sentinel && data(e) != d && e != sentinel) { 329 e = e->next; 330 } 331 if (e == sentinel) { 332 fail(list_fail_next_entry_nonexist,LIST_TEM_TYPEID_THIS); 333 } else { 334 if (e->next == sentinel) 335 fail(list_fail_next_entry_sentinel,LIST_TEM_TYPEID_THIS); 336 return data(e->next); 337 } 338 return data(e->next); 339 } 340 prev_entry(const T & d) const341 T prev_entry(const T& d) const { 342 List_Member_Base<T> *e = sentinel->next; 343 while (e!= sentinel && data(e) != d) { 344 e = e->next; 345 } 346 if (e == sentinel) { 347 fail(list_fail_prev_entry_nonexist,LIST_TEM_TYPEID_THIS); 348 } else { 349 if (e->prev == sentinel) 350 fail(list_fail_prev_entry_sentinel,LIST_TEM_TYPEID_THIS); 351 return data(e->prev); 352 } 353 return data(e->prev); 354 } 355 similar_entry(T const & d) const356 T const & similar_entry(T const& d) const 357 { 358 List_Member_Base<T> *e = sentinel->next; 359 while (e != sentinel) 360 { 361 if (data(e) == d) 362 break; 363 e = e->next; 364 365 } 366 if (e == sentinel) 367 { 368 fail(list_fail_similar_entry,LIST_TEM_TYPEID_THIS); 369 } 370 return data(e); 371 } 372 contains(const T & d)373 bool contains(const T& d) { 374 List_Member_Base<T> *e = sentinel->next; 375 while (e != sentinel && data(e) != d) { 376 e = e->next; 377 } 378 if (e == sentinel) return false; 379 else return true; 380 } 381 delete_last_entry()382 void delete_last_entry() { 383 if (sentinel->prev == sentinel) { 384 fail(list_fail_delete_last_entry,LIST_TEM_TYPEID_THIS); 385 } else { 386 // aiee. These lines work, but are a bit hairy. 387 388 sentinel->prev = sentinel->prev->prev; 389 delete sentinel->prev->next; 390 sentinel->prev->next = sentinel; 391 n_entries--; 392 } 393 cleanup(); 394 } 395 delete_first_entry()396 void delete_first_entry() { 397 if (sentinel->next == sentinel) { 398 fail(list_fail_delete_last_entry,LIST_TEM_TYPEID_THIS); 399 } else { 400 sentinel->next = sentinel->next->next; 401 delete sentinel->next->prev; 402 sentinel->next->prev = sentinel; 403 n_entries--; 404 } 405 cleanup(); 406 } 407 operator [](int i) const408 T const & operator[](int i) const { 409 if (i < 0 || i >= n_entries) 410 fail(list_fail_operator,LIST_TEM_TYPEID_THIS, i+1, n_entries); 411 412 if (!calculated_indices) { 413 if (entry_pointers != 0) 414 delete[] entry_pointers; 415 entry_pointers = new T*[n_entries+1]; 416 List_Member_Base<T>*e = sentinel->next; 417 int j = 0; 418 while (e != sentinel) { 419 entry_pointers[j] = &data(e); 420 e = e->next; 421 j++; 422 } 423 calculated_indices = true; 424 } 425 return *entry_pointers[i]; 426 } 427 last_entry()428 T & last_entry() 429 { 430 if (n_entries == 0) 431 fail(list_fail_last_entry,LIST_TEM_TYPEID_THIS); 432 return data(sentinel->prev); 433 } 434 last_entry() const435 T const & last_entry() const 436 { 437 if (n_entries == 0) 438 fail(list_fail_last_entry,LIST_TEM_TYPEID_THIS); 439 return data(sentinel->prev); 440 } 441 first_entry()442 T & first_entry() 443 { 444 if (n_entries == 0) 445 fail(list_fail_first_entry,LIST_TEM_TYPEID_THIS); 446 return data(sentinel->next); 447 } 448 first_entry() const449 T const & first_entry() const 450 { 451 if (n_entries == 0) 452 fail(list_fail_first_entry,LIST_TEM_TYPEID_THIS); 453 return data(sentinel->next); 454 } 455 size() const456 int size() const { return n_entries; } 457 cleanup()458 void cleanup() { calculated_indices = false; if (entry_pointers != 0) delete[] entry_pointers; entry_pointers = 0;} 459 operator ==(const List<T> & l1) const460 bool operator==(const List <T> &l1) const 461 { 462 if (n_entries != l1.n_entries) return false; 463 for (List_Member_Base<T> * e = sentinel->next, *e1 = l1.sentinel->next; e != sentinel; e = e->next, e1 = e1->next) 464 { 465 if (((List_Member<T> *)e)->data != ((List_Member<T> *)e1)->data) return false; 466 } 467 return true; 468 } 469 operator !=(const List<T> & l1) const470 bool operator!=(const List <T> &l1) const 471 { 472 if (n_entries != l1.n_entries) return true; 473 for (List_Member_Base<T> * e = sentinel->next, *e1 = l1.sentinel->next; e != sentinel; e = e->next, e1 = e1->next) 474 { 475 if (((List_Member<T> *)e)->data != ((List_Member<T> *)e1)->data) return true; 476 } 477 return false; 478 } 479 480 friend class List_Iterator_Forward<T>; 481 friend class ConstList_Iterator_Forward<T>; 482 friend class List_Iterator_Backward<T>; 483 friend class ConstList_Iterator_Backward<T>; 484 friend class List_Iterator_Loop<T>; 485 }; 486 487 // Use List_Iterator_{Forward,Backward} as follows: 488 // 489 // for(List_Iterator_Forward<T*> oi(&(List_of_T*)); // a _pointer_ 490 // // to the list. 491 // !oi.done(); 492 // oi.next() ) { 493 // do_something( oi() ) ; 494 // } 495 // 496 // First entry is the one past the sentinel, and next() and 497 // operator() fail if you try and iterate too far; check if it's 498 // done() before doing anything else, basically. 499 // 500 // As it's a doubly-linked list, we can go backwards and 501 // forwards. next() takes us to the entry that the type of iterator 502 // suggests; un_next() takes us in the other direction. un_next() is 503 // an ugly name, but next() and prev() are too suggestive of a 504 // particular direction. 505 506 template<class T> 507 class List_Iterator_Forward 508 { 509 private: 510 union 511 { 512 List_Member_Base<T> *m; 513 List_Member<T> *m_debug; // encourage the debugger to display the list members data 514 // hopefully casting from base to derived class would not 515 // cause the actual value of the ptr to change, so the debugger 516 // will display the information correctly, and this union 517 // won't cause any kind of performance hit 518 }; 519 List<T> *l; 520 521 public: List_Iterator_Forward()522 List_Iterator_Forward() {} List_Iterator_Forward(List<T> * list)523 List_Iterator_Forward(List<T> *list) { l = list; m = l->sentinel->next; } 524 next()525 void next() { 526 if (m != l->sentinel) { 527 m = m->next; 528 } else 529 fail(lit_fail_next,LIST_TEM_TYPEID_THIS); 530 } 531 un_next()532 void un_next() { 533 if (m != l->sentinel) { 534 m = m->prev; 535 } else 536 fail(lit_fail_next,LIST_TEM_TYPEID_THIS); 537 } 538 operator ()() const539 T & operator() () const { 540 if (m == l->sentinel) 541 fail(lit_fail_operator,LIST_TEM_TYPEID_THIS); 542 return l->data(m); 543 } 544 delete_current()545 void delete_current() { 546 if (m != l->sentinel) { 547 m = m->next; 548 l->delete_entry_by_pointer(m->prev); 549 } else 550 fail(lit_fail_delete_current,LIST_TEM_TYPEID_THIS); 551 } 552 change_current(T const & new_val) const553 void change_current(T const &new_val) const { 554 if (m != l->sentinel) { 555 // Delete the current member out of the list, put a new one in. 556 557 List_Member<T> * n = new List_Member<T>(new_val); 558 m->prev->next = n; 559 m->next->prev = n; 560 n->next = m->next; 561 n->prev = m->prev; 562 delete m; 563 *(List_Member_Base<T> **)&m =n; // or we're pointing at the thing we just deleted. 564 l->cleanup(); // because it's changed, but the List doesn't know that. 565 } else 566 fail(lit_fail_change_current,LIST_TEM_TYPEID_THIS); 567 } 568 done()569 bool done() { if (m == l->sentinel) return true; else return false; } restart()570 void restart() { m = l->sentinel->next; } 571 // Go to the end of the list. end()572 void end() { m = l->sentinel->prev; } 573 }; 574 575 #define LIF List_Iterator_Forward 576 577 template<class T> 578 class ConstList_Iterator_Forward 579 { 580 private: 581 union 582 { 583 List_Member_Base<T> *m; 584 List_Member<T> *m_debug; // encourage the debugger to display the list members data 585 }; 586 List<T> const *l; 587 588 public: ConstList_Iterator_Forward(List<T> const * list)589 ConstList_Iterator_Forward(List<T> const *list) { l = list; m = l->sentinel->next; } ConstList_Iterator_Forward()590 ConstList_Iterator_Forward(){} 591 next()592 void next() { 593 if (m == l->sentinel) { 594 fail(lit_fail_next,LIST_TEM_TYPEID_THIS); 595 } 596 m = m->next; 597 } 598 un_next()599 void un_next() { 600 if (m == l->sentinel) { 601 fail(lit_fail_next,LIST_TEM_TYPEID_THIS); 602 } 603 m = m->prev; 604 } 605 operator ()() const606 T const & operator() () const { 607 if (m == l->sentinel) 608 fail(lit_fail_operator,LIST_TEM_TYPEID_THIS); 609 return l->data(m); 610 } 611 612 #if 0 // shouldn't really be available on a const list 613 void change_current(T const & new_val) const { 614 if (m != l->sentinel) { 615 m->data = new_val; 616 } else 617 fail(lit_fail_change_current,LIST_TEM_TYPEID_THIS); 618 } 619 #endif 620 done() const621 bool done() const { if (m == l->sentinel) return true; else return false; } restart()622 void restart() { m = l->sentinel->next; } 623 // Go to the end of the list. end()624 void end() { m = l->sentinel->prev; } 625 }; 626 627 #define CLIF ConstList_Iterator_Forward 628 629 template<class T> 630 class List_Iterator_Backward 631 { 632 private: 633 union 634 { 635 List_Member_Base<T> *m; 636 List_Member<T> *m_debug; // encourage the debugger to display the list members data 637 }; 638 List<T> *l; 639 640 public: List_Iterator_Backward()641 List_Iterator_Backward() {} List_Iterator_Backward(List<T> * list)642 List_Iterator_Backward(List<T> *list) { l = list; m = l->sentinel->prev; } 643 next()644 void next() { 645 if (m != l->sentinel) { 646 m = m->prev; 647 } else 648 fail(lit_fail_next,LIST_TEM_TYPEID_THIS); 649 } 650 un_next()651 void un_next() { 652 if (m != l->sentinel) { 653 m = m->next; 654 } else 655 fail(lit_fail_next,LIST_TEM_TYPEID_THIS); 656 } 657 operator ()() const658 T & operator() () const { 659 if (m == l->sentinel) 660 fail(lit_fail_operator,LIST_TEM_TYPEID_THIS); 661 return l->data(m); 662 } 663 delete_current()664 void delete_current() { 665 if (m != l->sentinel) { 666 m = m->prev; 667 l->delete_entry_by_pointer(m->next); 668 } else 669 fail(lit_fail_delete_current,LIST_TEM_TYPEID_THIS); 670 } 671 change_current(T const & new_val)672 void change_current(T const & new_val) { 673 if (m != l->sentinel) { 674 // Delete the current member out of the list, put a new one in. 675 676 List_Member<T> * n = new List_Member<T>(new_val); 677 m->prev->next = n; 678 m->next->prev = n; 679 n->next = m->next; 680 n->prev = m->prev; 681 delete m; 682 m = n; // or we're pointing at the thing we just deleted. 683 l->cleanup(); // because it's changed, but the List doesn't know that. 684 } else 685 fail(lit_fail_change_current,LIST_TEM_TYPEID_THIS); 686 } 687 done()688 bool done() { if (m == l->sentinel) return true; else return false; } restart()689 void restart() { m = l->sentinel->prev; } 690 // Go to the end of the list. end()691 void end() { m = l->sentinel->prev; } 692 }; 693 694 #define LIB List_Iterator_Backward 695 696 template<class T> 697 class ConstList_Iterator_Backward 698 { 699 private: 700 union 701 { 702 List_Member_Base<T> *m; 703 List_Member<T> *m_debug; // encourage the debugger to display the list members data 704 }; 705 List<T> const *l; 706 707 public: ConstList_Iterator_Backward(List<T> const * list)708 ConstList_Iterator_Backward(List<T> const *list) { l = list; m = l->sentinel->prev; } ConstList_Iterator_Backward()709 ConstList_Iterator_Backward(){} 710 next()711 void next() { 712 if (m == l->sentinel) { 713 fail(lit_fail_next,LIST_TEM_TYPEID_THIS); 714 } 715 m = m->prev; 716 } 717 un_next()718 void un_next() { 719 if (m == l->sentinel) { 720 fail(lit_fail_next,LIST_TEM_TYPEID_THIS); 721 } 722 m = m->next; 723 } 724 operator ()() const725 T const & operator() () const { 726 if (m == l->sentinel) 727 fail(lit_fail_operator,LIST_TEM_TYPEID_THIS); 728 return l->data(m); 729 } 730 731 #if 0 // shouldn't really be available on a const list 732 void change_current(T const & new_val) const { 733 if (m != l->sentinel) { 734 m->data = new_val; 735 } else 736 fail(lit_fail_change_current,LIST_TEM_TYPEID_THIS); 737 } 738 #endif 739 done() const740 bool done() const { if (m == l->sentinel) return true; else return false; } restart()741 void restart() { m = l->sentinel->prev; } 742 // Go to the end of the list. end()743 void end() { m = l->sentinel->prev; } 744 }; 745 746 #define CLIB ConstList_Iterator_Backward 747 748 /* 749 A looping list iterator class : 750 next from the last member will go to the first 751 previous from the first member will go to the last 752 */ 753 754 template<class T> 755 class List_Iterator_Loop 756 { 757 private: 758 union 759 { 760 List_Member_Base<T> *m; 761 List_Member<T> *m_debug; // encourage the debugger to display the list members data 762 }; 763 List<T> *l; 764 765 public: List_Iterator_Loop(List<T> * list)766 List_Iterator_Loop(List<T> *list) { l = list; m = l->sentinel->next; } 767 next()768 void next() { 769 m=m->next; 770 if (m == l->sentinel) { 771 m = m->next; 772 } 773 } 774 previous()775 void previous() { 776 m=m->prev; 777 if (m == l->sentinel) { 778 m = m->prev; 779 } 780 } 781 operator ()()782 T const & operator() () { 783 if (m == l->sentinel) 784 { 785 m=m->next;//needed in case iterator was created before anything was added to the list 786 if (m == l->sentinel) 787 { 788 fail(lit_fail_operator,LIST_TEM_TYPEID_THIS); 789 } 790 } 791 return l->data(m); 792 } 793 delete_current()794 void delete_current() { 795 if (m == l->sentinel) 796 { 797 m=m->next;//needed in case iterator was created before anything was added to the list 798 if (m == l->sentinel) 799 { 800 fail(lit_fail_delete_current,LIST_TEM_TYPEID_THIS); 801 } 802 } 803 m = m->next; 804 l->delete_entry_by_pointer(m->prev); 805 } 806 807 change_current(T const & new_val)808 void change_current(T const & new_val) 809 { 810 if (m == l->sentinel) 811 m=m->next;//needed in case iterator was created before anything was added to the list 812 813 if (m != l->sentinel) 814 { 815 // Delete the current member out of the list, put a new one in. 816 List_Member<T> * n = new List_Member<T>(new_val); 817 m->prev->next = n; 818 m->next->prev = n; 819 n->next = m->next; 820 n->prev = m->prev; 821 delete m; 822 m = n; // or we're pointing at the thing we just deleted. 823 l->cleanup(); // because it's changed, but the List doesn't know that. 824 } 825 else 826 fail(lit_fail_change_current,LIST_TEM_TYPEID_THIS); 827 } 828 829 // Go to the start of the list. restart()830 void restart() { m = l->sentinel->next; } 831 832 // Go to the end of the list. end()833 void end() { m = l->sentinel->prev; } 834 835 // Is it on the last entry. at_last() const836 bool at_last() const { if (m == l->sentinel->prev) return true; else return false; } 837 838 // Get the next entry but done move the pointer. get_next()839 T const & get_next() { 840 if (m->next == l->sentinel) 841 { 842 if (m->next->next == l->sentinel) 843 { 844 fail(lit_fail_operator,LIST_TEM_TYPEID_THIS); 845 } 846 return l->data(m->next->next); 847 } 848 return l->data(m->next); 849 } 850 }; 851 852 #define LIL List_Iterator_Loop 853 854 #ifdef NDEBUG 855 #undef fail // allow other code to have local variables called or differently scoped 'fail' 856 #endif 857 858 #endif 859