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_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
00058
00059
00060
00061
00062
00063
00064
00065
00066 # ifndef MLN_INCLUDE_ONLY
00067
00068 namespace impl
00069 {
00070
00071 namespace generic
00072 {
00073
00074
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
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 }
00151
00152
00153
00154
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
00170 histo::array<mln_value(I)> h = histo::compute(input);
00171
00172
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
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
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
00205 histo::array<mln_value(I)> h = histo::compute(input);
00206
00207
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
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 }
00225
00226
00227
00228 namespace internal
00229 {
00230
00231
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
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 }
00290
00291
00292
00293
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 }
00330
00331 }
00332
00333
00334 #endif // ! MLN_DATA_SORT_OFFSETS_HH