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_MAX_H_HH 00027 # define MLN_ACCU_STAT_MAX_H_HH 00028 00032 00033 # include <mln/accu/internal/base.hh> 00034 # include <mln/core/concept/meta_accumulator.hh> 00035 # include <mln/accu/histo.hh> 00036 # include <mln/util/pix.hh> 00037 00038 00039 namespace mln 00040 { 00041 00042 // Forward declaration. 00043 namespace accu { 00044 namespace stat { 00045 template <typename V> struct max_h; 00046 } 00047 } 00048 00049 00050 // Traits. 00051 00052 namespace trait 00053 { 00054 00055 template <typename V> 00056 struct accumulator_< accu::stat::max_h<V> > 00057 { 00058 typedef accumulator::has_untake::yes has_untake; 00059 typedef accumulator::has_set_value::no has_set_value; 00060 typedef accumulator::has_stop::no has_stop; 00061 typedef accumulator::when_pix::use_v when_pix; 00062 }; 00063 00064 } // end of namespace mln::trait 00065 00066 00067 namespace accu 00068 { 00069 00070 namespace meta 00071 { 00072 00073 namespace stat 00074 { 00075 00077 struct max_h : public Meta_Accumulator< max_h > 00078 { 00079 template <typename T> 00080 struct with 00081 { 00082 typedef accu::stat::max_h<T> ret; 00083 }; 00084 }; 00085 00086 } // end of namespace mln::accu::meta::stat 00087 00088 } // end of namespace mln::accu::meta 00089 00090 00091 namespace stat 00092 { 00093 00098 // 00099 template <typename V> 00100 struct max_h : public mln::accu::internal::base< const V&, max_h<V> > 00101 { 00102 typedef V argument; 00103 00104 max_h(); 00105 00108 void init(); 00109 void take(const argument& t); 00110 void take_as_init_(const argument& t); 00111 void take(const max_h<V>& other); 00112 void untake(const argument& t); 00114 00115 unsigned card() const { return h_.sum(); } 00116 00118 const argument& to_result() const; 00119 00120 const accu::histo<V>& histo() const; 00121 00124 bool is_valid() const; 00125 00126 void debug_print_() const; 00127 00128 protected: 00129 00130 mutable accu::histo<V> h_; 00131 const value::set<V>& s_; // derived from h_ 00132 00133 mutable unsigned sum_; // number of taken values > t_ 00134 mutable unsigned i_; // the current max index ('current' means 'last known') 00135 mutable argument t_; // the current max argument 00136 00137 mutable bool valid_; // validity of the current indent / argument 00138 // when valid_ is false, an update of i_ and t_ is required 00139 00140 // Dev note: we can have at the same time (sum_ == 0) and 00141 // (valid_ == false) because of the 'untake' method. 00142 00143 // Auxiliary methods 00144 void update_() const; 00145 void go_minus_() const; 00146 void go_plus_() const; 00147 00148 void invariant_() const; 00149 }; 00150 00151 00152 template <typename I> struct max_h< util::pix<I> >; 00153 00154 # ifndef MLN_INCLUDE_ONLY 00155 00156 template <typename V> 00157 inline 00158 void 00159 max_h<V>::invariant_() const 00160 { 00161 // valid_ => (sum_ == 0) 00162 mln_invariant(! valid_ || (sum_ == 0)); 00163 } 00164 00165 template <typename V> 00166 inline 00167 max_h<V>::max_h() 00168 : h_(), 00169 s_(h_.vset()) 00170 { 00171 init(); 00172 invariant_(); 00173 } 00174 00175 template <typename V> 00176 inline 00177 void 00178 max_h<V>::take(const argument& t) 00179 { 00180 if (h_.sum() == 0) 00181 { 00182 this->take_as_init_(t); 00183 return; 00184 } 00185 h_.take(t); 00186 if (t > t_) 00187 { 00188 ++sum_; 00189 valid_ = false; 00190 } 00191 invariant_(); 00192 } 00193 00194 template <typename V> 00195 inline 00196 void 00197 max_h<V>::take(const max_h<V>& other) 00198 { 00199 // h_ 00200 h_.take(other.h_); 00201 for (unsigned i = this->card() - 1; i > i_; --i) 00202 sum_ += other.h_[i]; 00203 if (valid_ && sum_ != 0) 00204 valid_ = false; 00205 // FIXME: Optimize. 00206 invariant_(); 00207 } 00208 00209 template <typename V> 00210 inline 00211 void 00212 max_h<V>::untake(const argument& t) 00213 { 00214 mln_precondition(h_(t) != 0); 00215 h_.untake(t); 00216 if (h_.sum() == 0) 00217 { 00218 init(); 00219 return; 00220 } 00221 if (t > t_) 00222 { 00223 mln_invariant(sum_ >= 1); 00224 --sum_; 00225 valid_ = false; 00226 } 00227 else 00228 if (t == t_ && h_[i_] == 0) 00229 valid_ = false; 00230 invariant_(); 00231 } 00232 00233 template <typename V> 00234 inline 00235 void 00236 max_h<V>::update_() const 00237 { 00238 if (sum_ != 0) 00239 go_plus_(); 00240 else 00241 if (h_[i_] == 0) 00242 go_minus_(); 00243 valid_ = true; 00244 00245 mln_postcondition(sum_ == 0); 00246 mln_postcondition(h_[i_] != 0); 00247 for (unsigned j = i_ + 1; j < h_.nvalues(); ++j) 00248 mln_postcondition(h_[j] == 0); 00249 } 00250 00251 template <typename V> 00252 inline 00253 void 00254 max_h<V>::go_plus_() const 00255 { 00256 do 00257 { 00258 ++i_; 00259 if (h_[i_] != 0) 00260 sum_ -= h_[i_]; 00261 } 00262 while (sum_ != 0); 00263 t_ = s_[i_]; 00264 } 00265 00266 template <typename V> 00267 inline 00268 void 00269 max_h<V>::go_minus_() const 00270 { 00271 do 00272 --i_; 00273 while (h_[i_] == 0); 00274 t_ = s_[i_]; 00275 } 00276 00277 template <typename V> 00278 inline 00279 void 00280 max_h<V>::init() 00281 { 00282 h_.init(); 00283 sum_ = 0; 00284 i_ = mln_min(argument); 00285 t_ = s_[i_]; 00286 valid_ = true; 00287 } 00288 00289 template <typename V> 00290 inline 00291 void 00292 max_h<V>::take_as_init_(const argument& t) 00293 { 00294 h_.take(t); 00295 sum_ = 0; 00296 i_ = s_.index_of(t); 00297 t_ = t; 00298 valid_ = true; 00299 } 00300 00301 template <typename V> 00302 inline 00303 const typename max_h<V>::argument& 00304 max_h<V>::to_result() const 00305 { 00306 if (! valid_) 00307 update_(); 00308 invariant_(); 00309 return t_; 00310 } 00311 00312 template <typename V> 00313 inline 00314 const accu::histo<V>& 00315 max_h<V>::histo() const 00316 { 00317 return h_; 00318 } 00319 00320 template <typename V> 00321 inline 00322 bool 00323 max_h<V>::is_valid() const 00324 { 00325 return true; 00326 } 00327 00328 template <typename V> 00329 inline 00330 void 00331 max_h<V>::debug_print_() const 00332 { 00333 std::cout << "h={" << h_ << "} h.sum = " << h_.sum() << ' '; 00334 std::cout << "sum=" << sum_ << ' ' 00335 << "valid=" << valid_ << ' ' 00336 << "i=" << i_ << ' ' 00337 << "t=" << t_ << std::endl; 00338 } 00339 00340 template <typename V> 00341 inline 00342 std::ostream& operator<<(std::ostream& ostr, const max_h<V>& m) 00343 { 00344 return ostr << m.to_result(); 00345 } 00346 00347 # endif // ! MLN_INCLUDE_ONLY 00348 00349 } // end of namespace mln::accu::stat 00350 00351 } // end of namespace mln::accu 00352 00353 } // end of namespace mln 00354 00355 00356 #endif // ! MLN_ACCU_STAT_MAX_H_HH