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
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
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> struct 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
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
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
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_;
00212 mln_ch_value(I, nodes_t) children_;
00213
00214 function f_;
00215 sites_t s_;
00216
00217 nodes_t nodes_;
00218 leaves_t leaves_;
00219 unsigned nroots_;
00220 };
00221
00222
00223
00224
00225 template <typename T>
00226 struct up_site_piter
00227 : public mln::internal::piter_identity_< typename T::sites_t::bkd_piter,
00228 up_site_piter<T> >
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,
00249 dn_site_piter<T> >
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,
00270 up_node_piter<T> >
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,
00291 dn_node_piter<T> >
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,
00312 up_leaf_piter<T> >
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,
00333 dn_leaf_piter<T> >
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_;
00389 const mln_psite(T::function)* root_;
00390 };
00391
00392 }
00393
00394 }
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
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
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)
00460 {
00461 nodes_.insert(p);
00462 if (is_a_leaf(p))
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();
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
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)());
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
00688
00689
00690
00691
00692
00693
00694
00695
00696 mln_fwd_piter(T::nodes_t) child(s_->children(p_));
00697 for_all(child)
00698 {
00699
00700
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 }
00715
00716 }
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 }
00772
00773
00774 #endif // ! MLN_MORPHO_TREE_DATA_HH