Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2008, 2009, 2010, 2011 EPITA Research and Development 00002 // Laboratory (LRDE) 00003 // 00004 // This file is part of Olena. 00005 // 00006 // Olena is free software: you can redistribute it and/or modify it under 00007 // the terms of the GNU General Public License as published by the Free 00008 // Software Foundation, version 2 of the License. 00009 // 00010 // Olena is distributed in the hope that it will be useful, 00011 // but 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 Olena. If not, see <http://www.gnu.org/licenses/>. 00017 // 00018 // As a special exception, you may use this file as part of a free 00019 // software project without restriction. Specifically, if other files 00020 // instantiate templates or use macros or inline functions from this 00021 // file, or you compile this file and link it with other files to produce 00022 // an executable, this file does not by itself cause the resulting 00023 // executable to be covered by the GNU General Public License. This 00024 // exception does not however invalidate any other reasons why the 00025 // executable file might be covered by the GNU General Public License. 00026 00027 #ifndef MLN_MORPHO_TREE_DATA_HH 00028 # define MLN_MORPHO_TREE_DATA_HH 00029 00034 00035 # include <mln/morpho/tree/compute_parent.hh> 00036 # include <mln/core/site_set/p_array.hh> 00037 # include <mln/core/internal/site_set_iterator_base.hh> 00038 # include <mln/core/internal/piter_identity.hh> 00039 00040 # include <deque> 00041 # include <iostream> 00042 00043 # define mln_up_site_piter(T) typename T::up_site_piter 00044 # define mln_dn_site_piter(T) typename T::dn_site_piter 00045 # define mln_up_node_piter(T) typename T::up_node_piter 00046 # define mln_dn_node_piter(T) typename T::dn_node_piter 00047 # define mln_up_leaf_piter(T) typename T::up_leaf_piter 00048 # define mln_dn_leaf_piter(T) typename T::dn_leaf_piter 00049 # define mln_site_piter(T) typename T::site_piter 00050 # define mln_node_piter(T) typename T::node_piter 00051 # define mln_leaf_piter(T) typename T::leaf_piter 00052 # define mln_depth1st_piter(T) typename T::depth1st_piter 00053 00054 # define mln_up_site_piter_(T) T::up_site_piter 00055 # define mln_dn_site_piter_(T) T::dn_site_piter 00056 # define mln_up_node_piter_(T) T::up_node_piter 00057 # define mln_dn_node_piter_(T) T::dn_node_piter 00058 # define mln_up_leaf_piter_(T) T::up_leaf_piter 00059 # define mln_dn_leaf_piter_(T) T::dn_leaf_piter 00060 # define mln_site_piter_(T) T::site_piter 00061 # define mln_node_piter_(T) T::node_piter 00062 # define mln_leaf_piter_(T) T::leaf_piter 00063 # define mln_depth1st_piter_(T) T::depth1st_piter 00064 00065 00066 namespace mln 00067 { 00068 00069 namespace morpho 00070 { 00071 00072 namespace tree 00073 { 00074 00075 // Forward declarations. 00076 00078 template <typename T> struct up_site_piter; 00079 00081 template <typename T> struct dn_site_piter; 00082 00084 template <typename T> struct up_node_piter; 00085 00087 template <typename T> struct dn_node_piter; 00088 00090 template <typename T> struct up_leaf_piter; 00091 00093 template <typename T> struct dn_leaf_piter; 00094 00096 template <typename T> class depth1st_piter; 00097 00098 00099 template <typename I, typename S> 00100 class data 00101 { 00102 typedef data<I, S> self_; 00103 00104 public: 00106 typedef I function; 00108 typedef mln_psite(I) psite; 00109 typedef mln_site(I) site; 00111 typedef S sites_t; 00113 typedef p_array<mln_psite(I)> nodes_t; 00115 typedef p_array<mln_psite(I)> leaves_t; 00116 00118 typedef mln_ch_value(I, mln_psite(I)) parent_t; 00119 00121 typedef mln_ch_value(I, nodes_t) children_t; 00122 00123 // Iterate on all sites. 00124 typedef mln::morpho::tree::up_site_piter<self_> up_site_piter; 00125 typedef mln::morpho::tree::dn_site_piter<self_> dn_site_piter; 00126 typedef up_site_piter site_piter; 00127 00128 // Iterate on nodes only. 00129 typedef mln::morpho::tree::up_node_piter<self_> up_node_piter; 00130 typedef mln::morpho::tree::dn_node_piter<self_> dn_node_piter; 00131 typedef up_node_piter node_piter; 00132 00133 // Iterate on leaves only. 00134 typedef mln::morpho::tree::up_leaf_piter<self_> up_leaf_piter; 00135 typedef mln::morpho::tree::dn_leaf_piter<self_> dn_leaf_piter; 00136 typedef up_leaf_piter leaf_piter; 00137 00138 typedef mln::morpho::tree::depth1st_piter<self_> depth1st_piter; 00139 00140 00142 template <typename N> 00143 data(const Image<I>& f, 00144 const Site_Set<S>& s, 00145 const Neighborhood<N>& nbh); 00146 00150 data(const Image<I>& f, 00151 const parent_t& parent, 00152 const Site_Set<S>& s); 00153 00155 00156 mln_rvalue(I) f(const mln_psite(I)& p) const; 00157 const I& f() const; 00158 00160 00162 00163 mln_rvalue(parent_t) parent(const mln_psite(I)& p) const; 00164 const parent_t& parent_image() const; 00165 00167 00169 00170 mln_rvalue(children_t) children(const mln_psite(I)& p) const; 00171 const mln_ch_value(I, nodes_t)& children_image() const; 00172 00174 00176 00177 const p_array<mln_psite(I)>& nodes() const; 00178 00180 00182 00183 const p_array<mln_psite(I)>& leaves() const; 00184 00186 00188 00189 const S& domain() const; 00190 00192 00193 00194 00196 00197 bool is_valid() const; 00198 bool is_root(const mln_psite(I)& p) const; 00199 bool is_a_node(const mln_psite(I)& p) const; 00200 bool is_a_non_root_node(const mln_psite(I)& p) const; 00201 bool is_a_leaf(const mln_psite(I)& p) const; 00202 00204 00205 unsigned nroots() const; 00206 00207 protected: 00208 void compute_children_(); 00209 00210 protected: 00211 mln_ch_value(I, mln_psite(I)) parent_; // Parent image. 00212 mln_ch_value(I, nodes_t) children_; // Children image. 00213 00214 function f_; // f image containing values of the tree nodes. 00215 sites_t s_; // Sorted site set of the tree sites. (domain(f_) includes s_). 00216 00217 nodes_t nodes_; // Sorted node set. 00218 leaves_t leaves_; // Sorted leaf set. 00219 unsigned nroots_; // For non-contigous domain image purpose. 00220 }; 00221 00222 00223 /* Iterators */ 00224 00225 template <typename T> 00226 struct up_site_piter 00227 : public mln::internal::piter_identity_< typename T::sites_t::bkd_piter, // Adaptee. 00228 up_site_piter<T> > // Exact. 00229 { 00230 private: 00231 typedef typename T::sites_t::bkd_piter Pi_; 00232 typedef mln::internal::piter_identity_< Pi_, up_site_piter<T> > super_; 00233 00234 public: 00235 up_site_piter(const T& t) 00236 { 00237 this->change_target(t.domain()); 00238 } 00239 00240 up_site_piter(const Pi_& pi) 00241 : super_(pi) 00242 { 00243 } 00244 }; 00245 00246 template <typename T> 00247 struct dn_site_piter 00248 : public mln::internal::piter_identity_< typename T::sites_t::fwd_piter, // Adaptee. 00249 dn_site_piter<T> > // Exact. 00250 { 00251 private: 00252 typedef typename T::sites_t::fwd_piter Pi_; 00253 typedef mln::internal::piter_identity_< Pi_, dn_site_piter<T> > super_; 00254 00255 public: 00256 dn_site_piter(const T& t) 00257 { 00258 this->change_target(t.domain()); 00259 } 00260 00261 dn_site_piter(const Pi_& pi) 00262 : super_(pi) 00263 { 00264 } 00265 }; 00266 00267 template <typename T> 00268 struct up_node_piter 00269 : public mln::internal::piter_identity_< typename T::nodes_t::fwd_piter, // Adaptee. 00270 up_node_piter<T> > // Exact. 00271 { 00272 private: 00273 typedef typename T::nodes_t::fwd_piter Pi_; 00274 typedef mln::internal::piter_identity_< Pi_, up_node_piter<T> > super_; 00275 00276 public: 00277 up_node_piter(const T& t) 00278 { 00279 this->change_target(t.nodes()); 00280 } 00281 00282 up_node_piter(const Pi_& pi) 00283 : super_(pi) 00284 { 00285 } 00286 }; 00287 00288 template <typename T> 00289 struct dn_node_piter 00290 : public mln::internal::piter_identity_< typename T::nodes_t::bkd_piter, // Adaptee. 00291 dn_node_piter<T> > // Exact. 00292 { 00293 private: 00294 typedef typename T::nodes_t::bkd_piter Pi_; 00295 typedef mln::internal::piter_identity_< Pi_, dn_node_piter<T> > super_; 00296 00297 public: 00298 dn_node_piter(const T& t) 00299 { 00300 this->change_target(t.nodes()); 00301 } 00302 00303 dn_node_piter(const Pi_& pi) 00304 : super_(pi) 00305 { 00306 } 00307 }; 00308 00309 template <typename T> 00310 struct up_leaf_piter 00311 : public mln::internal::piter_identity_< typename T::leaves_t::fwd_piter, // Adaptee. 00312 up_leaf_piter<T> > // Exact. 00313 { 00314 private: 00315 typedef typename T::leaves_t::fwd_piter Pi_; 00316 typedef mln::internal::piter_identity_< Pi_, up_leaf_piter<T> > super_; 00317 00318 public: 00319 up_leaf_piter(const T& t) 00320 { 00321 this->change_target(t.leaves()); 00322 } 00323 00324 up_leaf_piter(const Pi_& pi) 00325 : super_(pi) 00326 { 00327 } 00328 }; 00329 00330 template <typename T> 00331 struct dn_leaf_piter 00332 : public mln::internal::piter_identity_< typename T::leaves_t::bkd_piter, // Adaptee. 00333 dn_leaf_piter<T> > // Exact. 00334 { 00335 private: 00336 typedef typename T::leaves_t::bkd_piter Pi_; 00337 typedef mln::internal::piter_identity_< Pi_, dn_leaf_piter<T> > super_; 00338 00339 public: 00340 dn_leaf_piter(const T& t) 00341 { 00342 this->change_target(t.leaves()); 00343 } 00344 00345 dn_leaf_piter(const Pi_& pi) 00346 : super_(pi) 00347 { 00348 } 00349 }; 00350 00351 template <typename T> 00352 class depth1st_piter 00353 : public mln::internal::site_set_iterator_base< T, depth1st_piter<T> > 00354 { 00355 typedef depth1st_piter<T> self_; 00356 typedef mln::internal::site_set_iterator_base<T, self_> super_; 00357 00358 public: 00359 00361 depth1st_piter(); 00362 00364 depth1st_piter(const T& t); 00365 00366 00367 depth1st_piter(const T& t, 00368 const mln_psite(T::function)& p); 00369 00371 bool is_valid_() const; 00372 00374 void invalidate_(); 00375 00377 void start_(); 00378 00380 void next_(); 00381 00383 void skip_children(); 00384 00385 protected: 00386 using super_::p_; 00387 using super_::s_; 00388 std::deque<mln_psite(T::function)> stack_; // FIXME: implement p_stack. 00389 const mln_psite(T::function)* root_; 00390 }; 00391 00392 } // end of namespace mln::morpho::tree 00393 00394 } // end of namespace mln::morpho 00395 00396 template <typename I, typename S> 00397 inline 00398 std::ostream& 00399 operator<< (std::ostream& os, const morpho::tree::data<I, S>& t); 00400 00401 00402 # ifndef MLN_INCLUDE_ONLY 00403 00404 namespace morpho 00405 { 00406 00407 namespace tree 00408 { 00409 00410 template <typename I, typename S> 00411 inline 00412 data<I, S>::data(const Image<I>& f, 00413 const mln_ch_value(I, mln_psite(I))& parent, 00414 const Site_Set<S>& s) 00415 : parent_ (parent), 00416 f_ (exact(f)), 00417 s_ (exact(s)) 00418 { 00419 compute_children_(); 00420 } 00421 00422 00423 00424 template <typename I, typename S> 00425 template <typename N> 00426 inline 00427 data<I,S>::data(const Image<I>& f, 00428 const Site_Set<S>& s, 00429 const Neighborhood<N>& nbh) 00430 : f_(exact(f)), 00431 s_(exact(s)) 00432 { 00433 // Compute parent image. 00434 const N& nbh_ = exact(nbh); 00435 parent_ = morpho::tree::compute_parent(f_, nbh_, s_); 00436 00437 compute_children_(); 00438 } 00439 00440 template <typename I, typename S> 00441 inline 00442 void 00443 data<I, S>::compute_children_() 00444 { 00445 initialize(children_, f_); 00446 00447 // Store tree nodes. 00448 nroots_ = 0; 00449 mln_bkd_piter(S) p(s_); 00450 for_all(p) 00451 { 00452 if (f_(parent_(p)) != f_(p)) 00453 { 00454 nodes_.insert(p); 00455 children_(parent_(p)).insert(p); 00456 if (is_a_leaf(p)) 00457 leaves_.insert(p); 00458 } 00459 else if (parent_(p) == p) //it's a root. 00460 { 00461 nodes_.insert(p); 00462 if (is_a_leaf(p)) // One pixel image... 00463 leaves_.insert(p); 00464 ++nroots_; 00465 } 00466 } 00467 mln_assertion(leaves_.nsites() > 0); 00468 } 00469 00470 00471 template <typename I, typename S> 00472 inline 00473 mln_rvalue_(mln_ch_value(I, mln_psite(I))) 00474 data<I,S>::parent(const mln_psite(I)& p) const 00475 { 00476 mln_precondition(parent_.domain().has(p)); 00477 return parent_(p); 00478 } 00479 00480 template <typename I, typename S> 00481 inline 00482 const mln_ch_value(I, mln_psite(I))& 00483 data<I,S>::parent_image() const 00484 { 00485 mln_precondition(is_valid()); 00486 return parent_; 00487 } 00488 00489 template <typename I, typename S> 00490 inline 00491 bool 00492 data<I,S>::is_valid() const 00493 { 00494 return parent_.is_valid(); // FIXME: and... (?) 00495 } 00496 00497 template <typename I, typename S> 00498 inline 00499 bool 00500 data<I,S>::is_root(const mln_psite(I)& p) const 00501 { 00502 mln_precondition(is_valid()); 00503 mln_precondition(parent_.domain().has(p)); 00504 return parent_(p) == p; 00505 } 00506 00507 00508 template <typename I, typename S> 00509 inline 00510 bool 00511 data<I,S>::is_a_node(const mln_psite(I)& p) const 00512 { 00513 mln_precondition(is_valid()); 00514 mln_precondition(parent_.domain().has(p)); 00515 return parent_(p) == p || f_(parent_(p)) != f_(p); 00516 } 00517 00518 template <typename I, typename S> 00519 inline 00520 bool 00521 data<I,S>::is_a_non_root_node(const mln_psite(I)& p) const 00522 { 00523 mln_precondition(is_valid()); 00524 mln_precondition(parent_.domain().has(p)); 00525 return f_(parent_(p)) != f_(p); 00526 } 00527 00528 00529 template <typename I, typename S> 00530 inline 00531 bool 00532 data<I,S>::is_a_leaf(const mln_psite(I)& p) const 00533 { 00534 mln_precondition(is_valid()); 00535 mln_precondition(children_.domain().has(p)); 00536 return children_(p).nsites() == 0; 00537 } 00538 00539 template <typename I, typename S> 00540 inline 00541 const p_array<mln_psite(I)>& 00542 data<I,S>::nodes() const 00543 { 00544 mln_precondition(is_valid()); 00545 return nodes_; 00546 } 00547 00548 template <typename I, typename S> 00549 inline 00550 const p_array<mln_psite(I)>& 00551 data<I,S>::leaves() const 00552 { 00553 mln_precondition(is_valid()); 00554 return leaves_; 00555 } 00556 00557 template <typename I, typename S> 00558 inline 00559 const S& 00560 data<I,S>::domain() const 00561 { 00562 return s_; 00563 } 00564 00565 template <typename I, typename S> 00566 inline 00567 unsigned 00568 data<I,S>::nroots() const 00569 { 00570 return nroots_; 00571 } 00572 00573 template <typename I, typename S> 00574 inline 00575 const I& 00576 data<I,S>::f() const 00577 { 00578 return f_; 00579 } 00580 00581 template <typename I, typename S> 00582 inline 00583 mln_rvalue(I) 00584 data<I,S>::f(const mln_psite(I)& p) const 00585 { 00586 return f_(p); 00587 } 00588 00589 template <typename I, typename S> 00590 inline 00591 mln_rvalue_(mln_ch_value(I, p_array<mln_psite(I)>)) 00592 data<I,S>::children(const mln_psite(I)& p) const 00593 { 00594 mln_precondition(is_a_node(p)); 00595 return children_(p); 00596 } 00597 00598 template <typename I, typename S> 00599 inline 00600 const mln_ch_value(I, p_array<mln_psite(I)>)& 00601 data<I,S>::children_image() const 00602 { 00603 return children_; 00604 } 00605 00606 00607 00608 // Iterators. 00609 00610 00611 template <typename T> 00612 inline 00613 depth1st_piter<T>::depth1st_piter() 00614 : root_ (0) 00615 { 00616 } 00617 00618 template <typename T> 00619 inline 00620 depth1st_piter<T>::depth1st_piter(const T& t) 00621 : root_ (0) 00622 { 00623 this->change_target(t); 00624 } 00625 00626 template <typename T> 00627 inline 00628 depth1st_piter<T>::depth1st_piter(const T& t, 00629 const mln_psite(T::function)& p) 00630 : root_ (&p) 00631 { 00632 mln_assertion(t.is_a_node(p)); 00633 this->change_target(t); 00634 } 00635 00636 template <typename T> 00637 inline 00638 bool 00639 depth1st_piter<T>::is_valid_() const 00640 { 00641 return !stack_.empty(); 00642 } 00643 00644 template <typename T> 00645 inline 00646 void 00647 depth1st_piter<T>::invalidate_() 00648 { 00649 stack_.clear(); 00650 } 00651 00652 template <typename T> 00653 inline 00654 void 00655 depth1st_piter<T>::start_() 00656 { 00657 this->invalidate(); 00658 stack_.push_back(mln_psite(T::function)()); // needed for last element. 00659 00660 if (root_) 00661 stack_.push_back(*root_); 00662 else 00663 { 00664 mln_dn_node_piter(T) n(*s_); 00665 unsigned roots = 0; 00666 for (n.start(); n.is_valid() && roots < s_->nroots(); n.next()) 00667 if (s_->is_root(n)) 00668 { 00669 stack_.push_back(n); 00670 roots++; 00671 } 00672 } 00673 00674 this->next(); 00675 } 00676 00677 template <typename T> 00678 inline 00679 void 00680 depth1st_piter<T>::next_() 00681 { 00682 p_ = stack_.back(); 00683 stack_.pop_back(); 00684 if (! this->is_valid()) 00685 return; 00686 00687 // mln_invariant(p_.is_valid()); 00688 // std::cout << "children(p).size = " << s_->children(p_).nsites() << std::endl; 00689 // if (s_->children(p_).nsites() != 0) 00690 // { 00691 // std::cout << "elt[0] = " << s_->children(p_)[0].to_site().graph().data_hook_() << std::endl; 00692 // std::cout << "elt[0] = " << s_->children(p_)[0] << std::endl; 00693 // } 00694 // std::cout << s_->children(p_) << std::endl; 00695 00696 mln_fwd_piter(T::nodes_t) child(s_->children(p_)); 00697 for_all(child) 00698 { 00699 // std::cout << child.to_site().graph().data_hook_() << std::endl; 00700 // mln_invariant(s_->parent(child) == p_); 00701 stack_.push_back(child); 00702 } 00703 } 00704 00705 template <typename T> 00706 inline 00707 void 00708 depth1st_piter<T>::skip_children() 00709 { 00710 while (stack_.size() != 1 && s_->parent(stack_.back()) == p_) 00711 stack_.pop_back(); 00712 } 00713 00714 } // end of namespace mln::morpho::tree 00715 00716 } // end of namespace mln::morpho 00717 00718 template <typename I, typename S> 00719 inline 00720 std::ostream& 00721 operator<< (std::ostream& os, const morpho::tree::data<I, S>& t) 00722 { 00723 typedef morpho::tree::data<I, S> self_t; 00724 00725 { 00726 typedef p_array<mln_psite(self_t)> A; 00727 00728 mln_ch_value(typename self_t::function, A) content; 00729 initialize(content, t.f()); 00730 00731 os << "Nodes:\tValue:\tPoints" << std::endl; 00732 00733 mln_up_site_piter(self_t) p(t); 00734 for_all(p) 00735 if (t.is_a_node(p)) 00736 { 00737 os << p << "\t" << t.f(p) << "\t" << content(p) << std::endl; 00738 content(p).clear(); 00739 } 00740 else 00741 content(t.parent(p)).insert(p); 00742 } 00743 00744 { 00745 typename self_t::depth1st_piter n(t); 00746 mln_psite(self_t) old; 00747 00748 os << std::endl << "Hierarchy: " << std::endl; 00749 n.start(); 00750 00751 if (!n.is_valid()) 00752 return os; 00753 00754 for (old = n, n.next(); n.is_valid(); old = n, n.next()) 00755 { 00756 if (old == t.parent(n)) 00757 os << old << " <- "; 00758 else 00759 os << old << std::endl 00760 << "\t" << t.parent(n) << " <- "; 00761 } 00762 00763 os << old << std::endl; 00764 return os; 00765 } 00766 00767 } 00768 00769 # endif // ! MLN_INCLUDE_ONLY 00770 00771 } // end of namespace mln 00772 00773 00774 #endif // ! MLN_MORPHO_TREE_DATA_HH