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