1 // Copyright (c) 2005,2007,2009,2010,2011 Tel-Aviv University (Israel). 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/Arrangement_on_surface_2/include/CGAL/Arr_counting_traits_2.h $ 7 // $Id: Arr_counting_traits_2.h 59a0da4 2021-05-19T17:23:53+02:00 Laurent Rineau 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // Author(s): Efi Fogel <efif@post.tau.ac.il> 11 // Eric Berberich <ericb@post.tau.ac.il> 12 13 #ifndef CGAL_ARR_COUNTING_TRAITS_H 14 #define CGAL_ARR_COUNTING_TRAITS_H 15 16 #include <CGAL/license/Arrangement_on_surface_2.h> 17 18 #include <CGAL/disable_warnings.h> 19 20 /*! \file 21 * A counting traits-class for the arrangement package. 22 * This is a meta-traits class. It is parameterized with another traits class 23 * and inherits from it. For each traits method it maintains a counter that 24 * counts the number of invokations into the method. 25 */ 26 27 #include <iostream> 28 #include <string.h> 29 #include <atomic> 30 31 #include <CGAL/basic.h> 32 #include <CGAL/Arr_enums.h> 33 #include <CGAL/Arr_tags.h> 34 35 namespace CGAL { 36 37 /*! \class 38 * A model of the ArrangementTraits_2 concept that counts the methods invoked. 39 */ 40 template <class Base_traits> 41 class Arr_counting_traits_2 : public Base_traits { 42 public: 43 enum Operation_id { 44 COMPARE_X_OP = 0, 45 COMPARE_XY_OP, 46 CONSTRUCT_MIN_VERTEX_OP, 47 CONSTRUCT_MAX_VERTEX_OP, 48 IS_VERTICAL_OP, 49 COMPARE_Y_AT_X_OP, 50 EQUAL_POINTS_OP, 51 EQUAL_CURVES_OP, 52 COMPARE_Y_AT_X_LEFT_OP, 53 COMPARE_Y_AT_X_RIGHT_OP, 54 MAKE_X_MONOTONE_OP, 55 SPLIT_OP, 56 INTERSECT_OP, 57 ARE_MERGEABLE_OP, 58 MERGE_OP, 59 CONSTRUCT_OPPOSITE_OP, 60 COMPARE_ENDPOINTS_XY_OP, 61 62 PARAMETER_SPACE_IN_X_CURVE_END_OP, 63 PARAMETER_SPACE_IN_X_POINT_OP, 64 PARAMETER_SPACE_IN_X_CURVE_OP, 65 IS_ON_X_IDENTIFICATION_POINT_OP, 66 IS_ON_X_IDENTIFICATION_CURVE_OP, 67 COMPARE_Y_ON_BOUNDARY_OP, 68 COMPARE_Y_NEAR_BOUNDARY_OP, 69 70 PARAMETER_SPACE_IN_Y_CURVE_END_OP, 71 PARAMETER_SPACE_IN_Y_POINT_OP, 72 PARAMETER_SPACE_IN_Y_CURVE_OP, 73 IS_ON_Y_IDENTIFICATION_POINT_OP, 74 IS_ON_Y_IDENTIFICATION_CURVE_OP, 75 COMPARE_X_AT_LIMIT_POINT_CURVE_END_OP, 76 COMPARE_X_AT_LIMIT_CURVE_ENDS_OP, 77 COMPARE_X_NEAR_LIMIT_OP, 78 COMPARE_X_ON_BOUNDARY_POINTS_OP, 79 COMPARE_X_ON_BOUNDARY_POINT_CURVE_END_OP, 80 COMPARE_X_ON_BOUNDARY_CURVE_ENDS_OP, 81 COMPARE_X_NEAR_BOUNDARY_OP, 82 83 NUMBER_OF_OPERATIONS 84 }; 85 86 typedef Base_traits Base; 87 typedef Arr_counting_traits_2<Base> Self; 88 89 /*! Construct default */ Arr_counting_traits_2()90 Arr_counting_traits_2() : Base() 91 { 92 clear_counters(); 93 increment(); 94 } 95 96 /*! Construct copy */ Arr_counting_traits_2(const Arr_counting_traits_2 & other)97 Arr_counting_traits_2(const Arr_counting_traits_2& other) : Base(other) 98 { 99 clear_counters(); 100 increment(); 101 } 102 103 /*! Obtain the counter of the given operation */ count(Operation_id id)104 size_t count(Operation_id id) const 105 { return m_counters[id]; } 106 count_compare_x()107 size_t count_compare_x() const 108 { return m_counters[COMPARE_X_OP]; } 109 count_compare_xy()110 size_t count_compare_xy() const 111 { return m_counters[COMPARE_XY_OP]; } 112 count_construct_min_vertex()113 size_t count_construct_min_vertex() const 114 { return m_counters[CONSTRUCT_MIN_VERTEX_OP]; } 115 count_construct_max_vertex()116 size_t count_construct_max_vertex() const 117 { return m_counters[CONSTRUCT_MAX_VERTEX_OP]; } 118 count_is_vertical()119 size_t count_is_vertical() const 120 { return m_counters[IS_VERTICAL_OP]; } 121 count_compare_y_at_x()122 size_t count_compare_y_at_x() const 123 { return m_counters[COMPARE_Y_AT_X_OP]; } 124 count_equal_points()125 size_t count_equal_points() const 126 { return m_counters[EQUAL_POINTS_OP]; } 127 count_equal_curves()128 size_t count_equal_curves() const 129 { return m_counters[EQUAL_CURVES_OP]; } 130 count_compare_y_at_x_left()131 size_t count_compare_y_at_x_left() const 132 { return m_counters[COMPARE_Y_AT_X_LEFT_OP]; } 133 count_compare_y_at_x_right()134 size_t count_compare_y_at_x_right() const 135 { return m_counters[COMPARE_Y_AT_X_RIGHT_OP]; } 136 count_make_x_monotone()137 size_t count_make_x_monotone() const 138 { return m_counters[MAKE_X_MONOTONE_OP]; } 139 count_split()140 size_t count_split() const 141 { return m_counters[SPLIT_OP]; } 142 count_intersect()143 size_t count_intersect() const 144 { return m_counters[INTERSECT_OP]; } 145 count_are_mergeable()146 size_t count_are_mergeable() const 147 { return m_counters[ARE_MERGEABLE_OP]; } 148 count_merge()149 size_t count_merge() const 150 { return m_counters[MERGE_OP]; } 151 count_construct_opposite()152 size_t count_construct_opposite() const 153 { return m_counters[CONSTRUCT_OPPOSITE_OP]; } 154 count_compare_endpoints_xy()155 size_t count_compare_endpoints_xy() const 156 { return m_counters[COMPARE_ENDPOINTS_XY_OP]; } 157 158 // left-right 159 count_parameter_space_in_x_curve_end()160 size_t count_parameter_space_in_x_curve_end() const 161 { return m_counters[PARAMETER_SPACE_IN_X_CURVE_END_OP]; } 162 count_parameter_space_in_x_curve()163 size_t count_parameter_space_in_x_curve() const 164 { return m_counters[PARAMETER_SPACE_IN_X_CURVE_OP]; } 165 count_parameter_space_in_x_point()166 size_t count_parameter_space_in_x_point() const 167 { return m_counters[PARAMETER_SPACE_IN_X_POINT_OP]; } 168 count_is_on_x_identification_point()169 size_t count_is_on_x_identification_point() const 170 { return m_counters[IS_ON_X_IDENTIFICATION_POINT_OP]; } 171 count_is_on_x_identification_curve()172 size_t count_is_on_x_identification_curve() const 173 { return m_counters[IS_ON_X_IDENTIFICATION_CURVE_OP]; } 174 count_compare_y_on_boundary()175 size_t count_compare_y_on_boundary() const 176 { return m_counters[COMPARE_Y_ON_BOUNDARY_OP]; } 177 count_compare_y_near_boundary()178 size_t count_compare_y_near_boundary() const 179 { return m_counters[COMPARE_Y_NEAR_BOUNDARY_OP]; } 180 181 182 // bottom-top 183 count_parameter_space_in_y_curve_end()184 size_t count_parameter_space_in_y_curve_end() const 185 { return m_counters[PARAMETER_SPACE_IN_Y_CURVE_END_OP]; } 186 count_parameter_space_in_y_curve()187 size_t count_parameter_space_in_y_curve() const 188 { return m_counters[PARAMETER_SPACE_IN_Y_CURVE_OP]; } 189 count_parameter_space_in_y_point()190 size_t count_parameter_space_in_y_point() const 191 { return m_counters[PARAMETER_SPACE_IN_Y_POINT_OP]; } 192 count_is_on_y_identification_point()193 size_t count_is_on_y_identification_point() const 194 { return m_counters[IS_ON_Y_IDENTIFICATION_POINT_OP]; } 195 count_is_on_y_identification_curve()196 size_t count_is_on_y_identification_curve() const 197 { return m_counters[IS_ON_Y_IDENTIFICATION_CURVE_OP]; } 198 count_compare_x_at_limit_point_curve_end()199 size_t count_compare_x_at_limit_point_curve_end() const 200 { return m_counters[COMPARE_X_AT_LIMIT_POINT_CURVE_END_OP]; } 201 count_compare_x_at_limit_curve_ends()202 size_t count_compare_x_at_limit_curve_ends() const 203 { return m_counters[COMPARE_X_AT_LIMIT_CURVE_ENDS_OP]; } 204 count_compare_x_near_limit()205 size_t count_compare_x_near_limit() const 206 { return m_counters[COMPARE_X_NEAR_LIMIT_OP]; } 207 count_compare_x_on_boundary_points()208 size_t count_compare_x_on_boundary_points() const 209 { return m_counters[COMPARE_X_ON_BOUNDARY_POINTS_OP]; } 210 count_compare_x_on_boundary_point_curve_end()211 size_t count_compare_x_on_boundary_point_curve_end() const 212 { return m_counters[COMPARE_X_ON_BOUNDARY_POINT_CURVE_END_OP]; } 213 count_compare_x_on_boundary_curve_ends()214 size_t count_compare_x_on_boundary_curve_ends() const 215 { return m_counters[COMPARE_X_ON_BOUNDARY_CURVE_ENDS_OP]; } 216 count_compare_x_near_boundary()217 size_t count_compare_x_near_boundary() const 218 { return m_counters[COMPARE_X_NEAR_BOUNDARY_OP]; } 219 220 /// \name Types and functors inherited from the base 221 //@{ 222 223 // Traits types: 224 typedef typename Base::Has_left_category Has_left_category; 225 typedef typename Base::Has_merge_category Has_merge_category; 226 typedef typename Base::Has_do_intersect_category Has_do_intersect_category; 227 228 typedef typename internal::Arr_complete_left_side_category< Base >::Category 229 Left_side_category; 230 typedef typename internal::Arr_complete_bottom_side_category< Base >::Category 231 Bottom_side_category; 232 typedef typename internal::Arr_complete_top_side_category< Base >::Category 233 Top_side_category; 234 typedef typename internal::Arr_complete_right_side_category< Base >::Category 235 Right_side_category; 236 237 typedef typename Base::Point_2 Point_2; 238 typedef typename Base::X_monotone_curve_2 X_monotone_curve_2; 239 typedef typename Base::Curve_2 Curve_2; 240 241 /*! A functor that compares the x-coordinates of two points */ 242 class Compare_x_2 { 243 private: 244 typename Base::Compare_x_2 m_object; 245 size_t& m_counter; 246 247 public: 248 /*! Construct */ Compare_x_2(const Base * base,size_t & counter)249 Compare_x_2(const Base* base, size_t& counter) : 250 m_object(base->compare_x_2_object()), m_counter(counter) {} 251 252 /*! Operate */ operator()253 Comparison_result operator()(const Point_2& p1, const Point_2& p2) const 254 { ++m_counter; return m_object(p1, p2); } 255 }; 256 257 /*! A functor that compares two points lexigoraphically: by x, then by y. */ 258 class Compare_xy_2 { 259 private: 260 typename Base::Compare_xy_2 m_object; 261 size_t& m_counter; 262 263 public: 264 /*! Construct */ Compare_xy_2(const Base * base,size_t & counter)265 Compare_xy_2(const Base* base, size_t& counter) : 266 m_object(base->compare_xy_2_object()), m_counter(counter) {} 267 268 /*! Operate */ operator()269 Comparison_result operator()(const Point_2& p1, const Point_2& p2) const 270 { ++m_counter; return m_object(p1, p2); } 271 }; 272 273 /*! A functor that obtains the left endpoint of an x-monotone curve. */ 274 class Construct_min_vertex_2 { 275 private: 276 typename Base::Construct_min_vertex_2 m_object; 277 size_t& m_counter; 278 279 public: 280 /*! Construct */ Construct_min_vertex_2(const Base * base,size_t & counter)281 Construct_min_vertex_2(const Base* base, size_t& counter) : 282 m_object(base->construct_min_vertex_2_object()), m_counter(counter) {} 283 284 /*! Operate */ operator()285 const Point_2 operator()(const X_monotone_curve_2& xc) const 286 { ++m_counter; return m_object(xc); } 287 }; 288 289 /*! A functor that obtains the right endpoint of an x-monotone curve. */ 290 class Construct_max_vertex_2 { 291 private: 292 typename Base::Construct_max_vertex_2 m_object; 293 size_t& m_counter; 294 295 public: 296 /*! Construct */ Construct_max_vertex_2(const Base * base,size_t & counter)297 Construct_max_vertex_2(const Base* base, size_t& counter) : 298 m_object(base->construct_max_vertex_2_object()), m_counter(counter) {} 299 300 /*! Operate */ operator()301 const Point_2 operator()(const X_monotone_curve_2& xc) const 302 { ++m_counter; return m_object(xc); } 303 }; 304 305 /*! A functor that checks whether a given x-monotone curve is vertical. */ 306 class Is_vertical_2 { 307 private: 308 typename Base::Is_vertical_2 m_object; 309 size_t& m_counter; 310 311 public: 312 /*! Construct */ Is_vertical_2(const Base * base,size_t & counter)313 Is_vertical_2(const Base* base, size_t& counter) : 314 m_object(base->is_vertical_2_object()), m_counter(counter) {} 315 316 /*! Operate */ operator()317 bool operator()(const X_monotone_curve_2& xc) const 318 { ++m_counter; return m_object(xc); } 319 }; 320 321 /*! A functor that compares the y-coordinates of a point and an 322 * x-monotone curve at the point x-coordinate. 323 */ 324 class Compare_y_at_x_2 { 325 private: 326 typename Base::Compare_y_at_x_2 m_object; 327 size_t& m_counter; 328 329 public: 330 /*! Construct */ Compare_y_at_x_2(const Base * base,size_t & counter)331 Compare_y_at_x_2(const Base* base, size_t& counter) : 332 m_object(base->compare_y_at_x_2_object()), m_counter(counter) {} 333 334 /*! Operate */ operator()335 Comparison_result operator()(const Point_2& p, 336 const X_monotone_curve_2& xc) const 337 { ++m_counter; return m_object(p, xc); } 338 }; 339 340 /*! A functor that checks whether two points and two x-monotone curves are 341 * identical. 342 */ 343 class Equal_2 { 344 private: 345 typename Base::Equal_2 m_object; 346 size_t& m_counter1; 347 size_t& m_counter2; 348 349 public: 350 /*! Construct */ Equal_2(const Base * base,size_t & counter1,size_t & counter2)351 Equal_2(const Base* base, size_t& counter1, size_t& counter2) : 352 m_object(base->equal_2_object()), 353 m_counter1(counter1), m_counter2(counter2) 354 {} 355 356 /*! Operate */ operator()357 bool operator()(const X_monotone_curve_2& xc1, 358 const X_monotone_curve_2& xc2) const 359 { ++m_counter1; return m_object(xc1, xc2); } 360 361 /*! Operate */ operator()362 bool operator()(const Point_2& p1, const Point_2& p2) const 363 { ++m_counter2; return m_object(p1, p2); } 364 }; 365 366 /*! A functor that compares compares the y-coordinates of two x-monotone 367 * curves immediately to the left of their intersection point. 368 */ 369 class Compare_y_at_x_left_2 { 370 private: 371 typename Base::Compare_y_at_x_left_2 m_object; 372 size_t& m_counter; 373 374 public: 375 /*! Construct */ Compare_y_at_x_left_2(const Base * base,size_t & counter)376 Compare_y_at_x_left_2(const Base* base, size_t& counter) : 377 m_object(base->compare_y_at_x_left_2_object()), m_counter(counter) {} 378 379 /*! Operate */ operator()380 Comparison_result operator()(const X_monotone_curve_2& xc1, 381 const X_monotone_curve_2& xc2, 382 const Point_2& p) const 383 { ++m_counter; return m_object(xc1, xc2, p); } 384 }; 385 386 /*! A functor that compares compares the y-coordinates of two x-monotone 387 * curves immediately to the right of their intersection point. 388 */ 389 class Compare_y_at_x_right_2 { 390 private: 391 typename Base::Compare_y_at_x_right_2 m_object; 392 size_t& m_counter; 393 394 public: 395 /*! Construct */ Compare_y_at_x_right_2(const Base * base,size_t & counter)396 Compare_y_at_x_right_2(const Base* base, size_t& counter) : 397 m_object(base->compare_y_at_x_right_2_object()), m_counter(counter) {} 398 399 /*! Operate */ operator()400 Comparison_result operator()(const X_monotone_curve_2& xc1, 401 const X_monotone_curve_2& xc2, 402 const Point_2& p) const 403 { ++m_counter; return m_object(xc1, xc2, p); } 404 }; 405 406 /*! \class Make_x_monotone_2 407 * A functor that subdivides a curve into x-monotone curves. 408 */ 409 class Make_x_monotone_2 { 410 private: 411 typename Base::Make_x_monotone_2 m_object; 412 size_t& m_counter; 413 414 public: 415 /*! Construct */ Make_x_monotone_2(const Base * base,size_t & counter)416 Make_x_monotone_2(const Base* base, size_t& counter) : 417 m_object(base->make_x_monotone_2_object()), m_counter(counter) {} 418 419 /*! Subdivide a given curve into x-monotone subcurves and insert them into 420 * a given output iterator. 421 * \param cv the curve. 422 * \param oi the output iterator for the result. Its value type is a variant 423 * that wraps Point_2 or an X_monotone_curve_2 objects. 424 * \return The past-the-end iterator. 425 */ 426 template <typename OutputIterator> operator()427 OutputIterator operator()(const Curve_2& cv, OutputIterator oi) const 428 { ++m_counter; return m_object(cv, oi); } 429 }; 430 431 /*! A functor that splits an arc at a point. */ 432 class Split_2 { 433 private: 434 typename Base::Split_2 m_object; 435 size_t& m_counter; 436 437 public: 438 /*! Construct */ Split_2(const Base * base,size_t & counter)439 Split_2(const Base* base, size_t& counter) : 440 m_object(base->split_2_object()), m_counter(counter) {} 441 442 /*! Operate */ operator()443 void operator()(const X_monotone_curve_2& xc, const Point_2& p, 444 X_monotone_curve_2& xc1, X_monotone_curve_2& xc2) const 445 { ++m_counter; m_object(xc, p, xc1, xc2); } 446 }; 447 448 /*! A functor that computes intersections between x-monotone curves. */ 449 class Intersect_2 { 450 private: 451 typename Base::Intersect_2 m_object; 452 size_t& m_counter; 453 454 public: 455 /*! Construct */ Intersect_2(const Base * base,size_t & counter)456 Intersect_2(const Base* base, size_t& counter) : 457 m_object(base->intersect_2_object()), m_counter(counter) {} 458 459 /*! Operate */ 460 template<class OutputIterator> operator()461 OutputIterator operator()(const X_monotone_curve_2& xc1, 462 const X_monotone_curve_2& xc2, 463 OutputIterator oi) const 464 { ++m_counter; return m_object(xc1, xc2, oi); } 465 }; 466 467 /*! A functor that tests whether two x-monotone curves can be merged. */ 468 class Are_mergeable_2 { 469 private: 470 typename Base::Are_mergeable_2 m_object; 471 size_t& m_counter; 472 473 public: 474 /*! Construct */ Are_mergeable_2(const Base * base,size_t & counter)475 Are_mergeable_2(const Base* base, size_t& counter) : 476 m_object(base->are_mergeable_2_object()), m_counter(counter) {} 477 478 /*! Operate */ operator()479 bool operator()(const X_monotone_curve_2& xc1, 480 const X_monotone_curve_2& xc2) const 481 { ++m_counter; return m_object(xc1, xc2); } 482 }; 483 484 /*! A functor that merges two x-monotone curves into one. */ 485 class Merge_2 { 486 private: 487 typename Base::Merge_2 m_object; 488 size_t& m_counter; 489 490 public: 491 /*! Construct */ Merge_2(const Base * base,size_t & counter)492 Merge_2(const Base* base, size_t& counter) : 493 m_object(base->merge_2_object()), m_counter(counter) {} 494 495 /*! Operate */ operator()496 void operator()(const X_monotone_curve_2& xc1, 497 const X_monotone_curve_2& xc2, 498 X_monotone_curve_2& xc) const 499 { ++m_counter; m_object(xc1, xc2, xc); } 500 }; 501 502 /*! A fnuctor that constructs an opposite x-monotone curve. */ 503 class Construct_opposite_2 { 504 private: 505 typename Base::Construct_opposite_2 m_object; 506 size_t& m_counter; 507 508 public: 509 /*! Construct */ Construct_opposite_2(const Base * base,size_t & counter)510 Construct_opposite_2(const Base* base, size_t& counter) : 511 m_object(base->construct_opposite_2_object()), m_counter(counter) {} 512 513 /*! Operate */ operator()514 X_monotone_curve_2 operator()(const X_monotone_curve_2& xc) 515 { ++m_counter; return m_object(xc); } 516 }; 517 518 /*! A functor that compares the two endpoints of an x-monotone curve 519 * lexigoraphically. 520 */ 521 class Compare_endpoints_xy_2 { 522 private: 523 typename Base::Compare_endpoints_xy_2 m_object; 524 size_t& m_counter; 525 526 public: 527 /*! Construct */ Compare_endpoints_xy_2(const Base * base,size_t & counter)528 Compare_endpoints_xy_2(const Base* base, size_t& counter) : 529 m_object(base->compare_endpoints_xy_2_object()), m_counter(counter) {} 530 531 /*! Operate */ operator()532 Comparison_result operator()(const X_monotone_curve_2& xc) 533 { ++m_counter; return m_object(xc); } 534 }; 535 536 // left-right 537 538 /*! A functor that determines whether an endpoint of an x-monotone curve lies 539 * on a boundary of the parameter space along the x axis. 540 */ 541 class Parameter_space_in_x_2 { 542 private: 543 typename Base::Parameter_space_in_x_2 m_object; 544 size_t& m_counter1; 545 size_t& m_counter2; 546 size_t& m_counter3; 547 548 public: 549 /*! Construct */ Parameter_space_in_x_2(const Base * base,size_t & counter1,size_t & counter2,size_t & counter3)550 Parameter_space_in_x_2(const Base* base, size_t& counter1, 551 size_t& counter2, size_t& counter3) : 552 m_object(base->parameter_space_in_x_2_object()), 553 m_counter1(counter1), 554 m_counter2(counter2), 555 m_counter3(counter3) {} 556 557 /*! Operate */ operator()558 Arr_parameter_space operator()(const X_monotone_curve_2& xc, 559 Arr_curve_end ce) const 560 { ++m_counter1; return m_object(xc, ce); } 561 562 563 /*! Operate */ operator()564 Arr_parameter_space operator()(const Point_2& p) const 565 { ++m_counter2; return m_object(p); } 566 567 568 /*! Operate */ operator()569 Arr_parameter_space operator()(const X_monotone_curve_2& xc) const 570 { ++m_counter3; return m_object(xc); } 571 572 }; 573 574 /*! A functor that determines whether a point or a curve lies on an 575 * identification in x. 576 */ 577 class Is_on_x_identification_2 { 578 private: 579 typename Base::Is_on_x_identificiation_2 m_object; 580 size_t& m_counter1; 581 size_t& m_counter2; 582 583 public: 584 /*! Construct */ Is_on_x_identification_2(const Base * base,size_t & counter1,size_t & counter2)585 Is_on_x_identification_2(const Base* base, 586 size_t& counter1, size_t& counter2) : 587 m_object(base->is_on_x_identificiation_2_object()), 588 m_counter1(counter1), 589 m_counter2(counter2) {} 590 591 /*! Operate */ operator()592 Arr_parameter_space operator()(const Point_2& p) const 593 { ++m_counter1; return m_object(p); } 594 595 596 /*! Operate */ operator()597 Arr_parameter_space operator()(const X_monotone_curve_2& xc) const 598 { ++m_counter2; return m_object(xc); } 599 600 }; 601 602 /*! A functor that compares the y-coordinate of two given points 603 * that lie on vertical boundaries. 604 */ 605 class Compare_y_on_boundary_2 { 606 private: 607 typename Base::Compare_y_on_boundary_2 m_object; 608 size_t& m_counter; 609 610 public: 611 /*! Construct */ Compare_y_on_boundary_2(const Base * base,size_t & counter)612 Compare_y_on_boundary_2(const Base* base, size_t& counter) : 613 m_object(base->compare_y_on_boundary_2_object()), 614 m_counter(counter) 615 {} 616 617 /*! Operate */ operator()618 Comparison_result operator()(const Point_2& p1, const Point_2& p2) const 619 { ++m_counter; return m_object(p1, p2); } 620 }; 621 622 /*! A functor that compares the y-coordinates of curve ends near the 623 * boundary of the parameter space. 624 */ 625 class Compare_y_near_boundary_2 { 626 private: 627 typename Base::Compare_y_near_boundary_2 m_object; 628 size_t& m_counter; 629 630 public: 631 /*! Construct */ Compare_y_near_boundary_2(const Base * base,size_t & counter)632 Compare_y_near_boundary_2(const Base* base, size_t& counter) : 633 m_object(base->compare_y_near_boundary_2_object()), m_counter(counter) {} 634 635 /*! Operate */ operator()636 Comparison_result operator()(const X_monotone_curve_2& xc1, 637 const X_monotone_curve_2& xc2, 638 Arr_curve_end ce) const 639 { ++m_counter; return m_object(xc1, xc2, ce); } 640 }; 641 642 // bottom-top 643 644 /*! A functor that determines whether an endpoint of an x-monotone arc lies 645 * on a boundary of the parameter space along the y axis. 646 */ 647 class Parameter_space_in_y_2 { 648 private: 649 typename Base::Parameter_space_in_y_2 m_object; 650 size_t& m_counter1; 651 size_t& m_counter2; 652 size_t& m_counter3; 653 654 public: 655 /*! Construct */ Parameter_space_in_y_2(const Base * base,size_t & counter1,size_t & counter2,size_t & counter3)656 Parameter_space_in_y_2(const Base* base, size_t& counter1, 657 size_t& counter2, size_t& counter3) : 658 m_object(base->parameter_space_in_y_2_object()), 659 m_counter1(counter1), 660 m_counter2(counter2), 661 m_counter3(counter3) {} 662 663 /*! Operate */ operator()664 Arr_parameter_space operator()(const X_monotone_curve_2& xc, 665 Arr_curve_end ce) const 666 { ++m_counter1; return m_object(xc, ce); } 667 668 /*! Operate */ operator()669 Arr_parameter_space operator()(const Point_2& p) const 670 { ++m_counter2; return m_object(p); } 671 672 /*! Operate */ operator()673 Arr_parameter_space operator()(const X_monotone_curve_2& xc) const 674 { ++m_counter3; return m_object(xc); } 675 676 }; 677 678 /*! A functor that determines whether a point or a curve lies on an 679 * identification in x. 680 */ 681 class Is_on_y_identification_2 { 682 private: 683 typename Base::Is_on_y_identificiation_2 m_object; 684 size_t& m_counter1; 685 size_t& m_counter2; 686 687 public: 688 /*! Construct */ Is_on_y_identification_2(const Base * base,size_t & counter1,size_t & counter2)689 Is_on_y_identification_2(const Base* base, 690 size_t& counter1, size_t& counter2) : 691 m_object(base->is_on_y_identificiation_2_object()), 692 m_counter1(counter1), 693 m_counter2(counter2) {} 694 695 /*! Operate */ operator()696 Arr_parameter_space operator()(const Point_2& p) const 697 { ++m_counter1; return m_object(p); } 698 699 700 /*! Operate */ operator()701 Arr_parameter_space operator()(const X_monotone_curve_2& xc) const 702 { ++m_counter2; return m_object(xc); } 703 704 }; 705 706 /*! A functor that compares the x-limits of curve ends on the 707 * boundary of the parameter space. 708 */ 709 class Compare_x_at_limit_2 { 710 private: 711 typename Base::Compare_x_at_limit_2 m_object; 712 size_t& m_counter1; 713 size_t& m_counter2; 714 715 public: 716 /*! Construct */ Compare_x_at_limit_2(const Base * base,size_t & counter1,size_t & counter2)717 Compare_x_at_limit_2(const Base* base, 718 size_t& counter1, size_t& counter2) : 719 m_object(base->compare_x_at_limit_2_object()), 720 m_counter1(counter1), 721 m_counter2(counter2) {} 722 723 /*! Operate */ operator()724 Comparison_result operator()(const Point_2& p, 725 const X_monotone_curve_2& xc, 726 Arr_curve_end ce) const 727 { ++m_counter1; return m_object(p, xc, ce); } 728 729 /*! Operate */ operator()730 Comparison_result operator()(const X_monotone_curve_2& xc1, 731 Arr_curve_end ce1, 732 const X_monotone_curve_2& xc2, 733 Arr_curve_end ce2) const 734 { ++m_counter2; return m_object(xc1, ce1, xc2, ce2); } 735 }; 736 737 738 /*! A functor that compares the x-coordinates of curve ends near the 739 * boundary of the parameter space. 740 */ 741 class Compare_x_near_limit_2 { 742 private: 743 typename Base::Compare_x_near_limit_2 m_object; 744 size_t& m_counter; 745 746 public: 747 /*! Construct */ Compare_x_near_limit_2(const Base * base,size_t & counter)748 Compare_x_near_limit_2(const Base* base, size_t& counter) : 749 m_object(base->compare_x_near_limit_2_object()), 750 m_counter(counter) {} 751 752 753 /*! Operate */ operator()754 Comparison_result operator()(const X_monotone_curve_2& xc1, 755 const X_monotone_curve_2& xc2, 756 Arr_curve_end ce) const 757 { ++m_counter; return m_object(xc1, xc2, ce); } 758 }; 759 760 /*! A functor that compares the x-coordinate of two given points 761 * that lie on horizontal boundaries. 762 */ 763 class Compare_x_on_boundary_2 { 764 private: 765 typename Base::Compare_x_on_boundary_2 m_object; 766 size_t& m_counter1; 767 size_t& m_counter2; 768 size_t& m_counter3; 769 770 public: 771 /*! Construct */ Compare_x_on_boundary_2(const Base * base,size_t & counter1,size_t & counter2,size_t & counter3)772 Compare_x_on_boundary_2(const Base* base, size_t& counter1, 773 size_t& counter2, size_t& counter3 ) : 774 m_object(base->compare_x_on_boundary_2_object()), 775 m_counter1(counter1), 776 m_counter2(counter2), 777 m_counter3(counter3) 778 {} 779 780 /*! Operate */ operator()781 Comparison_result operator()(const Point_2& p1, const Point_2& p2) const 782 { ++m_counter1; return m_object(p1, p2); } 783 784 /*! Operate */ operator()785 Comparison_result operator()(const Point_2& pt, 786 const X_monotone_curve_2& xcv, 787 Arr_curve_end ce) const 788 { ++m_counter2; return m_object(pt, xcv, ce); } 789 790 /*! Operate */ operator()791 Comparison_result operator()(const X_monotone_curve_2& xcv1, 792 Arr_curve_end ce1, 793 const X_monotone_curve_2& xcv2, 794 Arr_curve_end ce2) const 795 { ++m_counter3; return m_object(xcv1, ce1, xcv2, ce2); } 796 797 }; 798 799 /*! A functor that compares the x-coordinates of curve ends near the 800 * boundary of the parameter space. 801 */ 802 class Compare_x_near_boundary_2 { 803 private: 804 typename Base::Compare_x_near_boundary_2 m_object; 805 size_t& m_counter; 806 807 public: 808 /*! Construct */ Compare_x_near_boundary_2(const Base * base,size_t & counter)809 Compare_x_near_boundary_2(const Base* base, 810 size_t& counter) : 811 m_object(base->compare_x_near_boundary_2_object()), 812 m_counter(counter) {} 813 814 815 /*! Operate */ operator()816 Comparison_result operator()(const X_monotone_curve_2& xc1, 817 const X_monotone_curve_2& xc2, 818 Arr_curve_end ce) const 819 { ++m_counter; return m_object(xc1, xc2, ce); } 820 }; 821 822 //@} 823 824 825 826 /// \name Obtain the appropriate functor 827 //@{ 828 compare_x_2_object()829 Compare_x_2 compare_x_2_object() const 830 { return Compare_x_2(this, m_counters[COMPARE_X_OP]); } 831 compare_xy_2_object()832 Compare_xy_2 compare_xy_2_object() const 833 { return Compare_xy_2(this, m_counters[COMPARE_XY_OP]); } 834 construct_min_vertex_2_object()835 Construct_min_vertex_2 construct_min_vertex_2_object() const 836 { return Construct_min_vertex_2(this, m_counters[CONSTRUCT_MIN_VERTEX_OP]); } 837 construct_max_vertex_2_object()838 Construct_max_vertex_2 construct_max_vertex_2_object() const 839 { return Construct_max_vertex_2(this, m_counters[CONSTRUCT_MAX_VERTEX_OP]); } 840 is_vertical_2_object()841 Is_vertical_2 is_vertical_2_object() const 842 { return Is_vertical_2(this, m_counters[IS_VERTICAL_OP]); } 843 compare_y_at_x_2_object()844 Compare_y_at_x_2 compare_y_at_x_2_object() const 845 { return Compare_y_at_x_2(this, m_counters[COMPARE_Y_AT_X_OP]); } 846 equal_2_object()847 Equal_2 equal_2_object() const 848 { 849 return Equal_2(this, m_counters[EQUAL_POINTS_OP], 850 m_counters[EQUAL_CURVES_OP]); 851 } 852 compare_y_at_x_left_2_object()853 Compare_y_at_x_left_2 compare_y_at_x_left_2_object() const 854 { return Compare_y_at_x_left_2(this, m_counters[COMPARE_Y_AT_X_LEFT_OP]); } 855 compare_y_at_x_right_2_object()856 Compare_y_at_x_right_2 compare_y_at_x_right_2_object() const 857 { return Compare_y_at_x_right_2(this, m_counters[COMPARE_Y_AT_X_RIGHT_OP]); } 858 make_x_monotone_2_object()859 Make_x_monotone_2 make_x_monotone_2_object() const 860 { return Make_x_monotone_2(this, m_counters[MAKE_X_MONOTONE_OP]); } 861 split_2_object()862 Split_2 split_2_object() const 863 { return Split_2(this, m_counters[SPLIT_OP]); } 864 intersect_2_object()865 Intersect_2 intersect_2_object() const 866 { return Intersect_2(this, m_counters[INTERSECT_OP]); } 867 are_mergeable_2_object()868 Are_mergeable_2 are_mergeable_2_object() const 869 { return Are_mergeable_2(this, m_counters[ARE_MERGEABLE_OP]); } 870 merge_2_object()871 Merge_2 merge_2_object() const 872 { return Merge_2(this, m_counters[MERGE_OP]); } 873 construct_opposite_2_object()874 Construct_opposite_2 construct_opposite_2_object() const 875 { return Construct_opposite_2(this, m_counters[CONSTRUCT_OPPOSITE_OP]); } 876 compare_endpoints_xy_2_object()877 Compare_endpoints_xy_2 compare_endpoints_xy_2_object() const 878 { return Compare_endpoints_xy_2(this, m_counters[COMPARE_ENDPOINTS_XY_OP]); } 879 880 // left-right parameter_space_in_x_2_object()881 Parameter_space_in_x_2 parameter_space_in_x_2_object() const 882 { return Parameter_space_in_x_2( 883 this, 884 m_counters[PARAMETER_SPACE_IN_X_CURVE_END_OP], 885 m_counters[PARAMETER_SPACE_IN_X_POINT_OP], 886 m_counters[PARAMETER_SPACE_IN_X_CURVE_OP] 887 ); 888 } 889 is_on_x_identification_2_object()890 Is_on_x_identification_2 is_on_x_identification_2_object() const 891 { 892 return Is_on_x_identification_2(this, 893 m_counters[IS_ON_X_IDENTIFICATION_POINT_OP], 894 m_counters[IS_ON_X_IDENTIFICATION_CURVE_OP]); 895 } 896 compare_on_boundary_2_object()897 Compare_y_on_boundary_2 compare_on_boundary_2_object() const 898 { return Compare_y_on_boundary_2(this, m_counters[COMPARE_Y_ON_BOUNDARY_OP]); } 899 compare_near_boundary_2_object()900 Compare_y_near_boundary_2 compare_near_boundary_2_object() const 901 { 902 return Compare_y_near_boundary_2(this, 903 m_counters[COMPARE_Y_NEAR_BOUNDARY_OP]); 904 } 905 906 // bottom-top parameter_space_in_y_2_object()907 Parameter_space_in_y_2 parameter_space_in_y_2_object() const 908 { return Parameter_space_in_y_2( 909 this, 910 m_counters[PARAMETER_SPACE_IN_Y_CURVE_END_OP], 911 m_counters[PARAMETER_SPACE_IN_Y_POINT_OP], 912 m_counters[PARAMETER_SPACE_IN_Y_CURVE_OP] 913 ); 914 } 915 is_on_y_identification_2_object()916 Is_on_y_identification_2 is_on_y_identification_2_object() const 917 { return Is_on_y_identification_2( 918 this, 919 m_counters[IS_ON_Y_IDENTIFICATION_POINT_OP], 920 m_counters[IS_ON_Y_IDENTIFICATION_CURVE_OP] 921 ); 922 } 923 compare_x_at_limit_2_object()924 Compare_x_at_limit_2 compare_x_at_limit_2_object() const 925 { 926 return 927 Compare_x_at_limit_2(this, 928 m_counters[COMPARE_X_AT_LIMIT_POINT_CURVE_END_OP], 929 m_counters[COMPARE_X_AT_LIMIT_CURVE_ENDS_OP]); 930 } 931 compare_x_near_limit_2_object()932 Compare_x_near_limit_2 compare_x_near_limit_2_object() const 933 { return Compare_x_near_limit_2(this, m_counters[COMPARE_X_NEAR_LIMIT_OP]); } 934 compare_x_on_boundary_2_object()935 Compare_x_on_boundary_2 compare_x_on_boundary_2_object() const 936 { 937 return 938 Compare_x_on_boundary_2(this, 939 m_counters[COMPARE_X_ON_BOUNDARY_POINTS_OP], 940 m_counters[COMPARE_X_ON_BOUNDARY_POINT_CURVE_END_OP], 941 m_counters[COMPARE_X_ON_BOUNDARY_CURVE_ENDS_OP]); 942 } 943 compare_x_near_boundary_2_object()944 Compare_x_near_boundary_2 compare_x_near_boundary_2_object() const 945 { 946 return Compare_x_near_boundary_2(this, 947 m_counters[COMPARE_X_NEAR_BOUNDARY_OP]); 948 } 949 950 //@} 951 952 /*! Increment the construction counter 953 * \param doit indicates whethet to actually inceremnt the counter or not 954 * \return the counter at the end of the operation 955 */ 956 static size_t increment(bool doit = true) 957 { 958 #ifdef CGAL_NO_ATOMIC 959 static size_t counter; 960 #else 961 static std::atomic<size_t> counter; 962 #endif 963 if (doit) ++counter; 964 return counter; 965 } 966 967 /*! Clean all operation counters */ clear_counters()968 void clear_counters() 969 { memset(m_counters, 0, sizeof(m_counters)); } 970 971 private: 972 /*! The operation counters */ 973 mutable size_t m_counters[NUMBER_OF_OPERATIONS]; 974 }; 975 976 template <class Out_stream, class Base_traits> 977 inline 978 Out_stream& operator<<(Out_stream& os, 979 const Arr_counting_traits_2<Base_traits>& traits) 980 { 981 typedef Arr_counting_traits_2<Base_traits> Traits; 982 size_t sum = 0; 983 size_t i; 984 for (i = 0; i < Traits::NUMBER_OF_OPERATIONS; ++i) 985 sum += traits.count(static_cast<typename Traits::Operation_id>(i)); 986 os << "# of COMPARE_X operation = " 987 << traits.count_compare_x() << std::endl 988 << "# of COMPARE_XY operation = " 989 << traits.count_compare_xy() << std::endl 990 << "# of CONSTRUCT_MIN_VERTEX operation = " 991 << traits.count_construct_min_vertex() << std::endl 992 << "# of CONSTRUCT_MAX_VERTEX operation = " 993 << traits.count_construct_max_vertex() << std::endl 994 << "# of IS_VERTICAL operation = " 995 << traits.count_is_vertical() << std::endl 996 << "# of COMPARE_Y_AT_X operation = " 997 << traits.count_compare_y_at_x() << std::endl 998 << "# of EQUAL_POINTS operation = " 999 << traits.count_equal_points() << std::endl 1000 << "# of EQUAL_CURVES operation = " 1001 << traits.count_equal_curves() << std::endl 1002 << "# of COMPARE_Y_AT_X_LEFT operation = " 1003 << traits.count_compare_y_at_x_left() << std::endl 1004 << "# of COMPARE_Y_AT_X_RIGHT operation = " 1005 << traits.count_compare_y_at_x_right() << std::endl 1006 << "# of MAKE_X_MONOTONE operation = " 1007 << traits.count_make_x_monotone() << std::endl 1008 << "# of SPLIT operation = " 1009 << traits.count_split() << std::endl 1010 << "# of INTERSECT operation = " 1011 << traits.count_intersect() << std::endl 1012 << "# of ARE_MERGEABLE operation = " 1013 << traits.count_are_mergeable() << std::endl 1014 << "# of MERGE operation = " 1015 << traits.count_merge() << std::endl 1016 << "# of CONSTRUCT_OPPOSITE operation = " 1017 << traits.count_construct_opposite() << std::endl 1018 << "# of COMPARE_ENDPOINTS_XY operation = " 1019 << traits.count_compare_endpoints_xy() << std::endl 1020 // left-right 1021 << "# of PARAMETER_SPACE_IN_X curve-end operation = " 1022 << traits.count_parameter_space_in_x_curve_end() << std::endl 1023 << "# of PARAMETER_SPACE_IN_X point operation = " 1024 << traits.count_parameter_space_in_x_point() << std::endl 1025 << "# of PARAMETER_SPACE_IN_X curve operation = " 1026 << traits.count_parameter_space_in_x_curve() << std::endl 1027 << "# of IS_ON_X_IDENTIFICIATION point operation = " 1028 << traits.count_is_on_x_identification_point() << std::endl 1029 << "# of IS_ON_X_IDENTIFICATION curve operation = " 1030 << traits.count_is_on_x_identification_curve() << std::endl 1031 << "# of COMPARE_Y_ON_BOUNDARY operation = " 1032 << traits.count_compare_y_on_boundary() << std::endl 1033 << "# of COMPARE_Y_NEAR_BOUNDARY operation = " 1034 << traits.count_compare_y_near_boundary() << std::endl 1035 // bottom-top 1036 << "# of PARAMETER_SPACE_IN_Y curve-end operation = " 1037 << traits.count_parameter_space_in_y_curve_end() << std::endl 1038 << "# of PARAMETER_SPACE_IN_Y point operation = " 1039 << traits.count_parameter_space_in_y_point() << std::endl 1040 << "# of PARAMETER_SPACE_IN_Y curve operation = " 1041 << traits.count_parameter_space_in_y_curve() << std::endl 1042 << "# of IS_ON_Y_IDENTIFICIATION point operation = " 1043 << traits.count_is_on_y_identification_point() << std::endl 1044 << "# of IS_ON_Y_IDENTIFICATION curve operation = " 1045 << traits.count_is_on_y_identification_curve() << std::endl 1046 << "# of COMPARE_X_AT_LIMIT point/curve-end operation = " 1047 << traits.count_compare_x_at_limit_point_curve_end() << std::endl 1048 << "# of COMPARE_X_AT_LIMIT curve-ends operation = " 1049 << traits.count_compare_x_at_limit_curve_ends() << std::endl 1050 << "# of COMPARE_X_NEAR_LIMIT operation = " 1051 << traits.count_compare_x_near_limit() << std::endl 1052 << "# of COMPARE_X_ON_BOUNDARY points operation = " 1053 << traits.count_compare_x_on_boundary_points() << std::endl 1054 << "# of COMPARE_X_ON_BOUNDARY point/curve-end operation = " 1055 << traits.count_compare_x_on_boundary_point_curve_end() << std::endl 1056 << "# of COMPARE_X_ON_BOUNDARY curve-ends operation = " 1057 << traits.count_compare_x_on_boundary_curve_ends() << std::endl 1058 << "# of COMPARE_X_NEAR_BOUNDARY operation = " 1059 << traits.count_compare_x_near_boundary() << std::endl 1060 1061 << "total # = " << sum << std::endl 1062 << "# of traits constructed = " << Traits::increment(false) 1063 << std::endl; 1064 return os; 1065 } 1066 1067 } //namespace CGAL 1068 1069 #include <CGAL/enable_warnings.h> 1070 1071 #endif 1072