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

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 Sat May 4 22:00:24 2002 for vdk 2.0.1 by doxygen1.2.15