home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 February / Chip_2001-02_cd1.bin / bonus / demos / CS / exp / SOURCES / GLENGINE / List.h < prev    next >
C/C++ Source or Header  |  2000-07-29  |  4KB  |  207 lines
  1. /*
  2.  * Linked list class implementation
  3.  */
  4.  
  5. #ifndef __LINKED_LIST__
  6. #define __LINKED_LIST__
  7.  
  8. extern "C++" {
  9.  
  10. template <class __tp>
  11. struct linked_list_node {
  12.   linked_list_node<__tp>* next;
  13.   linked_list_node<__tp>* prev;
  14.   __tp data;
  15. };
  16.  
  17. template <class __type> class List
  18. {
  19.   typedef linked_list_node<__type> node;
  20.   typedef linked_list_node<__type>* nodeptr;
  21.   typedef List<__type> self;
  22.  
  23.   node sentinel;    
  24.   nodeptr current;  // iterator position
  25.   int n;            // number of nodes in the list (except for sentinel)
  26.  
  27. public:
  28.   List () : current(0), n(0) {
  29.     sentinel.next = sentinel.prev = &sentinel;
  30.   }
  31.  
  32.   int size () {
  33.     return n;
  34.   }
  35.   bool empty () {
  36.     return n==0;
  37.   }
  38.   bool begin () {
  39.     return current->prev==&sentinel;
  40.   }
  41.   bool end () {
  42.     return current->next==&sentinel;
  43.   }
  44.   
  45.   __type& operator* () {
  46.     return current->data;
  47.   }  
  48.  
  49.   List& operator++ () {
  50.     nodeptr __temp = current->next;
  51.     if(__temp!=&sentinel)
  52.       current = __temp;
  53.     return *this;
  54.   }
  55.   List& operator-- () {
  56.     nodeptr __temp = current->prev;
  57.     if(__temp!=&sentinel)
  58.       current = __temp;
  59.     return *this;
  60.   }
  61.  
  62.   List& rewind () {
  63.     current = sentinel.next;
  64.     return *this;
  65.   }
  66.   List& to_back () {
  67.     current = sentinel.prev;
  68.     return *this;
  69.   }
  70.   List& push_front (const __type& item) {
  71.     nodeptr __temp = new node;
  72.     __temp->data = item;
  73.     __temp->prev = &sentinel;
  74.     __temp->next = sentinel.next;
  75.     sentinel.next->prev = __temp;
  76.     sentinel.next = __temp;
  77.     n++;
  78.     return *this;
  79.   }
  80.   List& push_back (const __type& item) {
  81.     nodeptr __temp = new node;
  82.     __temp->data = item;
  83.     __temp->prev = sentinel.prev;
  84.     __temp->next = &sentinel;
  85.     sentinel.prev->next = __temp;
  86.     sentinel.prev = __temp;
  87.     n++;
  88.     return *this;
  89.   }
  90.   List& insert (const __type& item) {
  91.     nodeptr __temp = new node;
  92.     __temp->data = item;
  93.     __temp->prev = current->prev;
  94.     __temp->next = current;
  95.     current->prev->next = __temp;
  96.     current->prev = __temp;
  97.     current = __temp;
  98.     n++;
  99.     return *this;
  100.   }
  101.   List& pop_front () {
  102.     if(!empty()) {
  103.       nodeptr __head = sentinel.next;
  104.       sentinel.next = __head->next;
  105.       __head->next->prev = &sentinel;
  106.       if(current==__head)
  107.         current==__head->next;
  108.       delete __head;
  109.       n--;
  110.     }
  111.     return *this;
  112.   }
  113.   List& pop_back () {
  114.     if(!empty()) {
  115.       nodeptr __back = sentinel.prev;
  116.       sentinel.prev = __back->prev;
  117.       __back->prev->next = &sentinel;
  118.       if(current==__back)
  119.         current==__back->prev;
  120.       delete __back;
  121.       n--;
  122.     }
  123.     return *this;
  124.   }
  125.   List& remove () {
  126.     if(!empty()) {
  127.       current->prev->next = current->next;
  128.       current->next->prev = current->prev;
  129.       delete current;
  130.       current = current->next;
  131.       n--;
  132.     }
  133.     return *this;
  134.   }
  135.  
  136.   List& erase () {
  137.     nodeptr __temp = sentinel.next;
  138.     nodeptr __temp2;
  139.     while(__temp!=&sentinel) {
  140.       __temp2 = __temp->next;
  141.       delete __temp;
  142.       __temp = __temp2;
  143.     }
  144.     n = 0;
  145.     sentinel.prev = sentinel.next = &sentinel;
  146.     current = 0;
  147.     return *this;
  148.   }
  149.  
  150.   __type* array() {
  151.     __type* newarray = new __type[size()];
  152.     __type* p = newarray;
  153.     rewind();
  154.     for(int i=size(); i; i--) {
  155.       *p = current->data;
  156.       p++;
  157.       current = current->next;
  158.     }
  159.     return newarray;
  160.   }
  161.   
  162.   List& operator += (const List& L) 
  163.   {
  164.     nodeptr __src = L.sentinel.next;
  165.     nodeptr __temp = sentinel.prev;
  166.     nodeptr __temp2;
  167.     for(int i=L.n; i; i--) {
  168.       __temp->next = new node;
  169.       __temp2 = __temp->next;
  170.       __temp2->data = __src->data;
  171.       __temp2->prev = __temp;
  172.       __temp = __temp2;
  173.       __src = __src->next;
  174.     }
  175.     __temp->next = &sentinel;
  176.     sentinel.prev = __temp;
  177.     n += L.n;
  178.   }
  179.  
  180.   List(const List& L) : current(0), n(0)
  181.   {
  182.     nodeptr __src = L.sentinel.next;
  183.     nodeptr __temp = &sentinel;
  184.     nodeptr __temp2;
  185.     for(int i=L.n; i; i--) {
  186.       __temp->next = new node;
  187.       __temp2 = __temp->next;
  188.       __temp2->data = __src->data;
  189.       __temp2->prev = __temp;
  190.       __temp = __temp2;
  191.       __src = __src->next;
  192.     }
  193.     __temp->next = &sentinel;
  194.     sentinel.prev = __temp;
  195.     n = L.n;
  196.   }
  197.  
  198.   ~List() {
  199.     erase();
  200.   }
  201.   
  202. };
  203.  
  204. } // extern "C++"
  205.  
  206. #endif
  207.