Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2007, 2008, 2009 EPITA Research and Development Laboratory (LRDE) 00002 // 00003 // This file is part of Olena. 00004 // 00005 // Olena is free software: you can redistribute it and/or modify it under 00006 // the terms of the GNU General Public License as published by the Free 00007 // Software Foundation, version 2 of the License. 00008 // 00009 // Olena is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 // General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU General Public License 00015 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00016 // 00017 // As a special exception, you may use this file as part of a free 00018 // software project without restriction. Specifically, if other files 00019 // instantiate templates or use macros or inline functions from this 00020 // file, or you compile this file and link it with other files to produce 00021 // an executable, this file does not by itself cause the resulting 00022 // executable to be covered by the GNU General Public License. This 00023 // exception does not however invalidate any other reasons why the 00024 // executable file might be covered by the GNU General Public License. 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 // Branch methods 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 } // end of namespace mln::util 00564 00565 00566 } // end of namespace mln 00567 00568 00569 #endif // ! MLN_UTIL_TREE_HH