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