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_ACCU_STAT_RANK_HH
00027 # define MLN_ACCU_STAT_RANK_HH
00028
00035
00036 # include <vector>
00037 # include <mln/accu/internal/base.hh>
00038 # include <mln/accu/histo.hh>
00039 # include <mln/core/concept/meta_accumulator.hh>
00040 # include <mln/trait/value_.hh>
00041 # include <mln/util/pix.hh>
00042
00043
00044 namespace mln
00045 {
00046
00047 namespace accu
00048 {
00049
00050 namespace stat
00051 {
00052
00053
00059 template <typename T>
00060 struct rank : public mln::accu::internal::base< const T&, rank<T> >
00061 {
00062 typedef T argument;
00063 typedef mln::value::set<T> S;
00064
00065 rank();
00066 explicit rank(unsigned k);
00067
00070 void init();
00071 void take(const argument& t);
00072 void take(const rank<T>& other);
00073 void untake(const argument& t);
00074 void untake(const rank<T>& other);
00076
00077 unsigned card() const { return h_.sum(); }
00078
00080 const T& to_result() const;
00081
00084 bool is_valid() const;
00085
00087 unsigned k() const;
00088
00089 protected:
00090
00091 unsigned k_;
00092
00093 mutable accu::histo<T> h_;
00094 const S& s_;
00095
00096 mutable unsigned sum_minus_, sum_plus_;
00097
00098 mutable bool valid_;
00099 mutable unsigned i_;
00100 mutable argument t_;
00101
00102
00103 void update_() const;
00104 void go_minus_() const;
00105 void go_plus_() const;
00106 };
00107
00108
00109 template <typename I> struct rank< util::pix<I> >;
00110
00111
00112 }
00113
00114
00115 namespace meta
00116 {
00117
00118 namespace stat
00119 {
00120
00122
00123 struct rank : public Meta_Accumulator< rank >
00124 {
00125 rank(unsigned k_) : k(k_) {}
00126
00127 template <typename T>
00128 struct with
00129 {
00130 typedef accu::stat::rank<T> ret;
00131 };
00132
00133 unsigned k;
00134 };
00135
00136 }
00137
00138 }
00139
00140
00141 template <typename T>
00142 stat::rank<T> unmeta(const meta::stat::rank& m, T)
00143 {
00144 stat::rank<T> a(m.k);
00145 return a;
00146 }
00147
00148
00149
00150
00151 namespace stat
00152 {
00153
00154 # ifndef MLN_INCLUDE_ONLY
00155
00156 template <typename T>
00157 inline
00158 rank<T>::rank()
00159 : h_(),
00160 s_(h_.vset())
00161 {
00162 init();
00163 }
00164
00165 template <typename T>
00166 inline
00167 rank<T>::rank(unsigned k)
00168 : k_(k),
00169 h_(),
00170 s_(h_.vset())
00171 {
00172 init();
00173 }
00174
00175 template <typename T>
00176 inline
00177 unsigned
00178 rank<T>::k() const
00179 {
00180 return k_;
00181 }
00182
00183 template <typename T>
00184 inline
00185 void rank<T>::take(const argument& t)
00186 {
00187 h_.take(t);
00188
00189 if (t < t_)
00190 ++sum_minus_;
00191 else if (t > t_)
00192 ++sum_plus_;
00193
00194 if (valid_)
00195 valid_ = false;
00196 }
00197
00198 template <typename T>
00199 inline
00200 void
00201 rank<T>::take(const rank<T>& other)
00202 {
00203
00204 h_.take(other.h_);
00205
00206
00207 for (unsigned i = 0; i < i_; ++i)
00208 sum_minus_ += other.h_[i];
00209
00210
00211 for (unsigned i = i_ + 1; i < h_.nvalues(); ++i)
00212 sum_plus_ += other.h_[i];
00213
00214 if (valid_)
00215 valid_ = false;
00216 }
00217
00218
00219 template <typename T>
00220 inline
00221 void
00222 rank<T>::untake(const argument& t)
00223 {
00224 mln_precondition(h_(t) != 0);
00225 h_.untake(t);
00226
00227 if (t < t_)
00228 --sum_minus_;
00229 else if (t > t_)
00230 --sum_plus_;
00231
00232 if (valid_)
00233 valid_ = false;
00234 }
00235
00236 template <typename T>
00237 inline
00238 void
00239 rank<T>::untake(const rank<T>& other)
00240 {
00241
00242 h_.untake(other.h_);
00243
00244
00245 for (unsigned i = 0; i < i_; ++i)
00246 sum_minus_ -= other.h_[i];
00247
00248
00249 for (unsigned i = i_ + 1; i < h_.nvalues(); ++i)
00250 sum_plus_ -= other.h_[i];
00251
00252 if (valid_)
00253 valid_ = false;
00254 }
00255
00256 template <typename T>
00257 inline
00258 void
00259 rank<T>::update_() const
00260 {
00261 valid_ = true;
00262
00263 if (h_.sum() == 0)
00264 return;
00265
00266 if (sum_minus_ > k_)
00267 go_minus_();
00268 else
00269 if ((sum_minus_ + h_[i_]) < k_)
00270 go_plus_();
00271 else
00272 if (h_[i_] == 0)
00273 {
00274
00275 if (sum_plus_ > sum_minus_)
00276 go_plus_();
00277 else
00278 go_minus_();
00279 }
00280 }
00281
00282 template <typename T>
00283 inline
00284 void
00285 rank<T>::go_minus_() const
00286 {
00287 do
00288 {
00289 sum_plus_ += h_[i_];
00290 do
00291 --i_;
00292 while (h_[i_] == 0);
00293 sum_minus_ -= h_[i_];
00294 }
00295 while (sum_minus_ > k_);
00296 t_ = s_[i_];
00297 }
00298
00299 template <typename T>
00300 inline
00301 void
00302 rank<T>::go_plus_() const
00303 {
00304 do
00305 {
00306 sum_minus_ += h_[i_];
00307 do
00308 ++i_;
00309 while (h_[i_] == 0);
00310 sum_plus_ -= h_[i_];
00311 }
00312 while ((sum_minus_ + h_[i_]) < k_);
00313 t_ = s_[i_];
00314 }
00315
00316 template <typename T>
00317 inline
00318 void
00319 rank<T>::init()
00320 {
00321 h_.init();
00322 sum_minus_ = 0;
00323 sum_plus_ = 0;
00324 i_ = (s_.index_of(mln_max(argument))
00325 - s_.index_of(mln_min(argument))) / 2;
00326 t_ = s_[i_];
00327 valid_ = true;
00328 }
00329
00330 template <typename T>
00331 inline
00332 const T&
00333 rank<T>::to_result() const
00334 {
00335 if (! valid_)
00336 update_();
00337 return t_;
00338 }
00339
00340 template <typename T>
00341 inline
00342 bool
00343 rank<T>::is_valid() const
00344 {
00345 return valid_;
00346 }
00347
00348 # endif // ! MLN_INCLUDE_ONLY
00349
00350 }
00351
00352 }
00353
00354 }
00355
00356 #include <mln/accu/stat/rank_bool.hh>
00357
00358 #endif // ! MLN_ACCU_STAT_RANK_HH