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_MORPHO_TREE_DATA_HH
00027 # define MLN_MORPHO_TREE_DATA_HH
00028
00033
00034 # include <mln/morpho/tree/compute_parent.hh>
00035 # include <mln/core/site_set/p_array.hh>
00036 # include <mln/core/internal/site_set_iterator_base.hh>
00037 # include <mln/core/internal/piter_identity.hh>
00038 # include <deque>
00039
00040 # define mln_up_site_piter(T) typename T::up_site_piter
00041 # define mln_dn_site_piter(T) typename T::dn_site_piter
00042 # define mln_up_node_piter(T) typename T::up_node_piter
00043 # define mln_dn_node_piter(T) typename T::dn_node_piter
00044 # define mln_up_leaf_piter(T) typename T::up_leaf_piter
00045 # define mln_dn_leaf_piter(T) typename T::dn_leaf_piter
00046 # define mln_site_piter(T) typename T::site_piter
00047 # define mln_node_piter(T) typename T::node_piter
00048 # define mln_leaf_piter(T) typename T::leaf_piter
00049 # define mln_depth1st_piter(T) typename T::depth1st_piter
00050
00051 # define mln_up_site_piter_(T) T::up_site_piter
00052 # define mln_dn_site_piter_(T) T::dn_site_piter
00053 # define mln_up_node_piter_(T) T::up_node_piter
00054 # define mln_dn_node_piter_(T) T::dn_node_piter
00055 # define mln_up_leaf_piter_(T) T::up_leaf_piter
00056 # define mln_dn_leaf_piter_(T) T::dn_leaf_piter
00057 # define mln_site_piter_(T) T::site_piter
00058 # define mln_node_piter_(T) T::node_piter
00059 # define mln_leaf_piter_(T) T::leaf_piter
00060 # define mln_depth1st_piter_(T) T::depth1st_piter
00061
00062
00063 namespace mln
00064 {
00065
00066 namespace morpho
00067 {
00068
00069 namespace tree
00070 {
00071
00072
00073
00075 template <typename T> struct up_site_piter;
00076
00078 template <typename T> struct dn_site_piter;
00079
00081 template <typename T> struct up_node_piter;
00082
00084 template <typename T> struct dn_node_piter;
00085
00087 template <typename T> struct up_leaf_piter;
00088
00090 template <typename T> struct dn_leaf_piter;
00091
00093 template <typename T> struct depth1st_piter;
00094
00095
00096 template <typename I, typename S>
00097 class data
00098 {
00099 typedef data<I, S> self_;
00100
00101 public:
00103 typedef I function;
00105 typedef mln_psite(I) psite;
00106 typedef mln_site(I) site;
00108 typedef S sites_t;
00110 typedef p_array<mln_psite(I)> nodes_t;
00112 typedef p_array<mln_psite(I)> leaves_t;
00113
00115 typedef mln_ch_value(I, mln_psite(I)) parent_t;
00116
00117
00118 typedef mln::morpho::tree::up_site_piter<self_> up_site_piter;
00119 typedef mln::morpho::tree::dn_site_piter<self_> dn_site_piter;
00120 typedef up_site_piter site_piter;
00121
00122
00123 typedef mln::morpho::tree::up_node_piter<self_> up_node_piter;
00124 typedef mln::morpho::tree::dn_node_piter<self_> dn_node_piter;
00125 typedef up_node_piter node_piter;
00126
00127
00128 typedef mln::morpho::tree::up_leaf_piter<self_> up_leaf_piter;
00129 typedef mln::morpho::tree::dn_leaf_piter<self_> dn_leaf_piter;
00130 typedef up_leaf_piter leaf_piter;
00131
00132 typedef mln::morpho::tree::depth1st_piter<self_> depth1st_piter;
00133
00134
00136 template <typename N>
00137 data(const Image<I>& f, const Site_Set<S>& s, const Neighborhood<N>& nbh);
00138
00139
00140
00142
00143 const mln_psite(I)& parent(const mln_psite(I)& p) const;
00144 const parent_t& parent_image() const;
00145
00147
00149
00150 const p_array<mln_psite(I)>& children(const mln_psite(I)& p) const;
00151 const mln_ch_value(I, nodes_t)& children_image() const;
00152
00154
00156
00157 const p_array<mln_psite(I)>& nodes() const;
00158
00160
00162
00163 const p_array<mln_psite(I)>& leaves() const;
00164
00166
00168
00169 const S& domain() const;
00170
00172
00173
00174
00176
00177 bool is_valid() const;
00178 bool is_root(const mln_psite(I)& p) const;
00179 bool is_a_node(const mln_psite(I)& p) const;
00180 bool is_a_non_root_node(const mln_psite(I)& p) const;
00181 bool is_a_leaf(const mln_psite(I)& p) const;
00182
00184
00185
00186
00187
00188 unsigned nroots() const;
00189
00190
00191 const I& f() const;
00192
00193
00194 mln_rvalue(I) f(const mln_psite(I)& p) const;
00195
00196
00197 protected:
00198 const function& f_;
00199 const sites_t& s_;
00200 mln_ch_value(I, mln_psite(I)) parent_;
00201 mln_ch_value(I, nodes_t) children_;
00202 nodes_t nodes_;
00203 leaves_t leaves_;
00204 unsigned nroots_;
00205 };
00206
00207
00208
00209
00210 template <typename T>
00211 struct up_site_piter
00212 : public mln::internal::piter_identity_< typename T::sites_t::bkd_piter,
00213 up_site_piter<T> >
00214 {
00215 private:
00216 typedef typename T::sites_t::bkd_piter Pi_;
00217 typedef mln::internal::piter_identity_< Pi_, up_site_piter<T> > super_;
00218
00219 public:
00220 up_site_piter(const T& t)
00221 {
00222 this->change_target(t.domain());
00223 }
00224
00225 up_site_piter(const Pi_& pi)
00226 : super_(pi)
00227 {
00228 }
00229 };
00230
00231 template <typename T>
00232 struct dn_site_piter
00233 : public mln::internal::piter_identity_< typename T::sites_t::fwd_piter,
00234 dn_site_piter<T> >
00235 {
00236 private:
00237 typedef typename T::sites_t::fwd_piter Pi_;
00238 typedef mln::internal::piter_identity_< Pi_, dn_site_piter<T> > super_;
00239
00240 public:
00241 dn_site_piter(const T& t)
00242 {
00243 this->change_target(t.domain());
00244 }
00245
00246 dn_site_piter(const Pi_& pi)
00247 : super_(pi)
00248 {
00249 }
00250 };
00251
00252 template <typename T>
00253 struct up_node_piter
00254 : public mln::internal::piter_identity_< typename T::nodes_t::fwd_piter,
00255 up_node_piter<T> >
00256 {
00257 private:
00258 typedef typename T::nodes_t::fwd_piter Pi_;
00259 typedef mln::internal::piter_identity_< Pi_, up_node_piter<T> > super_;
00260
00261 public:
00262 up_node_piter(const T& t)
00263 {
00264 this->change_target(t.nodes());
00265 }
00266
00267 up_node_piter(const Pi_& pi)
00268 : super_(pi)
00269 {
00270 }
00271 };
00272
00273 template <typename T>
00274 struct dn_node_piter
00275 : public mln::internal::piter_identity_< typename T::nodes_t::bkd_piter,
00276 dn_node_piter<T> >
00277 {
00278 private:
00279 typedef typename T::nodes_t::bkd_piter Pi_;
00280 typedef mln::internal::piter_identity_< Pi_, dn_node_piter<T> > super_;
00281
00282 public:
00283 dn_node_piter(const T& t)
00284 {
00285 this->change_target(t.nodes());
00286 }
00287
00288 dn_node_piter(const Pi_& pi)
00289 : super_(pi)
00290 {
00291 }
00292 };
00293
00294 template <typename T>
00295 struct up_leaf_piter
00296 : public mln::internal::piter_identity_< typename T::leaves_t::fwd_piter,
00297 up_leaf_piter<T> >
00298 {
00299 private:
00300 typedef typename T::leaves_t::fwd_piter Pi_;
00301 typedef mln::internal::piter_identity_< Pi_, up_leaf_piter<T> > super_;
00302
00303 public:
00304 up_leaf_piter(const T& t)
00305 {
00306 this->change_target(t.leaves());
00307 }
00308
00309 up_leaf_piter(const Pi_& pi)
00310 : super_(pi)
00311 {
00312 }
00313 };
00314
00315 template <typename T>
00316 struct dn_leaf_piter
00317 : public mln::internal::piter_identity_< typename T::leaves_t::bkd_piter,
00318 dn_leaf_piter<T> >
00319 {
00320 private:
00321 typedef typename T::leaves_t::bkd_piter Pi_;
00322 typedef mln::internal::piter_identity_< Pi_, dn_leaf_piter<T> > super_;
00323
00324 public:
00325 dn_leaf_piter(const T& t)
00326 {
00327 this->change_target(t.leaves());
00328 }
00329
00330 dn_leaf_piter(const Pi_& pi)
00331 : super_(pi)
00332 {
00333 }
00334 };
00335
00336 template <typename T>
00337 class depth1st_piter
00338 : public mln::internal::site_set_iterator_base< T, depth1st_piter<T> >
00339 {
00340 typedef depth1st_piter<T> self_;
00341 typedef mln::internal::site_set_iterator_base<T, self_> super_;
00342
00343 public:
00344
00346 depth1st_piter();
00347
00349 depth1st_piter(const T& t);
00350
00351
00352 depth1st_piter(const T& t,
00353 const mln_psite(T::function)& p);
00354
00356 bool is_valid_() const;
00357
00359 void invalidate_();
00360
00362 void start_();
00363
00365 void next_();
00366
00368 void skip_children();
00369
00370 protected:
00371 using super_::p_;
00372 using super_::s_;
00373 std::deque<mln_psite(T::function)> stack_;
00374 const mln_psite(T::function)* root_;
00375 };
00376
00377
00378
00379
00380 # ifndef MLN_INCLUDE_ONLY
00381
00382 template <typename I, typename S>
00383 template <typename N>
00384 inline
00385 data<I,S>::data(const Image<I>& f, const Site_Set<S>& s, const Neighborhood<N>& nbh)
00386 : f_(exact(f)),
00387 s_(exact(s))
00388 {
00389 const N& nbh_ = exact(nbh);
00390
00391
00392 parent_ = morpho::tree::compute_parent(f_, nbh_, s_);
00393 initialize(children_, f);
00394
00395
00396 nroots_ = 0;
00397 mln_bkd_piter(S) p(s_);
00398 for_all(p)
00399 {
00400 if (f_(parent_(p)) != f_(p))
00401 {
00402 nodes_.insert(p);
00403 children_(parent_(p)).insert(p);
00404 if (is_a_leaf(p))
00405 leaves_.insert(p);
00406 }
00407 else if (parent_(p) == p)
00408 {
00409 nodes_.insert(p);
00410 if (is_a_leaf(p))
00411 leaves_.insert(p);
00412 ++nroots_;
00413 }
00414 }
00415 mln_assertion(leaves_.nsites() > 0);
00416 }
00417
00418 template <typename I, typename S>
00419 inline
00420 const mln_psite(I)&
00421 data<I,S>::parent(const mln_psite(I)& p) const
00422 {
00423 mln_precondition(is_valid());
00424 mln_precondition(parent_.domain().has(p));
00425 return parent_(p);
00426 }
00427
00428 template <typename I, typename S>
00429 inline
00430 const mln_ch_value(I, mln_psite(I))&
00431 data<I,S>::parent_image() const
00432 {
00433 mln_precondition(is_valid());
00434 return parent_;
00435 }
00436
00437 template <typename I, typename S>
00438 inline
00439 bool
00440 data<I,S>::is_valid() const
00441 {
00442 return parent_.is_valid();
00443 }
00444
00445 template <typename I, typename S>
00446 inline
00447 bool
00448 data<I,S>::is_root(const mln_psite(I)& p) const
00449 {
00450 mln_precondition(is_valid());
00451 mln_precondition(parent_.domain().has(p));
00452 return parent_(p) == p;
00453 }
00454
00455
00456 template <typename I, typename S>
00457 inline
00458 bool
00459 data<I,S>::is_a_node(const mln_psite(I)& p) const
00460 {
00461 mln_precondition(is_valid());
00462 mln_precondition(parent_.domain().has(p));
00463 return parent_(p) == p || f_(parent_(p)) != f_(p);
00464 }
00465
00466 template <typename I, typename S>
00467 inline
00468 bool
00469 data<I,S>::is_a_non_root_node(const mln_psite(I)& p) const
00470 {
00471 mln_precondition(is_valid());
00472 mln_precondition(parent_.domain().has(p));
00473 return f_(parent_(p)) != f_(p);
00474 }
00475
00476
00477 template <typename I, typename S>
00478 inline
00479 bool
00480 data<I,S>::is_a_leaf(const mln_psite(I)& p) const
00481 {
00482 mln_precondition(is_valid());
00483 mln_precondition(children_.domain().has(p));
00484 return children_(p).nsites() == 0;
00485 }
00486
00487 template <typename I, typename S>
00488 inline
00489 const p_array<mln_psite(I)>&
00490 data<I,S>::nodes() const
00491 {
00492 mln_precondition(is_valid());
00493 return nodes_;
00494 }
00495
00496 template <typename I, typename S>
00497 inline
00498 const p_array<mln_psite(I)>&
00499 data<I,S>::leaves() const
00500 {
00501 mln_precondition(is_valid());
00502 return leaves_;
00503 }
00504
00505 template <typename I, typename S>
00506 inline
00507 const S&
00508 data<I,S>::domain() const
00509 {
00510 return s_;
00511 }
00512
00513 template <typename I, typename S>
00514 inline
00515 unsigned
00516 data<I,S>::nroots() const
00517 {
00518 return nroots_;
00519 }
00520
00521 template <typename I, typename S>
00522 inline
00523 const I&
00524 data<I,S>::f() const
00525 {
00526 return f_;
00527 }
00528
00529 template <typename I, typename S>
00530 inline
00531 mln_rvalue(I)
00532 data<I,S>::f(const mln_psite(I)& p) const
00533 {
00534 return f_(p);
00535 }
00536
00537 template <typename I, typename S>
00538 inline
00539 const p_array<mln_psite(I)>&
00540 data<I,S>::children(const mln_psite(I)& p) const
00541 {
00542 return children_(p);
00543 }
00544
00545 template <typename I, typename S>
00546 inline
00547 const mln_ch_value(I, p_array<mln_psite(I)>)&
00548 data<I,S>::children_image() const
00549 {
00550 return children_;
00551 }
00552
00553
00554
00555
00556
00557
00558 template <typename T>
00559 inline
00560 depth1st_piter<T>::depth1st_piter()
00561 : root_ (0)
00562 {
00563 }
00564
00565 template <typename T>
00566 inline
00567 depth1st_piter<T>::depth1st_piter(const T& t)
00568 : root_ (0)
00569 {
00570 this->change_target(t);
00571 }
00572
00573 template <typename T>
00574 inline
00575 depth1st_piter<T>::depth1st_piter(const T& t,
00576 const mln_psite(T::function)& p)
00577 : root_ (&p)
00578 {
00579 mln_assertion(t.is_a_node(p));
00580 this->change_target(t);
00581 }
00582
00583 template <typename T>
00584 inline
00585 bool
00586 depth1st_piter<T>::is_valid_() const
00587 {
00588 return !stack_.empty();
00589 }
00590
00591 template <typename T>
00592 inline
00593 void
00594 depth1st_piter<T>::invalidate_()
00595 {
00596 stack_.clear();
00597 }
00598
00599 template <typename T>
00600 inline
00601 void
00602 depth1st_piter<T>::start_()
00603 {
00604 this->invalidate();
00605 stack_.push_back(mln_psite(T::function)());
00606
00607 if (root_)
00608 stack_.push_back(*root_);
00609 else
00610 {
00611 mln_dn_node_piter(T) n(*s_);
00612 unsigned roots = 0;
00613 for (n.start(); n.is_valid() && roots < s_->nroots(); n.next())
00614 if (s_->is_root(n))
00615 {
00616 stack_.push_back(n);
00617 roots++;
00618 }
00619 }
00620
00621 this->next();
00622 }
00623
00624 template <typename T>
00625 inline
00626 void
00627 depth1st_piter<T>::next_()
00628 {
00629 p_ = stack_.back();
00630 stack_.pop_back();
00631 if (!exact(this)->is_valid())
00632 return;
00633 mln_fwd_piter(T::nodes_t) child(s_->children(p_));
00634 for_all(child)
00635 stack_.push_back(child);
00636 }
00637
00638 template <typename T>
00639 inline
00640 void
00641 depth1st_piter<T>::skip_children()
00642 {
00643 while (stack_.size() != 1 && s_->parent(stack_.back()) == p_)
00644 stack_.pop_back();
00645 }
00646
00647
00648 # endif // ! MLN_INCLUDE_ONLY
00649
00650 }
00651
00652 }
00653
00654 }
00655
00656
00657 #endif // ! MLN_MORPHO_TREE_DATA_HH