00001 // Copyright (C) 2007, 2008, 2009 EPITA Research and Development Laboratory (LRDE) 00002 // 00003 // This file is part of Olena. 00004 // 00005 // Olena is free software: you can redistribute it and/or modify it under 00006 // the terms of the GNU General Public License as published by the Free 00007 // Software Foundation, version 2 of the License. 00008 // 00009 // Olena is distributed in the hope that it will be useful, 00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 // General Public License for more details. 00013 // 00014 // You should have received a copy of the GNU General Public License 00015 // along with Olena. If not, see <http://www.gnu.org/licenses/>. 00016 // 00017 // As a special exception, you may use this file as part of a free 00018 // software project without restriction. Specifically, if other files 00019 // instantiate templates or use macros or inline functions from this 00020 // file, or you compile this file and link it with other files to produce 00021 // an executable, this file does not by itself cause the resulting 00022 // executable to be covered by the GNU General Public License. This 00023 // exception does not however invalidate any other reasons why the 00024 // executable file might be covered by the GNU General Public License. 00025 00026 #ifndef MLN_ACCU_STAT_RANK_HH 00027 # define MLN_ACCU_STAT_RANK_HH 00028 00035 00036 # include <vector> 00037 # include <mln/accu/internal/base.hh> 00038 # include <mln/accu/histo.hh> 00039 # include <mln/core/concept/meta_accumulator.hh> 00040 # include <mln/trait/value_.hh> 00041 # include <mln/util/pix.hh> 00042 00043 00044 namespace mln 00045 { 00046 00047 namespace accu 00048 { 00049 00050 namespace stat 00051 { 00052 00053 00059 template <typename T> 00060 struct rank : public mln::accu::internal::base< const T&, rank<T> > 00061 { 00062 typedef T argument; 00063 typedef mln::value::set<T> S; 00064 00065 rank(); 00066 explicit rank(unsigned k); 00067 00070 void init(); 00071 void take(const argument& t); 00072 void take(const rank<T>& other); 00073 void untake(const argument& t); 00074 void untake(const rank<T>& other); 00076 00077 unsigned card() const { return h_.sum(); } 00078 00080 const T& to_result() const; 00081 00084 bool is_valid() const; 00085 00087 unsigned k() const; 00088 00089 protected: 00090 00091 unsigned k_; // 0 <= k_ < n 00092 00093 mutable accu::histo<T> h_; 00094 const S& s_; // derived from h_ 00095 00096 mutable unsigned sum_minus_, sum_plus_; 00097 00098 mutable bool valid_; 00099 mutable unsigned i_; // the median index 00100 mutable argument t_; // the median value 00101 00102 // Auxiliary methods 00103 void update_() const; 00104 void go_minus_() const; 00105 void go_plus_() const; 00106 }; 00107 00108 00109 template <typename I> struct rank< util::pix<I> >; 00110 00111 00112 } // end of mln::accu::stat 00113 00114 00115 namespace meta 00116 { 00117 00118 namespace stat 00119 { 00120 00122 00123 struct rank : public Meta_Accumulator< rank > 00124 { 00125 rank(unsigned k_) : k(k_) {} 00126 00127 template <typename T> 00128 struct with 00129 { 00130 typedef accu::stat::rank<T> ret; 00131 }; 00132 00133 unsigned k; 00134 }; 00135 00136 } // end of namespace mln::accu::meta::stat 00137 00138 } // end of namespace mln::accu::meta 00139 00140 00141 template <typename T> 00142 stat::rank<T> unmeta(const meta::stat::rank& m, T) 00143 { 00144 stat::rank<T> a(m.k); 00145 return a; 00146 } 00147 00148 00149 00150 00151 namespace stat 00152 { 00153 00154 # ifndef MLN_INCLUDE_ONLY 00155 00156 template <typename T> 00157 inline 00158 rank<T>::rank() 00159 : h_(), 00160 s_(h_.vset()) 00161 { 00162 init(); 00163 } 00164 00165 template <typename T> 00166 inline 00167 rank<T>::rank(unsigned k) 00168 : k_(k), 00169 h_(), 00170 s_(h_.vset()) 00171 { 00172 init(); 00173 } 00174 00175 template <typename T> 00176 inline 00177 unsigned 00178 rank<T>::k() const 00179 { 00180 return k_; 00181 } 00182 00183 template <typename T> 00184 inline 00185 void rank<T>::take(const argument& t) 00186 { 00187 h_.take(t); 00188 00189 if (t < t_) 00190 ++sum_minus_; 00191 else if (t > t_) 00192 ++sum_plus_; 00193 00194 if (valid_) 00195 valid_ = false; 00196 } 00197 00198 template <typename T> 00199 inline 00200 void 00201 rank<T>::take(const rank<T>& other) 00202 { 00203 // h_ 00204 h_.take(other.h_); 00205 00206 // sum_minus_ 00207 for (unsigned i = 0; i < i_; ++i) 00208 sum_minus_ += other.h_[i]; 00209 00210 // sum_plus_ 00211 for (unsigned i = i_ + 1; i < h_.nvalues(); ++i) 00212 sum_plus_ += other.h_[i]; 00213 00214 if (valid_) 00215 valid_ = false; 00216 } 00217 00218 00219 template <typename T> 00220 inline 00221 void 00222 rank<T>::untake(const argument& t) 00223 { 00224 mln_precondition(h_(t) != 0); 00225 h_.untake(t); 00226 00227 if (t < t_) 00228 --sum_minus_; 00229 else if (t > t_) 00230 --sum_plus_; 00231 00232 if (valid_) 00233 valid_ = false; 00234 } 00235 00236 template <typename T> 00237 inline 00238 void 00239 rank<T>::untake(const rank<T>& other) 00240 { 00241 // h_ 00242 h_.untake(other.h_); 00243 00244 // sum_minus_ 00245 for (unsigned i = 0; i < i_; ++i) 00246 sum_minus_ -= other.h_[i]; 00247 00248 // sum_plus_ 00249 for (unsigned i = i_ + 1; i < h_.nvalues(); ++i) 00250 sum_plus_ -= other.h_[i]; 00251 00252 if (valid_) 00253 valid_ = false; 00254 } 00255 00256 template <typename T> 00257 inline 00258 void 00259 rank<T>::update_() const 00260 { 00261 valid_ = true; 00262 00263 if (h_.sum() == 0) 00264 return; 00265 00266 if (sum_minus_ > k_) 00267 go_minus_(); 00268 else 00269 if ((sum_minus_ + h_[i_]) < k_) 00270 go_plus_(); 00271 else 00272 if (h_[i_] == 0) 00273 { 00274 // go to the heaviest side 00275 if (sum_plus_ > sum_minus_) 00276 go_plus_(); 00277 else 00278 go_minus_(); // default when both sides are balanced 00279 } 00280 } 00281 00282 template <typename T> 00283 inline 00284 void 00285 rank<T>::go_minus_() const 00286 { 00287 do 00288 { 00289 sum_plus_ += h_[i_]; 00290 do 00291 --i_; 00292 while (h_[i_] == 0); 00293 sum_minus_ -= h_[i_]; 00294 } 00295 while (sum_minus_ > k_); 00296 t_ = s_[i_]; 00297 } 00298 00299 template <typename T> 00300 inline 00301 void 00302 rank<T>::go_plus_() const 00303 { 00304 do 00305 { 00306 sum_minus_ += h_[i_]; 00307 do 00308 ++i_; 00309 while (h_[i_] == 0); 00310 sum_plus_ -= h_[i_]; 00311 } 00312 while ((sum_minus_ + h_[i_]) < k_); 00313 t_ = s_[i_]; 00314 } 00315 00316 template <typename T> 00317 inline 00318 void 00319 rank<T>::init() 00320 { 00321 h_.init(); 00322 sum_minus_ = 0; 00323 sum_plus_ = 0; 00324 i_ = (s_.index_of(mln_max(argument)) 00325 - s_.index_of(mln_min(argument))) / 2; 00326 t_ = s_[i_]; 00327 valid_ = true; 00328 } 00329 00330 template <typename T> 00331 inline 00332 const T& 00333 rank<T>::to_result() const 00334 { 00335 if (! valid_) 00336 update_(); 00337 return t_; 00338 } 00339 00340 template <typename T> 00341 inline 00342 bool 00343 rank<T>::is_valid() const 00344 { 00345 return valid_; 00346 } 00347 00348 # endif // ! MLN_INCLUDE_ONLY 00349 00350 } // end of namespace mln::accu::stat 00351 00352 } // end of namespace mln::accu 00353 00354 } // end of namespace mln 00355 00356 #include <mln/accu/stat/rank_bool.hh> 00357 00358 #endif // ! MLN_ACCU_STAT_RANK_HH
1.7.1