Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 2007, 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_DATA_SORT_OFFSETS_HH 00027 # define MLN_DATA_SORT_OFFSETS_HH 00028 00033 00034 # include <algorithm> 00035 00036 # include <mln/core/concept/image.hh> 00037 # include <mln/histo/compute.hh> 00038 # include <mln/util/array.hh> 00039 # include <mln/util/ord.hh> 00040 # include <mln/geom/nsites.hh> 00041 00042 00043 namespace mln 00044 { 00045 00046 namespace data 00047 { 00048 00052 template <typename I> 00053 util::array<unsigned> 00054 sort_offsets_increasing(const Image<I>& input); 00055 00056 00057 // /// Sort pixel offsets of the image \p input wrt decreasing pixel 00058 // /// values. 00059 // /// 00060 // template <typename I> 00061 // util::array<unsigned> 00062 // sort_offsets_decreasing(const Image<I>& input); 00063 00064 00065 00066 # ifndef MLN_INCLUDE_ONLY 00067 00068 namespace impl 00069 { 00070 00071 namespace generic 00072 { 00073 00074 // increasing 00075 00076 template <typename I> 00077 struct value_offset_less_ 00078 { 00079 const I& ima_; 00080 inline value_offset_less_(const I& ima) : ima_(ima) {} 00081 inline bool operator()(unsigned lhs, unsigned rhs) const 00082 { 00083 return util::ord_strict(ima_.element(lhs), ima_.element(rhs)) 00084 || (ima_.element(lhs) == ima_.element(rhs) 00085 && 00086 lhs < rhs); 00087 } 00088 }; 00089 00090 template <typename I> 00091 inline 00092 util::array<unsigned> 00093 sort_offsets_increasing(const Image<I>& input_) 00094 { 00095 trace::entering("data::impl::generic::sort_offsets_increasing"); 00096 00097 const I& input = exact(input_); 00098 00099 util::array<unsigned> v; 00100 v.reserve(input.nelements()); 00101 mln_fwd_pixter(const I) pxl(input); 00102 for_all(pxl) 00103 v.append(pxl.offset()); 00104 std::sort(v.hook_std_vector_().begin(), v.hook_std_vector_().end(), 00105 value_offset_less_<I>(input)); 00106 00107 trace::exiting("data::impl::generic::sort_offsets_increasing"); 00108 return v; 00109 } 00110 00111 00112 // decreasing 00113 00114 template <typename I> 00115 struct value_offset_greater_ 00116 { 00117 const I& ima_; 00118 inline value_offset_greater_(const I& ima) : ima_(ima) {} 00119 inline bool operator()(unsigned lhs, unsigned rhs) const 00120 { 00121 return util::ord_strict(ima_.element(rhs), ima_.element(lhs)) 00122 || (ima_.element(lhs) == ima_.element(rhs) 00123 && 00124 lhs > rhs); 00125 } 00126 }; 00127 00128 template <typename I> 00129 inline 00130 util::array<unsigned> 00131 sort_offsets_decreasing(const Image<I>& input_) 00132 { 00133 trace::entering("data::impl::generic::sort_offsets_decreasing"); 00134 00135 const I& input = exact(input_); 00136 00137 util::array<unsigned> v; 00138 v.reserve(input.nelements()); 00139 mln_fwd_pixter(const I) pxl(input); 00140 for_all(pxl) 00141 v.append(pxl.offset()); 00142 std::sort(v.hook_std_vector_().begin(), v.hook_std_vector_().end(), 00143 value_offset_greater_<I>(input)); 00144 00145 trace::exiting("data::impl::generic::sort_offsets_decreasing"); 00146 return v; 00147 } 00148 00149 00150 } // end of namespace mln::data::impl::generic 00151 00152 00153 00154 // increasing 00155 00156 template <typename I> 00157 inline 00158 util::array<unsigned> 00159 sort_offsets_increasing_radix(const Image<I>& input_) 00160 { 00161 trace::entering("data::impl::sort_offsets_increasing_radix"); 00162 00163 const I& input = exact(input_); 00164 00165 typedef mln_vset(I) S; 00166 const S& vset = input.values_eligible(); 00167 const unsigned n = vset.nvalues(); 00168 00169 // h 00170 histo::array<mln_value(I)> h = histo::compute(input); 00171 00172 // preparing output data 00173 std::vector<unsigned> loc(vset.nvalues()); 00174 loc[0] = 0; 00175 for (unsigned i = 1; i != n; ++i) 00176 loc[i] = loc[i-1] + h[i-1]; 00177 00178 // computing output data 00179 util::array<unsigned> vec(geom::nsites(input)); 00180 mln_fwd_pixter(const I) pxl(input); 00181 for_all(pxl) 00182 vec[loc[vset.index_of(pxl.val())]++] = pxl.offset(); 00183 00184 trace::exiting("data::impl::sort_offsets_increasing_radix"); 00185 return vec; 00186 } 00187 00188 00189 // decreasing 00190 00191 template <typename I> 00192 inline 00193 util::array<unsigned> 00194 sort_offsets_decreasing_radix(const Image<I>& input_) 00195 { 00196 trace::entering("data::impl::sort_offsets_decreasing_radix"); 00197 00198 const I& input = exact(input_); 00199 00200 typedef mln_vset(I) S; 00201 const S& vset = input.values_eligible(); 00202 const unsigned n = vset.nvalues(); 00203 00204 // h 00205 histo::array<mln_value(I)> h = histo::compute(input); 00206 00207 // preparing output data 00208 std::vector<unsigned> loc(vset.nvalues()); 00209 loc[n-1] = 0; 00210 for (int i = n - 2; i >= 0; --i) 00211 loc[i] = loc[i+1] + h[i+1]; 00212 00213 // computing output data 00214 util::array<unsigned> vec(geom::nsites(input)); 00215 mln_fwd_pixter(const I) pxl(input); 00216 for_all(pxl) 00217 vec[loc[vset.index_of(pxl.val())]++] = pxl.offset(); 00218 00219 trace::exiting("data::impl::sort_offsets_decreasing_radix"); 00220 return vec; 00221 } 00222 00223 00224 } // end of namespace mln::data::impl 00225 00226 00227 00228 namespace internal 00229 { 00230 00231 // increasing 00232 00233 template <typename I> 00234 inline 00235 util::array<unsigned> 00236 sort_offsets_increasing_dispatch(trait::image::quant::any, 00237 const Image<I>& input) 00238 { 00239 return impl::generic::sort_offsets_increasing(input); 00240 } 00241 00242 template <typename I> 00243 inline 00244 util::array<unsigned> 00245 sort_offsets_increasing_dispatch(trait::image::quant::low, 00246 const Image<I>& input) 00247 { 00248 return impl::sort_offsets_increasing_radix(input); 00249 } 00250 00251 template <typename I> 00252 inline 00253 util::array<unsigned> 00254 sort_offsets_increasing_dispatch(const Image<I>& input) 00255 { 00256 return sort_offsets_increasing_dispatch(mln_trait_image_quant(I)(), 00257 input); 00258 } 00259 00260 // decreasing 00261 00262 template <typename I> 00263 inline 00264 util::array<unsigned> 00265 sort_offsets_decreasing_dispatch(trait::image::quant::any, 00266 const Image<I>& input) 00267 { 00268 return impl::generic::sort_offsets_decreasing(input); 00269 } 00270 00271 template <typename I> 00272 inline 00273 util::array<unsigned> 00274 sort_offsets_decreasing_dispatch(trait::image::quant::low, 00275 const Image<I>& input) 00276 { 00277 return impl::sort_offsets_decreasing_radix(input); 00278 } 00279 00280 template <typename I> 00281 inline 00282 util::array<unsigned> 00283 sort_offsets_decreasing_dispatch(const Image<I>& input) 00284 { 00285 return sort_offsets_decreasing_dispatch(mln_trait_image_quant(I)(), 00286 input); 00287 } 00288 00289 } // end of namespace mln::data::internal 00290 00291 00292 00293 // Facades. 00294 00295 template <typename I> 00296 inline 00297 util::array<unsigned> 00298 sort_offsets_increasing(const Image<I>& input) 00299 { 00300 trace::entering("data::sort_offsets_increasing"); 00301 mlc_is(mln_trait_image_speed(I), 00302 trait::image::speed::fastest)::check(); 00303 00304 mln_precondition(exact(input).is_valid()); 00305 util::array<unsigned> output = internal::sort_offsets_increasing_dispatch(input); 00306 00307 trace::exiting("data::sort_offsets_increasing"); 00308 return output; 00309 } 00310 00311 template <typename I> 00312 inline 00313 util::array<unsigned> 00314 sort_offsets_decreasing(const Image<I>& input) 00315 { 00316 trace::entering("data::sort_offsets_decreasing"); 00317 mlc_is(mln_trait_image_speed(I), 00318 trait::image::speed::fastest)::check(); 00319 00320 mln_precondition(exact(input).is_valid()); 00321 util::array<unsigned> output = internal::sort_offsets_decreasing_dispatch(input); 00322 00323 trace::exiting("data::sort_offsets_decreasing"); 00324 return output; 00325 } 00326 00327 # endif // ! MLN_INCLUDE_ONLY 00328 00329 } // end of namespace mln::data 00330 00331 } // end of namespace mln 00332 00333 00334 #endif // ! MLN_DATA_SORT_OFFSETS_HH