Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members  

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 Sat May 4 23:45:38 2002 for vdk 2.0.1 by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002