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
00027
#ifndef DLIST_H
00028
#define DLIST_H
00029
00030
#define VDKListIterator VDKListiterator
00031
00032
00033
00034
00035
00036
00037
template <
class T>
class VDKItem
00038 {
00039
00040
public:
00041 T* x;
00042 VDKItem* next,*prev;
00043 VDKItem(T* x): x(x), next((VDKItem<T>*) 0),prev((VDKItem<T>*)0)
00044 {
00045 }
00046 ~VDKItem()
00047 {
00048 }
00049 };
00064 template <
class T>
class VDKList
00065 {
00066
00067 VDKItem<T>* head,* tail;
00068
int count;
00069
00070
00071
void addToTail(VDKItem<T>* i)
00072 {
00073
if(! head) head = tail = i;
00074
else { tail->next = i; i->prev=tail; tail = i; }
00075 count++;
00076 }
00077
00078
void addToHead(VDKItem<T>* i)
00079 {
00080
if(! head) head = tail = i;
00081
else { head->prev = i; i->next = head; head = i; }
00082 count++;
00083 }
00084
00085
void insertVDKItem(VDKItem<T>* i,
int pos);
00086
00087
00088 VDKItem<T>* fetch(
int n);
00089
00090
00091
void assign(
VDKList& l);
00092
00093
VDKList(
VDKList& c)
00094 {
00095 count = 0;
00096 head = tail = (VDKItem<T>* ) 0;
00097 assign(c);
00098 }
00099
00100
VDKList& operator=(
VDKList<T>& l)
00101 {
00102
00103
if(
this != &l) {
flush(); assign(l); }
00104
return *
this;
00105 }
00106
00107
00108
public:
00112 VDKList() : head(0),tail(0),count(0) {}
00123 ~VDKList() {
flush(); }
00129 void add(T* t)
00130 {
00131
if(!find(t))
00132 addToTail(
new VDKItem<T>(t));
00133 }
00139
void addH(T* t)
00140 {
00141
if(! find(t))
00142 addToHead(
new VDKItem<T>(t));
00143 }
00150 void insertAt(T* t,
int pos)
00151 {
00152
if(!find(t))
00153 insertVDKItem(
new VDKItem<T>(t),pos);
00154 }
00159 T* find(T* x);
00163 T* listhead() {
return fetch(0)->x; }
00168
int at(T* x);
00172 T* operator[](
int n) {
return fetch(n)->x; }
00177
int remove(T* x);
00181 int size() {
return count; }
00185
void flush();
00189 VDKItem<T>* Head() {
return head; }
00193 VDKItem<T>* Tail() {
return tail; }
00194 };
00195
00200 template <
class T>
class VDKListiterator
00201 {
00202
00203 VDKItem<T> *head,*tail,*p;
00204
public:
00209 VDKListiterator(
VDKList<T>& c) { p = head = c.
Head(); tail = c.
Tail(); }
00213 virtual ~VDKListiterator() {}
00217 void operator++() { p = p->next; }
00221 void operator++(
int) { p = p->next; }
00225 void operator--() { p = p->prev; }
00229 void operator--(
int) { p = p->prev; }
00233 void first() { p = head; }
00237 void last() { p = tail; }
00241 operator int() {
return p != (VDKItem<T>*) 0; }
00245 T*
current() {
return p->x; }
00249 VDKItem<T>* Next(VDKItem<T> *t) {
return t->next;}
00253 VDKItem<T>* Head() {
return head; }
00257 T* Now(VDKItem<T> * t) {
return t->x; }
00261 void restart() { p = head; }
00262 };
00263
00264
00265
00266
00267
00268
00269
00270
template <
class T>
00271
void VDKList<T>::assign(
VDKList<T>& l)
00272 {
00273
VDKListiterator<T> ci(l);
00274
while(ci) { add(ci.
current()); ci++; }
00275 }
00276
00277
00278
00279
00280
00281
template <
class T>
00282 VDKItem<T>*
VDKList<T>::fetch(
int n) {
00283
int t = 0;
00284
if(n >= count || n < 0) return (VDKItem<T>*) 0;
00285 VDKItem<T>* p = head;
00286
for( ;p && (t < n) ; t++, p = p->next);
00287
return p;
00288 }
00289
00290
00291
00292
00293
00294
00295
template <
class T>
00296 int VDKList<T>::at(T* x) {
00297
register int t = 0;
00298 VDKItem<T>* p = head;
00299
for(; p && (p->x != x);p = p->next,t++) ;
00300
return p ? t : -1;
00301 }
00302
00303
00304
00305
template <
class T>
00306 void VDKList<T>::flush()
00307 {
00308 VDKItem<T>*p = head;
00309 VDKItem<T>*p1;
00310
while(p) {
00311 p1 = p->next;
00312
delete p;
00313 p = p1;
00314 }
00315 head = tail = 0;
00316 count = 0;
00317 }
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
template <
class T>
00328 T*
VDKList<T>::find(T* x) {
00329 VDKItem<T>* p;
00330
for(p = head; p && (p->x != x); p = p->next) ;
00331
return p ? p->x : (T*) 0;
00332 }
00333
00334
00335
00336
00337
00338
00339
00340
template <
class T>
00341 int VDKList<T>::remove(T* x)
00342 {
00343 VDKItem<T>* cur;
00344
int n =
at(x);
00345
00346
if(n < 0)
return 0;
00347
else cur = fetch(n);
00348
00349
if(cur == head) {
00350 head = cur->next;
00351
00352
if(head != (VDKItem<T>*) 0) head->prev = (VDKItem<T>*) 0;
00353
else tail = (VDKItem<T>*) 0;
00354 }
00355
else {
00356 cur->prev->next = cur->next;
00357
if(cur != tail) cur->next->prev = cur->prev;
00358
00359
else tail = cur->prev;
00360 }
00361
delete cur;
00362 count--;
00363
return 1;
00364 }
00365
00366
00367
00368
template <
class T>
00369
void VDKList<T>::insertVDKItem(VDKItem<T>* i,
int pos)
00370 {
00371
int t = 0;
00372 VDKItem<T>* p = NULL;
00373
for(p = head; p && t < pos; p=p->next,t++)
00374 ;
00375
if(!p)
00376 addToTail(i);
00377
else if(p->prev)
00378 {
00379 p->prev->next = i;
00380 i->prev = p->prev;
00381 p->prev = i;
00382 i->next = p;
00383 count++;
00384 }
00385
else
00386 addToHead(i);
00387 }
00388
00389
#endif
00390
00391
00392
00393
00394