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