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_PSITES_HH
00027 # define MLN_DATA_SORT_PSITES_HH
00028
00034
00035 # include <algorithm>
00036
00037 # include <mln/core/concept/image.hh>
00038 # include <mln/convert/to_p_array.hh>
00039 # include <mln/histo/compute.hh>
00040 # include <mln/util/ord.hh>
00041 # include <mln/geom/nsites.hh>
00042
00043
00044 namespace mln
00045 {
00046
00047 namespace data
00048 {
00049
00057 template <typename I>
00058 p_array<mln_psite(I)> sort_psites_increasing(const Image<I>& input);
00059
00067 template <typename I>
00068 p_array<mln_psite(I)> sort_psites_decreasing(const Image<I>& input);
00069
00070
00071 # ifndef MLN_INCLUDE_ONLY
00072
00073 namespace impl
00074 {
00075
00076
00077
00078 template <typename I>
00079 struct value_psite_less_
00080 {
00081 const I& ima_;
00082
00083 inline
00084 value_psite_less_(const I& ima)
00085 : ima_(ima)
00086 {
00087 }
00088
00089 inline
00090 bool operator()(const mln_psite(I)& lhs,
00091 const mln_psite(I)& rhs) const
00092 {
00093 return util::ord_strict(ima_(lhs), ima_(rhs))
00094 || (ima_(lhs) == ima_(rhs)
00095 &&
00096 util::ord_strict(lhs, rhs));
00097 }
00098 };
00099
00100 template <typename I>
00101 struct value_psite_greater_
00102 {
00103 const I& ima_;
00104
00105 inline
00106 value_psite_greater_(const I& ima)
00107 : ima_(ima)
00108 {
00109 }
00110
00111 inline
00112 bool operator()(const mln_psite(I)& lhs,
00113 const mln_psite(I)& rhs) const
00114 {
00115 return util::ord_strict(ima_(rhs), ima_(lhs))
00116 || (ima_(lhs) == ima_(rhs)
00117 &&
00118 util::ord_strict(rhs, lhs));
00119 }
00120 };
00121
00122
00123
00124
00125 template <typename I>
00126 inline
00127 p_array<mln_psite(I)>
00128 sort_psites_increasing_(trait::image::quant::any,
00129 const I& input)
00130 {
00131 p_array<mln_psite(I)> v = mln::convert::to_p_array(input.domain());
00132 std::sort(v.hook_std_vector_().begin(), v.hook_std_vector_().end(),
00133 value_psite_less_<I>(input));
00134 return v;
00135 }
00136
00137 template <typename I>
00138 inline
00139 p_array<mln_psite(I)>
00140 sort_psites_increasing_(trait::image::quant::low,
00141 const I& input)
00142 {
00143 typedef mln_vset(I) S;
00144 const S& vset = input.values_eligible();
00145 const unsigned n = vset.nvalues();
00146
00147
00148 histo::array<mln_value(I)> h = histo::compute(input);
00149
00150
00151 std::vector<unsigned> loc(vset.nvalues());
00152 loc[0] = 0;
00153 for (unsigned i = 1; i != n; ++i)
00154 loc[i] = loc[i-1] + h[i-1];
00155
00156
00157 std::vector<mln_psite(I)> vec(geom::nsites(input));
00158 mln_fwd_piter(I) p(input.domain());
00159 for_all(p)
00160 vec[loc[vset.index_of(input(p))]++] = p;
00161
00162 p_array<mln_psite(I)> v(vec);
00163 return v;
00164 }
00165
00166
00167
00168
00169 template <typename I>
00170 inline
00171 p_array<mln_psite(I)>
00172 sort_psites_decreasing_(trait::image::quant::any,
00173 const I& input)
00174 {
00175 p_array<mln_psite(I)> v = mln::convert::to_p_array(input.domain());
00176 std::sort(v.hook_std_vector_().begin(), v.hook_std_vector_().end(),
00177 value_psite_greater_<I>(input));
00178 return v;
00179 }
00180
00181 template <typename I>
00182 inline
00183 p_array<mln_psite(I)>
00184 sort_psites_decreasing_(trait::image::quant::low,
00185 const I& input)
00186 {
00187 typedef mln_vset(I) S;
00188 const S& vset = input.values_eligible();
00189 const unsigned n = vset.nvalues();
00190
00191
00192 histo::array<mln_value(I)> h = histo::compute(input);
00193
00194
00195 std::vector<unsigned> loc(vset.nvalues());
00196 loc[n-1] = 0;
00197 for (int i = n - 2; i >= 0; --i)
00198 loc[i] = loc[i+1] + h[i+1];
00199
00200
00201 std::vector<mln_psite(I)> vec(geom::nsites(input));
00202 mln_fwd_piter(I) p(input.domain());
00203 for_all(p)
00204 vec[loc[vset.index_of(input(p))]++] = p;
00205
00206 p_array<mln_psite(I)> v(vec);
00207 return v;
00208 }
00209
00210
00211 }
00212
00213
00214
00215
00216 template <typename I>
00217 inline
00218 p_array<mln_psite(I)>
00219 sort_psites_increasing(const Image<I>& input)
00220 {
00221 mln_precondition(exact(input).is_valid());
00222 return impl::sort_psites_increasing_(mln_trait_image_quant(I)(),
00223 exact(input));
00224 }
00225
00226 template <typename I>
00227 inline
00228 p_array<mln_psite(I)>
00229 sort_psites_decreasing(const Image<I>& input)
00230 {
00231 mln_precondition(exact(input).is_valid());
00232 return impl::sort_psites_decreasing_(mln_trait_image_quant(I)(),
00233 exact(input));
00234 }
00235
00236 # endif // ! MLN_INCLUDE_ONLY
00237
00238 }
00239
00240 }
00241
00242
00243 #endif // ! MLN_DATA_SORT_PSITES_HH