00001 #ifndef h_HPP_GufieChainedList_HPP_h
00002
00003
00013
00014
00015
00016
00017 template <class U, unsigned int pow2>
00018 CGufieChainedList<U, pow2>::CGufieChainedList() : mlNumberOfNodes(0), mlNumberOfBlocks(0), mlBlockSize(ChainedBS), mpxBlock(NULL), mpxFirst(NULL), mpxLast(NULL), mpxCurrent(NULL), mbIntegrity(true), mpxBLast(NULL)
00019 {
00020 mbUseBlocks = (pow2==0) ? false: true;
00021 }
00022
00023
00024 template <class U, unsigned int pow2>
00025 CGufieChainedList<U, pow2>::CGufieChainedList(const CGufieChainedList & copy)
00026 {
00027 unsigned int i;
00028 mbUseBlocks = copy.mbUseBlocks;
00029 mbIntegrity = copy.mbIntegrity;
00030 mlBlockSize = copy.mlBlockSize;
00031 mlNumberOfNodes = copy.mlNumberOfNodes;
00032 mlNumberOfBlocks = copy.mlNumberOfBlocks;
00033
00034 if (mbUseBlocks)
00035 {
00036
00037 if (copy.mpxBlock == NULL)
00038 {
00039 mpxFirst = mpxLast = mpxCurrent = NULL;
00040 mpxBlock = mpxBLast = NULL;
00041 return;
00042 }
00043
00044
00045 LinearBlock<ChainedBS> * pBlock = new LinearBlock<ChainedBS>;
00046 LinearBlock<ChainedBS> * copyBlock = copy.mpxBlock;
00047
00048 if (pBlock == NULL) return;
00049
00050
00051 mpxBlock = pBlock;
00052 mpxBlock->spxPrevious = NULL;
00053 mpxBlock->spxNext = NULL;
00054 mpxBLast = pBlock;
00055 mpxBlock->soUsed = copy.mpxBlock->soUsed;
00056
00057
00058 for (i=1; i < mlNumberOfBlocks; i++)
00059 {
00060 if (!pBlock->CreateNewBlock()) return;
00061 pBlock->soUsed = copyBlock->soUsed;
00062 pBlock = pBlock->spxNext;
00063 copyBlock = copyBlock->spxNext;
00064 mpxBLast = pBlock;
00065 }
00066
00067
00068 ChainedNode * pNode = mpxBlock->GetData();
00069
00070 mpxFirst = pNode;
00071 mpxFirst->mpxPrevious = NULL;
00072 mpxCurrent = NULL;
00073 pBlock = mpxBlock;
00074
00075 for (i=0; i < mlNumberOfBlocks; i++)
00076 {
00077 pNode = pBlock->GetData();
00078 for (unsigned int j=0; j < ChainedBS; j++)
00079 {
00080 pNode->mpxPrevious = mpxCurrent;
00081 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode;
00082 mpxCurrent = pNode;
00083 pNode ++;
00084 }
00085 pBlock = pBlock->spxNext;
00086 }
00087
00088
00089 ChainedNode * copyNode = copy.mpxFirst;
00090 pNode = mpxFirst;
00091
00092 for (i=0; i < mlNumberOfNodes; i++)
00093 {
00094 if ((pNode == NULL)||(copyNode == NULL)) return;
00095 pNode->Set(copyNode->mpuElement);
00096 pNode = pNode->mpxNext;
00097 copyNode = copyNode->mpxNext;
00098 }
00099
00100
00101 if (pNode!=NULL) mpxLast = pNode->mpxPrevious; else mpxLast = mpxCurrent;
00102 mpxCurrent = pNode;
00103 mpxLast->mpxNext = NULL;
00104 mbIntegrity = true;
00105 }
00106 else
00107 {
00108
00109 ChainedNode * pNode0 = NULL;
00110 ChainedNode * pNode;
00111 ChainedNode * pCopy = copy.mpxFirst;
00112 for (unsigned int i = 0; i < mlNumberOfNodes; i++)
00113 {
00114 pNode = new ChainedNode;
00115
00116 if (pNode == NULL) return;
00117 if (i==0) mpxFirst = pNode;
00118 pNode->mpxPrevious = pNode0;
00119 if (pNode->mpxPrevious != NULL) pNode->mpxPrevious->mpxNext = pNode;
00120
00121
00122 if (pCopy == NULL) return;
00123
00124 pNode->Set(pCopy->mpuElement);
00125 pCopy = pCopy->mpxNext;
00126 pNode0 = pNode;
00127 }
00128
00129
00130 mpxLast = pNode;
00131 mpxCurrent = mpxLast;
00132 mpxBlock = mpxBLast = NULL;
00133
00134 }
00135 }
00136
00137
00138 template <class U, unsigned int pow2>
00139 CGufieChainedList<U, pow2>::~CGufieChainedList()
00140 {
00144 Free();
00145 }
00146
00147
00148
00149
00150
00151
00152 template <class U, unsigned int pow2>
00153 CGufieChainedList<U, pow2>& CGufieChainedList<U, pow2>::operator =(const CGufieChainedList & copy)
00154 {
00158 if (© == this) return (*this);
00159
00160 if (mpxBlock != NULL)
00161 if (!mpxBlock->DeleteAll()) return (*this);
00162
00163 unsigned int i;
00164 if (!mbUseBlocks)
00165 {
00166 ChainedNode * pNode = mpxFirst;
00167
00168
00169 if (mpxFirst!=NULL)
00170 {
00171
00172 while (pNode!=NULL)
00173 {
00174 mpxFirst = pNode->mpxNext;
00175 delete pNode;
00176 pNode = mpxFirst;
00177 }
00178 }
00179
00180 }
00181
00182 mbUseBlocks = copy.mbUseBlocks;
00183 mbIntegrity = copy.mbIntegrity;
00184 mlBlockSize = copy.mlBlockSize;
00185 mlNumberOfNodes = copy.mlNumberOfNodes;
00186 mlNumberOfBlocks = copy.mlNumberOfBlocks;
00187
00188 if (mbUseBlocks)
00189 {
00190
00191 if (copy.mpxBlock == NULL)
00192 {
00193 mpxFirst = mpxLast = mpxCurrent = NULL;
00194 mpxBlock = mpxBLast = NULL;
00195 return (*this);
00196 }
00197
00198
00199 LinearBlock<ChainedBS> * pBlock = new LinearBlock<ChainedBS>;
00200 LinearBlock<ChainedBS> * copyBlock = copy.mpxBlock;
00201
00202 if (pBlock == NULL) return (*this);
00203
00204
00205 mpxBlock = pBlock;
00206 mpxBlock->spxPrevious = NULL;
00207 mpxBlock->spxNext = NULL;
00208 mpxBLast = pBlock;
00209 mpxBlock->soUsed = copy.mpxBlock->soUsed;
00210
00211
00212 for (i=1; i < mlNumberOfBlocks; i++)
00213 {
00214 if (!pBlock->CreateNewBlock()) return (*this);
00215 pBlock->soUsed = copyBlock->soUsed;
00216 pBlock = pBlock->spxNext;
00217 copyBlock = copyBlock->spxNext;
00218 mpxBLast = pBlock;
00219 }
00220
00221
00222 ChainedNode * pNode = mpxBlock->GetData();
00223
00224 mpxFirst = pNode;
00225 mpxFirst->mpxPrevious = NULL;
00226 mpxCurrent = NULL;
00227 pBlock = mpxBlock;
00228
00229 for (i=0; i < mlNumberOfBlocks; i++)
00230 {
00231 pNode = pBlock->GetData();
00232 for (unsigned int j=0; j < ChainedBS; j++)
00233 {
00234 pNode->mpxPrevious = mpxCurrent;
00235 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode;
00236 mpxCurrent = pNode;
00237 pNode ++;
00238 }
00239 pBlock = pBlock->spxNext;
00240 }
00241
00242
00243 ChainedNode * copyNode = copy.mpxFirst;
00244 pNode = mpxFirst;
00245
00246 for (i=0; i < mlNumberOfNodes; i++)
00247 {
00248 if ((pNode == NULL)||(copyNode == NULL)) return (*this);
00249
00250 pNode->Set(copyNode->Get());
00251 pNode = pNode->mpxNext;
00252 copyNode = copyNode->mpxNext;
00253 }
00254
00255
00256 if (pNode!=NULL) mpxLast = pNode->mpxPrevious; else mpxLast = mpxCurrent;
00257 mpxCurrent = pNode;
00258 mpxLast->mpxNext = NULL;
00259 mbIntegrity = true;
00260 }
00261 else
00262 {
00263 ChainedNode * pNode = NULL;
00264
00265
00266 ChainedNode * pNode0 = NULL;
00267 ChainedNode * pCopy = copy.mpxFirst;
00268 for (unsigned int i = 0; i < mlNumberOfNodes; i++)
00269 {
00270 pNode = new ChainedNode;
00271
00272 if (pNode == NULL) return (*this);
00273 if (i==0) mpxFirst = pNode;
00274 pNode->mpxPrevious = pNode0;
00275 if (pNode->mpxPrevious != NULL) pNode->mpxPrevious->mpxNext = pNode;
00276
00277
00278 if (pCopy == NULL) return (*this);
00279
00280 pNode->Set(pCopy->Get());
00281 pCopy = pCopy->mpxNext;
00282 pNode0 = pNode;
00283 }
00284
00285
00286 mpxLast = pNode;
00287 mpxCurrent = mpxLast;
00288 mpxBlock = mpxBLast = NULL;
00289
00290 }
00291
00295 return (*this);
00296 }
00297
00298
00299
00300
00301
00302
00303 template <class T, unsigned int pow2>
00304 bool CGufieChainedList<T, pow2>::Connect(ChainedNode *pNode, ChainedNode *pP, ChainedNode *pN)
00305 {
00306
00310 if (pNode == NULL) return false;
00311 if ((pP==NULL)&&(pN==NULL)&&(pNode->mpuElement!=NULL)&&((pNode->mpxPrevious!=NULL)||(pNode->mpxNext!=NULL)))
00312 {
00313
00314 pNode->mpxPrevious = pP;
00315 pNode->mpxNext = pN;
00316 return false;
00317 }
00318
00319 pNode->mpxPrevious = pP;
00320 pNode->mpxNext = pN;
00321
00325 return true;
00326 }
00327
00328 template <class U, unsigned int pow2>
00329 unsigned int CGufieChainedList<U, pow2>::Find(const U & arg)
00330 {
00334 if (mpxFirst==NULL) return ChainedEnd;
00335
00336 unsigned int i=0;
00337 ChainedNode * pNode = mpxFirst;
00338 while ((i<mlNumberOfNodes)&&(pNode!=NULL))
00339 {
00340 #ifdef UseOperatorEqual
00341 if (pNode->Get() == arg) return i;
00342 #else
00343 if (memcmp(&pNode->Get(), &arg, sizeof(arg)) == 0) return i;
00344 #endif
00345 i++;
00346 pNode = pNode->mpxNext;
00347 }
00348
00352 return ChainedEnd;
00353 }
00354
00355 template <class U, unsigned int pow2>
00356 bool CGufieChainedList<U, pow2>::UseBlocks(const bool & arg)
00357 {
00361 if (mpxBlock != NULL) return false;
00362
00363 if (arg)
00364 {
00365 mbUseBlocks = true;
00366 return true;
00367 }
00368 else
00369 {
00370 mbUseBlocks = false;
00371 return true;
00372 }
00373
00377 return true;
00378 }
00379
00380 template <class U, unsigned int pow2>
00381 bool CGufieChainedList<U, pow2>::Add(const CGufieChainedList& copy, const unsigned int &pos)
00382 {
00386 if ((copy.mpxFirst==NULL)||(copy.mpxLast==NULL)) return false;
00387
00388 if (pos >= mlNumberOfNodes-1)
00389 {
00390
00391 if (mbUseBlocks)
00392 {
00393
00394 ChainedNode * pNode = NULL;
00395 ChainedNode * pNode0 = mpxLast;
00396 ChainedNode * pCopy = copy.mpxFirst;
00397
00398 for (unsigned int i=0; i < copy.mlNumberOfNodes; i++)
00399 {
00400 pNode = CreateNode();
00401 if (pNode == NULL) return false;
00402
00403 if (mpxFirst == NULL) mpxFirst = pNode;
00404 pNode->mpxPrevious = pNode0;
00405 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode;
00406
00407 if (pCopy == NULL) return false;
00408 pNode->Set(pCopy->mpuElement);
00409 pCopy = pCopy->mpxNext;
00410 pNode0 = pNode;
00411 }
00412
00413 mlNumberOfNodes += copy.mlNumberOfNodes;
00414 mpxLast = pNode;
00415 mpxLast->mpxNext = NULL;
00416
00417 return true;
00418
00419 }
00420 else
00421 {
00422
00423
00424 ChainedNode * pNode = NULL;
00425 ChainedNode * pNode0 = mpxLast;
00426 ChainedNode * pCopy = copy.mpxFirst;
00427
00428 for (unsigned int i=0; i < copy.mlNumberOfNodes; i++)
00429 {
00430 pNode = new ChainedNode;
00431 if (pNode == NULL) return false;
00432
00433 pNode->mpxPrevious = pNode0;
00434 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode;
00435
00436 if (pCopy == NULL) return false;
00437 pNode->Set(pCopy->mpuElement);
00438 pCopy = pCopy->mpxNext;
00439 pNode0 = pNode;
00440 }
00441
00442 mlNumberOfNodes += copy.mlNumberOfNodes;
00443 mpxLast = pNode;
00444 mpxCurrent = mpxLast;
00445 mpxLast->mpxNext = NULL;
00446
00447 return true;
00448 }
00449 }
00450 else
00451 {
00452 if (mbUseBlocks)
00453 {
00454 unsigned int i;
00455 ChainedNode * pNode = NULL;
00456 ChainedNode * pLast = mpxLast;
00457
00458
00459 for (i=0; i < copy.mlNumberOfNodes; i++)
00460 {
00461 pNode = CreateNode();
00462 if (pNode == NULL) return false;
00463
00464 pNode->mpxPrevious = pLast;
00465 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode;
00466
00467 pLast = pNode;
00468 }
00469
00470 mlNumberOfNodes += copy.mlNumberOfNodes;
00471
00472
00473 ChainedNode * pInsert = pNode;
00474 if (pInsert == NULL) return false;
00475 ChainedNode * pFirst = Goto(pos);
00476 if (pFirst == NULL) return false;
00477
00478 pNode = mpxLast;
00479 mpxLast = pInsert;
00480 mpxLast->mpxNext = NULL;
00481
00482 for (i=pos + copy.mlNumberOfNodes; i < mlNumberOfNodes; i++)
00483 {
00484 if ((pInsert==NULL)||(pNode == NULL)) return false;
00485 pInsert->Set(pNode->mpuElement);
00486
00487 pInsert = pInsert->mpxPrevious;
00488 pNode = pNode->mpxPrevious;
00489 }
00490
00491
00492 pInsert = pFirst;
00493 pNode = copy.mpxFirst;
00494 for (i = 0; i < copy.mlNumberOfNodes; i++)
00495 {
00496 if ((pInsert==NULL)||(pNode == NULL)) return false;
00497 pInsert->Set(pNode->mpuElement);
00498
00499 pInsert = pInsert->mpxNext;
00500 pNode = pNode->mpxNext;
00501 }
00502
00503
00504 return true;
00505
00506 }
00507 else
00508 {
00509
00510 ChainedNode * pNode = NULL;
00511 ChainedNode * pFirst = Goto(pos);
00512 if (pFirst == NULL) return false;
00513 ChainedNode * pNode0 = pFirst->mpxPrevious;
00514 ChainedNode * pCopy = copy.mpxFirst;
00515
00516 for (unsigned int i=0; i < copy.mlNumberOfNodes; i++)
00517 {
00518 pNode = new ChainedNode;
00519 if (pNode == NULL) return false;
00520
00521 pNode->mpxPrevious = pNode0;
00522 if ((i==0)&&(pos==0)) mpxFirst = pNode;
00523 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode;
00524
00525 if (pCopy == NULL) return false;
00526 pNode->Set(pCopy->mpuElement);
00527 pCopy = pCopy->mpxNext;
00528 pNode0 = pNode;
00529 }
00530
00531 mlNumberOfNodes += copy.mlNumberOfNodes;
00532 pNode->mpxNext = pFirst;
00533 pFirst->mpxPrevious = pNode;
00534
00535 return true;
00536 }
00537 }
00538
00539 }
00540
00541 template <class U, unsigned int pow2>
00542 bool CGufieChainedList<U, pow2>::Add(const U& a, const unsigned int& pos)
00543 {
00547 if (pos >= mlNumberOfNodes)
00548 {
00549
00550 if (mbUseBlocks)
00551 {
00552
00553 ChainedNode * pNode = CreateNode();
00554 if (pNode == NULL) return false;
00555
00556 pNode->Set(a);
00557 if (mpxBlock==NULL) return false;
00558 mpxBLast->soUsed ++;
00559
00560
00561 if (mlNumberOfNodes==0)
00562 {
00563 mpxFirst = pNode;
00564 pNode->mpxNext = NULL;
00565 pNode->mpxPrevious = NULL;
00566 mpxLast = mpxFirst;
00567 mlNumberOfNodes++;
00568 }
00569 else
00570 {
00571 mlNumberOfNodes++;
00572 mpxLast->mpxNext = pNode;
00573 pNode->mpxPrevious = mpxLast;
00574 pNode->mpxNext = NULL;
00575 mpxLast = pNode;
00576 }
00577
00578
00579 return true;
00580 }
00581 else
00582 {
00583 if (mpxFirst==NULL)
00584 {
00585
00586 mpxFirst = new ChainedNode(a);
00587
00588
00589 if (mpxFirst == NULL) return false;
00590
00591
00592 if (!Connect(mpxFirst,NULL,NULL)) return false;
00593
00594
00595 mpxLast = mpxFirst;
00596 mpxCurrent = mpxFirst;
00597
00598
00599 mlNumberOfNodes = 1;
00600
00601
00602 return true;
00603 }
00604 else
00605 {
00606
00607 mpxCurrent = new ChainedNode(a);
00608
00609
00610 if (mpxCurrent == NULL) return false;
00611
00612
00613 if (!Connect(mpxCurrent,mpxLast,NULL)) return false;
00614 mpxLast->mpxNext = mpxCurrent;
00615 mpxLast = mpxCurrent;
00616
00617
00618 mlNumberOfNodes ++;
00619
00620
00621 return true;
00622
00623 }
00624 }
00625 }
00626 else
00627 {
00628
00629
00630
00631 if (mbUseBlocks)
00632 {
00633
00634 ChainedNode * pNode;
00635
00636
00637 if (mpxBlock==NULL)
00638 {
00639 if (pos == 0) return Add(a); else return false;
00640 }
00641
00642 LinearBlock<ChainedBS> * pBlock = mpxBLast;
00643
00644 if (pBlock->soUsed < ChainedBS)
00645 {
00646
00647
00648 if (mpxCurrent == NULL) return false;
00649
00650 mpxLast->mpxNext = mpxCurrent;
00651 mpxLast = mpxCurrent;
00652 mpxCurrent = mpxCurrent->mpxNext;
00653 mpxLast->mpxNext = NULL;
00654 pNode = mpxLast;
00655
00656
00657 for (unsigned int i=pos; i < mlNumberOfNodes; i++)
00658 {
00659 if (pNode->mpxPrevious !=NULL)
00660 {
00661 pNode->Set(pNode->mpxPrevious->mpuElement);
00662 pNode = pNode->mpxPrevious;
00663 }
00664
00665
00666 }
00667
00668
00669 pNode->Set(a);
00670
00671 pBlock->soUsed++;
00672 mlNumberOfNodes ++;
00673 return true;
00674 }
00675 else
00676 {
00677 unsigned int i;
00678
00679 if (!pBlock->CreateNewBlock()) return false;
00680
00681 pBlock = pBlock->spxNext;
00682 mpxBLast = pBlock;
00683
00684
00685 pNode = pBlock->GetData();
00686
00687
00688 mpxCurrent = mpxLast;
00689 for (i = 0; i < ChainedBS; i++, pNode++)
00690 {
00691 pNode->mpxPrevious = mpxCurrent;
00692
00693
00694
00695 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode;
00696 mpxCurrent = pNode;
00697 }
00698
00699 mlNumberOfBlocks ++;
00700 mpxCurrent -= ChainedBS - 1;
00701
00702
00703
00704 if (mpxCurrent == NULL) return false;
00705
00706 mpxLast->mpxNext = mpxCurrent;
00707 mpxLast = mpxCurrent;
00708 mpxCurrent = mpxCurrent->mpxNext;
00709 mpxLast->mpxNext = NULL;
00710 pNode = mpxLast;
00711
00712
00713 for (i=pos; i < mlNumberOfNodes; i++)
00714 {
00715 if (pNode->mpxPrevious !=NULL)
00716 {
00717 pNode->Set(pNode->mpxPrevious->mpuElement);
00718 pNode = pNode->mpxPrevious;
00719 }
00720
00721
00722 }
00723
00724
00725 pNode->Set(a);
00726
00727 pBlock->soUsed++;
00728 mlNumberOfNodes ++;
00729 return true;
00730
00731 }
00732
00733 }
00734 else
00735 {
00736
00737 ChainedNode * pNode = new ChainedNode(a);
00738
00739
00740 if (pos!=0)
00741 {
00742 mpxCurrent = Goto(pos-1);
00743 if (mpxCurrent == NULL) return false;
00744
00745 Connect(pNode, mpxCurrent, mpxCurrent->mpxNext);
00746 mpxCurrent->mpxNext = pNode;
00747 if (pNode->mpxNext!=NULL) pNode->mpxNext->mpxPrevious = pNode;
00748
00749
00750 mlNumberOfNodes ++;
00751
00752 } else
00753 {
00754
00755 Connect(pNode, NULL, mpxFirst);
00756 mpxFirst->mpxPrevious = pNode;
00757 mpxFirst = pNode;
00758
00759
00760 mlNumberOfNodes ++;
00761
00762
00763 }
00764
00765
00766 }
00767 return true;
00768 }
00769
00773 }
00774
00775 template <class U, unsigned int pow2>
00776 bool CGufieChainedList<U, pow2>::Add(U* a, const unsigned int& pos)
00777 {
00781 if (pos >= mlNumberOfNodes)
00782 {
00783
00784 if (mbUseBlocks)
00785 {
00786
00787 ChainedNode * pNode = CreateNode();
00788 if (pNode == NULL) return false;
00789
00790 pNode->Set(a);
00791 if (mpxBlock==NULL) return false;
00792 mpxBLast->soUsed ++;
00793
00794
00795 if (mlNumberOfNodes==0)
00796 {
00797 mpxFirst = pNode;
00798 pNode->mpxNext = NULL;
00799 pNode->mpxPrevious = NULL;
00800 mpxLast = mpxFirst;
00801 mlNumberOfNodes++;
00802 }
00803 else
00804 {
00805 mlNumberOfNodes++;
00806 mpxLast->mpxNext = pNode;
00807 pNode->mpxPrevious = mpxLast;
00808 pNode->mpxNext = NULL;
00809 mpxLast = pNode;
00810 }
00811
00812
00813 return true;
00814 }
00815 else
00816 {
00817 if (mpxFirst==NULL)
00818 {
00819
00820 mpxFirst = new ChainedNode(a);
00821
00822
00823 if (mpxFirst == NULL) return false;
00824
00825
00826 if (!Connect(mpxFirst,NULL,NULL)) return false;
00827
00828
00829 mpxLast = mpxFirst;
00830 mpxCurrent = mpxFirst;
00831
00832
00833 mlNumberOfNodes = 1;
00834
00835
00836 return true;
00837 }
00838 else
00839 {
00840
00841 mpxCurrent = new ChainedNode(a);
00842
00843
00844 if (mpxCurrent == NULL) return false;
00845
00846
00847 if (!Connect(mpxCurrent,mpxLast,NULL)) return false;
00848 mpxLast->mpxNext = mpxCurrent;
00849 mpxLast = mpxCurrent;
00850
00851
00852 mlNumberOfNodes ++;
00853
00854
00855 return true;
00856
00857 }
00858 }
00859 }
00860 else
00861 {
00862
00863
00864
00865 if (mbUseBlocks)
00866 {
00867
00868 ChainedNode * pNode;
00869
00870
00871 if (mpxBlock==NULL)
00872 {
00873 if (pos == 0) return Add(a); else return false;
00874 }
00875
00876 LinearBlock<ChainedBS> * pBlock = mpxBLast;
00877
00878 if (pBlock->soUsed < ChainedBS)
00879 {
00880
00881
00882 if (mpxCurrent == NULL) return false;
00883
00884 mpxLast->mpxNext = mpxCurrent;
00885 mpxLast = mpxCurrent;
00886 mpxCurrent = mpxCurrent->mpxNext;
00887 mpxLast->mpxNext = NULL;
00888 pNode = mpxLast;
00889
00890
00891 for (unsigned int i=pos; i < mlNumberOfNodes; i++)
00892 {
00893 if (pNode->mpxPrevious !=NULL)
00894 {
00895 pNode->Set(pNode->mpxPrevious->mpuElement);
00896 pNode = pNode->mpxPrevious;
00897 }
00898
00899
00900 }
00901
00902
00903 pNode->Set(a);
00904
00905 pBlock->soUsed++;
00906 mlNumberOfNodes ++;
00907 return true;
00908 }
00909 else
00910 {
00911 unsigned int i;
00912
00913 if (!pBlock->CreateNewBlock()) return false;
00914
00915 pBlock = pBlock->spxNext;
00916 mpxBLast = pBlock;
00917
00918
00919 pNode = pBlock->GetData();
00920
00921
00922 mpxCurrent = mpxLast;
00923 for (i = 0; i < ChainedBS; i++, pNode++)
00924 {
00925 pNode->mpxPrevious = mpxCurrent;
00926
00927
00928
00929 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode;
00930 mpxCurrent = pNode;
00931 }
00932
00933 mlNumberOfBlocks ++;
00934 mpxCurrent -= ChainedBS - 1;
00935
00936
00937
00938 if (mpxCurrent == NULL) return false;
00939
00940 mpxLast->mpxNext = mpxCurrent;
00941 mpxLast = mpxCurrent;
00942 mpxCurrent = mpxCurrent->mpxNext;
00943 mpxLast->mpxNext = NULL;
00944 pNode = mpxLast;
00945
00946
00947 for (i=pos; i < mlNumberOfNodes; i++)
00948 {
00949 if (pNode->mpxPrevious !=NULL)
00950 {
00951 pNode->Set(pNode->mpxPrevious->mpuElement);
00952 pNode = pNode->mpxPrevious;
00953 }
00954
00955
00956 }
00957
00958
00959 pNode->Set(a);
00960
00961 pBlock->soUsed++;
00962 mlNumberOfNodes ++;
00963 return true;
00964
00965 }
00966
00967 }
00968 else
00969 {
00970
00971 ChainedNode * pNode = new ChainedNode(a);
00972
00973
00974 if (pos!=0)
00975 {
00976 mpxCurrent = Goto(pos-1);
00977 if (mpxCurrent == NULL) return false;
00978
00979 Connect(pNode, mpxCurrent, mpxCurrent->mpxNext);
00980 mpxCurrent->mpxNext = pNode;
00981 if (pNode->mpxNext!=NULL) pNode->mpxNext->mpxPrevious = pNode;
00982
00983
00984 mlNumberOfNodes ++;
00985
00986 } else
00987 {
00988
00989 Connect(pNode, NULL, mpxFirst);
00990 mpxFirst->mpxPrevious = pNode;
00991 mpxFirst = pNode;
00992
00993
00994 mlNumberOfNodes ++;
00995
00996
00997 }
00998
00999
01000 }
01001 return true;
01002 }
01003
01007 }
01008
01009 template <class U, unsigned int pow2>
01010 bool CGufieChainedList<U, pow2>::Sub(const unsigned int& pos)
01011 {
01015 if (pos >= mlNumberOfNodes-1)
01016 {
01017
01018 if (mbUseBlocks)
01019 {
01020
01021 if ((mpxLast == NULL)||(mpxBlock == NULL)) return false;
01022
01023 LinearBlock<ChainedBS> * pBlock = mpxBLast;
01024 ChainedNode * pNode = mpxLast->mpxPrevious;
01025
01026 if (pNode==NULL)
01027 {
01028
01029 if (!mpxBlock->DeleteAll()) return false;
01030 mpxBlock = NULL;
01031 mpxBLast = NULL;
01032 mlNumberOfNodes = 0;
01033 mlNumberOfBlocks = 0;
01034 mbUseBlocks = true;
01035 mbIntegrity = true;
01036 mpxCurrent = mpxFirst = mpxLast = NULL;
01037 return true;
01038 }
01039
01040 if (pBlock->soUsed == 1)
01041 {
01042
01043 pNode->mpxNext = NULL;
01044 mpxLast = pNode;
01045 mpxCurrent = NULL;
01046 pBlock->soUsed = 0;
01047 mlNumberOfNodes --;
01048 mlNumberOfBlocks --;
01049 mpxBLast = pBlock->spxPrevious;
01050 pBlock->Delete();
01051
01052 return true;
01053 }
01054
01055
01056 pNode->mpxNext = NULL;
01057 mpxLast->mpxNext = mpxCurrent;
01058 mpxCurrent = mpxLast;
01059 mpxLast = pNode;
01060
01061 mlNumberOfNodes --;
01062 pBlock->soUsed --;
01063
01064 return true;
01065
01066
01067 }
01068 else
01069 {
01070 if (mpxLast == NULL) return false;
01071 ChainedNode * pNode = mpxLast->mpxPrevious;
01072
01073 if (pNode == NULL)
01074 {
01075
01076 delete mpxLast;
01077 mpxLast = mpxFirst = mpxCurrent = NULL;
01078 mlNumberOfNodes = 0;
01079 return true;
01080 }
01081
01082 pNode->mpxNext = NULL;
01083 delete mpxLast;
01084 mpxLast = pNode;
01085 mpxCurrent = mpxLast;
01086 mlNumberOfNodes --;
01087
01088 return true;
01089 }
01090 }
01091 else
01092 {
01093
01094 if (mbUseBlocks)
01095 {
01096
01097 if ((mpxLast == NULL)||(mpxBlock == NULL)) return false;
01098
01099 LinearBlock<ChainedBS> * pBlock = mpxBLast;
01100 ChainedNode * pNode = Goto(pos);
01101
01102 if ((pNode == NULL)||(pBlock==NULL)) return false;
01103
01104 if (pBlock->soUsed == 1)
01105 {
01106
01107 for (unsigned int i = pos+1; i < mlNumberOfNodes; i++)
01108 {
01109 if (pNode->mpxNext == NULL) return false;
01110 pNode->Set(pNode->mpxNext->mpuElement);
01111 pNode = pNode->mpxNext;
01112 }
01113
01114
01115 mpxCurrent = NULL;
01116
01117 mpxLast = mpxLast->mpxPrevious;
01118 mpxLast->mpxNext = NULL;
01119
01120 pBlock->soUsed = 0;
01121 mpxBLast = pBlock->spxPrevious;
01122 pBlock->Delete();
01123
01124 mlNumberOfNodes --;
01125 mlNumberOfBlocks --;
01126
01127 return true;
01128 }
01129
01130
01131 for (unsigned int i = pos+1; i < mlNumberOfNodes; i++)
01132 {
01133 if (pNode->mpxNext == NULL) return false;
01134 pNode->Set(pNode->mpxNext->mpuElement);
01135 pNode = pNode->mpxNext;
01136 }
01137
01138
01139 mpxLast->mpxNext = mpxCurrent;
01140
01141 mpxCurrent = mpxLast;
01142
01143 mpxLast = mpxLast->mpxPrevious;
01144 mpxLast->mpxNext = NULL;
01145
01146 pBlock->soUsed --;
01147
01148 mlNumberOfNodes --;
01149
01150 return true;
01151
01152
01153 }
01154 else
01155 {
01156
01157 ChainedNode * pNode = Goto(pos);
01158 if (pNode == NULL) return false;
01159
01160
01161 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode->mpxNext;
01162 if (pNode->mpxNext!=NULL) pNode->mpxNext->mpxPrevious = pNode->mpxPrevious;
01163
01164
01165 if (pNode == mpxFirst) mpxFirst = pNode->mpxNext;
01166
01167 if (pNode == mpxLast) mpxLast = pNode->mpxPrevious;
01168
01169
01170 delete pNode;
01171 mlNumberOfNodes --;
01172
01173 return true;
01174 }
01175
01176 }
01177
01181
01182 }
01183
01184 template <class U, unsigned int pow2>
01185 bool CGufieChainedList<U, pow2>::Insert(U& a, const unsigned int& pos)
01186 {
01190 if (pos>= mlNumberOfNodes) return Add(a);
01191
01192 ChainedNode * pNode;
01193 if (mbUseBlocks)
01194 {
01195
01196 pNode = CreateNode();
01197
01198
01199 mbIntegrity = false;
01200 }
01201 else
01202 {
01203 pNode = new ChainedNode(a);
01204 }
01205
01206 if (pNode == NULL) return false;
01207
01208 pNode->Set(a);
01209
01210
01211 pNode->mpxNext = Goto(pos);
01212 if (pNode->mpxNext==NULL) return false;
01213
01214 pNode->mpxPrevious = pNode->mpxNext->mpxPrevious;
01215 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode;
01216 pNode->mpxNext->mpxPrevious = pNode;
01217
01221 return true;
01222 }
01223
01224 template <class U, unsigned int pow2>
01225 bool CGufieChainedList<U, pow2>::Swap(const unsigned int& pos0, const unsigned int& pos1)
01226 {
01230 if ((pos0>= mlNumberOfNodes)||(pos1>= mlNumberOfNodes)) return false;
01231
01232
01233 ChainedNode * pNode0 = Goto(pos0);
01234 ChainedNode * pNode1 = Goto(pos1);
01235
01236 if ((pNode0==NULL)||(pNode1==NULL)) return false;
01237
01238 if (mbUseBlocks)
01239 {
01240
01241
01242
01243 U * a = pNode1->mpuElement;
01244 pNode1->Set(pNode0->mpuElement);
01245 pNode0->Set(a);
01246
01247 return true;
01248 }
01249 else
01250 {
01251 if ((pNode0->mpxNext == pNode1)||(pNode0->mpxPrevious == pNode1))
01252 {
01253
01254 if (pNode0->mpxNext == pNode1)
01255 {
01256
01257 if (pNode0->mpxPrevious!=NULL) pNode0->mpxPrevious->mpxNext = pNode1;
01258 if (pNode1->mpxNext!=NULL) pNode1->mpxNext->mpxPrevious = pNode0;
01259
01260 pNode0->mpxNext = pNode1->mpxNext;
01261 pNode1->mpxPrevious = pNode0->mpxPrevious;
01262 pNode0->mpxPrevious = pNode1;
01263 pNode1->mpxNext = pNode0;
01264 } else
01265 {
01266
01267 if (pNode1->mpxPrevious!=NULL) pNode1->mpxPrevious->mpxNext = pNode0;
01268 if (pNode0->mpxNext!=NULL) pNode0->mpxNext->mpxPrevious = pNode1;
01269
01270 pNode1->mpxNext = pNode0->mpxNext;
01271 pNode0->mpxPrevious = pNode1->mpxPrevious;
01272 pNode1->mpxPrevious = pNode0;
01273 pNode0->mpxNext = pNode1;
01274 }
01275
01276 return true;
01277 }
01278
01279
01280 ChainedNode * pNodeTemp0 = pNode0->mpxPrevious;
01281 ChainedNode * pNodeTemp1 = pNode0->mpxNext;
01282
01283 if (pNode0->mpxPrevious!=NULL) pNode0->mpxPrevious->mpxNext = pNode1;
01284 if (pNode0->mpxNext!=NULL) pNode0->mpxNext->mpxPrevious = pNode1;
01285 if (pNode1->mpxPrevious!=NULL) pNode1->mpxPrevious->mpxNext = pNode0;
01286 if (pNode1->mpxNext!=NULL) pNode1->mpxNext->mpxPrevious = pNode0;
01287
01288 pNode0->mpxPrevious = pNode1->mpxPrevious;
01289 pNode0->mpxNext = pNode1->mpxNext;
01290
01291 pNode1->mpxPrevious = pNodeTemp0;
01292 pNode1->mpxNext = pNodeTemp1;
01293
01294 return true;
01295 }
01296
01300
01301 }
01302
01303 template <class U, unsigned int pow2>
01304 bool CGufieChainedList<U, pow2>::Remove(const unsigned int& pos)
01305 {
01309 if (pos>= mlNumberOfNodes) return false;
01310
01311
01312 ChainedNode * pNode = Goto(pos);
01313 if (pNode == NULL) return false;
01314
01315 if (mbUseBlocks)
01316 {
01317
01318 if (pNode==mpxLast)
01319 {
01320 LinearBlock<ChainedBS> * pBlock = mpxBLast;
01321 if (pBlock == NULL) return false;
01322 if (pBlock->soUsed == 1)
01323 {
01324
01325 pNode = mpxLast->mpxPrevious;
01326 if (pNode != NULL) pNode->mpxNext = NULL;
01327 mpxLast = pNode;
01328 mpxCurrent = NULL;
01329
01330
01331 pBlock->soUsed = 0;
01332 mlNumberOfNodes --;
01333 mlNumberOfBlocks --;
01334 mpxBLast = pBlock->spxPrevious;
01335 pBlock->Delete();
01336
01337 if (!mlNumberOfBlocks) mpxBlock = NULL;
01338 if (!mlNumberOfNodes) mpxFirst = NULL;
01339
01340 return true;
01341
01342 }
01343 else
01344 {
01345 mpxLast->mpxNext = mpxCurrent;
01346 mpxCurrent = mpxLast;
01347 mpxLast = mpxLast->mpxPrevious;
01348 mpxLast->mpxNext= NULL;
01349
01350 mlNumberOfNodes --;
01351 pBlock->soUsed --;
01352 return true;
01353 }
01354
01355 }
01356
01357
01358 LinearBlock<ChainedBS> * pBlock = mpxBlock->Find(pNode);
01359 if (pBlock == NULL) return false;
01360 pBlock->soUsed --;
01361
01362 mbIntegrity = false;
01363
01364 }
01365 else
01366 {
01367 }
01368
01369
01370 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode->mpxNext;
01371 if (pNode->mpxNext!=NULL) pNode->mpxNext->mpxPrevious = pNode->mpxPrevious;
01372
01373
01374 if (pNode == mpxFirst) mpxFirst = pNode->mpxNext;
01375
01376 if (pNode == mpxLast) mpxLast = pNode->mpxPrevious;
01377
01378
01379 if (!mbUseBlocks) delete pNode;
01380 mlNumberOfNodes --;
01381
01385 return true;
01386 }
01387
01388 template <class U, unsigned int pow2>
01389 typename CGufieChainedList<U, pow2>::ChainedNode* CGufieChainedList<U, pow2>::CreateNode()
01390 {
01395 if (mpxCurrent == NULL)
01396 {
01397
01398
01399 LinearBlock<ChainedBS> * pBlock;
01400 if (mpxBlock == NULL)
01401 {
01402 mpxBlock = new LinearBlock<ChainedBS>;
01403 if (mpxBlock==NULL) return NULL;
01404 mpxBLast = mpxBlock;
01405 pBlock = mpxBlock;
01406 }
01407 else
01408 {
01409
01410 if (mpxBlock->soUsed < ChainedBS)
01411 {
01412
01413
01414
01415 ChainedNode * pNode = mpxBlock->GetData();
01416 for (unsigned int i = 0; i < ChainedBS; i++)
01417 {
01418 if (pNode == NULL) return NULL;
01419 if (pNode->mpxNext != (pNode+1))
01420 {
01421
01422 return (pNode+1);
01423 }
01424
01425 pNode ++;
01426 }
01427 return NULL;
01428 }
01429
01430 pBlock = mpxBLast;
01431 if (pBlock->CreateNewBlock()!=true) return NULL;
01432 pBlock = pBlock->spxNext;
01433 mpxBLast = pBlock;
01434 }
01435
01436
01437
01438 ChainedNode * pNode = (ChainedNode*) pBlock->GetData();
01439
01440
01441
01442 for (unsigned int i = 0; i < ChainedBS; i++, pNode++)
01443 {
01444 pNode->mpxPrevious = mpxCurrent;
01445
01446
01447
01448 if (pNode->mpxPrevious!=NULL) pNode->mpxPrevious->mpxNext = pNode;
01449 mpxCurrent = pNode;
01450 }
01451
01452 mpxCurrent -= ChainedBS - 1;
01453
01454
01455 mlNumberOfBlocks ++;
01456
01457 mpxCurrent = mpxCurrent->mpxNext;
01458 return mpxCurrent->mpxPrevious;
01459
01460 }
01461
01462 if (mpxCurrent==NULL) return NULL;
01463
01464
01465 if (mpxCurrent->mpxPrevious == NULL || mpxCurrent->mpxPrevious->mpxNext == mpxCurrent || mpxCurrent->mpxNext == NULL)
01466 {
01467
01468 if (mpxBLast != NULL && mpxBLast->soUsed < ChainedBS)
01469 {
01470
01471 ChainedNode * pNode = mpxBLast->GetData();
01472 for (unsigned int i = 0; i < ChainedBS; i++)
01473 {
01474 if (pNode == NULL) return NULL;
01475 if (pNode->mpxNext != (pNode+1))
01476 {
01477
01478
01479
01480 if ((pNode+1) > (mpxBLast->GetData() + ChainedBS))
01481 {
01482
01483 mpxCurrent = NULL;
01484 return CreateNode();
01485 }
01486 else
01487
01488 {
01489 mpxCurrent = (pNode + 1)->mpxNext;
01490 }
01491
01492 return (pNode+1);
01493 }
01494 pNode ++;
01495 }
01496 }
01497
01498 else
01499 {
01500 mpxCurrent = NULL;
01501 return CreateNode();
01502 }
01503 }
01504
01505 mpxCurrent = mpxCurrent->mpxNext;
01506
01510 return mpxCurrent->mpxPrevious;
01511 }
01512
01513
01514
01515 template <class U, unsigned int pow2>
01516 typename CGufieChainedList<U, pow2>::ChainedNode* CGufieChainedList<U, pow2>::Goto(const unsigned int& pos)
01517 {
01521 if (mpxFirst == NULL) return NULL;
01522
01523 ChainedNode* pT;
01524 if ((mbUseBlocks)&&(mbIntegrity))
01525 {
01526 if (mpxBlock==NULL) return NULL;
01527
01528 unsigned int distinblock = (pos>>pow2);
01529 LinearBlock<ChainedBS> *pBlock = mpxBlock;
01530
01531
01532 for (unsigned int i = 0; i < distinblock; i++)
01533 {
01534 if (pBlock==NULL) return NULL;
01535 pBlock = pBlock->spxNext;
01536 }
01537
01538 pT = pBlock->GetData();
01539 pT += pos - (distinblock<<pow2);
01540
01541 }
01542 else
01543 {
01544 if (pos <= (mlNumberOfNodes>>1))
01545 {
01546
01547 pT = mpxFirst;
01548
01549 for (unsigned int i=0; i<pos; i++)
01550 {
01551 if (pT==NULL) return NULL;
01552 pT = pT->mpxNext;
01553 }
01554 } else
01555 {
01556
01557 pT = mpxLast;
01558
01559 for (unsigned int i=pos+1; i < mlNumberOfNodes; i++)
01560 {
01561 if (pT==NULL) return NULL;
01562 pT = pT->mpxPrevious;
01563 }
01564
01565 }
01566 }
01570 return pT;
01571 }
01572
01573 template <class U, unsigned int pow2>
01574 bool CGufieChainedList<U, pow2>::Change(U & a, const unsigned int & pos)
01575 {
01579 if (mpxFirst == NULL) return false;
01580
01581 if (pos > mlNumberOfNodes) return false;
01582
01583 if (pos == mlNumberOfNodes) Add(a);
01584
01585 ChainedNode* pT = Goto(pos);
01586 if (pT == NULL) return false;
01587
01588 #ifdef ChainedEqual
01589 pT->Get() = a;
01590 #else
01591 if (pT->mpuElement != NULL)
01592 delete pT->mpuElement;
01593
01594 pT->Set(a);
01595 #endif
01596
01600 return true;
01601
01602 }
01603
01604
01605 template <class U, unsigned int pow2>
01606 bool CGufieChainedList<U, pow2>::Free()
01607 {
01611 if (mpxFirst == NULL) return false;
01612
01613 if (mbUseBlocks)
01614 {
01615 if (mpxBlock == NULL) return false;
01616
01617 mpxBlock->DeleteAll();
01618 mpxBlock = NULL;
01619 mpxFirst = mpxLast = mpxCurrent = NULL;
01620 mlNumberOfNodes = 0;
01621 mlNumberOfBlocks = 0;
01622 mbIntegrity = true;
01623 mbUseBlocks = true;
01624
01625 }
01626 else
01627 {
01628 mpxCurrent = mpxFirst;
01629 for (unsigned int i=0; i < mlNumberOfNodes; i++)
01630 {
01631 mpxLast = mpxCurrent->mpxNext;
01632
01633 delete mpxCurrent;
01634
01635 mpxCurrent = mpxLast;
01636 if (mpxCurrent == NULL) return false;
01637 }
01638
01639 mpxFirst = mpxLast = mpxCurrent = NULL;
01640 mlNumberOfNodes = 0;
01641 mbIntegrity = true;
01642
01643 }
01644
01645
01649 return true;
01650 }
01651
01652 template <class U, unsigned int pow2>
01653 U* CGufieChainedList<U, pow2>::ParseList(const bool & bInit)
01654 {
01658 if (mpxFirst == NULL) return NULL;
01659
01660 if (bInit) { mpxCurrent = mpxFirst; return mpxCurrent->mpuElement; }
01661 else if (mpxCurrent!=mpxLast) { mpxCurrent = mpxCurrent->mpxNext; return mpxCurrent->mpuElement; }
01662 else return NULL;
01663
01664
01668
01669 }
01670
01671 template <class U, unsigned int pow2>
01672 U* CGufieChainedList<U, pow2>::ParseListStart(const unsigned int & uiPos)
01673 {
01677 if (uiPos != ChainedEnd) { mpxCurrent = Goto(uiPos); if (mpxCurrent!=NULL) return mpxCurrent->mpuElement; else return NULL; }
01678 else if (mpxCurrent!=NULL) { mpxCurrent = mpxCurrent->mpxNext; return mpxCurrent->mpuElement; }
01679 else return NULL;
01680
01681
01685
01686 }
01687
01688 template <class U, unsigned int pow2>
01689 U* CGufieChainedList<U, pow2>::ReverseParseList(const bool & bInit)
01690 {
01694 if (mpxLast == NULL) return NULL;
01695
01696 if (bInit) { mpxCurrent = mpxLast; return mpxCurrent->mpuElement; }
01697 else if (mpxCurrent!=mpxFirst) { mpxCurrent = mpxCurrent->mpxPrevious; return mpxCurrent->mpuElement; }
01698 else return NULL;
01699
01700
01704
01705 }
01706
01707 template <class U, unsigned int pow2>
01708 U* CGufieChainedList<U, pow2>::ReverseParseListStart(const unsigned int & uiPos)
01709 {
01713 if (uiPos != ChainedEnd) { mpxCurrent = Goto(uiPos); if (mpxCurrent!=NULL) return mpxCurrent->mpuElement; else return NULL; }
01714 else if (mpxCurrent!=NULL) { mpxCurrent = mpxCurrent->mpxPrevious; return mpxCurrent->mpuElement; }
01715 else return NULL;
01716
01717
01721
01722 }
01723
01724
01725
01726
01727
01728 #define h_HPP_GufieChainedList_HPP_h
01729 #endif