00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef MLN_UTIL_LAZY_SET_HH
00027 # define MLN_UTIL_LAZY_SET_HH
00028
00034 # include <vector>
00035 # include <set>
00036 # include <iterator>
00037 # include <algorithm>
00038
00039 # include <mln/core/internal/force_exact.hh>
00040 # include <mln/core/contract.hh>
00041
00042
00043 namespace mln
00044 {
00045
00046 namespace util
00047 {
00048
00065 template <typename E>
00066 class lazy_set_
00067 {
00068 public:
00069
00071 typedef E value;
00072
00081 lazy_set_<E>& insert(const E& elt);
00082
00083
00092 lazy_set_<E>& remove(const E& elt);
00093
00094
00103 const E& element(unsigned i) const;
00104
00113 const E& operator[](unsigned i) const;
00114
00117 unsigned nelements() const;
00118
00119
00126 bool has(const E& elt) const;
00127
00128
00131 bool is_empty() const;
00132
00133
00143 void clear();
00144
00145
00152 const std::vector<E>& vect() const;
00153
00155 lazy_set_();
00156
00167 void set_const_mode(bool mode);
00168
00170 bool get_mode() const;
00171
00172 private:
00173
00179 mutable std::vector<E> v_;
00180
00185 std::set<E> s_;
00186
00187
00192 void update_() const;
00193
00195 mutable bool needs_update_;
00196
00198 bool mode_;
00199 };
00200
00201
00202 # ifndef MLN_INCLUDE_ONLY
00203
00204 template <typename E>
00205 inline
00206 lazy_set_<E>::lazy_set_()
00207 {
00208 needs_update_ = false;
00209 mode_ = false;
00210 }
00211
00212 template <typename E>
00213 inline
00214 lazy_set_<E>&
00215 lazy_set_<E>::insert(const E& elt)
00216 {
00217 mln_assertion(!mode_);
00218 s_.insert(elt);
00219 if (needs_update_ == false)
00220 needs_update_ = true;
00221 return mln::internal::force_exact< lazy_set_<E> >(*this);
00222 }
00223
00224 template <typename E>
00225 inline
00226 lazy_set_<E>&
00227 lazy_set_<E>::remove(const E& elt)
00228 {
00229 mln_assertion(!mode_);
00230
00231 std::remove(s_.begin(), s_.end(), elt);
00232 if (needs_update_ == false)
00233 needs_update_ = true;
00234 return mln::internal::force_exact< lazy_set_<E> >(*this);
00235 }
00236
00237 template <typename E>
00238 inline
00239 const E&
00240 lazy_set_<E>::element(unsigned i) const
00241 {
00242 assert((!mode_ && i < s_.size())
00243 || i < v_.size());
00244 if (!mode_)
00245 if (needs_update_)
00246 update_();
00247 return v_[i];
00248 }
00249
00250 template <typename E>
00251 inline
00252 const E&
00253 lazy_set_<E>::operator[](unsigned i) const
00254 {
00255 return this->element(i);
00256 }
00257
00258 template <typename E>
00259 inline
00260 unsigned
00261 lazy_set_<E>::nelements() const
00262 {
00263 if (!mode_)
00264 return s_.size();
00265 else
00266 return v_.size();
00267 }
00268
00269 template <typename E>
00270 inline
00271 bool
00272 lazy_set_<E>::has(const E& elt) const
00273 {
00274 if (!mode_)
00275 return s_.find(elt) != s_.end();
00276 else
00277 return v_.find(elt) != v_.end();
00278 }
00279
00280 template <typename E>
00281 inline
00282 bool
00283 lazy_set_<E>::is_empty() const
00284 {
00285 return nelements() == 0;
00286 }
00287
00288 template <typename E>
00289 inline
00290 void
00291 lazy_set_<E>::clear()
00292 {
00293 v_.clear();
00294 s_.clear();
00295 needs_update_ = false;
00296 mode_ = false;
00297 mln_postcondition(is_empty());
00298 }
00299
00300 template <typename E>
00301 inline
00302 const std::vector<E>&
00303 lazy_set_<E>::vect() const
00304 {
00305 if (!mode_)
00306 if (needs_update_)
00307 update_();
00308 return v_;
00309 }
00310
00311 template <typename E>
00312 inline
00313 void
00314 lazy_set_<E>::set_const_mode(bool mode)
00315 {
00316 if (mode != mode_)
00317 {
00318 if (mode)
00319 {
00320 if (needs_update_)
00321 update_();
00322 s_.clear();
00323 }
00324 else
00325 {
00326 mln_assertion(s_.size() == 0);
00327 for (typename std::vector<E>::iterator it = v_.begin();
00328 it != v_.end(); it++)
00329 s_.insert(*it);
00330 needs_update_ = false;
00331 }
00332 mode_ = mode;
00333 }
00334 }
00335
00336 template <typename E>
00337 inline
00338 bool
00339 lazy_set_<E>::get_mode() const
00340 {
00341 return mode_;
00342 }
00343
00344 template <typename E>
00345 inline
00346 void
00347 lazy_set_<E>::update_() const
00348 {
00349 mln_precondition(needs_update_ && !mode_);
00350 v_.clear();
00351 std::copy(s_.begin(), s_.end(), std::back_inserter(v_));
00352
00353
00354
00355 needs_update_ = false;
00356 }
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371 # endif // ! MLN_INCLUDE_ONLY
00372
00373 }
00374
00375 }
00376
00377
00378 #endif // ! MLN_UTIL_LAZY_SET_HH