Main Page | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | Related Pages

value_sem_list.h

00001 /* 00002 * =========================== 00003 * VDK Visual Development Kit 00004 * Version 0.4 00005 * October 1998 00006 * =========================== 00007 * 00008 * Copyright (C) 1998, Mario Motta 00009 * Developed by Mario Motta <mmotta@guest.net> 00010 * 00011 * This library is free software; you can redistribute it and/or 00012 * modify it under the terms of the GNU Library General Public 00013 * License as published by the Free Software Foundation; either 00014 * version 2 of the License, or (at your option) any later version. 00015 * 00016 * This library is distributed in the hope that it will be useful, 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00019 * Library General Public License for more details. 00020 * 00021 * You should have received a copy of the GNU Library General Public 00022 * License along with this library; if not, write to the Free Software 00023 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 00024 * 02111-1307, USA. 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 forward 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 class VDKValueList, 00078 inherits from Container 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 copy initializer 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 assignement 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 destructor 00261 */ 00262 template <class T> 00263 VDKValueList<T>::~VDKValueList() 00264 { 00265 flush(); 00266 } 00267 /* 00268 flushes list 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 add a T type to list 00286 */ 00287 template <class T> 00288 void VDKValueList<T>::add( const T& t) 00289 { 00290 addToTail(new VDKValueItem<T>(t)); 00291 } 00292 /* 00293 pushes a T type into list 00294 */ 00295 template <class T> 00296 void VDKValueList<T>::push(const T& t) 00297 { 00298 addToHead(new VDKValueItem<T>(t)); 00299 } 00300 /* 00301 insert in order a T type into list 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 ordinal operator 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 find a T type value 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 private, 00360 copy VDKValueItems from a list 00361 into this 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 private, 00371 fetches n-th VDKValueItem 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 private, 00383 add an VDKValueItem to tail 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 private, 00394 add an VDKValueItem to tail 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 private, 00405 add an VDKValueItem in order 00406 return inserted list index 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 // avoid key clush 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

Generated on Wed Jul 28 17:23:53 2004 for vdk 2.0.3 by doxygen 1.3.7