00001
00002
00003
00004
00005
00006 #include <streams.h>
00007
00008 #define INTERNALTRAVERSELIST(list, cursor) \
00009 for ( cursor = (list).GetHeadPositionI() \
00010 ; cursor!=NULL \
00011 ; cursor = (list).Next(cursor) \
00012 )
00013
00014 #define INTERNALREVERSETRAVERSELIST(list, cursor) \
00015 for ( cursor = (list).GetTailPositionI() \
00016 ; cursor!=NULL \
00017 ; cursor = (list).Prev(cursor) \
00018 )
00019
00020 CBaseList::CBaseList(TCHAR *pName,
00021 INT iItems) :
00022 #ifdef DEBUG
00023 CBaseObject(pName),
00024 #endif
00025 m_pFirst(NULL),
00026 m_pLast(NULL),
00027 m_Count(0),
00028 m_Cache(iItems)
00029 {
00030 }
00031
00032 CBaseList::CBaseList(TCHAR *pName) :
00033 #ifdef DEBUG
00034 CBaseObject(pName),
00035 #endif
00036 m_pFirst(NULL),
00037 m_pLast(NULL),
00038 m_Count(0),
00039 m_Cache(DEFAULTCACHE)
00040 {
00041 }
00042
00043 #ifdef UNICODE
00044 CBaseList::CBaseList(CHAR *pName,
00045 INT iItems) :
00046 #ifdef DEBUG
00047 CBaseObject(pName),
00048 #endif
00049 m_pFirst(NULL),
00050 m_pLast(NULL),
00051 m_Count(0),
00052 m_Cache(iItems)
00053 {
00054 }
00055
00056 CBaseList::CBaseList(CHAR *pName) :
00057 #ifdef DEBUG
00058 CBaseObject(pName),
00059 #endif
00060 m_pFirst(NULL),
00061 m_pLast(NULL),
00062 m_Count(0),
00063 m_Cache(DEFAULTCACHE)
00064 {
00065 }
00066
00067 #endif
00068
00069 CBaseList::~CBaseList()
00070 {
00071
00072
00073 RemoveAll();
00074
00075 }
00076
00077 void CBaseList::RemoveAll()
00078 {
00079
00080
00081 CNode *pn = m_pFirst;
00082 while (pn) {
00083 CNode *op = pn;
00084 pn = pn->Next();
00085 delete op;
00086 }
00087
00088
00089
00090 m_Count = 0;
00091 m_pFirst = m_pLast = NULL;
00092
00093 }
00094
00095 POSITION CBaseList::GetHeadPositionI() const
00096 {
00097 return (POSITION) m_pFirst;
00098 }
00099
00100 POSITION CBaseList::GetTailPositionI() const
00101 {
00102 return (POSITION) m_pLast;
00103 }
00104
00105 int CBaseList::GetCountI() const
00106 {
00107 return m_Count;
00108 }
00109
00110 void *CBaseList::GetNextI(POSITION& rp) const
00111 {
00112
00113
00114 if (rp == NULL) {
00115 return NULL;
00116 }
00117
00118
00119
00120 void *pObject;
00121
00122
00123
00124 CNode *pn = (CNode *) rp;
00125 ASSERT(pn != NULL);
00126 rp = (POSITION) pn->Next();
00127
00128
00129
00130 pObject = pn->GetData();
00131
00132 return pObject;
00133 }
00134
00135 void *CBaseList::GetI(POSITION p) const
00136 {
00137 if (p == NULL) {
00138 return NULL;
00139 }
00140
00141 CNode * pn = (CNode *) p;
00142 void *pObject = pn->GetData();
00143
00144 return pObject;
00145 }
00146
00147 POSITION CBaseList::FindI( void * pObj) const
00148 {
00149 POSITION pn;
00150 INTERNALTRAVERSELIST(*this, pn){
00151 if (GetI(pn)==pObj) {
00152 return pn;
00153 }
00154 }
00155 return NULL;
00156 }
00157
00158 void *CBaseList::RemoveHeadI()
00159 {
00160
00161
00162 return RemoveI((POSITION)m_pFirst);
00163 }
00164
00165 void *CBaseList::RemoveTailI()
00166 {
00167
00168
00169 return RemoveI((POSITION)m_pLast);
00170 }
00171
00172 void *CBaseList::RemoveI(POSITION pos)
00173 {
00174
00175
00176
00177 if (pos==NULL) return NULL;
00178
00179 CNode *pCurrent = (CNode *) pos;
00180 ASSERT(pCurrent != NULL);
00181
00182
00183
00184 CNode *pNode = pCurrent->Prev();
00185 if (pNode == NULL) {
00186 m_pFirst = pCurrent->Next();
00187 } else {
00188 pNode->SetNext(pCurrent->Next());
00189 }
00190
00191
00192
00193 pNode = pCurrent->Next();
00194 if (pNode == NULL) {
00195 m_pLast = pCurrent->Prev();
00196 } else {
00197 pNode->SetPrev(pCurrent->Prev());
00198 }
00199
00200
00201
00202 void *pObject = pCurrent->GetData();
00203
00204
00205
00206
00207
00208 m_Cache.AddToCache(pCurrent);
00209
00210
00211
00212 --m_Count;
00213 ASSERT(m_Count >= 0);
00214 return pObject;
00215 }
00216
00217 POSITION CBaseList::AddTailI(void *pObject)
00218 {
00219
00220
00221 CNode *pNode;
00222
00223
00224
00225
00226 pNode = (CNode *) m_Cache.RemoveFromCache();
00227 if (pNode == NULL) {
00228 pNode = new CNode;
00229 }
00230
00231
00232
00233 if (pNode == NULL) {
00234 return NULL;
00235 }
00236
00237
00238
00239 pNode->SetData(pObject);
00240 pNode->SetNext(NULL);
00241 pNode->SetPrev(m_pLast);
00242
00243 if (m_pLast == NULL) {
00244 m_pFirst = pNode;
00245 } else {
00246 m_pLast->SetNext(pNode);
00247 }
00248
00249
00250
00251 m_pLast = pNode;
00252 ++m_Count;
00253
00254 return (POSITION) pNode;
00255 }
00256
00257 POSITION CBaseList::AddHeadI(void *pObject)
00258 {
00259 CNode *pNode;
00260
00261
00262
00263
00264 pNode = (CNode *) m_Cache.RemoveFromCache();
00265 if (pNode == NULL) {
00266 pNode = new CNode;
00267 }
00268
00269
00270
00271 if (pNode == NULL) {
00272 return NULL;
00273 }
00274
00275
00276
00277 pNode->SetData(pObject);
00278
00279
00280 pNode->SetPrev(NULL);
00281 pNode->SetNext(m_pFirst);
00282
00283 if (m_pFirst == NULL) {
00284 m_pLast = pNode;
00285 } else {
00286 m_pFirst->SetPrev(pNode);
00287 }
00288 m_pFirst = pNode;
00289
00290 ++m_Count;
00291
00292 return (POSITION) pNode;
00293 }
00294
00295 BOOL CBaseList::AddTail(CBaseList *pList)
00296 {
00297
00298 POSITION pos = pList->GetHeadPositionI();
00299
00300 while (pos) {
00301 if (NULL == AddTailI(pList->GetNextI(pos))) {
00302 return FALSE;
00303 }
00304 }
00305 return TRUE;
00306 }
00307
00308 BOOL CBaseList::AddHead(CBaseList *pList)
00309 {
00310
00311
00312 POSITION pos;
00313
00314 INTERNALREVERSETRAVERSELIST(*pList, pos) {
00315 if (NULL== AddHeadI(pList->GetI(pos))){
00316 return FALSE;
00317 }
00318 }
00319 return TRUE;
00320 }
00321
00322 POSITION CBaseList::AddAfterI(POSITION pos, void * pObj)
00323 {
00324 if (pos==NULL)
00325 return AddHeadI(pObj);
00326
00327
00328 CNode *pAfter = (CNode *) pos;
00329 ASSERT(pAfter != NULL);
00330 if (pAfter==m_pLast)
00331 return AddTailI(pObj);
00332
00333
00334
00335 CNode *pNode = (CNode *) m_Cache.RemoveFromCache();
00336 if (pNode == NULL) {
00337 pNode = new CNode;
00338 }
00339
00340
00341
00342 if (pNode == NULL) {
00343 return NULL;
00344 }
00345
00346
00347
00348 pNode->SetData(pObj);
00349
00350
00351 CNode * pBefore = pAfter->Next();
00352 ASSERT(pBefore != NULL);
00353
00354
00355 pNode->SetPrev(pAfter);
00356 pNode->SetNext(pBefore);
00357 pBefore->SetPrev(pNode);
00358 pAfter->SetNext(pNode);
00359
00360 ++m_Count;
00361
00362 return (POSITION) pNode;
00363
00364 }
00365
00366 BOOL CBaseList::AddAfter(POSITION p, CBaseList *pList)
00367 {
00368 POSITION pos;
00369 INTERNALTRAVERSELIST(*pList, pos) {
00370
00371 p = AddAfterI(p, pList->GetI(pos));
00372 if (p==NULL) return FALSE;
00373 }
00374 return TRUE;
00375 }
00376
00377 POSITION CBaseList::AddBeforeI(POSITION pos, void * pObj)
00378 {
00379 if (pos==NULL)
00380 return AddTailI(pObj);
00381
00382
00383
00384 CNode *pBefore = (CNode *) pos;
00385 ASSERT(pBefore != NULL);
00386 if (pBefore==m_pFirst)
00387 return AddHeadI(pObj);
00388
00389 CNode * pNode = (CNode *) m_Cache.RemoveFromCache();
00390 if (pNode == NULL) {
00391 pNode = new CNode;
00392 }
00393
00394
00395
00396 if (pNode == NULL) {
00397 return NULL;
00398 }
00399
00400
00401
00402 pNode->SetData(pObj);
00403
00404
00405
00406 CNode * pAfter = pBefore->Prev();
00407 ASSERT(pAfter != NULL);
00408
00409
00410 pNode->SetPrev(pAfter);
00411 pNode->SetNext(pBefore);
00412 pBefore->SetPrev(pNode);
00413 pAfter->SetNext(pNode);
00414
00415 ++m_Count;
00416
00417 return (POSITION) pNode;
00418
00419 }
00420
00421 BOOL CBaseList::AddBefore(POSITION p, CBaseList *pList)
00422 {
00423 POSITION pos;
00424 INTERNALREVERSETRAVERSELIST(*pList, pos) {
00425
00426 p = AddBeforeI(p, pList->GetI(pos));
00427 if (p==NULL) return FALSE;
00428 }
00429 return TRUE;
00430 }
00431
00432 BOOL CBaseList::MoveToTail
00433 (POSITION pos, CBaseList *pList)
00434 {
00435
00436
00437 if (pos==NULL) return TRUE;
00438
00439
00440 CNode * p = (CNode *)pos;
00441 int cMove = 0;
00442 while(p!=NULL) {
00443 p = p->Prev();
00444 ++cMove;
00445 }
00446
00447
00448 if (pList->m_pLast!=NULL)
00449 pList->m_pLast->SetNext(m_pFirst);
00450 if (m_pFirst!=NULL)
00451 m_pFirst->SetPrev(pList->m_pLast);
00452
00453
00454 p = (CNode *)pos;
00455
00456 if (pList->m_pFirst==NULL)
00457 pList->m_pFirst = m_pFirst;
00458 m_pFirst = p->Next();
00459 if (m_pFirst==NULL)
00460 m_pLast = NULL;
00461 pList->m_pLast = p;
00462
00463
00464 if (m_pFirst!=NULL)
00465 m_pFirst->SetPrev(NULL);
00466 p->SetNext(NULL);
00467
00468
00469 m_Count -= cMove;
00470 pList->m_Count += cMove;
00471
00472 return TRUE;
00473
00474 }
00475
00476 BOOL CBaseList::MoveToHead
00477 (POSITION pos, CBaseList *pList)
00478 {
00479
00480
00481
00482 if (pos==NULL) return TRUE;
00483
00484
00485 CNode * p = (CNode *)pos;
00486 int cMove = 0;
00487 while(p!=NULL) {
00488 p = p->Next();
00489 ++cMove;
00490 }
00491
00492
00493 if (pList->m_pFirst!=NULL)
00494 pList->m_pFirst->SetPrev(m_pLast);
00495 if (m_pLast!=NULL)
00496 m_pLast->SetNext(pList->m_pFirst);
00497
00498
00499 p = (CNode *)pos;
00500
00501 if (pList->m_pLast==NULL)
00502 pList->m_pLast = m_pLast;
00503
00504 m_pLast = p->Prev();
00505 if (m_pLast==NULL)
00506 m_pFirst = NULL;
00507 pList->m_pFirst = p;
00508
00509
00510 if (m_pLast!=NULL)
00511 m_pLast->SetNext(NULL);
00512 p->SetPrev(NULL);
00513
00514
00515 m_Count -= cMove;
00516 pList->m_Count += cMove;
00517
00518 return TRUE;
00519
00520 }
00521
00522 void CBaseList::Reverse()
00523 {
00524
00525 CNode * p;
00526
00527
00528 p = m_pFirst;
00529 while (p!=NULL) {
00530 CNode * q;
00531 q = p->Next();
00532 p->SetNext(p->Prev());
00533 p->SetPrev(q);
00534 p = q;
00535 }
00536
00537 p = m_pFirst;
00538 m_pFirst = m_pLast;
00539 m_pLast = p;
00540
00541 #if 0
00542
00543 if (m_pFirst==NULL) return;
00544 if (m_pFirst->Next()==NULL) return;
00545
00546
00547 for ( p = m_pFirst
00548 ; p!=NULL
00549 ; p = p->Next()
00550 ){
00551 p->SetPrev(p->Next());
00552 }
00553
00554
00555 m_pFirst->SetNext(NULL);
00556
00557
00558 for ( p = m_pFirst
00559 ; p->Prev()!=NULL
00560 ; p = p->Prev()
00561 ){
00562 p->Prev()->SetNext(p);
00563 }
00564
00565
00566 p = m_pFirst;
00567 m_pFirst = m_pLast;
00568 m_pLast = p;
00569 #endif
00570
00571 }
