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_COMPUTE_PARENT_HH
00027 # define MLN_MORPHO_TREE_COMPUTE_PARENT_HH
00028
00039
00040 # include <mln/core/concept/image.hh>
00041 # include <mln/core/concept/neighborhood.hh>
00042 # include <mln/data/fill.hh>
00043
00044
00045
00046 namespace mln
00047 {
00048
00049 namespace morpho
00050 {
00051
00052 namespace tree
00053 {
00054
00127 template <typename I, typename N, typename S>
00128 mln_ch_value(I, mln_psite(I))
00129 compute_parent(const Image<I>& f, const Neighborhood<N>& nbh,
00130 const Site_Set<S>& s);
00131
00132
00133
00134 # ifndef MLN_INCLUDE_ONLY
00135
00136
00137
00138
00139
00140 namespace internal
00141 {
00142
00143 template <typename I, typename N, typename S>
00144 void
00145 compute_parent_tests(const Image<I>& f_,
00146 const Neighborhood<N>& nbh_,
00147 const Site_Set<S>& s_)
00148 {
00149 const I& f = exact(f_);
00150 const N& nbh = exact(nbh_);
00151 const S& s = exact(s_);
00152
00153 mln_precondition(f.is_valid());
00154 mln_precondition(nbh.is_valid());
00155 mln_precondition(s == f.domain());
00156
00157 (void) f;
00158 (void) nbh;
00159 (void) s;
00160 }
00161
00162
00163
00164
00165 template <typename T>
00166 inline
00167 mln_psite(T)
00168 zfind_root(T& zpar, const mln_psite(T)& x)
00169 {
00170 mlc_equal(mln_value(T), mln_psite(T))::check();
00171 if (zpar(x) == x)
00172 return x;
00173 else
00174 return zpar(x) = zfind_root(zpar, zpar(x));
00175 }
00176
00177 }
00178
00179
00180
00181
00182
00183
00184 namespace impl
00185 {
00186
00187 namespace generic
00188 {
00189
00190 template <typename I, typename N, typename S>
00191 inline
00192 mln_ch_value(I, mln_psite(I))
00193 compute_parent(const Image<I>& f_,
00194 const Neighborhood<N>& nbh_,
00195 const Site_Set<S>& s_)
00196 {
00197 trace::entering("morpho::tree::impl::generic::compute_parent");
00198
00199 typedef mln_psite(I) P;
00200
00201 const I& f = exact(f_);
00202 const N& nbh = exact(nbh_);
00203 const S& s = exact(s_);
00204
00205
00206 internal::compute_parent_tests(f, nbh, s);
00207
00208
00209 mln_ch_value(I, bool) deja_vu;
00210 mln_ch_value(I, P) parent;
00211 mln_ch_value(I, P) zpar;
00212
00213 initialize(deja_vu, f);
00214 initialize(parent, f);
00215 initialize(zpar, f);
00216
00217
00218 data::fill(deja_vu, false);
00219
00220
00221 mln_bkd_piter(S) p(s);
00222 mln_niter(N) n(nbh, p);
00223 for_all(p)
00224 {
00225
00226 parent(p) = p;
00227 zpar(p) = p;
00228
00229 for_all(n)
00230 if (f.domain().has(n) && deja_vu(n))
00231 {
00232
00233 P r = internal::zfind_root(zpar, n);
00234 if (r != p)
00235 {
00236 parent(r) = p;
00237 zpar(r) = p;
00238 }
00239 }
00240 deja_vu(p) = true;
00241 }
00242
00243
00244 {
00245 mln_fwd_piter(S) p(s);
00246 for_all(p)
00247 {
00248 P q = parent(p);
00249 if (f(parent(q)) == f(q))
00250 parent(p) = parent(q);
00251 }
00252 }
00253
00254 trace::exiting("morpho::tree::impl::generic::compute_parent");
00255 return parent;
00256 }
00257
00258 }
00259
00260 }
00261
00262
00263
00264
00265 namespace internal
00266 {
00267
00268 template <typename I, typename N, typename S>
00269 inline
00270 mln_ch_value(I, mln_psite(I))
00271 compute_parent_dispatch(const Image<I>& f,
00272 const Neighborhood<N>& nbh,
00273 const Site_Set<S>& s)
00274 {
00275 return impl::generic::compute_parent(f, nbh, s);
00276 }
00277
00278 }
00279
00280
00281
00282
00283 template <typename I, typename N, typename S>
00284 inline
00285 mln_ch_value(I, mln_psite(I))
00286 compute_parent(const Image<I>& f, const Neighborhood<N>& nbh,
00287 const Site_Set<S>& s)
00288 {
00289 trace::entering("morpho::tree::compute_parent");
00290
00291 internal::compute_parent_tests(f, nbh, s);
00292
00293 mln_ch_value(I, mln_psite(I)) output;
00294 output = internal::compute_parent_dispatch(f, nbh, s);
00295
00296 trace::exiting("morpho::tree::compute_parent");
00297 return output;
00298 }
00299
00300 # endif // ! MLN_INCLUDE_ONLY
00301
00302 }
00303
00304 }
00305
00306 }
00307
00308
00309 #endif // ! MLN_MORPHO_TREE_COMPUTE_PARENT_HH