Milena (Olena)
User documentation 2.0a Id
|
00001 // Copyright (C) 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_UTIL_ADJACENCY_MATRIX_HH 00027 # define MLN_UTIL_ADJACENCY_MATRIX_HH 00028 00038 00039 # include <mln/core/image/image2d.hh> 00040 # include <mln/util/set.hh> 00041 # include <mln/util/ord_pair.hh> 00042 # include <mln/trait/value_.hh> 00043 # include <mln/metal/converts_to.hh> 00044 # include <mln/debug/println.hh> 00045 00046 00047 namespace mln 00048 { 00049 00050 namespace util 00051 { 00052 00053 namespace internal 00054 { 00055 00056 // Implementation for low quantification. 00057 00058 template <typename V, typename Q> 00059 struct adjacency_matrix_impl_selector 00060 { 00062 typedef image2d<bool> adj_t; 00063 00065 adjacency_matrix_impl_selector(const V& nelements); 00066 00068 void add(const V& e1, const V& e2); 00069 00071 void remove(const V& e1, const V& e2); 00072 00074 void clear(); 00075 00077 bool are_adjacent(const V& e1, const V& e2) const; 00078 00080 std::ostream& print_data_(std::ostream& ostr) const; 00081 00082 protected: 00083 adj_t adj_; 00084 }; 00085 00086 00087 // Implementation for high quantification. 00088 00089 template <typename V> 00090 struct adjacency_matrix_impl_selector<V, metal::bool_<false> > 00091 { 00093 typedef util::set< util::ord_pair<V> > adj_t; 00094 00096 adjacency_matrix_impl_selector(const V& nelements); 00097 00099 void add(const V& e1, const V& e2); 00100 00102 void remove(const V& e1, const V& e2); 00103 00105 void clear(); 00106 00108 bool are_adjacent(const V& e1, const V& e2) const; 00109 00111 std::ostream& print_data_(std::ostream& ostr) const; 00112 00113 protected: 00114 adj_t adj_; 00115 00116 # ifndef NDEBUG 00117 unsigned nelements_; 00118 # endif // ! NDEBUG 00119 }; 00120 00121 00122 } // end of namespace mln::util::internal 00123 00124 00134 // 00135 template <typename V = def::coord> 00136 class adjacency_matrix 00137 : private mlc_converts_to(V,unsigned)::check_t, 00138 public internal::adjacency_matrix_impl_selector<V, typename mlc_equal(mln_trait_value_quant(V),trait::value::quant::low)::eval> 00139 { 00140 typedef internal::adjacency_matrix_impl_selector<V, typename mlc_equal(mln_trait_value_quant(V),trait::value::quant::low)::eval> 00141 impl_t; 00142 00143 typedef typename impl_t::adj_t adj_t; 00144 00145 public: 00150 adjacency_matrix(); 00153 adjacency_matrix(const V& nelements); 00156 00158 const adj_t& hook_data_() const; 00159 }; 00160 00161 00162 // << 00163 00164 template <typename V> 00165 std::ostream& 00166 operator<<(std::ostream& ostr, const adjacency_matrix<V>& adj); 00167 00168 00169 00170 # ifndef MLN_INCLUDE_ONLY 00171 00172 00173 namespace internal 00174 { 00175 00176 // Low quantification. 00177 00178 template <typename V, typename Q> 00179 adjacency_matrix_impl_selector<V, Q>::adjacency_matrix_impl_selector(const V& nelements) 00180 : adj_(nelements, nelements) 00181 { 00182 clear(); 00183 } 00184 00185 template <typename V, typename Q> 00186 void 00187 adjacency_matrix_impl_selector<V, Q>::add(const V& e1, const V& e2) 00188 { 00189 mln_precondition(adj_.is_valid()); 00190 mln_precondition(e1 < adj_.nrows()); 00191 mln_precondition(e2 < adj_.nrows()); 00192 00193 if (e1 > e2) 00194 opt::at(adj_, e2, e1) = true; 00195 else 00196 opt::at(adj_, e1, e2) = true; 00197 } 00198 00199 template <typename V, typename Q> 00200 void 00201 adjacency_matrix_impl_selector<V, Q>::remove(const V& e1, const V& e2) 00202 { 00203 mln_precondition(adj_.is_valid()); 00204 mln_precondition(e1 < adj_.nrows()); 00205 mln_precondition(e2 < adj_.nrows()); 00206 00207 if (e1 > e2) 00208 opt::at(adj_, e2, e1) = false; 00209 else 00210 opt::at(adj_, e1, e2) = false; 00211 } 00212 00213 template <typename V, typename Q> 00214 void 00215 adjacency_matrix_impl_selector<V, Q>::clear() 00216 { 00217 mln_precondition(adj_.is_valid()); 00218 data::fill(adj_, false); 00219 } 00220 00221 template <typename V, typename Q> 00222 bool 00223 adjacency_matrix_impl_selector<V, Q>::are_adjacent(const V& e1, 00224 const V& e2) const 00225 { 00226 mln_precondition(adj_.is_valid()); 00227 mln_precondition(e1 < adj_.nrows()); 00228 mln_precondition(e2 < adj_.nrows()); 00229 00230 if (e1 > e2) 00231 return opt::at(adj_, e2, e1); 00232 return opt::at(adj_, e1, e2); 00233 } 00234 00235 template <typename V, typename Q> 00236 std::ostream& 00237 adjacency_matrix_impl_selector<V, Q>::print_data_(std::ostream& ostr) const 00238 { 00239 mln_precondition(adj_.is_valid()); 00240 debug::println(adj_); 00241 return ostr; 00242 } 00243 00244 00245 00246 00247 // High quantification. 00248 00249 template <typename V> 00250 adjacency_matrix_impl_selector<V, metal::bool_<false> > 00251 ::adjacency_matrix_impl_selector(const V& nelements) 00252 { 00253 (void) nelements; 00254 # ifndef NDEBUG 00255 nelements_ = nelements; 00256 # endif // ! NDEBUG 00257 } 00258 00259 template <typename V> 00260 void 00261 adjacency_matrix_impl_selector<V, metal::bool_<false> > 00262 ::add(const V& e1, const V& e2) 00263 { 00264 mln_precondition(int(e1) < int(nelements_)); 00265 mln_precondition(int(e2) < int(nelements_)); 00266 adj_.insert(make::ord_pair(e1, e2)); 00267 } 00268 00269 template <typename V> 00270 void 00271 adjacency_matrix_impl_selector<V, metal::bool_<false> > 00272 ::remove(const V& e1, const V& e2) 00273 { 00274 mln_precondition(int(e1) < int(nelements_)); 00275 mln_precondition(int(e2) < int(nelements_)); 00276 mln_precondition(adj_.has(make::ord_pair(e1, e2))); 00277 adj_.remove(make::ord_pair(e1, e2)); 00278 } 00279 00280 template <typename V> 00281 void 00282 adjacency_matrix_impl_selector<V, metal::bool_<false> >::clear() 00283 { 00284 adj_.clear(); 00285 } 00286 00287 template <typename V> 00288 bool 00289 adjacency_matrix_impl_selector<V, metal::bool_<false> > 00290 ::are_adjacent(const V& e1, const V& e2) const 00291 { 00292 mln_precondition(int(e1) < int(nelements_)); 00293 mln_precondition(int(e2) < int(nelements_)); 00294 return adj_.has(make::ord_pair(e1, e2)); 00295 } 00296 00297 template <typename V> 00298 std::ostream& 00299 adjacency_matrix_impl_selector<V, metal::bool_<false> >::print_data_(std::ostream& ostr) const 00300 { 00301 return ostr << adj_; 00302 } 00303 00304 } // end of namespace mln::internal 00305 00306 00307 template <typename V> 00308 adjacency_matrix<V>::adjacency_matrix() 00309 : impl_t() 00310 { 00311 } 00312 00313 00314 template <typename V> 00315 adjacency_matrix<V>::adjacency_matrix(const V& nelements) 00316 : impl_t(nelements) 00317 { 00318 } 00319 00320 00321 template <typename V> 00322 std::ostream& 00323 operator<<(std::ostream& ostr, const adjacency_matrix<V>& adj) 00324 { 00325 return adj.print_data_(ostr); 00326 } 00327 00328 00329 # endif // ! MLN_UTIL_ADJACENCY_MATRIX_HH 00330 00331 } // end of namespace mln::util 00332 00333 } // end of namespace mln 00334 00335 00336 #endif // ! MLN_UTIL_ADJACENCY_MATRIX_HH