ceph/src/boost/boost/geometry/algorithms/for_each.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
   6 // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
   7
   8 // This file was modified by Oracle on 2014-2020.
   9 // Modifications copyright (c) 2014-2020, Oracle and/or its affiliates.
  10
  11 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  12 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  13
  14 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  15 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  16
  17 // Use, modification and distribution is subject to the Boost Software License,
  18 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  19 // http://www.boost.org/LICENSE_1_0.txt)
  20
  21 #ifndef BOOST_GEOMETRY_ALGORITHMS_FOR_EACH_HPP
  22 #define BOOST_GEOMETRY_ALGORITHMS_FOR_EACH_HPP
  23
  24
  25 #include <algorithm>
  26
  27 #include <boost/range/begin.hpp>
  28 #include <boost/range/end.hpp>
  29 #include <boost/range/reference.hpp>
  30 #include <boost/range/value_type.hpp>
  31
  32 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
  33 #include <boost/geometry/algorithms/not_implemented.hpp>
  34 #include <boost/geometry/core/closure.hpp>
  35 #include <boost/geometry/core/exterior_ring.hpp>
  36 #include <boost/geometry/core/interior_rings.hpp>
  37 #include <boost/geometry/core/point_type.hpp>
  38 #include <boost/geometry/core/tag_cast.hpp>
  39 #include <boost/geometry/core/tags.hpp>
  40
  41 #include <boost/geometry/geometries/concepts/check.hpp>
  42
  43 #include <boost/geometry/geometries/segment.hpp>
  44
  45 #include <boost/geometry/util/range.hpp>
  46 #include <boost/geometry/util/type_traits.hpp>
  47
  48 #include <boost/geometry/views/detail/indexed_point_view.hpp>
  49
  50
  51 namespace boost { namespace geometry
  52 {
  53
  54 #ifndef DOXYGEN_NO_DETAIL
  55 namespace detail { namespace for_each
  56 {
  57
  58
  59 struct fe_point_point
  60 {
  61     template <typename Point, typename Functor>
  62     static inline bool apply(Point& point, Functor&& f)
  63     {
  64         return f(point);
  65     }
  66 };
  67
  68
  69 struct fe_segment_point
  70 {
  71     template <typename Point, typename Functor>
  72     static inline bool apply(Point& , Functor&& )
  73     {
  74         // TODO: if non-const, we should extract the points from the segment
  75         // and call the functor on those two points
  76
  77         //model::referring_segment<Point> s(point, point);
  78         //return f(s);
  79
  80         return true;
  81     }
  82 };
  83
  84
  85 struct fe_point_segment
  86 {
  87     template <typename Segment, typename Functor>
  88     static inline bool apply(Segment& s, Functor&& f)
  89     {
  90         // Or should we guarantee that the type of points is
  91         // point_type<Segment>::type ?
  92         geometry::detail::indexed_point_view<Segment, 0> p0(s);
  93         geometry::detail::indexed_point_view<Segment, 1> p1(s);
  94         return f(p0) && f(p1);
  95     }
  96 };
  97
  98 struct fe_segment_segment
  99 {
 100     template <typename Segment, typename Functor>
 101     static inline bool apply(Segment& s, Functor&& f)
 102     {
 103         // Or should we guarantee that the type of segment is
 104         // referring_segment<...> ?
 105         return f(s);
 106     }
 107 };
 108
 109
 110 template <typename Range>
 111 struct fe_range_value
 112 {
 113     typedef util::transcribe_const_t
 114         <
 115             Range,
 116             typename boost::range_value<Range>::type
 117         > type;
 118 };
 119
 120 template <typename Range>
 121 struct fe_point_type
 122 {
 123     typedef util::transcribe_const_t
 124         <
 125             Range,
 126             typename point_type<Range>::type
 127         > type;
 128 };
 129
 130
 131 template <typename Range>
 132 struct fe_point_type_is_referencable
 133 {
 134     static const bool value =
 135         std::is_const<Range>::value
 136      || std::is_same
 137             <
 138                 typename boost::range_reference<Range>::type,
 139                 typename fe_point_type<Range>::type&
 140             >::value;
 141 };
 142
 143
 144 template
 145 <
 146     typename Range,
 147     bool UseReferences = fe_point_type_is_referencable<Range>::value
 148 >
 149 struct fe_point_call_f
 150 {
 151     template <typename Iterator, typename Functor>
 152     static inline bool apply(Iterator it, Functor&& f)
 153     {
 154         // Implementation for real references (both const and mutable)
 155         // and const proxy references.
 156         typedef typename fe_point_type<Range>::type point_type;
 157         point_type& p = *it;
 158         return f(p);
 159     }
 160 };
 161
 162 template <typename Range>
 163 struct fe_point_call_f<Range, false>
 164 {
 165     template <typename Iterator, typename Functor>
 166     static inline bool apply(Iterator it, Functor&& f)
 167     {
 168         // Implementation for proxy mutable references.
 169         // Temporary point has to be created and assigned afterwards.
 170         typedef typename fe_point_type<Range>::type point_type;
 171         point_type p = *it;
 172         bool result = f(p);
 173         *it = p;
 174         return result;
 175     }
 176 };
 177
 178
 179 struct fe_point_range
 180 {
 181     template <typename Range, typename Functor>
 182     static inline bool apply(Range& range, Functor&& f)
 183     {
 184         auto const end = boost::end(range);
 185         for (auto it = boost::begin(range); it != end; ++it)
 186         {
 187             if (! fe_point_call_f<Range>::apply(it, f))
 188             {
 189                 return false;
 190             }
 191         }
 192
 193         return true;
 194     }
 195 };
 196
 197
 198 template
 199 <
 200     typename Range,
 201     bool UseReferences = fe_point_type_is_referencable<Range>::value
 202 >
 203 struct fe_segment_call_f
 204 {
 205     template <typename Iterator, typename Functor>
 206     static inline bool apply(Iterator it0, Iterator it1, Functor&& f)
 207     {
 208         // Implementation for real references (both const and mutable)
 209         // and const proxy references.
 210         // If const proxy references are returned by iterators
 211         // then const real references here prevents temporary
 212         // objects from being destroyed.
 213         typedef typename fe_point_type<Range>::type point_type;
 214         point_type& p0 = *it0;
 215         point_type& p1 = *it1;
 216         model::referring_segment<point_type> s(p0, p1);
 217         return f(s);
 218     }
 219 };
 220
 221 template <typename Range>
 222 struct fe_segment_call_f<Range, false>
 223 {
 224     template <typename Iterator, typename Functor>
 225     static inline bool apply(Iterator it0, Iterator it1, Functor&& f)
 226     {
 227         // Mutable proxy references returned by iterators.
 228         // Temporary points have to be created and assigned afterwards.
 229         typedef typename fe_point_type<Range>::type point_type;
 230         point_type p0 = *it0;
 231         point_type p1 = *it1;
 232         model::referring_segment<point_type> s(p0, p1);
 233         bool result = f(s);
 234         *it0 = p0;
 235         *it1 = p1;
 236         return result;
 237     }
 238 };
 239
 240
 241 template <closure_selector Closure>
 242 struct fe_segment_range_with_closure
 243 {
 244     template <typename Range, typename Functor>
 245     static inline bool apply(Range& range, Functor&& f)
 246     {
 247         auto it = boost::begin(range);
 248         auto const end = boost::end(range);
 249         if (it == end)
 250         {
 251             return true;
 252         }
 253
 254         auto previous = it++;
 255         if (it == end)
 256         {
 257             return fe_segment_call_f<Range>::apply(previous, previous, f);
 258         }
 259
 260         while (it != end)
 261         {
 262             if (! fe_segment_call_f<Range>::apply(previous, it, f))
 263             {
 264                 return false;
 265             }
 266             previous = it++;
 267         }
 268
 269         return true;
 270     }
 271 };
 272
 273
 274 template <>
 275 struct fe_segment_range_with_closure<open>
 276 {
 277     template <typename Range, typename Functor>
 278     static inline bool apply(Range& range, Functor&& f)
 279     {
 280         fe_segment_range_with_closure<closed>::apply(range, f);
 281
 282         auto const begin = boost::begin(range);
 283         auto end = boost::end(range);
 284         if (begin == end)
 285         {
 286             return true;
 287         }
 288
 289         --end;
 290
 291         if (begin == end)
 292         {
 293             // single point ranges already handled in closed case above
 294             return true;
 295         }
 296
 297         return fe_segment_call_f<Range>::apply(end, begin, f);
 298     }
 299 };
 300
 301
 302 struct fe_segment_range
 303 {
 304     template <typename Range, typename Functor>
 305     static inline bool apply(Range& range, Functor&& f)
 306     {
 307         return fe_segment_range_with_closure
 308             <
 309                 closure<Range>::value
 310             >::apply(range, f);
 311     }
 312 };
 313
 314
 315 template <typename RangePolicy>
 316 struct for_each_polygon
 317 {
 318     template <typename Polygon, typename Functor>
 319     static inline bool apply(Polygon& poly, Functor&& f)
 320     {
 321         if (! RangePolicy::apply(exterior_ring(poly), f))
 322         {
 323             return false;
 324         }
 325
 326         typename interior_return_type<Polygon>::type
 327             rings = interior_rings(poly);
 328
 329         auto const end = boost::end(rings);
 330         for (auto it = boost::begin(rings); it != end; ++it)
 331         {
 332             // NOTE: Currently lvalue iterator required
 333             if (! RangePolicy::apply(*it, f))
 334             {
 335                 return false;
 336             }
 337         }
 338
 339         return true;
 340     }
 341
 342 };
 343
 344 // Implementation of multi, for both point and segment,
 345 // just calling the single version.
 346 template <typename SinglePolicy>
 347 struct for_each_multi
 348 {
 349     template <typename MultiGeometry, typename Functor>
 350     static inline bool apply(MultiGeometry& multi, Functor&& f)
 351     {
 352         auto const end = boost::end(multi);
 353         for (auto it = boost::begin(multi); it != end; ++it)
 354         {
 355             // NOTE: Currently lvalue iterator required
 356             if (! SinglePolicy::apply(*it, f))
 357             {
 358                 return false;
 359             }
 360         }
 361
 362         return true;
 363     }
 364 };
 365
 366 }} // namespace detail::for_each
 367 #endif // DOXYGEN_NO_DETAIL
 368
 369
 370 #ifndef DOXYGEN_NO_DISPATCH
 371 namespace dispatch
 372 {
 373
 374 template
 375 <
 376     typename Geometry,
 377     typename Tag = typename tag_cast<typename tag<Geometry>::type, multi_tag>::type
 378 >
 379 struct for_each_point: not_implemented<Tag>
 380 {};
 381
 382
 383 template <typename Point>
 384 struct for_each_point<Point, point_tag>
 385     : detail::for_each::fe_point_point
 386 {};
 387
 388
 389 template <typename Segment>
 390 struct for_each_point<Segment, segment_tag>
 391     : detail::for_each::fe_point_segment
 392 {};
 393
 394
 395 template <typename Linestring>
 396 struct for_each_point<Linestring, linestring_tag>
 397     : detail::for_each::fe_point_range
 398 {};
 399
 400
 401 template <typename Ring>
 402 struct for_each_point<Ring, ring_tag>
 403     : detail::for_each::fe_point_range
 404 {};
 405
 406
 407 template <typename Polygon>
 408 struct for_each_point<Polygon, polygon_tag>
 409     : detail::for_each::for_each_polygon
 410         <
 411             detail::for_each::fe_point_range
 412         >
 413 {};
 414
 415
 416 template <typename MultiGeometry>
 417 struct for_each_point<MultiGeometry, multi_tag>
 418     : detail::for_each::for_each_multi
 419         <
 420             // Specify the dispatch of the single-version as policy
 421             for_each_point
 422                 <
 423                     typename detail::for_each::fe_range_value
 424                         <
 425                             MultiGeometry
 426                         >::type
 427                 >
 428         >
 429 {};
 430
 431
 432 template
 433 <
 434     typename Geometry,
 435     typename Tag = typename tag<Geometry>::type
 436 >
 437 struct for_each_segment: not_implemented<Tag>
 438 {};
 439
 440 template <typename Point>
 441 struct for_each_segment<Point, point_tag>
 442     : detail::for_each::fe_segment_point // empty
 443 {};
 444
 445
 446 template <typename Segment>
 447 struct for_each_segment<Segment, segment_tag>
 448     : detail::for_each::fe_segment_segment
 449 {};
 450
 451
 452 template <typename Linestring>
 453 struct for_each_segment<Linestring, linestring_tag>
 454     : detail::for_each::fe_segment_range
 455 {};
 456
 457
 458 template <typename Ring>
 459 struct for_each_segment<Ring, ring_tag>
 460     : detail::for_each::fe_segment_range
 461 {};
 462
 463
 464 template <typename Polygon>
 465 struct for_each_segment<Polygon, polygon_tag>
 466     : detail::for_each::for_each_polygon
 467         <
 468             detail::for_each::fe_segment_range
 469         >
 470 {};
 471
 472
 473 template <typename MultiPoint>
 474 struct for_each_segment<MultiPoint, multi_point_tag>
 475     : detail::for_each::fe_segment_point // empty
 476 {};
 477
 478
 479 template <typename MultiLinestring>
 480 struct for_each_segment<MultiLinestring, multi_linestring_tag>
 481     : detail::for_each::for_each_multi
 482         <
 483             detail::for_each::fe_segment_range
 484         >
 485 {};
 486
 487 template <typename MultiPolygon>
 488 struct for_each_segment<MultiPolygon, multi_polygon_tag>
 489     : detail::for_each::for_each_multi
 490         <
 491             detail::for_each::for_each_polygon
 492                 <
 493                     detail::for_each::fe_segment_range
 494                 >
 495         >
 496 {};
 497
 498
 499 } // namespace dispatch
 500 #endif // DOXYGEN_NO_DISPATCH
 501
 502
 503 template<typename Geometry, typename UnaryPredicate>
 504 inline bool all_points_of(Geometry& geometry, UnaryPredicate p)
 505 {
 506     concepts::check<Geometry>();
 507
 508     return dispatch::for_each_point<Geometry>::apply(geometry, p);
 509 }
 510
 511
 512 template<typename Geometry, typename UnaryPredicate>
 513 inline bool all_segments_of(Geometry const& geometry, UnaryPredicate p)
 514 {
 515     concepts::check<Geometry const>();
 516
 517     return dispatch::for_each_segment<Geometry const>::apply(geometry, p);
 518 }
 519
 520
 521 template<typename Geometry, typename UnaryPredicate>
 522 inline bool any_point_of(Geometry& geometry, UnaryPredicate p)
 523 {
 524     concepts::check<Geometry>();
 525
 526     return ! dispatch::for_each_point<Geometry>::apply(geometry, [&](auto&& pt)
 527     {
 528         return ! p(pt);
 529     });
 530 }
 531
 532
 533 template<typename Geometry, typename UnaryPredicate>
 534 inline bool any_segment_of(Geometry const& geometry, UnaryPredicate p)
 535 {
 536     concepts::check<Geometry const>();
 537
 538     return ! dispatch::for_each_segment<Geometry const>::apply(geometry, [&](auto&& s)
 539     {
 540         return ! p(s);
 541     });
 542 }
 543
 544 template<typename Geometry, typename UnaryPredicate>
 545 inline bool none_point_of(Geometry& geometry, UnaryPredicate p)
 546 {
 547     concepts::check<Geometry>();
 548
 549     return dispatch::for_each_point<Geometry>::apply(geometry, [&](auto&& pt)
 550     {
 551         return ! p(pt);
 552     });
 553 }
 554
 555
 556 template<typename Geometry, typename UnaryPredicate>
 557 inline bool none_segment_of(Geometry const& geometry, UnaryPredicate p)
 558 {
 559     concepts::check<Geometry const>();
 560
 561     return dispatch::for_each_segment<Geometry const>::apply(geometry, [&](auto&& s)
 562     {
 563         return ! p(s);
 564     });
 565 }
 566
 567
 568 /*!
 569 \brief \brf_for_each{point}
 570 \details \det_for_each{point}
 571 \ingroup for_each
 572 \param geometry \param_geometry
 573 \param f \par_for_each_f{point}
 574 \tparam Geometry \tparam_geometry
 575 \tparam Functor \tparam_functor
 576
 577 \qbk{[include reference/algorithms/for_each_point.qbk]}
 578 \qbk{[heading Example]}
 579 \qbk{[for_each_point] [for_each_point_output]}
 580 \qbk{[for_each_point_const] [for_each_point_const_output]}
 581 */
 582 template<typename Geometry, typename Functor>
 583 inline Functor for_each_point(Geometry& geometry, Functor f)
 584 {
 585     concepts::check<Geometry>();
 586
 587     dispatch::for_each_point<Geometry>::apply(geometry, [&](auto&& pt)
 588     {
 589         f(pt);
 590         // TODO: Implement separate function?
 591         return true;
 592     });
 593     return f;
 594 }
 595
 596
 597 /*!
 598 \brief \brf_for_each{segment}
 599 \details \det_for_each{segment}
 600 \ingroup for_each
 601 \param geometry \param_geometry
 602 \param f \par_for_each_f{segment}
 603 \tparam Geometry \tparam_geometry
 604 \tparam Functor \tparam_functor
 605
 606 \qbk{[include reference/algorithms/for_each_segment.qbk]}
 607 \qbk{[heading Example]}
 608 \qbk{[for_each_segment_const] [for_each_segment_const_output]}
 609 */
 610 template<typename Geometry, typename Functor>
 611 inline Functor for_each_segment(Geometry& geometry, Functor f)
 612 {
 613     concepts::check<Geometry>();
 614
 615     dispatch::for_each_segment<Geometry>::apply(geometry, [&](auto&& s)
 616     {
 617         f(s);
 618         // TODO: Implement separate function?
 619         return true;
 620     });
 621     return f;
 622 }
 623
 624
 625 }} // namespace boost::geometry
 626
 627
 628 #endif // BOOST_GEOMETRY_ALGORITHMS_FOR_EACH_HPP