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