home *** CD-ROM | disk | FTP | other *** search
/ Geek 6 / Geek-006.iso / linux / video / xmovie-1.5.3.tar.gz / xmovie-1.5.3.tar / xmovie-1.5.3 / guicast / linklist.h < prev    next >
C/C++ Source or Header  |  2000-11-29  |  6KB  |  285 lines
  1. #ifndef LINKLIST_H
  2. #define LINKLIST_H
  3.  
  4. template<class TYPE>
  5. class ListItem;
  6.  
  7. template<class TYPE>
  8. class List                        // inherited by lists
  9. {
  10. public:
  11.     List();
  12.     virtual ~List();
  13.  
  14.     void remove(TYPE *item);   // delete the item and the pointers to it
  15.     void remove_pointer(ListItem<TYPE> *item);  // remove the pointers to the item only
  16.  
  17. // these must be used to add an item to a list
  18.     TYPE *append();  // create new node and return pointer of it
  19.     TYPE *append(TYPE *new_item);   // append the new pointer to the list
  20.     TYPE *insert_before(TYPE *item);  // create new node and return pointer of it
  21.     TYPE *insert_before(TYPE *item, TYPE *new_item);  // create new node and return pointer of it
  22.     TYPE *insert_after(TYPE *item);
  23.     TYPE *insert_after(TYPE *item, TYPE *new_item);
  24.     TYPE *get_item_number(int number);
  25.     int get_item_number(TYPE *item);
  26.     void swap(TYPE *item1, TYPE *item2);
  27.  
  28. // query the list
  29.     int total();     // total number of nodes
  30.  
  31. // convenience macros
  32. #define PREVIOUS current->previous
  33. #define NEXT current->next
  34.  
  35. // references to list
  36.     TYPE *first;
  37.     TYPE *last;
  38. };
  39.  
  40. template<class TYPE>
  41. class ListItem                        // inherited by list items
  42. {
  43. public:
  44.     ListItem();
  45.     virtual ~ListItem();
  46.  
  47.     int get_item_number();
  48.     TYPE *previous;
  49.     TYPE *next;
  50.     List<TYPE> *owner;             // list that owns this item for deletion
  51. };
  52.  
  53. template<class TYPE>
  54. List<TYPE>::List()
  55. {
  56.     last = first = 0;
  57. }
  58.  
  59. template<class TYPE>
  60. List<TYPE>::~List()     // delete nodes
  61. {
  62.     while(last)
  63.     {
  64.         delete last;
  65.     }
  66. }
  67.  
  68. template<class TYPE>
  69. int List<TYPE>::total()     // total number of nodes
  70. {
  71.     int total = 0;
  72.     TYPE* current;
  73.     
  74.     for(current = first; current; current = NEXT)
  75.     {
  76.         total++;
  77.     }
  78.     return total;
  79. }
  80.  
  81. template<class TYPE>
  82. TYPE* List<TYPE>::get_item_number(int number)
  83. {
  84.     TYPE* current;
  85.     int i;
  86.     for(i = 0, current = first; current && i < number; current = NEXT, i++)
  87.     {
  88.         ;
  89.     }
  90.     return current;
  91. }
  92.  
  93. template<class TYPE>
  94. int List<TYPE>::get_item_number(TYPE *item)
  95. {
  96.     TYPE* current;
  97.     int i;
  98.     for(i = 0, current = first; current && current != item; current = NEXT, i++)
  99.     {
  100.         ;
  101.     }
  102.     return i;
  103. }
  104.  
  105.  
  106. template<class TYPE>
  107. TYPE* List<TYPE>::append()
  108. {
  109.     TYPE* current_item;
  110.  
  111.     if(!last)        // add first node
  112.     {
  113.         current_item = last = first = new TYPE;
  114.         current_item->previous = current_item->next = 0;
  115.         current_item->owner = this;
  116.         return current_item;
  117.     }
  118.     else
  119.     {                // append node
  120.         current_item = last->next = new TYPE;
  121.         current_item->previous = last;
  122.         current_item->next = 0;
  123.         last = current_item;
  124.         current_item->owner = this;
  125.         return current_item;
  126.     }
  127. }
  128.  
  129. template<class TYPE>
  130. TYPE* List<TYPE>::append(TYPE *new_item)
  131. {
  132.     TYPE* current_item;
  133.     
  134.     if(!last)        // add first node
  135.     {
  136.         current_item = last = first = new_item;
  137.         current_item->previous = current_item->next = 0;
  138.         current_item->owner = this;
  139.         return current_item;
  140.     }
  141.     else
  142.     {                // append node
  143.         current_item = last->next = new_item;
  144.         current_item->previous = last;
  145.         current_item->next = 0;
  146.         last = current_item;
  147.         current_item->owner = this;
  148.         return current_item;
  149.     }
  150. }
  151.  
  152. template<class TYPE>
  153. TYPE* List<TYPE>::insert_before(TYPE *item)
  154. {
  155.     TYPE* new_item = new TYPE;
  156.     return insert_before(item, new_item);
  157. }
  158.  
  159. template<class TYPE>
  160. TYPE* List<TYPE>::insert_before(TYPE *item, TYPE *new_item)
  161. {
  162.     if(!item) return append(new_item);      // if item is null, append
  163.  
  164.     TYPE* current_item = new_item;
  165.  
  166.     if(item == first) first = current_item;   // set *first
  167.  
  168.     current_item->previous = item->previous;       // set this node's pointers
  169.     current_item->next = item;
  170.     
  171.     if(current_item->previous) current_item->previous->next = current_item;         // set previous node's pointers
  172.  
  173.     if(current_item->next) current_item->next->previous = current_item;        // set next node's pointers
  174.     
  175.     current_item->owner = this;
  176.     return current_item;
  177. }
  178.  
  179. template<class TYPE>
  180. TYPE* List<TYPE>::insert_after(TYPE *item)
  181. {
  182.     TYPE *new_item = new TYPE;
  183.     return insert_after(item, new_item);
  184. }
  185.  
  186. template<class TYPE>
  187. TYPE* List<TYPE>::insert_after(TYPE *item, TYPE *new_item)
  188. {
  189.     if(!item) return append(new_item);      // if item is null, append
  190.  
  191.     TYPE* current_item = new_item;
  192.  
  193.     if(item == last) last = current_item;   // set *last
  194.  
  195.     current_item->previous = item;       // set this node's pointers
  196.     current_item->next = item->next;
  197.     
  198.     if(current_item->previous) current_item->previous->next = current_item;         // set previous node's pointers
  199.  
  200.     if(current_item->next) current_item->next->previous = current_item;        // set next node's pointers
  201.     
  202.     current_item->owner = this;
  203.     return current_item;
  204. }
  205.  
  206. template<class TYPE>
  207. void List<TYPE>::swap(TYPE *item1, TYPE *item2)
  208. {
  209.     TYPE *new_item0, *new_item1, *new_item2, *new_item3;
  210.  
  211. // old == item0 item1 item2 item3
  212. // new == item0 item2 item1 item3
  213.  
  214.     new_item0 = item1->previous;
  215.     new_item1 = item2;
  216.     new_item2 = item1;
  217.     new_item3 = item2->next;
  218.  
  219.     if(new_item0) 
  220.         new_item0->next = new_item1;
  221.     else
  222.         first = new_item1;
  223.  
  224.     if(new_item1) new_item1->next = new_item2;
  225.     if(new_item2) new_item2->next = new_item3;
  226.     if(new_item3)
  227.         new_item3->previous = new_item2;
  228.     else
  229.         last = new_item2;
  230.  
  231.     if(new_item2) new_item2->previous = new_item1;
  232.     if(new_item1) new_item1->previous = new_item0;
  233. }
  234.  
  235. template<class TYPE>
  236. void List<TYPE>::remove(TYPE *item)
  237. {
  238.     if(!item) return;
  239.     delete item;                        // item calls back to remove pointers
  240. }
  241.  
  242. template<class TYPE>
  243. void List<TYPE>::remove_pointer(ListItem<TYPE> *item)
  244. {
  245. //printf("List<TYPE>::remove_pointer %x %x %x\n", item, last, first);
  246.     if(!item) return;
  247.  
  248.     if(item == last && item == first)
  249.     {
  250. // last item
  251.         last = first = 0;
  252.         return;
  253.     }
  254.  
  255.     if(item == last) last = item->previous;      // set *last and *first
  256.     else
  257.     if(item == first) first = item->next;
  258.  
  259.     if(item->previous) item->previous->next = item->next;         // set previous node's pointers
  260.  
  261.     if(item->next) item->next->previous = item->previous;       // set next node's pointers
  262. }
  263.  
  264. template<class TYPE>
  265. ListItem<TYPE>::ListItem()
  266. {
  267. // don't delete the pointer to this if it's not part of a list
  268.     owner = 0;
  269. }
  270.  
  271. template<class TYPE>
  272. ListItem<TYPE>::~ListItem()
  273. {
  274. // don't delete the pointer to this if it's not part of a list
  275.     if(owner) owner->remove_pointer(this);
  276. }
  277.  
  278. template<class TYPE>
  279. int ListItem<TYPE>::get_item_number()
  280. {
  281.     return owner->get_item_number((TYPE*)this);
  282. }
  283.  
  284. #endif
  285.