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
00046 #ifndef VALUE_SEM_LIST_H
00047 #define VALUE_SEM_LIST_H
00048 #include <assert.h>
00049 #define nihil (VDKValueItem<T>*) 0
00050
00051
00052
00053
00054 template <class T> class VDKValueList;
00055 template <class T> class VDKValueListIterator;
00056
00061 template <class T>
00062 class VDKValueItem
00063 {
00064 friend class VDKValueList<T>;
00065 friend class VDKValueListIterator<T>;
00066 T data;
00067 VDKValueItem *next,*prev;
00068 VDKValueItem(const T& data): data(data),next(nihil),prev(nihil)
00069 {
00070 }
00071 ~VDKValueItem()
00072 {
00073 }
00074 };
00075
00076
00077
00078
00079
00080 template <class T>
00081 class VDKValueList
00082 {
00083
00084 protected:
00085 VDKValueItem<T> *head,*tail;
00086 int count;
00087
00088 public:
00092 VDKValueList():head(nihil),tail(nihil),count(0) {}
00096 VDKValueList(const VDKValueList<T>& l);
00100 VDKValueList<T>& operator=(const VDKValueList<T>& l);
00104 virtual ~VDKValueList();
00108 void add(const T& t);
00112 void push( const T& t);
00117 int insert( const T& t, bool unique = false);
00121 void flush();
00125 T& operator[](int n);
00130 T* find(T& t);
00134 int size() { return count; }
00139 bool unlink(int ndx);
00143 int at(T& t);
00144
00145 protected:
00146 friend class VDKValueListIterator<T>;
00147 void assign(const VDKValueList<T>& l);
00148 VDKValueItem<T>* fetch(int n);
00149 void addToTail(VDKValueItem<T>* i);
00150 void addToHead(VDKValueItem<T>* i);
00151 int insertVDKValueItem(VDKValueItem<T>* i, bool unique);
00152
00153 };
00178 template <class T>
00179 class VDKValueListIterator
00180 {
00181 VDKValueItem<T>* head,*tail,*p;
00182 public:
00186 VDKValueListIterator():head(nihil),tail(nihil),p(nihil) {}
00191 VDKValueListIterator(const VDKValueList<T>& l):
00192 head(l.head),tail(l.tail),p(l.head) {}
00196 virtual ~VDKValueListIterator() {}
00200 void operator++() { p = p->next; }
00204 void operator++(int) { p = p->next; }
00208 void operator--() { p = p->prev; }
00212 void operator--(int) { p = p->prev; }
00216 void first() { p = head; }
00220 void last() { p = tail; }
00224 operator int() { return p != nihil; }
00228 T& current() { return p->data; }
00232 void restart() { p = head; }
00233 };
00234
00235
00236
00237
00238
00239 template <class T>
00240 VDKValueList<T>::VDKValueList(const VDKValueList<T>& l)
00241 {
00242 count = 0;
00243 head = tail = nihil;
00244 assign(l);
00245 }
00246
00247
00248
00249 template <class T>
00250 VDKValueList<T>& VDKValueList<T>::operator=(const VDKValueList<T>& l)
00251 {
00252 if(this != &l)
00253 {
00254 flush();
00255 assign(l);
00256 }
00257 return *this;
00258 }
00259
00260
00261
00262 template <class T>
00263 VDKValueList<T>::~VDKValueList()
00264 {
00265 flush();
00266 }
00267
00268
00269
00270 template <class T>
00271 void VDKValueList<T>::flush()
00272 {
00273 VDKValueItem<T>* p = head;
00274 VDKValueItem<T>* p1;
00275 while(p)
00276 {
00277 p1 = p->next;
00278 delete p;
00279 p = p1;
00280 }
00281 head = tail = nihil;
00282 count = 0;
00283 }
00284
00285
00286
00287 template <class T>
00288 void VDKValueList<T>::add( const T& t)
00289 {
00290 addToTail(new VDKValueItem<T>(t));
00291 }
00292
00293
00294
00295 template <class T>
00296 void VDKValueList<T>::push(const T& t)
00297 {
00298 addToHead(new VDKValueItem<T>(t));
00299 }
00300
00301
00302
00303 template <class T>
00304 int VDKValueList<T>::insert(const T& t, bool unique)
00305 {
00306
00307 return insertVDKValueItem(new VDKValueItem<T>(t), unique);
00308 }
00309
00310
00311
00312 template <class T>
00313 T& VDKValueList<T>::operator[](int n)
00314 {
00315 assert(n<count);
00316 return fetch(n)->data;
00317 }
00318
00319
00320
00321 template <class T>
00322 T* VDKValueList<T>::find(T& t)
00323 {
00324 VDKValueItem<T>* p = head;
00325 for(; p && !(p->data == t); p = p->next);
00326 return p ? &(p->data): (T*) 0;
00327 }
00328
00329
00330 template <class T>
00331 int
00332 VDKValueList<T>::at(T& x) {
00333 int t = 0;
00334 VDKValueItem<T>* p = head;
00335 for(; p && !(p->data == x);p = p->next,t++) ;
00336 return p ? t : -1;
00337 }
00338
00339
00340 template <class T>
00341 bool
00342 VDKValueList<T>::unlink(int ndx)
00343 {
00344 VDKValueItem<T> *x = fetch(ndx);
00345 if(!x) return false;
00346 if(x->prev != nihil)
00347 x->prev->next = x->next;
00348 else
00349 head = x->next;
00350 if(x->next != nihil)
00351 x->next->prev = x->prev;
00352 else
00353 tail = x->prev;
00354 count--;
00355 delete x;
00356 return true;
00357 }
00358
00359
00360
00361
00362
00363 template <class T>
00364 void VDKValueList<T>::assign(const VDKValueList<T>& l)
00365 {
00366 for(VDKValueListIterator<T> li(l);li;li++)
00367 add(li.current());
00368 }
00369
00370
00371
00372
00373 template <class T>
00374 VDKValueItem<T>* VDKValueList<T>::fetch(int n)
00375 {
00376 int t = 0;
00377 VDKValueItem<T>* p ;
00378 for(p = head; p && (t<n); t++, p = p->next);
00379 return p;
00380 }
00381
00382
00383
00384
00385 template <class T>
00386 void VDKValueList<T>::addToTail(VDKValueItem<T>* i)
00387 {
00388 if(! head) head = tail = i;
00389 else { tail->next = i; i->prev = tail; tail = i; }
00390 count++;
00391 }
00392
00393
00394
00395
00396 template <class T>
00397 void VDKValueList<T>::addToHead(VDKValueItem<T>* i)
00398 {
00399 if(! head) head = tail = i;
00400 else { head->prev = i; i->next = head; head = i; }
00401 count++;
00402 }
00403
00404
00405
00406
00407
00408 template <class T>
00409 int VDKValueList<T>::insertVDKValueItem(VDKValueItem<T>* i,
00410 bool unique)
00411 {
00412 VDKValueItem<T>* p;
00413 int t=0;
00414 for(p = head,t=0; p && (p->data < i->data); p = p->next,t++);
00415
00416 if(unique && p && (p->data == i->data))
00417 {
00418 delete i;
00419 return -1;
00420 }
00421 if(!p)
00422 {
00423 addToTail(i);
00424 return count-1;
00425 }
00426 else if (p->prev)
00427 {
00428 p->prev->next = i;
00429 i->prev = p->prev;
00430 p->prev = i;
00431 i->next = p;
00432 count++;
00433 return t;
00434 }
00435 else
00436 {
00437 addToHead(i);
00438 return 0;
00439 }
00440 }
00441 #endif
00442
00443
00444
00445
00446
00447
00448
00449