Main Page | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members

linklist.h

Go to the documentation of this file.
00001 #ifndef LINKLIST_H
00002 #define LINKLIST_H
00003 
00004 template<class TYPE>
00005 class ListItem;
00006 
00007 template<class TYPE>
00008 class List                        // inherited by lists
00009 {
00010 public:
00011         List();
00012         virtual ~List();
00013 
00014         void remove(TYPE *item);   // delete the item and the pointers to it
00015         void remove_pointer(ListItem<TYPE> *item);  // remove the pointers to the item only
00016 
00017 // these must be used to add an item to a list
00018         TYPE *append();  // create new node and return pointer of it
00019         TYPE *append(TYPE *new_item);   // append the new pointer to the list
00020         TYPE *insert_before(TYPE *item);  // create new node and return pointer of it
00021         TYPE *insert_before(TYPE *item, TYPE *new_item);  // create new node and return pointer of it
00022         TYPE *insert_after(TYPE *item);
00023         TYPE *insert_after(TYPE *item, TYPE *new_item);
00024         TYPE *get_item_number(int number);
00025         int get_item_number(TYPE *item);
00026         void swap(TYPE *item1, TYPE *item2);
00027 
00028 // query the list
00029         int total();     // total number of nodes
00030         int number_of(TYPE *item);
00031 
00032 // convenience macros
00033 #define PREVIOUS current->previous
00034 #define NEXT current->next
00035 
00036 // references to list
00037         TYPE *first;
00038         TYPE *last;
00039 };
00040 
00041 template<class TYPE>
00042 class ListItem                        // inherited by list items
00043 {
00044 public:
00045         ListItem();
00046         virtual ~ListItem();
00047 
00048         int get_item_number();
00049         TYPE *previous;
00050         TYPE *next;
00051         List<TYPE> *owner;             // list that owns this item for deletion
00052 };
00053 
00054 template<class TYPE>
00055 List<TYPE>::List()
00056 {
00057         last = first = 0;
00058 }
00059 
00060 template<class TYPE>
00061 List<TYPE>::~List()     // delete nodes
00062 {
00063         while(last)
00064         {
00065                 delete last;
00066         }
00067 }
00068 
00069 template<class TYPE>
00070 int List<TYPE>::total()     // total number of nodes
00071 {
00072         int total = 0;
00073         TYPE* current;
00074         
00075         for(current = first; current; current = NEXT)
00076         {
00077                 total++;
00078         }
00079         return total;
00080 }
00081 
00082 template<class TYPE>
00083 int List<TYPE>::number_of(TYPE *item)
00084 {
00085         TYPE* current;
00086         int total = 0;
00087         for(current = first; current; current = NEXT)
00088         {
00089                 if(current == item) return total;
00090                 total++;
00091         }
00092         return 0;
00093 }
00094 
00095 template<class TYPE>
00096 TYPE* List<TYPE>::get_item_number(int number)
00097 {
00098         TYPE* current;
00099         int i;
00100         for(i = 0, current = first; current && i < number; current = NEXT, i++)
00101         {
00102                 ;
00103         }
00104         return current;
00105 }
00106 
00107 template<class TYPE>
00108 int List<TYPE>::get_item_number(TYPE *item)
00109 {
00110         TYPE* current;
00111         int i;
00112         for(i = 0, current = first; current && current != item; current = NEXT, i++)
00113         {
00114                 ;
00115         }
00116         return i;
00117 }
00118 
00119 
00120 template<class TYPE>
00121 TYPE* List<TYPE>::append()
00122 {
00123         TYPE* current_item;
00124 
00125         if(!last)        // add first node
00126         {
00127                 current_item = last = first = new TYPE;
00128                 current_item->previous = current_item->next = 0;
00129                 current_item->owner = this;
00130                 return current_item;
00131         }
00132         else
00133         {                // append node
00134                 current_item = last->next = new TYPE;
00135                 current_item->previous = last;
00136                 current_item->next = 0;
00137                 last = current_item;
00138                 current_item->owner = this;
00139                 return current_item;
00140         }
00141 }
00142 
00143 template<class TYPE>
00144 TYPE* List<TYPE>::append(TYPE *new_item)
00145 {
00146         TYPE* current_item;
00147         
00148         if(!last)        // add first node
00149         {
00150                 current_item = last = first = new_item;
00151                 current_item->previous = current_item->next = 0;
00152                 current_item->owner = this;
00153                 return current_item;
00154         }
00155         else
00156         {                // append node
00157                 current_item = last->next = new_item;
00158                 current_item->previous = last;
00159                 current_item->next = 0;
00160                 last = current_item;
00161                 current_item->owner = this;
00162                 return current_item;
00163         }
00164 }
00165 
00166 template<class TYPE>
00167 TYPE* List<TYPE>::insert_before(TYPE *item)
00168 {
00169         TYPE* new_item = new TYPE;
00170         return insert_before(item, new_item);
00171 }
00172 
00173 template<class TYPE>
00174 TYPE* List<TYPE>::insert_before(TYPE *item, TYPE *new_item)
00175 {
00176         if(!item) return append(new_item);      // if item is null, append
00177 
00178         TYPE* current_item = new_item;
00179 
00180         if(item == first) first = current_item;   // set *first
00181 
00182         current_item->previous = item->previous;       // set this node's pointers
00183         current_item->next = item;
00184         
00185         if(current_item->previous) current_item->previous->next = current_item;         // set previous node's pointers
00186 
00187         if(current_item->next) current_item->next->previous = current_item;        // set next node's pointers
00188         
00189         current_item->owner = this;
00190         return current_item;
00191 }
00192 
00193 template<class TYPE>
00194 TYPE* List<TYPE>::insert_after(TYPE *item)
00195 {
00196         TYPE *new_item = new TYPE;
00197         return insert_after(item, new_item);
00198 }
00199 
00200 template<class TYPE>
00201 TYPE* List<TYPE>::insert_after(TYPE *item, TYPE *new_item)
00202 {
00203         if(!item) return append(new_item);      // if item is null, append
00204 
00205         TYPE* current_item = new_item;
00206 
00207         if(item == last) last = current_item;   // set *last
00208 
00209         current_item->previous = item;       // set this node's pointers
00210         current_item->next = item->next;
00211         
00212         if(current_item->previous) current_item->previous->next = current_item;         // set previous node's pointers
00213 
00214         if(current_item->next) current_item->next->previous = current_item;        // set next node's pointers
00215         
00216         current_item->owner = this;
00217         return current_item;
00218 }
00219 
00220 template<class TYPE>
00221 void List<TYPE>::swap(TYPE *item1, TYPE *item2)
00222 {
00223         TYPE **temp_array;
00224         int total = this->total();
00225         temp_array = new TYPE*[total];
00226 // Copy entire list to a temp.  This rewrites the pointers in the original items.
00227         for(int i = 0; i < total; i++)
00228         {
00229                 temp_array[i] = get_item_number(i);
00230         }
00231         while(last) remove_pointer(last);
00232         for(int i = 0; i < total; i++)
00233         {
00234                 if(temp_array[i] == item1) append(item2);
00235                 else
00236                 if(temp_array[i] == item2) append(item1);
00237                 else
00238                         append(temp_array[i]);
00239         }
00240         delete [] temp_array;
00241 
00242 #if 0
00243         TYPE *new_item0, *new_item1, *new_item2, *new_item3;
00244 
00245 // old == item0 item1 item2 item3
00246 // new == item0 item2 item1 item3
00247 
00248         new_item0 = item1->previous;
00249         new_item1 = item2;
00250         new_item2 = item1;
00251         new_item3 = item2->next;
00252 
00253         if(new_item0) 
00254                 new_item0->next = new_item1;
00255         else
00256                 first = new_item1;
00257 
00258         if(new_item1) new_item1->next = new_item2;
00259         if(new_item2) new_item2->next = new_item3;
00260         if(new_item3)
00261                 new_item3->previous = new_item2;
00262         else
00263                 last = new_item2;
00264 
00265         if(new_item2) new_item2->previous = new_item1;
00266         if(new_item1) new_item1->previous = new_item0;
00267 #endif
00268 }
00269 
00270 template<class TYPE>
00271 void List<TYPE>::remove(TYPE *item)
00272 {
00273         if(!item) return;
00274         delete item;                        // item calls back to remove pointers
00275 }
00276 
00277 template<class TYPE>
00278 void List<TYPE>::remove_pointer(ListItem<TYPE> *item)
00279 {
00280 //printf("List<TYPE>::remove_pointer %x %x %x\n", item, last, first);
00281         if(!item) return;
00282 
00283         if(item == last && item == first)
00284         {
00285 // last item
00286                 last = first = 0;
00287                 return;
00288         }
00289 
00290         if(item == last) last = item->previous;      // set *last and *first
00291         else
00292         if(item == first) first = item->next;
00293 
00294         if(item->previous) item->previous->next = item->next;         // set previous node's pointers
00295 
00296         if(item->next) item->next->previous = item->previous;       // set next node's pointers
00297 }
00298 
00299 template<class TYPE>
00300 ListItem<TYPE>::ListItem()
00301 {
00302         next = previous = 0;
00303 // don't delete the pointer to this if it's not part of a list
00304         owner = 0;
00305 }
00306 
00307 template<class TYPE>
00308 ListItem<TYPE>::~ListItem()
00309 {
00310 // don't delete the pointer to this if it's not part of a list
00311         if(owner) owner->remove_pointer(this);
00312 }
00313 
00314 template<class TYPE>
00315 int ListItem<TYPE>::get_item_number()
00316 {
00317         return owner->get_item_number((TYPE*)this);
00318 }
00319 
00320 #endif

Generated on Sun Jan 8 13:26:35 2006 for Guicast-svn by  doxygen 1.4.4