Main Page   Namespace List   Alphabetical List   Compound List   File List   Compound Members   File Members  

detree.h

Go to the documentation of this file.
00001 
00002 //
00003 //  detree.h
00004 //
00005 //  
00006 //  begin       : Thu Feb 7 2002
00007 //  copyright   : (C) 2002 by Solstice
00008 //  email       : solstice@deninet.com
00009 //
00011 
00012 #ifndef DETREE_H
00013 #define DETREE_H
00014 
00015 #include <vector>
00016 #include <stack>
00017 #include <utility>
00018 
00019 #ifndef null
00020 #define null 0L
00021 #endif
00022 
00023 namespace deml
00024 {
00029     template <class T> class tree
00030     {
00031         //  member classes
00032         private:
00033         
00034         class node
00035         {
00036             public:
00037             node(void);
00038             node(T);
00039             ~node(void);
00040             void clear(void);
00041             void append_child(T);
00042             void insert(T);
00043             void replace(T);
00044             T                   data;
00045             node*           next;
00046             node*           prev;
00047             node*           parent;
00048             node*           child_start;
00049             node*           child_end;
00050         };
00051         
00052         public:
00053         
00059         class iterator
00060         {
00061             public:
00063             iterator(void);
00065             iterator(const iterator& i);
00067             iterator& operator++(void);
00069             iterator& operator--(void);
00071             T operator*(void);
00073             T* operator->(void);
00075             bool operator==(const iterator&);
00077             bool operator!=(const iterator&);
00078             
00081             iterator step_in(void);
00084             iterator step_out(void);
00086             iterator begin(void);
00088             iterator end(void);
00090             bool valid(void);
00091             
00092             friend tree;
00093             private:
00094             iterator(node*);
00095             node*   current;
00096         };
00097         
00098         //  member functions
00099         public:
00100         
00102         iterator begin(void);       
00104         iterator end(void);     
00106         iterator append_child(iterator, T);
00108         iterator insert(iterator, T);
00110         iterator replace(iterator, T);
00112         iterator erase(iterator);
00113         
00114         //  data members
00115         friend iterator;
00116         private:
00117         
00118         node    treeRoot;
00119     };
00120     
00121     template<class T> tree<T>::iterator tree<T>::begin(void)
00122     {
00123         return iterator(&treeRoot);
00124     }
00125     
00126     template<class T> tree<T>::iterator tree<T>::end(void)
00127     {
00128         return iterator(&treeRoot);
00129     }
00130     
00131     template<class T> tree<T>::iterator tree<T>::append_child(iterator i, T data)
00132     {
00133         tree<T>::node* current = i.current;
00134         
00135         if(current != null)
00136         {
00137             current->append_child(data);
00138             return iterator(current->child_end);
00139         }
00140         
00141         return iterator(null);
00142     }
00143     
00144     template<class T> tree<T>::iterator tree<T>::insert(iterator i, T data)
00145     {
00146         tree<T>::node* n = i->current;
00147         
00148         if(n != null)
00149         {
00150             n->insert(data);
00151             return iterator(n->prev);
00152         }
00153         
00154         return iterator(null);
00155     }
00156     
00157     template<class T> tree<T>::iterator tree<T>::replace(iterator i, T data)
00158     {
00159         tree<T>::node* n = i.current;
00160         
00161         if(n != null)
00162             n->replace(data);
00163         
00164         return i;   
00165     }
00166     
00167     template<class T> tree<T>::iterator tree<T>::erase(iterator i)
00168     {
00169         node* n = i->current;
00170                 
00171         if(n == null)
00172             return;
00173         
00174         if(n == &treeRoot)
00175             n->clear();
00176                 
00177         if(n->prev != null)
00178             i->current = n->prev;
00179         else
00180             i->current = n->next;
00181             
00182         delete n;
00183         return i;
00184     }
00185     
00186     template<class T> tree<T>::iterator::iterator(void)
00187     {
00188         current = null;
00189     }
00190     
00191     template<class T> tree<T>::iterator::iterator(node* n)
00192     {
00193         current = n;
00194     }
00195     
00196     template<class T> tree<T>::iterator::iterator(const tree<T>::iterator& i)
00197     {
00198         current = i.current;
00199     }
00200     
00201     template<class T> tree<T>::iterator& tree<T>::iterator::operator++(void)
00202     {
00203         if(current->next != null)
00204             current = current->next;
00205         else
00206             current = null;
00207                     
00208         return (*this);
00209     }
00210     
00211     template<class T> tree<T>::iterator& tree<T>::iterator::operator--(void)
00212     {
00213         if(current->prev != null)
00214             current = current->prev;
00215         else
00216             current = null;
00217                     
00218         return (*this);
00219     }
00220     
00221     template<class T> T tree<T>::iterator::operator*(void)
00222     {
00223         return current->data;
00224     }
00225 
00226     template<class T> T* tree<T>::iterator::operator->(void)
00227     {
00228         return &current->data;
00229     }
00230     
00231     template<class T> bool tree<T>::iterator::operator==(const iterator& i)
00232     {
00233         if(i.current == current)
00234             return true;
00235             
00236         return false;
00237     }
00238     
00239     template<class T> bool tree<T>::iterator::operator!=(const iterator& i)
00240     {
00241         if(i.current != current)
00242             return true;
00243             
00244         return false;
00245     }
00246     
00247     template<class T> tree<T>::iterator tree<T>::iterator::step_in(void)
00248     {
00249         if(current == null)
00250             return (*this);
00251             
00252         if(current->child_start == null)
00253             return iterator(null);
00254         
00255         current = current->child_start;         
00256         return (*this);
00257     }
00258     
00259     template<class T> tree<T>::iterator tree<T>::iterator::step_out(void)
00260     {
00261         if(current == null)
00262             return (*this);
00263             
00264         if(current->parent == null)
00265             return iterator(null);
00266             
00267         current = current->parent;  
00268         return (*this);
00269     }
00270         
00271     template<class T> tree<T>::iterator tree<T>::iterator::begin(void)
00272     {
00273         if(current->parent == null)
00274             return current;
00275             
00276         node* parent = current->parent;
00277         
00278         return iterator(parent->child_start);
00279     }
00280     
00281     template<class T> tree<T>::iterator tree<T>::iterator::end(void)
00282     {
00283         if(current->parent == null)
00284             return current;
00285             
00286         node* parent = current->parent;
00287         
00288         return iterator(parent->child_end);
00289     }
00290     
00291     template<class T> bool tree<T>::iterator::valid(void)
00292     {
00293         if(current == null)
00294             return false;
00295             
00296         return true;
00297     }
00298     
00299     template<class T> tree<T>::node::node(void)
00300     {
00301         prev = null;
00302         next = null;
00303         parent = null;
00304         child_start = null;
00305         child_end = null;
00306     }
00307     
00308     template<class T> tree<T>::node::node(T value)
00309     {
00310         data = value;
00311         prev = null;
00312         next = null;
00313         parent = null;
00314         child_start = null;
00315         child_end = null;
00316     }
00317     
00318     template<class T> tree<T>::node::~node(void)
00319     {
00320         clear();
00321     }
00322     
00323     template<class T> void tree<T>::node::clear(void)
00324     {
00325         //  sever parent connection
00326         if(parent != null)
00327         {
00328             if(parent->child_start == this)
00329                 parent->child_start = next;
00330                 
00331             if(parent->child_end == this)
00332                 parent->child_end = prev;
00333                 
00334             parent = null;
00335         }
00336         
00337         //  remove this node from the list
00338         if(prev != null)
00339             prev->next = next;
00340             
00341         if(next != null)
00342             next->prev = prev;
00343         
00344         prev = next = null;
00345                 
00346         //  progressivly delete the children
00347         tree<T>::node* current = child_start;
00348         while(current != null)
00349         {
00350             tree<T>::node* temp = current->next;
00351             delete current;
00352             current = temp;
00353         }   
00354     }
00355     
00356     template<class T> void tree<T>::node::append_child(T value)
00357     {
00358         node* n = new node(value);
00359         n->parent = this;
00360             
00361         if(child_start == null)
00362         {
00363             child_start = child_end = n;
00364             return;
00365         }
00366             
00367         n->prev = child_end;
00368         child_end->next = n;
00369         child_end = n;
00370     }
00371     
00372     template<class T> void tree<T>::node::insert(T value)
00373     {
00374         tree<T>::node* n = new node(value);
00375         n->prev = prev;
00376         n->next = this;
00377         
00378         if(prev != null)
00379             prev->next = n;
00380         else
00381             parent->child_start = n;
00382         
00383         prev = n;
00384     }
00385     
00386     template<class T> void tree<T>::node::replace(T value)
00387     {
00388         data = value;
00389     }
00390 };
00391 
00392 #endif

Generated at Sun Mar 3 20:34:56 2002 for Chroma by doxygen1.2.9.1 written by Dimitri van Heesch, © 1997-2001