00001 /* 00002 * List is a loop-linked list of objects. 00003 * When inserting/deleting objects list uses 00004 * system memory allocation deallocation 00005 * functions. 00006 * Advantages: 00007 * The size of list is not specified at the beginning and 00008 * can grow to fill up the available system memory. 00009 * Drawbacks: 00010 * System calls to new/delete functions are slow. 00011 * For more efficient allocation/deallocation use 00012 * Collection and Container classes which use their 00013 * own allocation/deallocation routines from a fixed i 00014 * size memory pool (see collection.*). 00015 */ 00016 00017 // CLASSES: 00018 template <class Element> 00019 struct Pointer 00020 { Element *element; 00021 Pointer *next,*prev; 00022 }; 00023 template <class Element> 00024 class List { 00025 int nelements;//number of elements in the list 00026 struct Pointer<Element> *first,*last,*current; 00027 public: 00028 List(); 00029 List(int n); 00030 ~List(); 00031 inline int number(){ return nelements; } 00032 inline void setFirst(){ first=last->next; } 00033 inline void setFirstLast(){ first=last; } 00034 inline void goFirst(){ current=first; } 00035 inline void goFirstNext(){ current=first->next; } 00036 inline void FirstNext(){ first=first->next; } 00037 inline void FirstPrev(){ first=first->prev; } 00038 inline bool isFirstLast(){ if(first==last) return true; else return false; } 00039 inline void goLastNext(){ current=last->next; } 00040 inline void goLast(){ current=last; } 00041 inline void goNext(){ current=current->next; } 00042 inline void goPrev(){ current=current->prev; } 00043 inline bool isFirst(){ return current==first?true:false; } 00044 inline bool isLast(){ if(current==last) return true; else return false; } 00045 inline void LastNext(){ last=last->next; } 00046 inline void LastPrev(){ last=last->prev; } 00047 inline void go(Pointer<Element> *p) { current=p; }//not safe 00048 inline Element *First(){ return first->element; } 00049 inline Element *Last(){ return last->element; } 00050 inline Element *Next(){ current=current->next; return current->element; } 00051 inline Element *getNext(){ return current->next->element; } 00052 inline Element *Prev(){ current=current->prev; return current->element; } 00053 inline Element *getPrev(){ return current->prev->element; } 00054 inline Element *Current(){ return current->element; } 00055 inline Pointer<Element> *getPointer() { return current; } 00056 inline Pointer<Element> *getFirstPointer() { return first; } 00057 inline Pointer<Element> *getLastPointer() { return last; } 00058 //- void init(); //DDD: the same as List(); 00059 int init(int n); //initialize with n elements 00060 int insert(Element *element); 00061 int insert(); 00062 int append(Element *element); 00063 int append(); 00064 int link(Pointer<Element> *p); 00065 void unlink(Pointer<Element> *p); 00066 int prepend(Element *element); 00067 bool locate(Element *element); 00068 bool locate(Pointer<Element> *pointer); 00069 void moveAfterFirst(); 00070 void swapAfterFirst(); 00071 void moveBehindFirst(); 00072 int erase(); 00073 bool erase(Element *element); 00074 void eraseall(); 00075 bool remove(); 00076 void cleanup(); 00077 void remove(Pointer<Element> *pointer); 00078 }; 00079 template <class Element> 00080 List<Element>::List() 00081 { nelements=0; 00082 current=first=last=NULL; 00083 } 00084 //-template <class Element> 00085 //-void List<Element>::init()///DDD 00086 //-{ nelements=0; 00087 //- current=first=last=NULL; 00088 //-} 00089 template <class Element> 00090 List<Element>::~List() { 00091 cleanup(); 00092 } 00093 template <class Element> 00094 void List<Element>::eraseall() { 00095 while (erase()); 00096 current=first=last=NULL; 00097 nelements=0; 00098 } 00099 template <class Element> 00100 void List<Element>::cleanup() { 00101 while (remove()); 00102 current=first=last=NULL; 00103 nelements=0; 00104 } 00105 template <class Element> 00106 int List<Element>::init(int n) 00107 { //initializes list with n elements 00108 for(int i=0;i<n;i++) if(append()==0) return 0; 00109 nelements=n; 00110 return n; 00111 } 00112 template <class Element> 00113 int List<Element>::prepend(Element *element) 00114 { //appends before last 00115 if(last==NULL) { 00116 last=new Pointer<Element>; 00117 last->next=last->prev=last; 00118 last->element=element; 00119 current=first=last; 00120 nelements=1; 00121 return 1; 00122 } 00123 Pointer<Element> *tmp=last->prev; 00124 last->prev=new Pointer<Element>; 00125 if(last->prev==NULL) return 0;//failed to append: the memory is full 00126 tmp->next=last->prev; 00127 last->prev->next=last; 00128 last=last->prev; 00129 last->prev=tmp; 00130 last->element=element; 00131 nelements++; 00132 first=last->next; 00133 return 1; 00134 } 00135 template <class Element> 00136 int List<Element>::append(Element *element) 00137 { //appends after last 00138 if(last==NULL) { 00139 last=new Pointer<Element>; 00140 last->next=last->prev=last; 00141 last->element=element; 00142 current=first=last; 00143 nelements=1; 00144 return 1; 00145 } 00146 Pointer<Element> *lastnext=last->next; 00147 last->next=new Pointer<Element>; 00148 if(last->next==NULL) return 0;//failed to append: the memory is full 00149 lastnext->prev=last->next; 00150 last->next->prev=last; 00151 last=last->next; 00152 last->next=lastnext; 00153 last->element=element; 00154 nelements++; 00155 first=lastnext; 00156 return 1; 00157 } 00158 template <class Element> 00159 int List<Element>::append() 00160 { //appends before last 00161 Element *element=new Element; 00162 return append(element); 00163 } 00164 template <class Element> 00165 int List<Element>::link(Pointer<Element> *pointer) 00166 { //appends after last 00167 if(pointer==NULL) return 0; 00168 if(last==NULL) { 00169 last=pointer; 00170 last->next=last->prev=last; 00171 current=first=last; 00172 nelements=1; 00173 return 1; 00174 } 00175 Pointer<Element> *lastnext=last->next; 00176 last->next=pointer; 00177 lastnext->prev=last->next; 00178 last->next->prev=last; 00179 last=last->next; 00180 last->next=lastnext; 00181 nelements++; 00182 //- first=lastnext; 00183 return 1; 00184 } 00185 template <class Element> 00186 int List<Element>::insert(Element *element) 00187 { //inserts after current 00188 if(last==NULL) { 00189 last=new Pointer<Element>; 00190 last->next=last->prev=last; 00191 last->element=element; 00192 current=first=last; 00193 nelements=1; 00194 return 1; 00195 } 00196 Pointer<Element> *tmp=current->next; 00197 current->next=new Pointer<Element>; 00198 if(current->next==NULL) return 0;//failed to insert: the memory is full 00199 tmp->prev=current->next; 00200 current->next->prev=current; 00201 current=current->next; 00202 current->next=tmp; 00203 current->element=element; 00204 last=current; 00205 nelements++; 00206 return 1; 00207 } 00208 template <class Element> 00209 int List<Element>::insert() 00210 { //inserts after current 00211 Element *element=new Element; 00212 return insert(element); 00213 } 00214 template <class Element> 00215 bool List<Element>::remove() { // deletes current, but does not delete the element 00216 if(current==NULL) return false;//failed to remove: the list is empty 00217 if(current->next==current) { 00218 first=last=NULL; 00219 delete current; 00220 current=NULL; 00221 nelements=0; 00222 return true; 00223 } 00224 current->next->prev=current->prev; 00225 current->prev->next=current->next; 00226 if(current==last)last=last->prev; 00227 if(current==first)first=first->next; 00228 Pointer<Element> *old=current; 00229 current=current->prev; 00230 delete old; 00231 nelements--; 00232 return true; 00233 } 00234 template <class Element> 00235 int List<Element>::erase() { // deletes current 00236 if(current==NULL) return 0;//failed to erase: the list is empty 00237 if(current->next==current) 00238 { delete current->element; 00239 first=last=NULL; 00240 delete current; 00241 current=NULL; 00242 nelements=0; 00243 return 1; 00244 } 00245 current->next->prev=current->prev; 00246 current->prev->next=current->next; 00247 if(last==current)last=last->prev; 00248 Pointer<Element> *old=current; 00249 current=current->prev; 00250 delete old->element; 00251 delete old; 00252 nelements--; 00253 first=last->next; 00254 return 1; 00255 } 00256 template <class Element> 00257 void List<Element>::unlink(Pointer<Element> *pointer) { // deletes current 00258 if(last==NULL||pointer==NULL) { 00259 //- cerr<<"Failed to remove from the list: the list is empty\n"; 00260 return; 00261 } 00262 //- if(locate(pointer)) { 00263 //- remove();///DDD: slow but safe 00264 if(pointer==current) current=current->next; 00265 if(pointer==last)last=last->prev; 00266 if(pointer==first)first=first->next; 00267 pointer->next->prev=pointer->prev; 00268 pointer->prev->next=pointer->next; 00269 if(--nelements==0){ first=NULL; last=NULL;} 00270 } 00271 template <class Element> 00272 void List<Element>::remove(Pointer<Element> *pointer) { // deletes current 00273 if(current==NULL||pointer==NULL) { 00274 //- cerr<<"Failed to remove from the list: the list is empty\n"; 00275 return; 00276 } 00277 if(locate(pointer)) remove(); 00278 else { 00279 cerr<<"Can't locate pointer in the list\n"; 00280 exit(1); 00281 } 00282 00283 //+ current=pointer; //fast but unsafe 00284 //+ remove(); 00285 } 00286 template <class Element> 00287 bool List<Element>::erase(Element *element) { 00288 if(!locate(element))return false; 00289 erase(); 00290 return true; 00291 } 00292 template <class Element> 00293 bool List<Element>::locate(Element *element) { 00294 if(current==NULL) return false; 00295 current=first; 00296 do { 00297 if(current->element==element) return true; 00298 current=current->next; 00299 } while(current!=first); 00300 return false; 00301 } 00302 template <class Element> 00303 bool List<Element>::locate(Pointer<Element> *pointer) { 00304 if(current==NULL) return false; 00305 current=first; 00306 do { 00307 if(current==pointer) return true; 00308 current=current->next; 00309 } while(current!=first); 00310 return false; 00311 } 00312 template <class Element> 00313 void List<Element>::swapAfterFirst() { 00314 Element *tmp=current->element; 00315 current->element=first->next->element; 00316 first->next->element=tmp; 00317 current=first->next; 00318 } 00319 template <class Element> 00320 void List<Element>::moveAfterFirst() { 00321 Pointer<Element> *firstnext=first->next; 00322 if(current==firstnext)return; 00323 first->next=current; 00324 firstnext->prev=current; 00325 current->next->prev=current->prev; 00326 current->prev->next=current->next; 00327 current->prev=first; 00328 current->next=firstnext; 00329 } 00330 template <class Element> 00331 void List<Element>::moveBehindFirst() { 00332 Pointer<Element> *firstprev=first->prev; 00333 if(current==firstprev)return; 00334 first->prev=current; 00335 firstprev->next=current; 00336 current->next->prev=current->prev; 00337 current->prev->next=current->next; 00338 current->next=first; 00339 current->prev=firstprev; 00340 } 00341 //-DEPRECATED: 00342 //-class Molecule; 00343 //-namespace GridList {// Keeps local node lists to avoid N^2 pair interaction loop 00344 //- extern REAL cellsize; 00345 //- extern int ncells[DIM+1];// number of cells in each space direction 00346 //- extern List<Molecule> *nodes;//nodes[ncells[0]*ncells[1]*...*ncells[DIM-1]] 00347 //- extern int *dimensions(); 00348 //- extern int index(int gridcell[]); 00349 //- extern void index(int icell, int gridcell[]); 00350 //- extern void init(REAL ymin[], REAL ymax[], REAL radius); 00351 //- extern void put(Molecule *node); 00352 //- extern List<Molecule> *get(int index[]); 00353 //-};
1.5.7.1