Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 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_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 // Tests. 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 // Z-Find-Root. 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 } // end of namespace mln::morpho::tree::internal 00178 00179 00180 00181 // Implementations. 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 // Tests. 00206 internal::compute_parent_tests(f, nbh, s); 00207 00208 // Auxiliary data. 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 // Initialization. 00218 data::fill(deja_vu, false); 00219 00220 // Body. 00221 mln_bkd_piter(S) p(s); // Backward. 00222 mln_niter(N) n(nbh, p); 00223 for_all(p) 00224 { 00225 // Make-Set. 00226 parent(p) = p; 00227 zpar(p) = p; 00228 00229 for_all(n) 00230 if (f.domain().has(n) && deja_vu(n)) 00231 { 00232 // Do-Union. 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 // Canonization. 00244 { 00245 mln_fwd_piter(S) p(s); // Forward. 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 } // end of namespace mln::morpho::tree::impl::generic 00259 00260 } // end of namespace mln::morpho::tree::impl 00261 00262 00263 // Dispatch. 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 } // end of namespace mln::morpho::tree::internal 00279 00280 00281 // Facade. 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 } // end of namespace mln::morpho::tree 00303 00304 } // end of namespace mln::morpho 00305 00306 } // end of namespace mln 00307 00308 00309 #endif // ! MLN_MORPHO_TREE_COMPUTE_PARENT_HH