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_HH 00027 # define MLN_CORE_SITE_SET_P_QUEUE_HH 00028 00032 00040 # include <deque> 00041 # include <mln/core/site_set/p_array.hh> 00042 00043 00044 namespace mln 00045 { 00046 00047 // Forward declaration. 00048 template <typename P> class p_queue; 00049 00050 00051 namespace trait 00052 { 00053 00054 template <typename P> 00055 struct site_set_< p_queue<P> > 00056 { 00057 typedef trait::site_set::nsites::known nsites; 00058 typedef trait::site_set::bbox::unknown bbox; 00059 typedef trait::site_set::contents::growing contents; 00060 typedef trait::site_set::arity::multiple arity; 00061 }; 00062 00063 } // end of namespace trait 00064 00065 00066 00070 00073 template <typename P> 00074 class p_queue : public internal::site_set_base_< P, p_queue<P> > 00075 { 00076 typedef p_queue<P> self_; 00077 public: 00078 00080 typedef P element; 00081 00082 00084 typedef p_indexed_psite<self_> psite; 00085 00087 typedef p_indexed_fwd_piter<self_> fwd_piter; 00088 00090 typedef p_indexed_bkd_piter<self_> bkd_piter; 00091 00093 typedef fwd_piter piter; 00094 00095 00097 p_queue(); 00098 00099 00101 bool has(const psite& p) const; 00102 00104 bool has(const util::index& i) const; 00105 00107 bool is_valid() const; 00108 00109 00111 unsigned nsites() const; 00112 00113 00115 void push(const P& p); 00116 00118 typedef P i_element; 00119 00121 void insert(const P& p); 00122 00123 00126 void pop(); 00127 00130 const P& front() const; 00131 00135 P pop_front(); 00136 00137 00139 void clear(); 00140 00141 00143 const P& operator[](unsigned i) const; 00144 00146 const std::deque<P>& std_deque() const; 00147 00149 std::size_t memory_size() const; 00150 00151 00152 protected: 00153 00154 std::deque<P> q_; 00155 }; 00156 00157 00158 00159 # ifndef MLN_INCLUDE_ONLY 00160 00161 template <typename P> 00162 inline 00163 p_queue<P>::p_queue() 00164 { 00165 } 00166 00167 template <typename P> 00168 inline 00169 bool 00170 p_queue<P>::has(const psite& p) const 00171 { 00172 mln_precondition(p.target_() == this); // FIXME: Refine. 00173 if (p.index() < 0 || unsigned(p.index()) >= nsites()) 00174 return false; 00175 // The type of rhs below is mln_site(p_array<P>). 00176 mln_invariant(p.to_site() == (*this)[p.index()]); 00177 return true; 00178 } 00179 00180 template <typename P> 00181 inline 00182 bool 00183 p_queue<P>::has(const util::index& i) const 00184 { 00185 return i >= 0 && unsigned(i) < nsites(); 00186 } 00187 00188 template <typename P> 00189 inline 00190 bool 00191 p_queue<P>::is_valid() const 00192 { 00193 return true; 00194 } 00195 00196 template <typename P> 00197 inline 00198 unsigned 00199 p_queue<P>::nsites() const 00200 { 00201 return q_.size(); 00202 } 00203 00204 template <typename P> 00205 inline 00206 void 00207 p_queue<P>::push(const P& p) 00208 { 00209 q_.push_back(p); 00210 } 00211 00212 template <typename P> 00213 inline 00214 void 00215 p_queue<P>::pop() 00216 { 00217 mln_precondition(! this->is_empty()); 00218 q_.pop_front(); 00219 } 00220 00221 template <typename P> 00222 inline 00223 const P& 00224 p_queue<P>::front() const 00225 { 00226 mln_precondition(! this->is_empty()); 00227 return q_.front(); 00228 } 00229 00230 template <typename P> 00231 inline 00232 P 00233 p_queue<P>::pop_front() 00234 { 00235 mln_precondition(! this->is_empty()); 00236 P res = this->front(); 00237 this->pop(); 00238 return res; 00239 } 00240 00241 template <typename P> 00242 inline 00243 void 00244 p_queue<P>::clear() 00245 { 00246 q_.clear(); 00247 } 00248 00249 template <typename P> 00250 inline 00251 const P& 00252 p_queue<P>::operator[](unsigned i) const 00253 { 00254 mln_precondition(i < nsites()); 00255 return q_[i]; 00256 } 00257 00258 template <typename P> 00259 inline 00260 void 00261 p_queue<P>::insert(const P& p) 00262 { 00263 this->push(p); 00264 } 00265 00266 template <typename P> 00267 inline 00268 const std::deque<P>& 00269 p_queue<P>::std_deque() const 00270 { 00271 return q_; 00272 } 00273 00274 template <typename P> 00275 inline 00276 std::size_t 00277 p_queue<P>::memory_size() const 00278 { 00279 return sizeof(q_) + nsites() * sizeof(P); 00280 } 00281 00282 # endif // ! MLN_INCLUDE_ONLY 00283 00284 } // end of namespace mln 00285 00286 00287 #endif // ! MLN_CORE_SITE_SET_P_QUEUE_HH