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