00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
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
00173
00178 inline void
00179 son (short label);
00183 inline void father ();
00184
00185 inline tree_node_base * tell_father();
00186
00187
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
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
00573
00574
00575
00576
00577
00578
00579
00580
00582
00583
00584
00585
00586
00587
00588
00589
00591
00592
00593
00594
00595
00596
00597
00598
00599
00601
00602
00603
00604
00605
00606
00607
00608
00609
00610
00611
00612
00613
00614
00615
00616
00617
00618 };
00619
00620 #endif