00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #include <limits.h>
00027
00028 #include "listt_i.hpp"
00029
00030
00031
00032 _PList& _PList::_create_d(const _PList& a)
00033 {
00034 if (h != a.h) { clear(); _append_d(a); }
00035 return *this;
00036 }
00037
00038
00039
00040 _PList& _PList::_create_p(_PList& a)
00041 {
00042 if (h != a.h) { clear(); _append_p(a); }
00043 return *this;
00044 }
00045
00046
00047
00048 BOOL _PList::OK(VOID) const
00049 {
00050 BOOL v = TRUE;
00051 if (h != 0) {
00052 _PListNode* t = h;
00053 long count = LONG_MAX;
00054 do {
00055 count--;
00056 v &= t->b->f == t;
00057 v &= t->f->b == t;
00058 t = t->f;
00059 } while (v && count > 0 && t != h);
00060 v &= count > 0;
00061 }
00062 return v;
00063 }
00064
00065
00066
00067 BOOL _PList::owns(Lix p) const
00068 {
00069 _PListNode* t = h;
00070 if (t != 0 && p != 0) {
00071 do {
00072 if (Lix(t) == p)
00073 return TRUE;
00074 t = t->f;
00075 } while (t != h);
00076 }
00077 return FALSE;
00078 }
00079
00080
00081
00082 LIINT _PList::index (Lix p) const
00083 {
00084 _PListNode* t = h;
00085 if ((p!=0) && (t!=0)) {
00086 LIINT l = 0;
00087 do {
00088 if (Lix(t) == p)
00089 return l;
00090 l++;
00091 t = t->f;
00092 } while (t != h);
00093 }
00094 LISTVERIFY(p,"index");
00095 return -1;
00096 }
00097
00098
00099
00100 Lix _PList::lix( LIINT i ) const
00101 {
00102 _PListNode* t = h;
00103 if (t != 0) do { if ((i--)==0) return t; t = t->f; } while (t != h);
00104 return 0;
00105 }
00106
00107
00108
00109 LIINT _PList::length(VOID) const
00110 {
00111 LIINT l = 0;
00112 _PListNode* t = h;
00113 if (t != 0) do { ++l; t = t->f; } while (t != h);
00114 return l;
00115 }
00116
00117
00118
00119 VOID _PList::reverse(VOID)
00120 {
00121 if (h != 0) {
00122 _PListNode* w;
00123 _PListNode* t = h;
00124 do { __SWAP__(t->b,t->f,w); t=t->b; } while (t!=h);
00125 h = t->f;
00126 }
00127 }
00128
00129
00130
00131 Lix _PList::_prepend_d(const _PList& a)
00132 {
00133 for (Lix p=a.last(); p!=0; p=a.prev(p))
00134 __prepend(__newNode_d(a.__getNode(p)));
00135 return first();
00136 }
00137
00138
00139
00140 Lix _PList::_append_d(const _PList& a)
00141 {
00142 for (Lix p=a.first(); p!=0; p=a.next(p))
00143 __append(__newNode_d(a.__getNode(p)));
00144 return last();
00145 }
00146
00147
00148
00149 Lix _PList::_insbefore_d(Lix p, const _PList& a)
00150 {
00151 if (p == 0) return _append_d(a);
00152 LISTVERIFY(p,"_insbefore_d");
00153 for (Lix q=a.last(); q!=0; q=a.prev(q))
00154 p=__insbefore(p,__newNode_d(a.__getNode(q)));
00155 return p;
00156 }
00157
00158
00159
00160 Lix _PList::_insafter_d(Lix p, const _PList& a)
00161 {
00162 if (p == 0) return _prepend_d(a);
00163 LISTVERIFY(p,"_insafter_d");
00164 for (Lix q=a.first(); q!=0; q=a.next(q))
00165 p=__insafter(p,__newNode_d(a.__getNode(q)));
00166 return p;
00167 }
00168
00169
00170
00171 Lix _PList::_prepend_p(_PList& a)
00172 {
00173 for (Lix p=a.last(); p!=0; p=a.prev(p))
00174 __prepend(__newNode_p((_PListNode*)a.__getNode(p)));
00175 return first();
00176 }
00177
00178
00179
00180 Lix _PList::_append_p(_PList& a)
00181 {
00182 for (Lix p=a.first(); p!=0; p=a.next(p))
00183 __append(__newNode_p((_PListNode*)a.__getNode(p)));
00184 return last();
00185 }
00186
00187
00188
00189 Lix _PList::_insbefore_p(Lix p, _PList& a)
00190 {
00191 if (p == 0) return _append_p(a);
00192 LISTVERIFY(p,"_insbefore_p");
00193 for (Lix q=a.last(); q!=0; q=a.prev(q))
00194 p=__insbefore(p,__newNode_p((_PListNode*)a.__getNode(q)));
00195 return p;
00196 }
00197
00198
00199
00200 Lix _PList::_insafter_p(Lix p, _PList& a)
00201 {
00202 if (p == 0) return _prepend_p(a);
00203 LISTVERIFY(p,"_insafter_p");
00204 for (Lix q=a.first(); q!=0; q=a.next(q))
00205 p=__insafter(p,__newNode_p((_PListNode*)a.__getNode(q)));
00206 return p;
00207 }
00208
00209
00210
00211 Lix _PList::_prepend_mv(_PList& a, Lix ni, Lix nf )
00212 {
00213 _PListNode* t1 = (_PListNode*)(ni?ni:a.h);
00214 _PListNode* t2 = (_PListNode*)(nf?nf: a.h?a.h->b:0);
00215 #ifdef LIST_PTRVERIFY
00216 XLISTVERIFY(a,(Lix)t1,"_prepend_mv");
00217 XLISTVERIFY(a,(Lix)t2,"_prepend_mv");
00218 if (t1 && t2) assert(a.index(t1)<=a.index(t2));
00219 #endif
00220 if (t1->b == t2) a.h = 0;
00221 else {
00222 t1->b->f = t2->f;
00223 t2->f->b = t1->b;
00224 if (a.h==t1) a.h=t2->f;
00225 }
00226
00227 if (t1 && t2) {
00228 if (h==0) {
00229 h = t1;
00230 t1->b=t2;
00231 t2->f=t1;
00232 }
00233 else {
00234 t1->b = h->b;
00235 h->b->f=t1;
00236 t2->f = h;
00237 h->b=t2;
00238 h=t1;
00239 }
00240 }
00241 return Lix(h);
00242 }
00243
00244 #ifdef ORI
00245 Lix _PList::_prepend_mv(_PList& a )
00246 {
00247 _PListNode* t = a.h;
00248 a.h = 0;
00249 if (h == 0)
00250 h = t;
00251 else if (t != 0) {
00252 _PListNode* l = h->b;
00253 t->b->f = h;
00254 h->b = t->b;
00255 t->b = l;
00256 l->f = t;
00257 h = t;
00258 }
00259 return Lix(h);
00260 }
00261 #endif
00262
00263
00264
00265 Lix _PList::_append_mv(_PList& a, Lix ni, Lix nf )
00266 {
00267 _PListNode* t1 = (_PListNode*)(ni?ni:a.h);
00268 _PListNode* t2 = (_PListNode*)(nf?nf: a.h?a.h->b:0);
00269 #ifdef LIST_PTRVERIFY
00270 XLISTVERIFY(a,(Lix)t1,"_append_mv");
00271 XLISTVERIFY(a,(Lix)t2,"_append_mv");
00272 if (t1 && t2) assert(a.index(t1)<=a.index(t2));
00273 #endif
00274 if (t1->b == t2) a.h = 0;
00275 else {
00276 t1->b->f = t2->f;
00277 t2->f->b = t1->b;
00278 if (a.h==t1) a.h=t2->f;
00279 }
00280
00281 if (t1 && t2) {
00282 if (h==0) {
00283 h = t1;
00284 t1->b=t2;
00285 t2->f=t1;
00286 }
00287 else {
00288 t1->b = h->b;
00289 h->b->f=t1;
00290 t2->f = h;
00291 h->b=t2;
00292 }
00293 }
00294 return Lix(h->b);
00295 }
00296
00297 #ifdef ORI
00298 Lix _PList::_append_mv(_PList& a)
00299 {
00300 _PListNode* t = a.h;
00301 a.h = 0;
00302 if (h == 0)
00303 h = t;
00304 else if (t != 0) {
00305 _PListNode* l = t->b;
00306 h->b->f = t;
00307 t->b = h->b;
00308 h->b = l;
00309 l->f = h;
00310 }
00311 return Lix(h->b);
00312 }
00313 #endif
00314
00315
00316
00317 Lix _PList::_insbefore_mv(Lix p, _PList& a, Lix ni, Lix nf )
00318 {
00319 if (p==0) return _append_mv(a,ni,nf);
00320 LISTVERIFY(p,"_insbefore_mv");
00321 if ((p==h)||(!h)) return _prepend_mv(a);
00322
00323 _PListNode* t1 = (_PListNode*)(ni?ni:a.h);
00324 _PListNode* t2 = (_PListNode*)(nf?nf: a.h?a.h->b:0);
00325 #ifdef LIST_PTRVERIFY
00326 XLISTVERIFY(a,(Lix)t1,"_insbefore_mv");
00327 XLISTVERIFY(a,(Lix)t2,"_insbefore_mv");
00328 if (t1 && t2) assert(a.index(t1)<=a.index(t2));
00329 #endif
00330 if (t1->b == t2) a.h = 0;
00331 else {
00332 t1->b->f = t2->f;
00333 t2->f->b = t1->b;
00334 if (a.h==t1) a.h=t2->f;
00335 }
00336
00337 if (t1 && t2) {
00338 _PListNode* l = (_PListNode*)p;
00339 t1->b = l->b;
00340 t2->f = l;
00341 l->b->f=t1;
00342 l->b=t2;
00343 }
00344
00345 return Lix(t1);
00346 }
00347
00348 #ifdef ORI
00349 Lix _PList::_insbefore_mv(Lix p, _PList& a)
00350 {
00351 if (p == 0) return _append_mv(a);
00352 LISTVERIFY(p,"_insbefore_p");
00353 if (p==h) return _prepend_mv(a);
00354 _PListNode* t = a.h;
00355 a.h = 0;
00356 if (h == 0) {
00357 h = t;
00358 return Lix(h);
00359 }
00360 else if (t != 0) {
00361 _PListNode* l = ((_PListNode*)p)->b;
00362 t->b->f = (_PListNode*)p;
00363 ((_PListNode*)p)->b = t->b;
00364 t->b = l;
00365 l->f = t;
00366 }
00367 return Lix(t);
00368 }
00369 #endif
00370
00371
00372
00373 Lix _PList::_insafter_mv(Lix p, _PList& a, Lix ni, Lix nf )
00374 {
00375 if (p==0) return _prepend_mv(a,ni,nf);
00376 LISTVERIFY(p,"_insafter_mv");
00377 if (!h) return _append_mv(a);
00378
00379 _PListNode* t1 = (_PListNode*)(ni?ni:a.h);
00380 _PListNode* t2 = (_PListNode*)(nf?nf: a.h?a.h->b:0);
00381 #ifdef LIST_PTRVERIFY
00382 XLISTVERIFY(a,(Lix)t1,"_insafter_mv");
00383 XLISTVERIFY(a,(Lix)t2,"_insafter_mv");
00384 if (t1 && t2) assert(a.index(t1)<=a.index(t2));
00385 #endif
00386 if (t1->b == t2) a.h = 0;
00387 else {
00388 t1->b->f = t2->f;
00389 t2->f->b = t1->b;
00390 if (a.h==t1) a.h=t2->f;
00391 }
00392
00393 if (t1 && t2) {
00394 _PListNode* l = (_PListNode*)p;
00395 t1->b = l;
00396 t2->f = l->f;
00397 l->f->b=t2;
00398 l->f=t1;
00399 }
00400
00401 return Lix(t2);
00402 }
00403
00404 #ifdef ORI
00405 Lix _PList::_insafter_mv(Lix p, _PList& a)
00406 {
00407 if (p==0) return _prepend_mv(a);
00408 LISTVERIFY(p,"_insafter_p");
00409 _PListNode* t = a.h;
00410 a.h = 0;
00411 if (h == 0) {
00412 h = t;
00413 return Lix(h->b);
00414 }
00415 else if (t != 0) {
00416 Lix tb = t->b;
00417 ((_PListNode*)p)->f->b = t->b;
00418 t->b->f = ((_PListNode*)p)->f;
00419 t->b = (_PListNode*)p;
00420 ((_PListNode*)p)->f = t;
00421 return tb;
00422 }
00423 return 0;
00424 }
00425 #endif
00426
00427
00428
00429 Lix _PList::_del(Lix p, BOOL cdata, INT dir)
00430 {
00431 Lix q= __del(p,dir);
00432 if (cdata) __deleteNode_d((_PListNode *)p);
00433 else __deleteNode_p((_PListNode *)p);
00434 return q;
00435 }
00436
00437
00438
00439 VOID _PList::_delnext(Lix p, BOOL cdata)
00440 {
00441 if (!p) { _delfirst(cdata); return; }
00442 p=next(p);
00443 if (!p) { LISTERROR("_delnext","empty tail"); }
00444 else _del(p,cdata);
00445 }
00446
00447
00448
00449 VOID _PList::_delprev(Lix p, BOOL cdata)
00450 {
00451 if (!p) { _dellast(cdata); return; }
00452 p=prev(p);
00453 if (!p) { LISTERROR("_delprev","empty front"); }
00454 else _del(p,cdata);
00455 }
00456
00457
00458
00459 Lix _PList::_delfirst(BOOL cdata)
00460 {
00461 if (!h) {
00462 LISTERROR("_delfirst","empty list");
00463 return 0;
00464 }
00465 _del(first(),cdata);
00466 return h->f;
00467 }
00468
00469
00470
00471 Lix _PList::_dellast(BOOL cdata)
00472 {
00473 if (!h) {
00474 LISTERROR("_dellast","empty list");
00475 return 0;
00476 }
00477 _del(last(),cdata);
00478 return h->b;
00479 }
00480
00481
00482
00483 #ifdef LIST_PTRVERIFY
00484 Lix _PList::next(Lix p) const { if (p == 0 || p == h->b) return 0; LISTVERIFY(p,"next"); return Lix(((_PListNode*)p)->f); }
00485 Lix _PList::prev(Lix p) const { if (p == 0 || p == h) return 0; LISTVERIFY(p,"prev"); return Lix(((_PListNode*)p)->b); }
00486 const VOID *_PList::_item(Lix p) const { if (p == 0) { LISTNONULL(p,"_item"); return 0; }; LISTVERIFY(p,"_item"); return ((_PListNode*)p)->dp; }
00487 const VOID *_PList::_item_first(VOID) const { if (h == 0) { LISTERROR("_item_first","empty list"); return 0; }; return h->dp; }
00488 const VOID *_PList::_item_last(VOID) const { if (h == 0) { LISTERROR("_item_last","empty list"); return 0; }; return h->b->dp; }
00489 #endif
00490
00491
