00001 // Copyright (C) 2007, 2008, 2009 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_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 // FIXME: remove 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 // Auxiliary methods 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 } // end of mln::accu::stat 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 } // end of namespace mln::accu::meta::stat 00135 00136 } // end of namespace mln::accu::meta 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 // update h_ 00168 h_.take(t); 00169 00170 // particular case: 00171 // current state was initialization 00172 if (h_[i_] == 0) 00173 { 00174 // std::cout << "init!" << std::endl; 00175 i_ = s_.index_of(t); 00176 t_ = t; 00177 return; 00178 } 00179 00180 // particular case: 00181 // the median does not change 00182 if (t == t_) 00183 { 00184 // std::cout << "no change!" << std::endl; 00185 return; 00186 } 00187 00188 // general case: 00189 00190 if (t < t_) 00191 { 00192 ++sum_minus_; 00193 if (2 * sum_minus_ > h_.sum()) 00194 go_minus_(); 00195 } 00196 else 00197 // t > t_ 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 // update h_ 00214 h_.untake(t); 00215 00216 // particular case: 00217 // the only value has been removed 00218 if (h_.sum() == 0) 00219 { 00220 init(); 00221 return; 00222 } 00223 00224 // general case: 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 // t == t_ 00239 { 00240 if (h_[i_] == 0) 00241 { 00242 // go to the heaviest side 00243 if (sum_plus_ > sum_minus_) 00244 go_plus_(); 00245 else 00246 go_minus_(); // default when both sides are balanced 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 // else no change 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 } // end of namespace mln::accu::stat 00331 00332 # endif // ! MLN_INCLUDE_ONLY 00333 00334 } // end of namespace mln::accu 00335 00336 } // end of namespace mln 00337 00338 00339 #endif // ! MLN_ACCU_STAT_MEDIAN_ALT_HH