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_MIN_H_HH 00027 # define MLN_ACCU_STAT_MIN_H_HH 00028 00032 00033 # include <mln/accu/internal/base.hh> 00034 # include <mln/accu/histo.hh> 00035 # include <mln/value/set.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 min_h; 00046 } 00047 } 00048 00049 00050 // Traits. 00051 00052 namespace trait 00053 { 00054 00055 template <typename V> 00056 struct accumulator_< accu::stat::min_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 min_h : public Meta_Accumulator< min_h > 00078 { 00079 template <typename T> 00080 struct with 00081 { 00082 typedef accu::stat::min_h<T> ret; 00083 }; 00084 }; 00085 00086 } // end of namespace mln::meta::stat 00087 00088 } // end of namespace mln::meta 00089 00090 00091 namespace stat 00092 { 00093 00098 // 00099 template <typename V> 00100 struct min_h : public mln::accu::internal::base< const V& , min_h<V> > 00101 { 00102 typedef V argument; 00103 00104 min_h(); 00105 00108 void init(); 00109 void take(const argument& t); 00110 void take_as_init_(const argument& t); 00111 void take(const min_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_; 00134 mutable bool valid_; 00135 mutable unsigned i_; // the min index 00136 mutable argument t_; // the min value 00137 00138 // Auxiliary methods 00139 void update_() const; 00140 void go_minus_() const; 00141 void go_plus_() const; 00142 }; 00143 00144 00145 00146 template <typename I> struct min_h< util::pix<I> >; 00147 00148 00149 # ifndef MLN_INCLUDE_ONLY 00150 00151 template <typename V> 00152 inline 00153 min_h<V>::min_h() 00154 : h_(), 00155 s_(h_.vset()) 00156 { 00157 init(); 00158 } 00159 00160 template <typename V> 00161 inline 00162 void 00163 min_h<V>::take(const argument& t) 00164 { 00165 if (h_.sum() == 0) 00166 { 00167 this->take_as_init_(t); 00168 return; 00169 } 00170 h_.take(t); 00171 if (t < t_) 00172 { 00173 ++sum_; 00174 valid_ = false; 00175 } 00176 } 00177 00178 template <typename V> 00179 inline 00180 void 00181 min_h<V>::take(const min_h<V>& other) 00182 { 00183 // h_ 00184 h_.take(other.h_); 00185 for (unsigned i = 0; i < i_; ++i) 00186 sum_ += other.h_[i]; 00187 valid_ = false; 00188 // FIXME: Optimize. 00189 } 00190 00191 template <typename V> 00192 inline 00193 void 00194 min_h<V>::untake(const argument& t) 00195 { 00196 mln_precondition(h_(t) != 0); 00197 h_.untake(t); 00198 if (h_.sum() == 0) 00199 { 00200 init(); 00201 return; 00202 } 00203 if (t < t_) 00204 { 00205 mln_invariant(sum_ >= 1); 00206 --sum_; 00207 valid_ = false; 00208 } 00209 else 00210 if (t == t_ && h_[i_] == 0) 00211 valid_ = false; 00212 } 00213 00214 template <typename V> 00215 inline 00216 void 00217 min_h<V>::update_() const 00218 { 00219 if (sum_ != 0) 00220 go_minus_(); 00221 else 00222 if (h_[i_] == 0) 00223 go_plus_(); 00224 valid_ = true; 00225 } 00226 00227 template <typename V> 00228 inline 00229 void 00230 min_h<V>::go_minus_() const 00231 { 00232 do 00233 { 00234 --i_; 00235 if (h_[i_] != 0) 00236 sum_ -= h_[i_]; 00237 } 00238 while (sum_ != 0); 00239 t_ = s_[i_]; 00240 } 00241 00242 template <typename V> 00243 inline 00244 void 00245 min_h<V>::go_plus_() const 00246 { 00247 do 00248 ++i_; 00249 while (h_[i_] == 0); 00250 t_ = s_[i_]; 00251 } 00252 00253 template <typename V> 00254 inline 00255 void 00256 min_h<V>::init() 00257 { 00258 h_.init(); 00259 sum_ = 0; 00260 i_ = mln_max(argument); 00261 t_ = s_[i_]; 00262 valid_ = true; 00263 } 00264 00265 template <typename V> 00266 inline 00267 void 00268 min_h<V>::take_as_init_(const argument& t) 00269 { 00270 h_.take(t); 00271 sum_ = 0; 00272 i_ = s_.index_of(t); 00273 t_ = t; 00274 valid_ = true; 00275 } 00276 00277 template <typename V> 00278 inline 00279 const typename min_h<V>::argument& 00280 min_h<V>::to_result() const 00281 { 00282 if (! valid_) 00283 update_(); 00284 return t_; 00285 } 00286 00287 template <typename V> 00288 inline 00289 const accu::histo<V>& 00290 min_h<V>::histo() const 00291 { 00292 return h_; 00293 } 00294 00295 template <typename V> 00296 inline 00297 bool 00298 min_h<V>::is_valid() const 00299 { 00300 return true; 00301 } 00302 00303 00304 template <typename V> 00305 inline 00306 void 00307 min_h<V>::debug_print_() const 00308 { 00309 std::cout << "h={" << h_ << "} "; 00310 std::cout << "sum=" << sum_ << ' ' 00311 << "valid=" << valid_ << ' ' 00312 << "i=" << i_ << ' ' 00313 << "t=" << t_ << std::endl; 00314 } 00315 00316 template <typename V> 00317 inline 00318 std::ostream& operator<<(std::ostream& ostr, const min_h<V>& m) 00319 { 00320 return ostr << m.to_result(); 00321 } 00322 00323 # endif // ! MLN_INCLUDE_ONLY 00324 00325 00326 } // end of namespace mln::accu::stat 00327 00328 } // end of namespace mln::accu 00329 00330 } // end of namespace mln 00331 00332 #endif // ! MLN_ACCU_STAT_MIN_H_HH