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_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 // utility 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 // increasing 00124 00125 template <typename I> 00126 inline 00127 p_array<mln_psite(I)> 00128 sort_psites_increasing_(trait::image::quant::any, // general case 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, // low quantization 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 // h 00148 histo::array<mln_value(I)> h = histo::compute(input); 00149 00150 // preparing output data 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 // computing output data 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 // decreasing 00168 00169 template <typename I> 00170 inline 00171 p_array<mln_psite(I)> 00172 sort_psites_decreasing_(trait::image::quant::any, // general case 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, // low quantization 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 // h 00192 histo::array<mln_value(I)> h = histo::compute(input); 00193 00194 // preparing output data 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 // computing output data 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 } // end of namespace mln::data::impl 00212 00213 00214 // Facades. 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 } // end of namespace mln::data 00239 00240 } // end of namespace mln 00241 00242 00243 #endif // ! MLN_DATA_SORT_PSITES_HH