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