1 // Copyright (c) 2010-2011 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_iterators_base.h $ 7 // $Id: Combinatorial_map_iterators_base.h 5ecd852 2021-04-26T21:37:02+01:00 Giles Bathgate 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_ITERATORS_BASE_HH 13 #define CGAL_COMBINATORIAL_MAP_ITERATORS_BASE_HH 1 14 15 #include <CGAL/disable_warnings.h> 16 17 #include <CGAL/Compact_container.h> 18 #include <queue> 19 #include <boost/mpl/if.hpp> 20 #include <boost/type_traits/is_same.hpp> 21 22 namespace CGAL { 23 24 /** @file Combinatorial_map_iterators_base.h 25 * Basic classes that serve as tools for definition of iterators. 26 There are 3 classes: 27 * - CMap_dart_iterator<Map,Const> is the basic generic class defining 28 * what is an interator on darts. 29 * - CMap_extend_iterator<Map,Ite,Bi> to extend the given iterator by adding 30 * the involution Bi. 31 * - CMap_non_basic_iterator<Map_,Ite> to transform the basic iterator Ite 32 * into the corresponding non basic iterator. 33 * - CMap_range<Map,It,ConstIt,BasicIt> generic definition of a range 34 * given an iterator and its const version 35 * - CMap_const_range<Map,It,ConstIt,BasicIt> generic definition of a const 36 * range given an iterator and its const version 37 */ 38 //**************************************************************************** 39 /// OperationState: type to keep the last operation used by the previous ++. 40 typedef char OperationState; 41 42 /// Enum of all the possible operations used by the ++ operator. 43 enum 44 { 45 OP_NONE = -1, ///< Beginning of the iterator (there is not yet operator++). 46 OP_BETAI, ///< Previous op was the first beta. 47 OP_BETAI_INV, ///< Previous op was the inverse of the first beta. 48 OP_BETAJ, ///< Previous op was the second beta. 49 OP_BETAK, ///< Previous op was the third beta. 50 OP_BETA0I, ///< Previous op was beta0 o the first beta. 51 OP_BETAI1, ///< Previous op was the first beta o beta1. 52 OP_BETAIJ, ///< Previous op was the composition of two beta. 53 OP_BETAJI, ///< Previous op was the composition of two beta. 54 OP_BETA21, ///< Previous op was beta21. 55 OP_JUMP, ///< Previous op was a jump . 56 OP_POP, ///< Previous op pop a dart from a stack or a queue. 57 OP_END ///< Previous op go out of the iterator. 58 }; 59 //**************************************************************************** 60 /** Generic class of iterator onto darts. 61 * Class CMap_dart_iterator is a generic iterator. All the combinatorial 62 * map iterator classes inherit from this class (or one of its subclass). 63 */ 64 template < typename Map_,bool Const=false > 65 class CMap_dart_iterator: public boost::mpl::if_c< Const, 66 typename Map_::Dart_container::const_iterator, 67 typename Map_::Dart_container::iterator>::type 68 //public internal::CC_iterator<typename Map_::Dart_container,Const> 69 { 70 public: 71 typedef CMap_dart_iterator<Map_,Const> Self; 72 73 typedef typename boost::mpl::if_c< Const, 74 typename Map_::Dart_container::const_iterator, 75 typename Map_::Dart_container::iterator>::type Base; 76 77 typedef typename boost::mpl::if_c< Const, 78 typename Map_::Dart_const_handle, 79 typename Map_::Dart_handle>::type 80 Dart_handle; 81 typedef typename boost::mpl::if_c< Const, const Map_, 82 Map_>::type Map; 83 84 typedef std::input_iterator_tag iterator_category; 85 typedef typename Base::value_type value_type; 86 typedef typename Base::difference_type difference_type; 87 typedef typename Base::pointer pointer; 88 typedef typename Base::reference reference; 89 90 /// true iff this iterator is basic 91 typedef Tag_true Basic_iterator; 92 93 typedef typename Map::size_type size_type; 94 95 public: 96 /// Main constructor. CMap_dart_iterator(Map & amap,Dart_handle adart)97 CMap_dart_iterator(Map& amap, Dart_handle adart): 98 Base(adart), 99 mmap(&amap), 100 mfirst_dart(adart), 101 mprev_op(OP_NONE) 102 {} 103 104 /// == operator. 105 bool operator==(const Self& aiterator) const 106 { 107 return ( ((*this==mmap->null_handle) && (aiterator==mmap->null_handle)) || 108 (mfirst_dart == aiterator.mfirst_dart && 109 static_cast<const Base&>(*this)== 110 static_cast<const Base&>(aiterator)) ); 111 } 112 113 /// != operator. 114 bool operator!=(const Self& aiterator) const 115 { return !operator==(aiterator); } 116 117 /// Accessor to the initial dart of the iterator. get_first_dart()118 Dart_handle get_first_dart() const { return mfirst_dart; } 119 120 /// Accessor to the combinatorial map. get_combinatorial_map()121 Map* get_combinatorial_map() const { return mmap; } 122 123 /// Rewind of the iterator to its beginning. rewind()124 void rewind() 125 { set_current_dart(mfirst_dart); mprev_op = OP_NONE; } 126 127 /// Test if the iterator is at its end. cont()128 bool cont() const 129 { return static_cast<const Base&>(*this)!=mmap->null_handle; } 130 131 /// Get the previous operation used for the last ++. prev_operation()132 OperationState prev_operation() const { return mprev_op; } 133 134 protected: 135 /// Set the current dart to a given dart set_current_dart(Dart_handle adart)136 void set_current_dart(Dart_handle adart) 137 { Base::operator=(adart); } 138 139 private: 140 /// operator -- in private to invalidate the base operator. 141 Self& operator--() 142 { return *this; } 143 /// operator -- in private to invalidate the base operator. 144 Self operator--(int) 145 { return *this; } 146 147 protected: 148 /// test if adart->beta(ai) exists and is not marked for amark is_unmarked(Dart_handle adart,unsigned int ai,size_type amark)149 bool is_unmarked(Dart_handle adart, unsigned int ai, size_type amark) const 150 { return 151 !mmap->is_marked(mmap->beta(adart,ai), amark); 152 } 153 154 /// test if adart->beta(ai)->beta(aj) exists exist_betaij(Dart_handle adart,unsigned int ai,unsigned int aj)155 bool exist_betaij(Dart_handle adart, unsigned int ai, unsigned int aj) const 156 { return !mmap->is_free(adart, ai) && !mmap->is_free(mmap->beta(adart, ai), aj); } 157 158 /// test if adart->beta(ai)->beta(aj) exists and is not marked for amark is_unmarked2(Dart_handle adart,unsigned int ai,unsigned int aj,typename Map::size_type amark)159 bool is_unmarked2(Dart_handle adart, unsigned int ai, unsigned int aj, 160 typename Map::size_type amark) const 161 { return 162 !mmap->is_marked(mmap->beta(adart, ai, aj), amark); 163 } 164 165 protected: 166 /// The map containing the darts to iterate on. 167 Map* mmap; 168 169 /// The initial dart of the iterator. 170 Dart_handle mfirst_dart; 171 172 /// The last operation used for the ++ operator. 173 OperationState mprev_op; 174 }; 175 //**************************************************************************** 176 /* Class CMap_extend_iterator<Map,Ite,Bi> which extend a given iterator by 177 * adding Bi and by using a stack and a mark. 178 * General case when Ite does not have already a stack. 179 */ 180 template <typename Map_,typename Ite,int Bi, 181 typename Ite_has_stack=typename Ite::Use_mark> 182 class CMap_extend_iterator: public Ite 183 { 184 public: 185 typedef CMap_extend_iterator<Map_,Ite,Bi, Ite_has_stack> Self; 186 typedef Ite Base; 187 188 typedef typename Base::Dart_handle Dart_handle; 189 typedef typename Base::Map Map; 190 191 typedef Tag_true Use_mark; 192 193 typedef typename Map::size_type size_type; 194 195 CGAL_static_assertion( (Bi<=Map::dimension && 196 boost::is_same<Ite_has_stack,Tag_false>::value) ); 197 198 public: 199 /// Main constructor. CMap_extend_iterator(Map & amap,Dart_handle adart,size_type amark)200 CMap_extend_iterator(Map& amap, Dart_handle adart, size_type amark): 201 Base(amap, adart), 202 mmark_number(amark), 203 minitial_dart(adart) 204 { 205 if ( minitial_dart!=amap.null_handle ) 206 { 207 this->mmap->mark_null_dart(mmark_number); 208 this->mmap->mark(minitial_dart, mmark_number); 209 if (!this->mmap->is_free(minitial_dart, Bi) && 210 this->mmap->beta(minitial_dart, Bi)!=minitial_dart ) 211 { 212 mto_treat.push(this->mmap->beta(minitial_dart, Bi)); 213 } 214 } 215 } 216 217 /// Rewind of the iterator to its beginning. rewind()218 void rewind() 219 { 220 CGAL_assertion(mmark_number != Map::INVALID_MARK); 221 Base::operator= ( Base(*this->mmap,minitial_dart) ); 222 mto_treat = std::queue<Dart_handle>(); 223 this->mmap->mark(minitial_dart, mmark_number); 224 this->mmap->mark_null_dart(mmark_number); 225 if (!this->mmap->is_free(minitial_dart, Bi) && 226 this->mmap->beta(minitial_dart, Bi)!=minitial_dart) 227 { 228 mto_treat.push(this->mmap->beta(minitial_dart, Bi)); 229 } 230 } 231 232 /// Prefix ++ operator. 233 Self& operator++() 234 { 235 CGAL_assertion(mmark_number != Map::INVALID_MARK); 236 CGAL_assertion(this->cont()); 237 238 do 239 { 240 Base::operator++(); 241 } 242 while ( this->cont() && 243 this->mmap->is_marked(*this, mmark_number) ); 244 245 if ( !this->cont() ) 246 { 247 while ( !mto_treat.empty() && 248 this->mmap->is_marked(mto_treat.front(), mmark_number)) 249 { 250 mto_treat.pop(); 251 } 252 253 if ( !mto_treat.empty() ) 254 { 255 Base::operator= ( Base(*this->mmap,mto_treat.front()) ); 256 mto_treat.pop(); 257 this->mprev_op = OP_POP; 258 CGAL_assertion( !this->mmap->is_marked((*this), mmark_number) ); 259 this->mmap->mark((*this), mmark_number); 260 261 if ( 262 !this->mmap->is_marked(this->mmap->beta(*this, Bi), mmark_number) ) 263 { 264 mto_treat.push(this->mmap->beta(*this, Bi)); 265 } 266 } 267 } 268 else 269 { 270 this->mmap->mark((*this), mmark_number); 271 if ( 272 !this->mmap->is_marked(this->mmap->beta(*this, Bi), mmark_number) ) 273 { 274 mto_treat.push(this->mmap->beta(*this, Bi)); 275 } 276 } 277 278 return *this; 279 } 280 281 /// Postfix ++ operator. 282 Self operator++(int) 283 { Self res=*this; operator ++(); return res; } 284 285 protected: 286 /// Queue of darts to process. 287 std::queue<Dart_handle> mto_treat; 288 289 /// Index of the used mark. 290 size_type mmark_number; 291 292 /// Initial dart 293 Dart_handle minitial_dart; 294 }; 295 //**************************************************************************** 296 /* Class CMap_extend_iterator<Map,Ite,Bi> which extend a given iterator by 297 * adding Bi and by using a stack and a mark. 298 * Specialization when Ite has already a stack. 299 */ 300 template <typename Map_,typename Ite,int Bi> 301 class CMap_extend_iterator<Map_,Ite,Bi,Tag_true>: public Ite 302 { 303 public: 304 typedef CMap_extend_iterator<Map_,Ite,Bi,Tag_true> Self; 305 typedef Ite Base; 306 307 typedef typename Base::Dart_handle Dart_handle; 308 typedef typename Base::Map Map; 309 310 typedef Tag_true Use_mark; 311 312 typedef typename Map::size_type size_type; 313 314 /// Main constructor. CMap_extend_iterator(Map & amap,Dart_handle adart,size_type amark)315 CMap_extend_iterator(Map& amap, Dart_handle adart, size_type amark): 316 Base(amap, adart, amark) 317 { 318 if ( this->minitial_dart!=amap.null_handle && 319 !this->mmap->is_free(this->minitial_dart, Bi) && 320 this->mmap->beta(this->minitial_dart, Bi)!=this->minitial_dart ) 321 { 322 this->mto_treat.push(this->mmap->beta(this->minitial_dart, Bi)); 323 } 324 } 325 326 /// Rewind of the iterator to its beginning. rewind()327 void rewind() 328 { 329 CGAL_assertion(this->mmark_number != Map::INVALID_MARK); 330 Base::rewind(); 331 if ( !this->mmap->is_free(this->minitial_dart, Bi) && 332 this->mmap->beta(this->minitial_dart, Bi)!=this->minitial_dart ) 333 { 334 this->mto_treat.push(this->mmap->beta(this->minitial_dart, Bi)); 335 } 336 } 337 338 /// Prefix ++ operator. 339 Self& operator++() 340 { 341 Base::operator++(); 342 343 if ( this->cont() ) 344 { 345 CGAL_assertion( this->mmap->is_marked(*this, this->mmark_number) ); 346 347 if ( 348 !this->mmap->is_marked(this->mmap->beta(*this, Bi), this->mmark_number) ) 349 { 350 this->mto_treat.push(this->mmap->beta(*this, Bi)); 351 } 352 } 353 return *this; 354 } 355 356 /// Postfix ++ operator. 357 Self operator++(int) 358 { Self res=*this; operator ++(); return res; } 359 }; 360 //**************************************************************************** 361 //* Class CMap_non_basic_iterator allows to transform a basic_iterator onto 362 //* a non basic one, depending if the basic iterator uses mark or not. 363 template <typename Map_,typename Basic_iterator, 364 typename Use_mark=typename Basic_iterator::Use_mark> 365 class CMap_non_basic_iterator; 366 //**************************************************************************** 367 template <typename Map_,typename Base_> 368 class CMap_non_basic_iterator<Map_,Base_,Tag_true>: 369 public Base_ 370 { 371 public: 372 typedef CMap_non_basic_iterator<Map_,Base_,Tag_true> Self; 373 typedef Base_ Base; 374 375 typedef typename Base::Map Map; 376 typedef typename Base::Dart_handle Dart_handle; 377 378 /// True iff this iterator is basic 379 typedef Tag_false Basic_iterator; 380 381 typedef typename Map::size_type size_type; 382 383 CGAL_static_assertion( (boost::is_same<typename Base::Basic_iterator, 384 Tag_true>::value) ); 385 386 /// Main constructor. CMap_non_basic_iterator(Map & amap,Dart_handle adart1)387 CMap_non_basic_iterator(Map& amap, Dart_handle adart1): 388 Base(amap, adart1, amap.get_new_mark()) 389 {} 390 391 /// Destructor. 392 ~CMap_non_basic_iterator() noexcept(!CGAL_ASSERTIONS_ENABLED) 393 { 394 CGAL_destructor_assertion( this->mmark_number!=Map::INVALID_MARK ); 395 if (this->mmap->get_number_of_times_mark_reserved 396 (this->mmark_number)==1) 397 unmark_treated_darts(); 398 this->mmap->free_mark(this->mmark_number); 399 this->mmark_number = Map::INVALID_MARK; // To avoid basic class to try to unmark darts. 400 } 401 402 /// Copy constructor. CMap_non_basic_iterator(const Self & aiterator)403 CMap_non_basic_iterator(const Self& aiterator): 404 Base(aiterator) 405 { this->mmap->share_a_mark(this->mmark_number); } 406 407 /// Assignment operator. 408 Self& operator=(const Self& aiterator) 409 { 410 if (this != &aiterator) 411 { 412 if (this->mmap->get_number_of_times_mark_reserved 413 (this->mmark_number)==1) 414 unmark_treated_darts(); 415 this->mmap->free_mark(this->mmark_number); 416 this->mmark_number = Map::INVALID_MARK; 417 418 Base::operator=(aiterator); 419 this->mmap->share_a_mark(this->mmark_number); 420 } 421 return *this; 422 } 423 424 /// Rewind of the iterator to its beginning. rewind()425 void rewind() 426 { 427 unmark_treated_darts(); 428 Base::rewind(); 429 } 430 431 using Base::operator++; 432 433 /// Postfix ++ operator. 434 Self operator++(int) 435 { Self res=*this; operator ++(); return res; } 436 437 protected: 438 /// Unmark all the marked darts during the iterator. unmark_treated_darts()439 void unmark_treated_darts() 440 { 441 if (this->mmap->is_whole_map_unmarked(this->mmark_number)) return; 442 443 this->mmap->negate_mark(this->mmark_number); 444 445 if (this->mmap->is_whole_map_unmarked(this->mmark_number)) return; 446 447 Base::rewind(); 448 while (this->mmap->number_of_unmarked_darts(this->mmark_number) > 0) 449 this->operator++(); 450 this->mmap->negate_mark(this->mmark_number); 451 CGAL_assertion(this->mmap->is_whole_map_unmarked(this->mmark_number)); 452 } 453 }; 454 //**************************************************************************** 455 template <typename Map_,typename Base_> 456 class CMap_non_basic_iterator<Map_,Base_,Tag_false>: 457 public Base_ 458 { 459 public: 460 typedef CMap_non_basic_iterator<Map_,Base_,Tag_false> Self; 461 typedef Base_ Base; 462 463 typedef typename Base::Map Map; 464 typedef typename Base::Dart_handle Dart_handle; 465 466 /// True iff this iterator is basic 467 typedef Tag_false Basic_iterator; 468 469 CGAL_static_assertion( (boost::is_same<typename Base::Basic_iterator, 470 Tag_true>::value) ); 471 472 /// Main constructor. CMap_non_basic_iterator(Map & amap,Dart_handle adart)473 CMap_non_basic_iterator(Map& amap, Dart_handle adart): 474 Base(amap, adart) 475 {} 476 }; 477 //**************************************************************************** 478 template <typename Map_, typename It, typename Const_it, 479 typename Basic_iterator=typename It::Basic_iterator> 480 struct CMap_range 481 { 482 typedef It iterator; 483 typedef Const_it const_iterator; CMap_rangeCMap_range484 CMap_range(Map_ &amap, typename Map_::Dart_handle adart) : 485 mmap(amap), mdart(adart), msize(0) 486 {} beginCMap_range487 iterator begin() { return iterator(mmap,mdart); } endCMap_range488 iterator end() { return iterator(mmap,mmap.null_handle); } beginCMap_range489 const_iterator begin() const { return const_iterator(mmap,mdart); } endCMap_range490 const_iterator end() const { return const_iterator(mmap,mmap.null_handle); } sizeCMap_range491 typename Map_::size_type size() const 492 { 493 if (msize==0) 494 for ( const_iterator it=begin(), itend=end(); it!=itend; ++it) 495 ++msize; 496 return msize; 497 } emptyCMap_range498 bool empty() const 499 { return mmap.is_empty(); } 500 private: 501 Map_ & mmap; 502 typename Map_::Dart_handle mdart; 503 mutable typename Map_::size_type msize; 504 }; 505 //**************************************************************************** 506 template <typename Map_, typename It, typename Const_it> 507 struct CMap_range<Map_,It,Const_it,Tag_true> 508 { 509 typedef CMap_range<Map_,It,Const_it,Tag_true> Base_cmap_range; 510 typedef It iterator; 511 typedef Const_it const_iterator; 512 513 typedef typename Map_::size_type size_type; 514 515 CMap_range(Map_ &amap, typename Map_::Dart_handle adart, size_type amark=Map_::INVALID_MARK): 516 mmap(amap), mdart(adart), msize(0), mmark(amark) 517 {} 518 iterator begin() { return iterator(mmap,mdart,mmark); } 519 iterator end() { return iterator(mmap,mmap.null_handle,mmark); } 520 const_iterator begin() const { return const_iterator(mmap,mdart,mmark); } 521 const_iterator end() const { return const_iterator(mmap,mmap.null_handle,mmark); } 522 typename Map_::size_type size() const 523 { 524 if (msize==0) 525 for ( CMap_non_basic_iterator<Map_,const_iterator> it(mmap,mdart); 526 it.cont(); ++it ) 527 ++msize; 528 return msize; 529 } 530 bool empty() const 531 { return mmap.is_empty(); } 532 private: 533 Map_ & mmap; 534 typename Map_::Dart_handle mdart; 535 mutable typename Map_::size_type msize; 536 size_type mmark; 537 }; 538 //**************************************************************************** 539 template <typename Map_, typename Const_it, 540 typename Basic_iterator=typename Const_it::Basic_iterator> 541 struct CMap_const_range 542 { 543 typedef Const_it const_iterator; 544 CMap_const_range(const Map_ &amap, typename Map_::Dart_const_handle adart): 545 mmap(amap), mdart(adart), msize(0) 546 {} 547 const_iterator begin() const { return const_iterator(mmap,mdart); } 548 const_iterator end() const { return const_iterator(mmap,mmap.null_handle); } 549 typename Map_::size_type size() const 550 { 551 if (msize==0) 552 for ( const_iterator it=begin(), itend=end(); it!=itend; ++it) 553 ++msize; 554 return msize; 555 } 556 bool empty() const 557 { return mmap.is_empty(); } 558 private: 559 const Map_ & mmap; 560 typename Map_::Dart_const_handle mdart; 561 mutable typename Map_::size_type msize; 562 }; 563 //**************************************************************************** 564 template <typename Map_, typename Const_it> 565 struct CMap_const_range<Map_,Const_it,Tag_true> 566 { 567 typedef Const_it const_iterator; 568 typedef typename Map_::size_type size_type; 569 CMap_const_range(const Map_ &amap, typename Map_::Dart_const_handle adart, 570 size_type amark=Map_::INVALID_MARK): 571 mmap(amap), mdart(adart), msize(0), mmark(amark) 572 {} 573 const_iterator begin() const { return const_iterator(mmap,mdart,mmark); } 574 const_iterator end() const { return const_iterator(mmap,mmap.null_handle,mmark); } 575 typename Map_::size_type size() const 576 { 577 if (msize==0) 578 for ( CMap_non_basic_iterator<Map_,const_iterator> it(mmap,mdart); 579 it.cont(); ++it ) 580 ++msize; 581 return msize; 582 } 583 bool empty() const 584 { return mmap.is_empty(); } 585 private: 586 const Map_ & mmap; 587 typename Map_::Dart_const_handle mdart; 588 mutable typename Map_::size_type msize; 589 size_type mmark; 590 }; 591 //**************************************************************************** 592 } // namespace CGAL 593 594 #include <CGAL/enable_warnings.h> 595 596 //****************************************************************************** 597 #endif // CGAL_COMBINATORIAL_MAP_ITERATORS_BASE_HH 598 //****************************************************************************** 599