1 // Copyright (c) 2016 CNRS and LIRIS' Establishments (France). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org) 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Linear_cell_complex/include/CGAL/GMap_linear_cell_complex_storages.h $ 7 // $Id: GMap_linear_cell_complex_storages.h 70bf903 2020-10-22T15:42:15+02:00 Guillaume Damiand 8 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // Author(s) : Guillaume Damiand <guillaume.damiand@liris.cnrs.fr> 11 // 12 #ifndef CGAL_GMAP_LINEAR_CELL_COMPLEX_STORAGES_H 13 #define CGAL_GMAP_LINEAR_CELL_COMPLEX_STORAGES_H 1 14 15 #include <CGAL/Compact_container.h> 16 #include <CGAL/Dart.h> 17 #include <CGAL/Handle_hash_function.h> 18 #include <bitset> 19 20 #include <boost/config.hpp> 21 #if (BOOST_GCC >= 40900) 22 _Pragma("GCC diagnostic push") 23 _Pragma("GCC diagnostic ignored \"-Warray-bounds\"") 24 #endif 25 26 namespace CGAL { 27 28 namespace internal { 29 template <typename M> 30 struct Combinatorial_map_helper; 31 32 template<typename Concurrent_tag, class T, class Alloc_> 33 struct Container_type; 34 } 35 36 /** @file GMap_linear_cell_complex_storages.h 37 * Definition of storages for dD Linear cell complex for generalized map. 38 */ 39 40 // Storage of darts with compact container, alpha with handles 41 // Copy of Generalized_map_storage_1 and add new types related 42 // to geometry (not possible to inherith because we use Self type 43 // as template parameter of Dart_wrapper. If we inherit, Self is not 44 // the correct type). 45 template<unsigned int d_, unsigned int ambient_dim, 46 class Traits_, class Items_, class Alloc_, class Concurrent_tag > 47 class GMap_linear_cell_complex_storage_1 48 { 49 public: 50 typedef typename Traits_::Point Point; 51 typedef typename Traits_::Vector Vector; 52 typedef typename Traits_::FT FT; 53 54 typedef GMap_linear_cell_complex_storage_1<d_, ambient_dim, Traits_, 55 Items_, Alloc_, Concurrent_tag> Self; 56 typedef CGAL::Tag_false Use_index; 57 58 typedef internal::Combinatorial_map_helper<Self> Helper; 59 60 typedef typename Items_::template Dart_wrapper<Self> Dart_wrapper; 61 62 typedef typename internal::template Get_dart_info<Dart_wrapper>::type 63 Dart_info; 64 typedef typename internal::template Get_darts_with_id<Dart_wrapper>::type 65 Darts_with_id; 66 typedef CGAL::Dart<d_, Self, Dart_info, Darts_with_id> Dart; 67 68 typedef std::allocator_traits<Alloc_> Allocator_traits; 69 typedef typename Allocator_traits::template rebind_alloc<Dart> Dart_allocator; 70 71 typedef typename internal::Container_type 72 <Concurrent_tag, Dart, Dart_allocator>::type Dart_container; 73 74 75 typedef typename Dart_container::iterator Dart_handle; 76 typedef typename Dart_container::const_iterator Dart_const_handle; 77 typedef typename Dart_container::size_type size_type; 78 79 typedef std::nullptr_t Null_handle_type; 80 static const Null_handle_type null_handle; 81 82 typedef Items_ Items; 83 typedef Alloc_ Alloc; 84 85 template <typename T> 86 struct Container_for_attributes : 87 public internal::Container_type 88 <Concurrent_tag, T, 89 typename std::allocator_traits<Alloc_>::template rebind_alloc<T>>::type 90 {}; 91 /// Typedef for attributes 92 typedef typename internal::template Get_attributes_tuple<Dart_wrapper>::type 93 Attributes; 94 95 template<int i> 96 struct Attribute_type: public Helper::template Attribute_type<i> 97 {}; 98 template<int i> 99 struct Attribute_handle: public Helper::template Attribute_handle<i> 100 {}; 101 template<int i> 102 struct Attribute_const_handle: 103 public Helper::template Attribute_const_handle<i> 104 {}; 105 template<int i> 106 struct Attribute_range: public Helper::template Attribute_range<i> 107 {}; 108 template<int i> 109 struct Attribute_const_range: 110 public Helper::template Attribute_const_range<i> 111 {}; 112 113 typedef typename Attribute_type<0>::type Vertex_attribute; 114 typedef typename Attribute_handle<0>::type Vertex_attribute_handle; 115 typedef typename Attribute_const_handle<0>::type 116 Vertex_attribute_const_handle; 117 118 typedef typename Attribute_range<0>::type Vertex_attribute_range; 119 typedef typename Attribute_const_range<0>::type 120 Vertex_attribute_const_range; 121 122 /// Number of marks 123 static const size_type NB_MARKS = 32; 124 125 /// The dimension of the generalized map. 126 static const unsigned int dimension = d_; 127 128 typedef Handle_hash_function Hash_function; 129 130 // Init init_storage()131 void init_storage() 132 { null_dart_handle=nullptr; } 133 134 /** Return if this dart is free for adimension. 135 * @param dh a dart handle 136 * @param i the dimension. 137 * @return true iff dh is linked with nullptr for \em adimension. 138 */ 139 template<unsigned int i> is_free(Dart_const_handle dh)140 bool is_free(Dart_const_handle dh) const 141 { 142 CGAL_assertion( dh!=nullptr ); 143 CGAL_assertion(i <= dimension); 144 return dh->mf[i]==dh; 145 } is_free(Dart_const_handle dh,unsigned int i)146 bool is_free(Dart_const_handle dh, unsigned int i) const 147 { 148 CGAL_assertion( dh!=nullptr ); 149 CGAL_assertion(i <= dimension); 150 return dh->mf[i]==dh; 151 } is_perforated(Dart_const_handle)152 bool is_perforated(Dart_const_handle /*dh*/) const 153 { return false; } 154 155 /// Set simultaneously all the marks of this dart to a given value. set_dart_marks(Dart_const_handle ADart,const std::bitset<NB_MARKS> & amarks)156 void set_dart_marks(Dart_const_handle ADart, 157 const std::bitset<NB_MARKS>& amarks) const 158 { 159 CGAL_assertion( ADart!=nullptr ); 160 ADart->set_marks(amarks); 161 } 162 /// Return all the marks of a dart. get_dart_marks(Dart_const_handle ADart)163 std::bitset<NB_MARKS> get_dart_marks(Dart_const_handle ADart) const 164 { 165 CGAL_assertion( ADart!=nullptr ); 166 return ADart->get_marks(); 167 } 168 /// Return the mark value of dart a given mark number. get_dart_mark(Dart_const_handle ADart,size_type amark)169 bool get_dart_mark(Dart_const_handle ADart, size_type amark) const 170 { 171 CGAL_assertion( ADart!=nullptr ); 172 return ADart->get_mark(amark); 173 } 174 175 /// Set the mark of a given mark number to a given value. set_dart_mark(Dart_const_handle ADart,size_type amark,bool avalue)176 void set_dart_mark(Dart_const_handle ADart, size_type amark, bool avalue) const 177 { 178 CGAL_assertion( ADart!=nullptr ); 179 ADart->set_mark(amark, avalue); 180 } 181 182 /// Flip the mark of a given mark number to a given value. flip_dart_mark(Dart_const_handle ADart,size_type amark)183 void flip_dart_mark(Dart_const_handle ADart, size_type amark) const 184 { 185 CGAL_assertion( ADart!=nullptr ); 186 ADart->flip_mark(amark); 187 } 188 189 // Access to alpha maps get_alpha(Dart_handle ADart,int B1)190 Dart_handle get_alpha(Dart_handle ADart, int B1) 191 { 192 CGAL_assertion(ADart!=nullptr && B1>=0 && B1<=(int)dimension); 193 return ADart->mf[B1]; 194 } get_alpha(Dart_const_handle ADart,int B1)195 Dart_const_handle get_alpha(Dart_const_handle ADart, int B1) const 196 { 197 CGAL_assertion(ADart!=nullptr && B1>=0 && B1<=(int)dimension); 198 return ADart->mf[B1]; 199 } 200 template<int B1> get_alpha(Dart_handle ADart)201 Dart_handle get_alpha(Dart_handle ADart) 202 { 203 CGAL_assertion(ADart!=nullptr && B1>=0 && B1<=(int)dimension); 204 return ADart->mf[B1]; 205 } 206 template<int B1> get_alpha(Dart_const_handle ADart)207 Dart_const_handle get_alpha(Dart_const_handle ADart) const 208 { 209 CGAL_assertion(ADart!=nullptr && B1>=0 && B1<=(int)dimension); 210 return ADart->mf[B1]; 211 } 212 213 // return a handle on the i-attribute 214 template<unsigned int i> attribute(Dart_handle ADart)215 typename Attribute_handle<i>::type attribute(Dart_handle ADart) 216 { 217 CGAL_static_assertion_msg(Helper::template Dimension_index<i>::value>=0, 218 "attribute<i> called but i-attributes are disabled."); 219 return std::get<Helper::template Dimension_index<i>::value> 220 (ADart->mattribute_handles); 221 } 222 template<unsigned int i> 223 typename Attribute_const_handle<i>::type attribute(Dart_const_handle ADart)224 attribute(Dart_const_handle ADart) const 225 { 226 CGAL_static_assertion_msg(Helper::template Dimension_index<i>::value>=0, 227 "attribute<i> called but i-attributes are disabled."); 228 return std::get<Helper::template Dimension_index<i>::value> 229 (ADart->mattribute_handles); 230 } 231 232 // Copy a given attribute 233 template<unsigned int i> copy_attribute(typename Attribute_const_handle<i>::type ah)234 typename Attribute_handle<i>::type copy_attribute 235 (typename Attribute_const_handle<i>::type ah) 236 { 237 CGAL_static_assertion_msg(Helper::template Dimension_index<i>::value>=0, 238 "copy_attribute<i> called but i-attributes are disabled."); 239 typename Attribute_handle<i>::type res= 240 std::get<Helper::template Dimension_index<i>::value> 241 (mattribute_containers).emplace(*ah); 242 this->template init_attribute_ref_counting<i>(res); 243 return res; 244 } 245 246 // Test if a given attribute is valid 247 template<unsigned int i> is_valid_attribute(typename Attribute_const_handle<i>::type ah)248 bool is_valid_attribute(typename Attribute_const_handle<i>::type ah) const 249 { 250 CGAL_assertion( ah!=nullptr ); 251 return ah->is_valid(); 252 } 253 254 // accessors and modifiers to the attribute ref counting given its handle 255 template<unsigned int i> get_attribute_ref_counting(typename Attribute_const_handle<i>::type ah)256 std::size_t get_attribute_ref_counting 257 (typename Attribute_const_handle<i>::type ah) const 258 { 259 CGAL_assertion( ah!=nullptr ); 260 return ah->get_nb_refs(); 261 } 262 template<unsigned int i> init_attribute_ref_counting(typename Attribute_handle<i>::type ah)263 void init_attribute_ref_counting(typename Attribute_handle<i>::type ah) 264 { 265 CGAL_assertion( ah!=nullptr ); 266 ah->mrefcounting=0; 267 } 268 template<unsigned int i> inc_attribute_ref_counting(typename Attribute_handle<i>::type ah)269 void inc_attribute_ref_counting(typename Attribute_handle<i>::type ah) 270 { 271 CGAL_assertion( ah!=nullptr ); 272 ah->inc_nb_refs(); 273 } 274 template<unsigned int i> dec_attribute_ref_counting(typename Attribute_handle<i>::type ah)275 void dec_attribute_ref_counting(typename Attribute_handle<i>::type ah) 276 { 277 CGAL_assertion( ah!=nullptr ); 278 ah->dec_nb_refs(); 279 } 280 281 // get the attribute given its handle 282 template<unsigned int i> 283 typename Attribute_type<i>::type& get_attribute(typename Attribute_handle<i>::type ah)284 get_attribute(typename Attribute_handle<i>::type ah) 285 { 286 CGAL_assertion( ah!=nullptr ); 287 return *ah; 288 } 289 template<unsigned int i> 290 const typename Attribute_type<i>::type& get_attribute(typename Attribute_const_handle<i>::type ah)291 get_attribute(typename Attribute_const_handle<i>::type ah) const 292 { 293 CGAL_assertion( ah!=nullptr ); 294 return *ah; 295 } 296 297 // Get the dart of the given attribute 298 template<unsigned int i> dart_of_attribute(typename Attribute_handle<i>::type ah)299 Dart_handle dart_of_attribute(typename Attribute_handle<i>::type ah) 300 { 301 CGAL_assertion( ah!=nullptr ); 302 return ah->dart(); 303 } 304 template<unsigned int i> 305 Dart_const_handle dart_of_attribute(typename Attribute_const_handle<i>::type ah)306 dart_of_attribute(typename Attribute_const_handle<i>::type ah) const 307 { 308 CGAL_assertion( ah!=nullptr ); 309 return ah->dart(); 310 } 311 312 // Set the dart of the given attribute 313 template<unsigned int i> set_dart_of_attribute(typename Attribute_handle<i>::type ah,Dart_handle adart)314 void set_dart_of_attribute(typename Attribute_handle<i>::type ah, 315 Dart_handle adart) 316 { 317 CGAL_assertion( ah!=nullptr ); 318 ah->set_dart(adart); 319 } 320 321 // Get the information associated with a given dart info(Dart_handle adart)322 Dart_info& info(Dart_handle adart) 323 { return adart->info(); } info(Dart_const_handle adart)324 const Dart_info& info(Dart_const_handle adart) const 325 { return adart->info(); } 326 327 // Get the info of the given attribute 328 template<unsigned int i> 329 typename Attribute_type<i>::type::Info & info_of_attribute(typename Attribute_handle<i>::type ah)330 info_of_attribute(typename Attribute_handle<i>::type ah) 331 { 332 CGAL_assertion( ah!=nullptr ); 333 return ah->info(); 334 } 335 template<unsigned int i> 336 const typename Attribute_type<i>::type::Info & info_of_attribute(typename Attribute_const_handle<i>::type ah)337 info_of_attribute(typename Attribute_const_handle<i>::type ah) const 338 { 339 CGAL_assertion( ah!=nullptr ); 340 return ah->info(); 341 } 342 343 // Get the info of the i-cell attribute associated with the given dart 344 template<unsigned int i> info(Dart_handle adart)345 typename Attribute_type<i>::type::Info & info(Dart_handle adart) 346 { 347 CGAL_assertion( adart!=nullptr ); 348 CGAL_assertion( attribute<i>(adart)!=nullptr ); 349 return info_of_attribute<i>(attribute<i>(adart)); 350 } 351 template<unsigned int i> 352 const typename Attribute_type<i>::type::Info & info(Dart_const_handle adart)353 info(Dart_const_handle adart) const 354 { 355 CGAL_assertion( adart!=nullptr ); 356 CGAL_assertion( attribute<i>(adart)!=nullptr ); 357 return info_of_attribute<i>(attribute<i>(adart)); 358 } 359 360 // Get the dart of the i-cell attribute associated with the given dart 361 template<unsigned int i> dart(Dart_handle adart)362 Dart_handle dart(Dart_handle adart) 363 { 364 CGAL_assertion( adart!=nullptr ); 365 CGAL_assertion( attribute<i>(adart)!=nullptr ); 366 return dart_of_attribute<i>(attribute<i>(adart)); 367 } 368 template<unsigned int i> dart(Dart_const_handle adart)369 Dart_const_handle dart(Dart_const_handle adart) const 370 { 371 CGAL_assertion( adart!=nullptr ); 372 CGAL_assertion( attribute<i>(adart)!=nullptr ); 373 return dart_of_attribute<i>(attribute<i>(adart)); 374 } 375 376 // Get the dart of the given 0-attribute point_of_vertex_attribute(typename Attribute_handle<0>::type vh)377 Point & point_of_vertex_attribute(typename Attribute_handle<0>::type vh) 378 { 379 CGAL_assertion( vh!=nullptr ); 380 return get_attribute<0>(vh).point(); 381 } 382 point_of_vertex_attribute(typename Attribute_const_handle<0>::type vh)383 const Point & point_of_vertex_attribute 384 (typename Attribute_const_handle<0>::type vh) const 385 { 386 CGAL_assertion( vh!=nullptr ); 387 return get_attribute<0>(vh).point(); 388 } 389 390 // Debug function display_dart(Dart_const_handle ADart)391 void display_dart(Dart_const_handle ADart) const 392 { std::cout<<mdarts.index(ADart); } 393 394 template<unsigned int i> display_attribute(typename Attribute_const_handle<i>::type ah)395 void display_attribute(typename Attribute_const_handle<i>::type ah) const 396 { std::cout<< std::get<Helper::template Dimension_index<i>::value> 397 (mattribute_containers).index(ah); } 398 399 protected: 400 // Set the handle on the i th attribute 401 template<unsigned int i> basic_set_dart_attribute(Dart_handle dh,typename Attribute_handle<i>::type ah)402 void basic_set_dart_attribute(Dart_handle dh, 403 typename Attribute_handle<i>::type ah) 404 { 405 std::get<Helper::template Dimension_index<i>::value> 406 (dh->mattribute_handles) = ah; 407 } 408 409 /** Link a dart with a given dart for a given dimension. 410 * @param adart the dart to link. 411 * @param adart2 the dart to link with. 412 * @param i the dimension. 413 */ 414 template<unsigned int i> dart_link_alpha(Dart_handle adart,Dart_handle adart2)415 void dart_link_alpha(Dart_handle adart, Dart_handle adart2) 416 { 417 CGAL_assertion(i <= dimension); 418 CGAL_assertion(adart!=nullptr && adart2!=nullptr); 419 adart->mf[i] = adart2; 420 } dart_link_alpha(Dart_handle adart,Dart_handle adart2,unsigned int i)421 void dart_link_alpha(Dart_handle adart, Dart_handle adart2, unsigned int i) 422 { 423 CGAL_assertion(i <= dimension); 424 CGAL_assertion(adart!=nullptr && adart2!=nullptr); 425 adart->mf[i] = adart2; 426 } 427 428 /** Unlink a dart for a given dimension. 429 * @param adart a dart. 430 * @param i the dimension. 431 */ 432 template<unsigned int i> dart_unlink_alpha(Dart_handle adart)433 void dart_unlink_alpha(Dart_handle adart) 434 { 435 CGAL_assertion(adart!=nullptr && i <= dimension); 436 adart->mf[i] = adart; 437 } dart_unlink_alpha(Dart_handle adart,unsigned int i)438 void dart_unlink_alpha(Dart_handle adart, unsigned int i) 439 { 440 CGAL_assertion(adart!=nullptr && i <= dimension); 441 adart->mf[i] = adart; 442 } 443 444 protected: 445 Dart_handle null_dart_handle; // To be compatible with combinatorial map 446 447 /// Dart container. 448 Dart_container mdarts; 449 450 /// Tuple of attributes containers 451 typename Helper::Attribute_containers mattribute_containers; 452 }; 453 454 /// null_handle 455 template <unsigned int d_, unsigned int ambient_dim, 456 class Traits_, class Items_, class Alloc_, class Concurrent_tag > 457 const typename GMap_linear_cell_complex_storage_1<d_, ambient_dim, Traits_, 458 Items_, Alloc_, Concurrent_tag>::Null_handle_type 459 GMap_linear_cell_complex_storage_1<d_, ambient_dim, Traits_, 460 Items_, Alloc_, Concurrent_tag>::null_handle = nullptr; 461 } // namespace CGAL 462 463 #if (BOOST_GCC >= 40900) 464 _Pragma("GCC diagnostic pop") 465 #endif 466 #endif // CGAL_GMAP_LINEAR_CELL_COMPLEX_STORAGES_H // 467 // EOF // 468