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_CORE_SITE_SET_P_QUEUE_FAST_HH 00027 # define MLN_CORE_SITE_SET_P_QUEUE_FAST_HH 00028 00035 00036 # include <mln/core/site_set/p_array.hh> 00037 00038 00039 namespace mln 00040 { 00041 00042 // Forward declaration. 00043 template <typename P> class p_queue_fast; 00044 00045 00046 00047 namespace trait 00048 { 00049 00050 template <typename P> 00051 struct site_set_< p_queue_fast<P> > 00052 { 00053 typedef trait::site_set::nsites::known nsites; 00054 typedef trait::site_set::bbox::unknown bbox; 00055 typedef trait::site_set::contents::growing contents; 00056 typedef trait::site_set::arity::multiple arity; 00057 }; 00058 00059 } // end of namespace trait 00060 00061 00062 00066 00071 template <typename P> 00072 class p_queue_fast : public internal::site_set_base_< P, p_queue_fast<P> > 00073 { 00074 typedef p_queue_fast<P> self_; 00075 public: 00076 00078 typedef P element; 00079 00081 typedef p_indexed_psite<self_> psite; 00082 00084 typedef p_indexed_fwd_piter<self_> fwd_piter; 00085 00087 typedef p_indexed_bkd_piter<self_> bkd_piter; 00088 00090 typedef fwd_piter piter; 00091 00092 00094 p_queue_fast(); 00095 00097 void reserve(typename p_array<P>::size_type n); 00098 00100 bool has(const psite& p) const; 00101 00103 bool has(const util::index& i) const; 00104 00106 bool is_valid() const; 00107 00109 bool compute_has(const P& p) const; 00110 00112 unsigned nsites() const; 00113 00115 bool empty() const; 00116 00118 void push(const P& p); 00119 00121 typedef P i_element; 00122 00124 void insert(const P& p); 00125 00126 00129 void pop(); 00130 00133 const P& front() const; 00134 00138 const P& pop_front(); 00139 00140 00142 void purge(); 00143 00145 void clear(); 00146 00147 00149 const P& operator[](unsigned i) const; 00150 00152 const std::vector<P>& std_vector() const; 00153 00155 std::size_t memory_size() const; 00156 00157 protected: 00158 00159 p_array<P> q_; 00160 unsigned begin_; 00161 unsigned end_; 00162 }; 00163 00164 00165 00166 # ifndef MLN_INCLUDE_ONLY 00167 00168 template <typename P> 00169 inline 00170 p_queue_fast<P>::p_queue_fast() 00171 { 00172 begin_ = 0; 00173 end_ = 0; 00174 } 00175 00176 template <typename P> 00177 inline 00178 void 00179 p_queue_fast<P>::reserve(typename p_array<P>::size_type n) 00180 { 00181 q_.reserve(n); 00182 } 00183 00184 template <typename P> 00185 inline 00186 void 00187 p_queue_fast<P>::purge() 00188 { 00189 std::vector<P>& v = q_.hook_std_vector_(); 00190 std::copy(v.begin() + begin_, 00191 v.begin() + end_, 00192 v.begin()); 00193 v.resize(end_ - begin_); 00194 end_ -= begin_; 00195 begin_ = 0; 00196 } 00197 00198 template <typename P> 00199 inline 00200 bool 00201 p_queue_fast<P>::has(const psite& p) const 00202 { 00203 mln_precondition(p.target_() == this); // FIXME: Refine. 00204 if (p.index() < 0 || unsigned(p.index()) >= nsites()) 00205 return false; 00206 // The type of rhs below is mln_site(p_array<P>). 00207 // mln_invariant(p.to_site() == (*this)[p.index()]); 00208 return true; 00209 } 00210 00211 template <typename P> 00212 inline 00213 bool 00214 p_queue_fast<P>::has(const util::index& i) const 00215 { 00216 return i >= 0 && unsigned(i) < nsites(); 00217 } 00218 00219 template <typename P> 00220 inline 00221 bool 00222 p_queue_fast<P>::compute_has(const P& p) const 00223 { 00224 for (unsigned i = begin_; i < end_; ++i) 00225 if (q_[i] == p) 00226 return true; 00227 return false; 00228 } 00229 00230 template <typename P> 00231 inline 00232 bool 00233 p_queue_fast<P>::is_valid() const 00234 { 00235 return true; 00236 } 00237 00238 template <typename P> 00239 inline 00240 unsigned 00241 p_queue_fast<P>::nsites() const 00242 { 00243 mln_invariant(end_ >= begin_); 00244 return end_ - begin_; 00245 } 00246 00247 template <typename P> 00248 inline 00249 bool 00250 p_queue_fast<P>::empty() const 00251 { 00252 mln_invariant(end_ >= begin_); 00253 return end_ == begin_; 00254 } 00255 00256 template <typename P> 00257 inline 00258 void 00259 p_queue_fast<P>::push(const P& p) 00260 { 00261 q_.append(p); 00262 ++end_; 00263 } 00264 00265 template <typename P> 00266 inline 00267 void 00268 p_queue_fast<P>::pop() 00269 { 00270 mln_precondition(! this->is_empty()); 00271 ++begin_; 00272 } 00273 00274 template <typename P> 00275 inline 00276 const P& 00277 p_queue_fast<P>::front() const 00278 { 00279 mln_precondition(! this->is_empty()); 00280 return q_[begin_]; 00281 } 00282 00283 template <typename P> 00284 inline 00285 const P& 00286 p_queue_fast<P>::pop_front() 00287 { 00288 mln_precondition(! this->is_empty()); 00289 const P& res = this->front(); 00290 this->pop(); 00291 return res; 00292 } 00293 00294 template <typename P> 00295 inline 00296 void 00297 p_queue_fast<P>::clear() 00298 { 00299 end_ = begin_; 00300 } 00301 00302 template <typename P> 00303 inline 00304 const P& 00305 p_queue_fast<P>::operator[](unsigned i) const 00306 { 00307 mln_precondition(i < nsites()); 00308 return q_[begin_ + i]; 00309 } 00310 00311 template <typename P> 00312 inline 00313 void 00314 p_queue_fast<P>::insert(const P& p) 00315 { 00316 this->push(p); 00317 } 00318 00319 template <typename P> 00320 inline 00321 const std::vector<P>& 00322 p_queue_fast<P>::std_vector() const 00323 { 00324 return q_.std_vector(); 00325 } 00326 00327 template <typename P> 00328 inline 00329 std::size_t 00330 p_queue_fast<P>::memory_size() const 00331 { 00332 return q_.memory_size() + 2 * sizeof(unsigned); 00333 } 00334 00335 # endif // ! MLN_INCLUDE_ONLY 00336 00337 } // end of namespace mln 00338 00339 00340 #endif // ! MLN_CORE_SITE_SET_P_QUEUE_FAST_HH