guicast/linklist.h

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