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