00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef MLN_UTIL_TREE_HH
00027 # define MLN_UTIL_TREE_HH
00028
00029 # include <vector>
00030 # include <algorithm>
00031 # include <iostream>
00032 # include <algorithm>
00033 # include <mln/core/contract.hh>
00034
00042 namespace mln
00043 {
00044
00045 namespace util
00046 {
00047
00049 template <typename T> class tree_node;
00050 template <typename T> class tree;
00051 template <typename T> class branch;
00052
00053
00057 template <typename T>
00058 class tree_node
00059 {
00060 public:
00061
00062 typedef std::vector< tree_node<T>* > children_t;
00063
00067 tree_node();
00068
00073 tree_node(T elt);
00074
00075
00080 T& elt();
00081
00086 const T& elt() const;
00087
00088
00093 children_t& children();
00094
00095
00100 const children_t& children() const;
00101
00102
00107 tree_node<T>* parent();
00108
00109
00117 tree_node<T>* add_child(T elt);
00118
00126 tree_node<T>* add_child(tree_node<T>* tree_node);
00127
00134 void set_parent(tree_node<T>* parent);
00135
00139 tree_node<T>* delete_tree_node();
00140
00148 void print(std::ostream& ostr, int level = 0);
00149
00154 bool check_consistency();
00155
00156
00164 tree_node<T>* search(T& elt);
00165
00167 int search_rec(tree_node<T>** res, T& elt);
00168
00169 private:
00170
00172 T elt_;
00173
00175 tree_node<T>* parent_;
00176
00178 std::vector< tree_node<T>* > child_;
00179 };
00180
00181
00182
00186 template <typename T>
00187 class tree
00188 {
00189 public:
00190
00191 typedef tree_node<T> tree_node_t;
00192
00196 tree();
00197
00202 tree(tree_node<T>* root);
00203
00204
00209 tree_node<T>* root();
00210
00215 branch<T> main_branch();
00216
00221 bool check_consistency();
00222
00223
00229 void add_tree_up (T& elt);
00230
00236 void add_tree_down (T& elt);
00237
00238 private:
00239
00241 tree_node<T>* root_;
00242 };
00243
00244
00248 template <typename T>
00249 class branch
00250 {
00251 public:
00252
00258 branch(tree<T>& tree, tree_node<T>& apex);
00259
00264 tree_node<T>& apex();
00265
00270 tree<T>& util_tree();
00271
00272 private:
00274 util::tree<T>& tree_;
00275
00277 tree_node<T>& apex_;
00278 };
00279
00280
00281 # ifndef MLN_INCLUDE_ONLY
00282
00283 template <typename T>
00284 inline
00285 tree<T>::tree()
00286 : root_ (0)
00287 {
00288 }
00289
00290 template <typename T>
00291 inline
00292 tree<T>::tree(tree_node<T>* root)
00293 : root_ (root)
00294 {
00295 mln_assertion (root != 0);
00296 }
00297
00298 template <typename T>
00299 inline
00300 tree_node<T>*
00301 tree<T>::root()
00302 {
00303 return root_;
00304 }
00305
00306 template <typename T>
00307 inline
00308 branch<T>
00309 tree<T>::main_branch()
00310 {
00311 return branch<T>(*this, *root());
00312 }
00313
00314 template <typename T>
00315 inline
00316 void
00317 tree<T>::add_tree_up(T& elt)
00318 {
00319 tree_node<T>* n = new tree_node<T> (elt);
00320 root_->set_parent(n);
00321 n->children().push_back (root_);
00322 root_ = n;
00323 }
00324
00325 template <typename T>
00326 inline
00327 void
00328 tree<T>::add_tree_down(T& elt)
00329 {
00330 tree_node<T>* n = new tree_node<T> (elt);
00331 root_->child_.push_back (n);
00332 }
00333
00334
00335 template <typename T>
00336 inline
00337 bool
00338 tree<T>::check_consistency()
00339 {
00340 return root()->check_consistency ();
00341 }
00342
00343 template <typename T>
00344 inline
00345 tree_node<T>::tree_node()
00346 : parent_ (0)
00347 {
00348 }
00349
00350 template <typename T>
00351 inline
00352 tree_node<T>::tree_node(T elt)
00353 : elt_ (elt),
00354 parent_ (0)
00355 {
00356 }
00357
00358 template <typename T>
00359 inline
00360 const T&
00361 tree_node<T>::elt() const
00362 {
00363 return elt_;
00364 }
00365
00366 template <typename T>
00367 inline
00368 T&
00369 tree_node<T>::elt()
00370 {
00371 return elt_;
00372 }
00373
00374
00375 template <typename T>
00376 inline
00377 std::vector< tree_node<T>* >&
00378 tree_node<T>::children()
00379 {
00380 return child_;
00381 }
00382
00383 template <typename T>
00384 inline
00385 const std::vector< tree_node<T>* >&
00386 tree_node<T>::children() const
00387 {
00388 return child_;
00389 }
00390
00391 template <typename T>
00392 inline
00393 tree_node<T>*
00394 tree_node<T>::add_child(T elt)
00395 {
00396 tree_node<T>* s = new tree_node<T>(elt);
00397
00398 s->parent_ = this;
00399 this->child_.push_back(s);
00400 return s;
00401 }
00402
00403
00404 template <typename T>
00405 inline
00406 tree_node<T>*
00407 tree_node<T>::add_child(tree_node<T>* tree_node)
00408 {
00409 if (tree_node->parent_)
00410 {
00411 for (typename std::vector<util::tree_node<T>* >::iterator it = tree_node->parent()->children().begin();
00412 it != tree_node->parent()->children().end(); ++it)
00413 if ((*it) == tree_node)
00414 {
00415 tree_node->parent()->children().erase(it);
00416 break;
00417 }
00418 }
00419 tree_node->parent_ = this;
00420 this->children().push_back(tree_node);
00421 return tree_node;
00422 }
00423
00424 template <typename T>
00425 inline
00426 tree_node<T>*
00427 tree_node<T>::delete_tree_node()
00428 {
00429 mln_assertion(parent_ != 0);
00430 tree_node<T>* res = parent_;
00431
00432 typename std::vector<tree_node<T>* >::iterator it = parent_->children().begin();
00433 for (; it < parent_->children().end(); ++it)
00434 if ((*it) == this)
00435 {
00436 parent_->children().erase(it);
00437 break;
00438 }
00439
00440 for (typename std::vector<tree_node<T>* >::iterator it = this->child_.begin();
00441 it != this->child_.end(); ++it)
00442 parent_->add_child(*it);
00443 return (res);
00444 }
00445
00446 template <typename T>
00447 inline
00448 void
00449 tree_node<T>::print(std::ostream& ostr, int level)
00450 {
00451 ostr << level << std::endl;
00452
00453 ostr << " elt " << this->elt() << std::endl;
00454
00455
00456 for (typename std::vector<tree_node<T>* >::iterator it = this->child_.begin();
00457 it != this->child_.end(); ++it)
00458 {
00459 (*it)->print(level + 1);
00460 }
00461 }
00462
00463
00464 template <typename T>
00465 inline
00466 void
00467 tree_node<T>::set_parent(tree_node<T>* parent)
00468 {
00469 mln_assertion(parent != 0);
00470 parent_ = parent;
00471 parent->child_.push_back(this);
00472 }
00473
00474 template <typename T>
00475 inline
00476 tree_node<T>*
00477 tree_node<T>::parent()
00478 {
00479 return parent_;
00480 }
00481
00482 template <typename T>
00483 inline
00484 int
00485 tree_node<T>::search_rec(tree_node<T>** res, T& elt)
00486 {
00487 if (elt == this->elt_)
00488 {
00489 *res = this;
00490 return 1;
00491 }
00492 else
00493 {
00494 for (typename std::vector<tree_node<T>* >::iterator it = this->child_.begin();
00495 it != this->child_.end(); ++it)
00496 {
00497 if ((**it).search_rec(res, elt))
00498 return 1;
00499 }
00500 }
00501 return 0;
00502 }
00503
00504 template <typename T>
00505 inline
00506 tree_node<T>*
00507 tree_node<T>::search(T& elt)
00508 {
00509 tree_node<T>* res = 0;
00510
00511 if (search_rec(&res, elt))
00512 return res;
00513 return 0;
00514 }
00515
00516 template <typename T>
00517 inline
00518 bool
00519 tree_node<T>::check_consistency()
00520 {
00521 for (typename std::vector<tree_node<T>* >::iterator it = this->child_.begin();
00522 it != this->child_.end(); ++it)
00523 {
00524 if ((**it).parent() != this)
00525 return false;
00526
00527 if (!((**it).check_consistency()))
00528 return false;
00529 }
00530 return true;
00531 }
00532
00533
00534
00535 template <typename T>
00536 inline
00537 branch<T>::branch(util::tree<T>& tree,
00538 util::tree_node<T>& apex)
00539 : tree_(tree),
00540 apex_(apex)
00541 {
00542 }
00543
00544
00545 template <typename T>
00546 inline
00547 util::tree_node<T>&
00548 branch<T>::apex()
00549 {
00550 return apex_;
00551 }
00552
00553 template <typename T>
00554 inline
00555 mln::util::tree<T>&
00556 branch<T>::util_tree()
00557 {
00558 return tree_;
00559 }
00560
00561 # endif // ! MLN_INCLUDE_ONLY
00562
00563 }
00564
00565
00566 }
00567
00568
00569 #endif // ! MLN_UTIL_TREE_HH