Version 4.1.5
Main Page | Class Hierarchy | Class List | File List | Class Members | Related Pages

tree_t.h

00001 /* seqpp/tree_t.h
00002  *
00003  * Copyright (C) 2003 Laboratoire Statistique & Génome
00004  *
00005  * This program is free software; you can redistribute it and/or modify
00006  * it under the terms of the GNU General Public License as published by
00007  * the Free Software Foundation; either version 2 of the License, or (at
00008  * your option) any later version.
00009  *
00010  * This program is distributed in the hope that it will be useful, but
00011  * WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013  * General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU General Public License
00016  * along with this program; if not, write to the Free Software
00017  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00018  */
00019 
00020 
00032 #ifndef SEQPP_TREE_T_H
00033 #define SEQPP_TREE_T_H
00034 
00035 #include <iostream>
00036 #include <cstdlib>
00037 
00038 
00039 using namespace std;
00040 
00041 
00050 class tree_node_base
00051 {
00052       public:
00053         tree_node_base * *_sons;        
00054         tree_node_base *
00055                 _father;        
00056         short
00057                 _label;         
00058         short
00059                 _size;          
00060 
00067         inline tree_node_base (short size, short label, tree_node_base * father);
00069 
00072         inline tree_node_base (tree_node_base & source);
00074         inline virtual ~ tree_node_base ();
00080         inline tree_node_base & operator= (tree_node_base & source);
00081 };
00082 
00083 
00084 tree_node_base::tree_node_base (short size, short label =-1, tree_node_base * father = NULL)
00085 {
00086         if (label != -1)
00087         {
00088                 _label = label;
00089                 _father = father;
00090         }
00091         else
00092                 _father = NULL;
00093         _size = size;
00094         _sons = new tree_node_base *[_size];
00095         for (short label = 0; label < _size; label++)
00096         {
00097                 _sons[label] = NULL;
00098         }
00099 };
00100 
00101 tree_node_base::tree_node_base (tree_node_base & source)
00102 {
00103         _father = source._father;
00104         _size = source._size;
00105         _sons = new tree_node_base *[_size];
00106         for (int i = 0; i < _size; i++)
00107         {
00108                 if (source._sons[i])
00109                         _sons[i] = new tree_node_base (*(source._sons[i]));
00110                 else{
00111                   _sons[i] = NULL;
00112                 }
00113         }
00114 };
00115 
00116 tree_node_base::~tree_node_base ()
00117 {
00118         for (short label = 0; label < _size; label++)
00119         {
00120                 if (_sons[label])
00121                         delete _sons[label];
00122         }
00123         delete[]_sons;
00124 };
00125 
00126 tree_node_base & tree_node_base::operator= (tree_node_base & source)
00127 {
00128         cerr << "Error in _tree_node_base : no affectation operator in clas"
00129                 << endl;
00130         exit (1);
00131 };
00132 
00133 
00139 template < class T > class tree_node:public tree_node_base
00140 {
00141       public:
00142         T _content;             
00143 
00144       tree_node (short size, T & init, short label = 0, tree_node_base * father = NULL):tree_node_base (size, label, father),
00145                 _content
00146                 (init)
00147         {
00148         };
00150       tree_node (tree_node & source):tree_node_base (source)
00151         {
00152                 _content = source._content;
00153         };
00154 };
00155 
00156 //###########################################################################
00157 
00163 class tree_iterator_base
00164 {
00165       public:
00166         tree_node_base * _current;      
00167 
00169         inline tree_iterator_base ();
00171         inline tree_iterator_base (tree_node_base * ptr);
00172         // tree_iterator_base( tree_iterator_base & source) using default
00173         // tree_iterator_base & operator=(tree_iterator_base & source) using default
00178         inline void
00179         son (short label);
00183         inline void father ();
00184 
00185         inline tree_node_base * tell_father();
00186         /*
00187          * \brief Returns the label of the currently pointed node
00188          */
00189         inline short
00190         label () const;
00192         inline bool on_leaf (short label) const;
00194         inline bool on_leaf ()const;
00195         inline bool
00196         on_leaf_one () const;
00198         inline bool on_root ()const;
00204         inline tree_iterator_base & operator++ ();
00210         inline tree_iterator_base & operator-- ();
00212         inline bool operator== (const tree_iterator_base & source) const;
00214         inline bool operator!= (const tree_iterator_base & source) const;
00216         inline int
00217         level () const;
00218 };
00219 
00220 tree_iterator_base::tree_iterator_base ()
00221 {
00222         _current = NULL;
00223 };
00224 
00225 tree_iterator_base::tree_iterator_base (tree_node_base * ptr)
00226 {
00227         _current = ptr;
00228 };
00229 
00230 void
00231 tree_iterator_base::son (short label)
00232 {
00233         _current = _current->_sons[label];
00234 };
00235 
00236 void
00237 tree_iterator_base::father ()
00238 {
00239         _current = _current->_father;
00240 };
00241 
00242 tree_node_base *
00243 tree_iterator_base::tell_father ()
00244 {
00245   return _current->_father;
00246 };
00247 
00248 short
00249 tree_iterator_base::label () const
00250 {
00251         return (_current->_label);
00252 };
00253 
00254 bool tree_iterator_base::on_leaf (short label) const
00255 {
00256         return bool (!(_current->_sons[label]));
00257 };
00258 
00259 bool tree_iterator_base::on_leaf () const
00260 {
00261         bool
00262                 test = true;
00263         for (short label = 0; label < _current->_size; label++)
00264                 test = test & !(bool (_current->_sons[label]));
00265         return test;
00266 };
00267 
00268 bool tree_iterator_base::on_leaf_one () const
00269 {
00270         bool
00271                 test = false;
00272         for (int i = 0; i < _current->_size; i++)
00273         {
00274                 if (!(_current->_sons[i]))
00275                         return true;
00276         }
00277         return test;
00278 };
00279 
00280 bool tree_iterator_base::on_root () const
00281 {
00282         return (_current->_father == NULL);
00283 };
00284 
00285 tree_iterator_base & tree_iterator_base::operator++ ()
00286 {
00287         bool goon = true;
00288         for (int i = 0; i < _current->_size; i++)
00289         {
00290                 if (_current->_sons[i])
00291                 {
00292                         _current = _current->_sons[i];
00293                         goon = false;
00294                         break;
00295                 }
00296         }
00297         while (goon && bool (_current->_father))
00298         {
00299                 short
00300                         label = _current->_label;
00301                 for (int i = label + 1; i < _current->_size; i++)
00302                 {
00303                         if (_current->_father->_sons[i])
00304                         {
00305                                 goon = false;
00306                                 _current = _current->_father->_sons[i];
00307                                 break;
00308                         }
00309                 }
00310                 if (goon)
00311                 {
00312                         _current = _current->_father;
00313                 }
00314         }
00315         return *this;
00316 };
00317 
00318 tree_iterator_base & tree_iterator_base::operator-- ()
00319 {
00320         short
00321                 label;
00322         if (_current->_father != NULL)
00323         {
00324                 _current = _current->_father;
00325                 label = _current->_label;
00326         }
00327         else
00328                 label = _current->_size;
00329 
00330         bool goon = false;
00331         for (int i = label - 1; i > -1; i--)
00332         {
00333                 if (_current->_sons[i])
00334                 {
00335                         _current = _current->_sons[i];
00336                         goon = true;
00337                         break;
00338                 }
00339         }
00340         if (goon == false)
00341                 return *this;
00342         while (goon)
00343         {
00344                 goon = false;
00345                 for (int i = _current->_size - 1; i > -1; i--)
00346                 {
00347                         if (_current->_sons[i])
00348                         {
00349                                 _current = _current->_sons[i];
00350                                 goon = true;
00351                                 break;
00352                         }
00353                 }
00354         }
00355         return *this;
00356 };
00357 
00358 bool tree_iterator_base::operator== (const tree_iterator_base & source) const
00359 {
00360         return _current == source._current;
00361 };
00362 
00363 bool tree_iterator_base::operator!= (const tree_iterator_base & source) const
00364 {
00365         return _current != source._current;
00366 };
00367 
00368 int
00369 tree_iterator_base::level () const
00370 {
00371         int level = 0;
00372         tree_iterator_base it = *this;
00373         while (!it.on_root ())
00374         {
00375                 it.father ();
00376                 level++;
00377         }
00378         return level;
00379 };
00380 
00381 //###########################################################################
00386 template < class T, class TRef, class TPtr > class tree_iterator:public tree_iterator_base
00387 {
00388       public:
00389         typedef tree_iterator < T, T &, T * >iterator;  
00390         typedef tree_iterator < T, const T &, const T *>const_iterator; 
00391         typedef tree_iterator < T, TRef, TPtr > _self;
00392 
00393         typedef T value_type;   
00394         typedef TRef reference; 
00395         typedef TPtr pointer;   
00396         typedef tree_node < T > _node;  
00397 
00402       tree_iterator (_node * source):tree_iterator_base (source)
00403         {
00404         };
00409       tree_iterator (_node & source):tree_iterator_base (&source)
00410         {
00411         };
00417       tree_iterator ():tree_iterator_base ()
00418         {
00419         };
00423         tree_iterator (const iterator & it):tree_iterator_base (it._current)
00424         {
00425           //cout<<"copy construct"<<endl;
00426         };
00433         inline reference operator* () const
00434         {
00435                 return static_cast < _node * >(_current)->_content;
00436         };
00443         inline pointer operator-> () const
00444         {
00445                 return &(operator* ());
00446         };
00454         inline iterator & insert (short label, value_type & init)
00455         {
00456           if (_current->_sons[label]){
00457             delete _current->_sons[label];
00458           }
00459           _current = (_current->_sons[label] =
00460                       new _node (_current->_size,
00461                                  init, label, _current));
00462           return *this;
00463         };
00469         inline iterator & remove ()
00470         {
00471                 short label = _current->_label;
00472                 if (_current->_father)
00473                 {
00474                         _current = _current->_father;
00475                         delete _current->_sons[label];
00476                         _current->_sons[label] = NULL;
00477                 }
00478                 else
00479                         cerr << "tree_iterator<T>::remove : Root node can't be removed" << endl;
00480                 return *this;
00481         };      
00482 };
00483 
00484 
00485 
00486 
00487 
00488 
00495 template < class T > class tree_t
00496 {
00497       public:
00498         typedef tree_node < T > _node;
00499         typedef tree_iterator < T, T &, T * >iterator;  
00500         typedef tree_iterator < T, const T &, const T *>const_iterator; 
00501         typedef T value_type;
00502         typedef T & reference;
00503         typedef T *pointer;
00504 
00505       protected:
00506         _node * _root;          
00507 
00510         inline void
00511                 filltree (int size, value_type & init,
00512                           int depth, iterator & it)
00513         {
00514                 for (int i = 0; i < size; i++)
00515                 {
00516                         it = it.insert (i, init);
00517                         if (depth > 1)
00518                         {
00519                                 filltree (size, init, depth - 1, it);
00520                         }
00521                         if (it._current->_father)
00522                                 it.father ();
00523                 }
00524         };
00525       public:
00530         tree_t (int size)
00531         {
00532                 _root = new _node (size);
00533         };
00539         tree_t (int size, value_type & init)
00540         {
00541                 _root = new _node (size, init, -1, NULL);
00542         };
00548         tree_t (int size, value_type & init, int depth)
00549         {
00550                 _root = new _node (size, init);
00551                 iterator it = begin ();
00552                 filltree (size, init, depth, it);
00553         };
00555         tree_t (tree_t & source)
00556         {
00557                 cerr << "tree_t : copy constructor not yet implemented" <<
00558                         endl;
00559         };
00561         virtual ~tree_t ()
00562         {
00563                 delete _root;
00564         };
00566         iterator begin () const
00567         {
00568                 return iterator (_root);
00569         };
00570         /*
00572         iterator nodes (path_t path) const
00573         {
00574                 iterator it = begin ();
00575                 for (int i = 0; i < path._length; i++)
00576                 {
00577                         it.son (path._path[i]);
00578                 }
00579                 return it;
00580         };
00582         iterator leaves (path_t path) const
00583         {
00584                 iterator it = begin ();
00585                 int step = 0;
00586                 while ((step < path._length) && !(it.on_leaf (path[step])))
00587                           it.son (path[step++]);
00588                   return it;
00589         };
00591         const_iterator const_nodes (path_t path)
00592         {
00593                 const_iterator it = begin ();
00594                 for (int i = 0; i < path._length; i++)
00595                 {
00596                         it.son (path._path[i]);
00597                 }
00598                 return it;
00599         };
00601         path_t & path (iterator it, path_t & _path)
00602         {
00603                 int i = it.level ();
00604                 if (_path._length != i)
00605                 {
00606                         cerr << "Error in tree_t::path : provided path_t has not required length" << endl;
00607                         return _path;
00608                 }
00609 
00610                 while (!it.on_root ())
00611                 {
00612                         _path[--i] = it.label ();
00613                         it.father ();
00614                 }
00615                 return _path;
00616         };
00617         */
00618 };
00619 
00620 #endif



Download seq++ 4.1.5
Download previous versions
Statistique & Genome Home


Generated on Thu Aug 4 18:34:04 2005 for seqpp by doxygen 1.3.9.1