00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 template <class Element>
00020 struct Item {
00021 Element element;
00022 Item *next,*prev;
00023 };
00024 template <class Element>
00025 class Collection {
00026 int mitems,nitems;
00027 bool locked;
00028 struct Item<Element>
00029 *items,
00030 *dead,
00031 *first,*last,*current,
00032 *current1[maxcounters];
00033 public:
00034 Collection();
00035 ~Collection();
00036 inline int maxCounters(){return maxcounters;}
00037 inline int number(){return nitems;}
00038 inline int maxnumber(){return mitems;}
00039 inline void setFirst(){ first=last->next; }
00040 inline void setFirstLast(){ first=last; }
00041 inline void goFirst(){
00042 current=first;
00043 #ifdef OMP
00044 for(int i=0;i<maxcounters;i++)current1[i]=first;
00045 #endif
00046 }
00047 inline void goFirst(int i){ current1[i]=first; }
00048 inline void goFirstNext(){ current=first->next; }
00049 inline void goFirstNext(int i){ current1[i]=first->next; }
00050 inline void FirstNext(){ first=first->next; }
00051 inline void FirstPrev(){ first=first->prev; }
00052 inline bool isFirstLast(){ if(first==last) return true; else return false; }
00053 inline void goLastNext(){ current=last->next; }
00054 inline void goLastNext(int i){ current1[i]=last->next; }
00055 inline void goLast(){ current=last; }
00056 inline void goLast(int i){ current1[i]=last; }
00057 inline void goNext(){ current=current->next; }
00058 inline void goNext(int i){ current1[i]=current1[i]->next; }
00059 inline void goPrev(){ current=current->prev; }
00060 inline void goPrev(int i){ current1[i]=current1[i]->prev; }
00061 inline bool isFirst(){ return current==first?true:false; }
00062 inline bool isFirst(int i){ return current1[i]==first?true:false; }
00063 inline bool isLast(){ if(current==last) return true; else return false; }
00064 inline bool isLast(int i){ if(current1[i]==last) return true; else return false; }
00065 inline void LastNext(){ last=last->next; }
00066 inline void LastPrev(){ last=last->prev; }
00067 inline void go(Item<Element> *p) { current=p; }
00068 inline Element *First(){ return &first->element; }
00069 inline Element *Last(){ return &last->element; }
00070 inline Element *Next(){ current=current->next; return ¤t->element; }
00071 inline Element *Next(int i){ current1[i]=current1[i]->next; return ¤t1[i]->element; }
00072 inline Element *getNext(){ return ¤t->next->element; }
00073 inline Element *getNext(int i){ return ¤t1[i]->next->element; }
00074 inline Element *Prev(){ current=current->prev; return ¤t->element; }
00075 inline Element *Prev(int i){ current1[i]=current1[i]->prev; return ¤t1[i]->element; }
00076 inline Element *getPrev(){ return ¤t->prev->element; }
00077 inline Element *getPrev(int i){ return ¤t1[i]->prev->element; }
00078 inline Element *Current(){ return ¤t->element; }
00079 inline Element *Current(int i){ return ¤t1[i]->element; }
00080 inline Item<Element> *getItem() { return current; }
00081 inline Item<Element> *getItem(int i) { return current1[i]; }
00082 inline Item<Element> *getFirstItem() { return first; }
00083 inline Item<Element> *getLastItem() { return last; }
00084 bool init(int n);
00085 Element *insertAfter();
00086 Element *insert0();
00087 Element *insert();
00088 Element *insert(int icounter);
00089 bool insert0(Element *element);
00090 bool insert(Element *element);
00091 bool insert(Element *element, int icounter);
00092 Element *append0();
00093 Element *append();
00094 Element *append(int icounter);
00095 bool append0(Element *element);
00096 bool append(Element *element);
00097 bool append(Element *element, int icounter);
00098 bool remove0();
00099 bool remove();
00100 bool remove(int icounter);
00101 };
00102 template <class Element>
00103 Collection<Element>::Collection() {
00104 mitems=nitems=0;
00105 locked=false;
00106 dead=first=last=current=NULL;
00107 for(int i=0;i<maxcounters;i++)current1[i]=NULL;
00108 }
00109 template <class Element>
00110 Collection<Element>::~Collection() {
00111
00112 mitems=nitems=0;
00113 dead=first=last=current=NULL;
00114 for(int i=0;i<maxcounters;i++)current1[i]=NULL;
00115 }
00116 template <class Element>
00117 bool Collection<Element>::init(int n) {
00118 dead=new Item<Element>[n];
00119 if(dead==NULL) {
00120 cout<<"CAN'T ALLOCATE "<<n<<" ITEMS\n";cout.flush();
00121 exit(1);
00122 }
00123 for(int i=1;i<n-1;i++) {
00124 current=dead+i;
00125 current->next=dead+i+1;
00126 current->prev=dead+i-1;
00127 for(int i=0;i<maxcounters;i++) {
00128 current1[i]=dead+i;
00129 current1[i]->next=dead+i+1;
00130 current1[i]->prev=dead+i-1;
00131 }
00132 }
00133 dead->next=dead+1;
00134 dead->prev=dead+n-1;
00135 dead[n-1].next=dead;
00136 dead[n-1].prev=dead+n-2;
00137 nitems=0;mitems=n;
00138 first=last=current=dead;
00139 #ifdef OMP
00140 for(int i=0;i<maxcounters;i++) current1[i]=dead;
00141 #endif
00142 }
00143 template <class Element>
00144 Element *Collection<Element>::insertAfter() {
00145
00146 if(dead->next==dead) {
00147 cout<<"CAN'T INSERT AFTER THE ELEMENT: Collection OF "<<nitems<<" IS FULL\n";
00148 cout.flush();
00149 return NULL;
00150 }
00151 Item<Element> *newitem=dead;
00152 if(first!=dead) {
00153
00154 dead=dead->next;
00155 dead->prev=newitem->prev;
00156 dead->prev->next=dead;
00157
00158 Item<Element> *tmp=current->prev;
00159 current->prev=newitem;
00160 tmp->next=newitem;
00161 newitem->next=current;
00162 newitem->prev=tmp;
00163
00164 } else {
00165 dead=dead->next;
00166 dead->prev=first->prev;
00167 dead->prev->next=dead;
00168 first->next=first->prev=first;
00169 newitem=last=current=first;
00170 #ifdef OMP
00171 for(int i=0;i<maxcounters;i++)current1[i]=current;
00172 #endif
00173 }
00174
00175 nitems++;
00176 return &newitem->element;
00177 }
00178 template <class Element>
00179 Element *Collection<Element>::insert0() {
00180
00181 if(dead->next==dead) {
00182 cout<<"CAN'T INSERT ELEMENT: Collection OF "<<nitems<<" IS FULL\n";
00183 cout.flush();
00184 return NULL;
00185 }
00186 Item<Element> *newitem=dead;
00187 if(first!=dead) {
00188
00189 dead=dead->next;
00190 dead->prev=newitem->prev;
00191 dead->prev->next=dead;
00192
00193 Item<Element> *tmp=current->next;
00194 current->next=newitem;
00195 tmp->prev=newitem;
00196 newitem->prev=current;
00197 newitem->next=tmp;
00198
00199 } else {
00200 dead=dead->next;
00201 dead->prev=first->prev;
00202 dead->prev->next=dead;
00203 first->next=first->prev=first;
00204 newitem=last=current=first;
00205 #ifdef OMP
00206 for(int i=0;i<maxcounters;i++)current1[i]=current;
00207 #endif
00208 }
00209
00210 nitems++;
00211 return &newitem->element;
00212 }
00213 template <class Element>
00214 Element *Collection<Element>::insert() {
00215 #ifdef OMP
00216 WAIT; locked=true;
00217 #endif
00218 Element *newelement=insert0();
00219 #ifdef OMP
00220 newelement->index(number());
00221 locked=false;
00222 #endif
00223 return newelement;
00224 }
00225 template <class Element>
00226 Element *Collection<Element>::insert(int icounter) {
00227 #ifdef OMP
00228 WAIT; locked=true;
00229 if(current1[icounter]!=NULL)current=current1[icounter];
00230 #endif
00231 Element *element=insert0();
00232 #ifdef OMP
00233 for(int i=0;i<maxcounters;i++) if(current1[i]==NULL)current1[i]=current;
00234 locked=false;
00235 #endif
00236 if(element==NULL) return NULL;
00237 return element;
00238 }
00239 template <class Element>
00240 bool Collection<Element>::insert(Element *element) {
00241 Element *newelement=insert();
00242 if(newelement==NULL) return false;
00243 newelement->copy(element);
00244 return true;
00245 }
00246 template <class Element>
00247 bool Collection<Element>::insert(Element *element,int icounter) {
00248 #ifdef OMP
00249 WAIT;
00250 locked=true;
00251 if(current1[icounter]!=NULL)current=current1[icounter];
00252 #endif
00253 Element *newelement=insert0();
00254 #ifdef OMP
00255 for(int i=0;i<maxcounters;i++) if(current1[i]==NULL)current1[i]=current;
00256 locked=false;
00257 #endif
00258 if(newelement==NULL) return false;
00259 newelement->copy(element);
00260 return true;
00261 }
00262 template <class Element>
00263 Element *Collection<Element>::append0() {
00264 if(dead->next==dead) {
00265 cout<<"CAN'T APPEND ELEMENT: Collection OF "<<nitems<<" IS FULL\n";
00266 cout.flush();
00267 return NULL;
00268 }
00269 if(first!=dead) {
00270 Item<Element> *old=dead;
00271
00272 dead=dead->next;
00273 dead->prev=old->prev;
00274 dead->prev->next=dead;
00275
00276 Item<Element> *tmp=last->next;
00277 last->next=old;
00278 tmp->prev=old;
00279 old->prev=last;
00280 old->next=tmp;
00281 last=old;
00282 } else {
00283 dead=dead->next;
00284 dead->prev=first->prev;
00285 dead->prev->next=dead;
00286 first->next=first->prev=first;
00287 last=current=first;
00288 #ifdef OMP
00289 for(int i=0;i<maxcounters;i++)current1[i]=current;
00290 #endif
00291 }
00292
00293 nitems++;
00294 return &last->element;
00295 }
00296 template <class Element>
00297 Element *Collection<Element>::append() {
00298 #ifdef OMP
00299 WAIT; locked=true;
00300 #endif
00301 Element *element=append0();
00302 #ifdef OMP
00303 locked=false;
00304 #endif
00305 return element;
00306 }
00307 template <class Element>
00308 Element *Collection<Element>::append(int icounter) {
00309 #ifdef OMP
00310 WAIT; locked=true;
00311 if(current1[icounter]!=NULL)current=current1[icounter];
00312 #endif
00313 Element *element=append0();
00314 #ifdef OMP
00315 for(int i=0;i<maxcounters;i++) if(current1[i]==NULL)current1[i]=current;
00316 locked=false;
00317 #endif
00318 if(element==NULL) return NULL;
00319 return element;
00320 }
00321 template <class Element>
00322 bool Collection<Element>::append(Element *element) {
00323 Element *newelement=append();
00324 if(newelement==NULL) return false;
00325 newelement->copy(element);
00326 return true;
00327 }
00328 template <class Element>
00329 bool Collection<Element>::append(Element *element,int icounter) {
00330 #ifdef OMP
00331 WAIT; locked=true;
00332 if(current1[icounter]!=NULL)current=current1[icounter];
00333 #endif
00334 Element *newelement=append0();
00335 #ifdef OMP
00336 for(int i=0;i<maxcounters;i++) if(current1[i]==NULL)current1[i]=current;
00337 locked=false;
00338 #endif
00339 if(newelement==NULL) return false;
00340 newelement->copy(element);
00341 return true;
00342 }
00343 template <class Element>
00344 bool Collection<Element>::remove0() {
00345 if(current==dead||nitems<=0) {
00346 cout<<"CAN'T REMOVE ITEM FROM AN EMPTY COLLECTION\n";
00347 cout.flush();
00348 return false;
00349 }
00350 if(current->next==current) {
00351 current->next=dead;
00352 current->prev=dead->prev;
00353 dead->prev->next=current;
00354 dead->prev=current;
00355 first=last=dead=current;
00356 #ifdef OMP
00357 for(int i=0;i<maxcounters;i++)current1[i]=current;
00358 #endif
00359 } else {
00360 current->next->prev=current->prev;
00361 current->prev->next=current->next;
00362 Item<Element> *deadprev=dead->prev;
00363 deadprev->next=current;
00364 dead->prev=current;
00365 if(current==first)first=first->next;
00366 if(current!=last) current=current->next;
00367 else {
00368 last=last->prev;
00369 current=last;
00370 }
00371 dead->prev->next=dead;
00372 dead=dead->prev;
00373 dead->prev=deadprev;
00374 }
00375 nitems--;
00376 return true;
00377 }
00378 template <class Element>
00379 bool Collection<Element>::remove() {
00380 bool returned=true;
00381 #ifdef OMP
00382 WAIT; locked=true;
00383 for(int i=0;i<maxcounters;i++) if(current1[i]==current)current1[i]=NULL;
00384 #endif
00385 returned=remove0();
00386 #ifdef OMP
00387 for(int i=0;i<maxcounters;i++) if(current1[i]==NULL)current1[i]=current;
00388 locked=false;
00389 #endif
00390 return returned;
00391 }
00392 template <class Element>
00393 bool Collection<Element>::remove(int icounter) {
00394 bool returned=true;
00395 #ifdef OMP
00396 WAIT; locked=true;
00397 if(icounter>=0&&icounter<maxcounters&¤t1[icounter]!=NULL)current=current1[icounter];
00398 for(int i=0;i<maxcounters;i++)if(current1[i]==current)current1[i]=NULL;
00399 #endif
00400 returned=remove0();
00401 #ifdef OMP
00402 for(int i=0;i<maxcounters;i++)if(current1[i]==NULL)current1[i]=current;
00403 locked=false;
00404 #endif
00405 return returned;
00406 }
00407
00408 template <class Element>
00409 struct Ptr {
00410 Element *element;
00411 Ptr *next,*prev;
00412 };
00413 template <class Element>
00414 struct Pool {
00415 int mptrs,nptrs;
00416 Ptr<Element> *hook;
00417 Pool(int nptrs);
00418 ~Pool();
00419 inline int size() {return nptrs;}
00420 Ptr<Element> *get();
00421 bool put(Ptr<Element> *ptr);
00422 bool check(char *msg);
00423 };
00424 template <class Element>
00425 Pool<Element>::Pool(int n) {
00426 hook=new Ptr<Element>[n];
00427 if(hook==NULL) {
00428 cout<<"CAN'T ALLOCATE "<<n<<" ITEMS FOR THE POOL\n";
00429 cout.flush();
00430 exit(1);
00431 }
00432
00433 for(int i=1;i<n-1;i++) {
00434 Ptr<Element> *ptr=hook+i;
00435 ptr->next=hook+i+1;
00436 ptr->prev=hook+i-1;
00437 ptr->element=NULL;
00438 }
00439 Ptr<Element> *first=hook;
00440 first->next=hook+1;
00441 first->prev=hook+n-1;
00442 first->element=NULL;
00443 Ptr<Element> *last=hook+n-1;
00444 last->next=hook;
00445 last->prev=hook+n-2;
00446 last->element=NULL;
00447 mptrs=nptrs=n;
00448 if(Run::option.verbose||Run::option.debug) cout<<"Pool size: "<<nptrs<<endl;
00449 }
00450 template <class Element>
00451 Pool<Element>::~Pool() {
00452
00453 mptrs=nptrs=0;
00454 hook=NULL;
00455 }
00456 template <class Element>
00457 Ptr<Element> *Pool<Element>::get() {
00458 if(hook->next==hook) {
00459 cout<<"\nPool::get:POOL-ALLOCATION FAILED: POOL SIZE: "<<nptrs<<endl;
00460 cout.flush();
00461 return NULL;
00462 }
00463 Ptr<Element> *out=hook->next;
00464 hook->next=out->next;
00465 out->next->prev=hook;
00466 out->next=out->prev=NULL;
00467 nptrs--;
00468 return out;
00469 }
00470 template <class Element>
00471 bool Pool<Element>::put(Ptr<Element> *ptr) {
00472 if(nptrs==mptrs) {
00473 cout<<"POOL IS FILLED UP\n";
00474 cout.flush();
00475 return false;
00476 }
00477 if(ptr==NULL) {
00478 cout<<"\nNULL POINTER RETURNED TO POOL\n";
00479 cout.flush();
00480 return false;
00481 }
00482
00483
00484 ptr->prev->next=ptr->next;
00485 ptr->next->prev=ptr->prev;
00486
00487 ptr->prev=hook;
00488 ptr->next=hook->next;
00489 ptr->next->prev=ptr;
00490 hook->next=ptr;
00491 nptrs++;
00492 return true;
00493 }
00494 template <class Element>
00495 bool Pool<Element>::check(char *msg) {
00496 Ptr<Element> *tmp=hook;
00497 int n=0;
00498 do {
00499 n++;tmp=tmp->next;
00500 if(n>mptrs+100) break;
00501 } while(tmp!=hook);
00502 cout<<"Pool::check("<<msg<<"):nptrs="<<nptrs<<", n="<<n<<", hook="<<hook<<", hook->next="<<hook->next<<" ";cout.flush();
00503 if(n!=nptrs){cout<<"broken pool!\n";cout.flush();exit(1);}
00504 cout<<endl;
00505 }
00506
00507
00508
00509
00510
00511 template <class Element>
00512 class Container {
00513 int nptrs;
00514 bool locked;
00515
00516 Ptr<Element>
00517 *first,*last,*current,
00518 *first1[maxcounters],*current1[maxcounters];
00519 public:
00520 Container();
00521 ~Container();
00522 inline bool islocked(){ return locked; }
00523 inline void lock() { locked=true; }
00524 inline void unlock() { locked=false; }
00525 inline int number(){ return nptrs; }
00526 inline void setFirst(){ first=last->next; }
00527 inline void setFirst(int i){ first1[i]=last->next; }
00528 inline void setFirstLast(){ first=last; }
00529 inline void setFirstLast(int i){ first1[i]=last; }
00530 inline void goFirst(){
00531 current=first;
00532 #ifdef OMP
00533 for(int i=0;i<maxcounters;i++)current1[i]=first1[i]=first;
00534 #endif
00535 }
00536 inline void goFirst(int i){ current1[i]=first1[i]; }
00537 inline void goFirstNext(){ current=first->next; }
00538 inline void goFirstNext(int i){ current1[i]=first1[i]->next; }
00539 inline void FirstNext(){ first=first->next; }
00540 inline void FirstNext(int i){ first1[i]=first1[i]->next; }
00541 inline void FirstPrev(){ first=first->prev; }
00542 inline void FirstPrev(int i){ first1[i]=first1[i]->prev; }
00543 inline bool isFirstLast(){ if(first==last) return true; else return false; }
00544 inline bool isFirstLast(int i){ if(first1[i]==last) return true; else return false; }
00545 inline void goLastNext(){ current=last->next; }
00546 inline void goLastNext(int i){ current1[i]=last->next; }
00547 inline void goLast(){ current=last; }
00548 inline void goLast(int i){ current1[i]=last; }
00549 inline void goNext(){ current=current->next; }
00550 inline void goNext(int i){ current1[i]=current1[i]->next; }
00551 inline void goPrev(){ current=current->prev; }
00552 inline void goPrev(int i){ current1[i]=current1[i]->prev; }
00553 inline bool isFirst(){ return current==first?true:false; }
00554 inline bool isFirst(int i){ return current1[i]==first1[i]?true:false; }
00555 inline bool isLast(){ if(current==last) return true; else return false; }
00556 inline bool isLast(int i){ if(current1[i]==last) return true; else return false; }
00557 inline void LastNext(){ last=last->next; }
00558 inline void LastPrev(){ last=last->prev; }
00559 inline void go(Ptr<Element> *p) { current=p; }
00560 inline void go(Ptr<Element> *p, int i) { current1[i]=p; }
00561 inline Element *First(){ return first->element; }
00562 inline Element *First(int i){ return first1[i]->element; }
00563 inline Element *Last(){ return last->element; }
00564 inline Element *Next(){ current=current->next; return current->element; }
00565 inline Element *Next(int i){ current1[i]=current1[i]->next; return current1[i]->element; }
00566 inline Element *getNext(){ return current->next->element; }
00567 inline Element *getNext(int i){ return current1[i]->next->element; }
00568 inline Element *Prev(){ current=current->prev; return current->element; }
00569 inline Element *Prev(int i){ current1[i]=current1[i]->prev; return current1[i]->element; }
00570 inline Element *getPrev(){ return current->prev->element; }
00571 inline Element *getPrev(int i){ return current1[i]->prev->element; }
00572 inline Element *Current(){ return current->element; }
00573 inline Element *Current(int i){ return current1[i]->element; }
00574 inline Ptr<Element> *getPtr() { return current; }
00575 inline Ptr<Element> *getPtr(int i) { return current1[i]; }
00576 inline Ptr<Element> *getFirstPtr() { return first; }
00577 inline Ptr<Element> *getFirstPtr(int i) { return first1[i]; }
00578 inline Ptr<Element> *getLastPtr() { return last; }
00579 bool insert0(Element *element);
00580 bool insert(Element *element);
00581 bool insert(Element *element,int i);
00582 Ptr<Element> *insert1(Element *element,int i);
00583 bool insert0();
00584 bool insert();
00585 bool insert(int i);
00586 bool append0(Element *element);
00587 bool append(Element *element);
00588 bool append(Element *element, int i);
00589 bool append0();
00590 bool append();
00591 bool append(int i);
00592 Ptr<Element> *append1(Element *element,int i);
00593 bool link0(Ptr<Element> *&ptr);
00594 bool link(Ptr<Element> *&ptr);
00595
00596
00597 bool unlink0(Ptr<Element> *&ptr);
00598 bool unlink(Ptr<Element> *&ptr);
00599
00600 bool remove0();
00601 bool remove();
00602 bool remove(int i);
00603 bool remove0(Ptr<Element> *&ptr);
00604 bool remove(Ptr<Element> *ptr);
00605 bool remove(Ptr<Element> *ptr, int i);
00606 bool checkPool(char *msg, Pool<Element> *pool);
00607 };