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

dlist.h

00001 /* 00002 * =========================== 00003 * VDK Visual Develeopment 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 00027 #ifndef DLIST_H 00028 #define DLIST_H 00029 // just a cosmetic capitalizing (suggestion by Ionutz Borcoman) 00030 #define VDKListIterator VDKListiterator 00031 00032 /* 00033 ============ 00034 VDKItem class 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 // append to list 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 // over head loading 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 // insert at pos 00085 void insertVDKItem(VDKItem<T>* i, int pos); 00086 00087 // fetch an VDKItem at <n> position 00088 VDKItem<T>* fetch(int n); 00089 00090 // assign VDKItems to container 00091 void assign(VDKList& l); 00092 // on reference semantic copy-assign is prohibited 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 // avoid l = l; 00103 if(this != &l) { flush(); assign(l); } 00104 return *this; 00105 } 00106 00107 /* class interface methods */ 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 //NON-INLINE MEMBER FUNCTIONS 00265 /*======================= 00266 PRIVATE: 00267 assign VDKItems copyng them 00268 from another list 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 PRIVATE: 00279 fetch VDKItem<T> at n position 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 PRIVATE: 00291 find ordinal position of VDKItem 00292 containing a type<T> object, 00293 return -1 if not found 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 flushes list 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 find(type<T>) , iterate 00321 over container to find 00322 an object. 00323 hint: compare pointers only.. 00324 so is good only for identities.. 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 remove a type<T>. 00337 Return a 1 or 0 (not removed) 00338 ============================== 00339 */ 00340 template <class T> 00341 int VDKList<T>::remove(T* x) 00342 { 00343 VDKItem<T>* cur; 00344 int n = at(x); 00345 // object not found 00346 if(n < 0) return 0; 00347 else cur = fetch(n); 00348 // removing head 00349 if(cur == head) { 00350 head = cur->next; 00351 // one element list 00352 if(head != (VDKItem<T>*) 0) head->prev = (VDKItem<T>*) 0; 00353 else tail = (VDKItem<T>*) 0; 00354 } 00355 else { // remove tail or intermediate element 00356 cur->prev->next = cur->next; 00357 if(cur != tail) cur->next->prev = cur->prev; 00358 // remove tail 00359 else tail = cur->prev; 00360 } 00361 delete cur; 00362 count--; 00363 return 1; 00364 } 00365 /* 00366 insert an item a <t> position 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

Generated on Tue Aug 17 12:39:50 2004 for vdk 2.4.0 by doxygen 1.3.7