00001 // Copyright (C) 2007, 2008, 2009, 2011 EPITA Research and Development 00002 // Laboratory (LRDE) 00003 // 00004 // This file is part of Olena. 00005 // 00006 // Olena is free software: you can redistribute it and/or modify it under 00007 // the terms of the GNU General Public License as published by the Free 00008 // Software Foundation, version 2 of the License. 00009 // 00010 // Olena is distributed in the hope that it will be useful, 00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 // General Public License for more details. 00014 // 00015 // You should have received a copy of the GNU General Public License 00016 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00017 // 00018 // As a special exception, you may use this file as part of a free 00019 // software project without restriction. Specifically, if other files 00020 // instantiate templates or use macros or inline functions from this 00021 // file, or you compile this file and link it with other files to produce 00022 // an executable, this file does not by itself cause the resulting 00023 // executable to be covered by the GNU General Public License. This 00024 // exception does not however invalidate any other reasons why the 00025 // executable file might be covered by the GNU General Public License. 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 // Forward declaration. 00049 template <typename V> 00050 struct median_h; 00051 00052 } // end of namespace mln::accu::stat 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 } // end of namespace mln::accu::meta::stat 00071 00072 } // end of namespace mln::accu::meta 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_; // derived from h_ 00112 00113 mutable unsigned sum_minus_, sum_plus_; 00114 00115 mutable bool valid_; 00116 mutable unsigned i_; // the median_h index 00117 mutable argument t_; // the median_h value 00118 00119 // Auxiliary methods 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 // h_ 00173 h_.take(other.h_); 00174 00175 // sum_minus_ 00176 for (unsigned i = 0; i < i_; ++i) 00177 sum_minus_ += other.h_[i]; 00178 00179 // sum_plus_ 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 // go to the heaviest side 00223 if (sum_plus_ > sum_minus_) 00224 go_plus_(); 00225 else 00226 go_minus_(); // default when both sides are balanced 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 } // end of namespace mln::accu::stat 00307 00308 } // end of namespace mln::accu 00309 00310 } // end of namespace mln 00311 00312 #endif // ! MLN_ACCU_STAT_MEDIAN_H_HH
1.7.1