ceph/src/boost/boost/geometry/algorithms/detail/visit.hpp

   1 // Boost.Geometry
   2
   3 // Copyright (c) 2021, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   6
   7 // Licensed under the Boost Software License version 1.0.
   8 // http://www.boost.org/users/license.html
   9
  10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_VISIT_HPP
  11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_VISIT_HPP
  12
  13 #include <deque>
  14 #include <iterator>
  15 #include <utility>
  16
  17 #include <boost/range/begin.hpp>
  18 #include <boost/range/end.hpp>
  19
  20 #include <boost/geometry/core/static_assert.hpp>
  21 #include <boost/geometry/core/tag.hpp>
  22 #include <boost/geometry/core/tags.hpp>
  23 #include <boost/geometry/core/visit.hpp>
  24 #include <boost/geometry/util/type_traits.hpp>
  25
  26 namespace boost { namespace geometry
  27 {
  28
  29 #ifndef DOXYGEN_NO_DISPATCH
  30 namespace dispatch
  31 {
  32
  33 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
  34 struct visit_one
  35 {
  36     template <typename F, typename G>
  37     static void apply(F && f, G && g)
  38     {
  39         f(std::forward<G>(g));
  40     }
  41 };
  42
  43 template <typename Geometry>
  44 struct visit_one<Geometry, void>
  45 {
  46     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
  47         "Not implemented for this Geometry type.",
  48         Geometry);
  49 };
  50
  51 template <typename Geometry>
  52 struct visit_one<Geometry, dynamic_geometry_tag>
  53 {
  54     template <typename F, typename Geom>
  55     static void apply(F && function, Geom && geom)
  56     {
  57         traits::visit
  58             <
  59                 util::remove_cref_t<Geom>
  60             >::apply(std::forward<F>(function), std::forward<Geom>(geom));
  61     }
  62 };
  63
  64
  65 template
  66 <
  67     typename Geometry1, typename Geometry2,
  68     typename Tag1 = typename tag<Geometry1>::type,
  69     typename Tag2 = typename tag<Geometry2>::type
  70 >
  71 struct visit_two
  72 {
  73     template <typename F, typename G1, typename G2>
  74     static void apply(F && f, G1 && geom1, G2 && geom2)
  75     {
  76         f(std::forward<G1>(geom1), std::forward<G2>(geom2));
  77     }
  78 };
  79
  80 template <typename Geometry1, typename Geometry2, typename Tag2>
  81 struct visit_two<Geometry1, Geometry2, void, Tag2>
  82 {
  83     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
  84         "Not implemented for this Geometry1 type.",
  85         Geometry1);
  86 };
  87
  88 template <typename Geometry1, typename Geometry2, typename Tag1>
  89 struct visit_two<Geometry1, Geometry2, Tag1, void>
  90 {
  91     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
  92         "Not implemented for this Geometry2 type.",
  93         Geometry2);
  94 };
  95
  96 template <typename Geometry1, typename Geometry2>
  97 struct visit_two<Geometry1, Geometry2, void, void>
  98 {
  99     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
 100         "Not implemented for these types.",
 101         Geometry1, Geometry2);
 102 };
 103
 104 template <typename Geometry1, typename Geometry2, typename Tag2>
 105 struct visit_two<Geometry1, Geometry2, dynamic_geometry_tag, Tag2>
 106 {
 107     template <typename F, typename G1, typename G2>
 108     static void apply(F && f, G1 && geom1, G2 && geom2)
 109     {
 110         traits::visit<util::remove_cref_t<G1>>::apply([&](auto && g1)
 111         {
 112             f(std::forward<decltype(g1)>(g1), std::forward<G2>(geom2));
 113         }, std::forward<G1>(geom1));
 114     }
 115 };
 116
 117 template <typename Geometry1, typename Geometry2, typename Tag1>
 118 struct visit_two<Geometry1, Geometry2, Tag1, dynamic_geometry_tag>
 119 {
 120     template <typename F, typename G1, typename G2>
 121     static void apply(F && f, G1 && geom1, G2 && geom2)
 122     {
 123         traits::visit<util::remove_cref_t<G2>>::apply([&](auto && g2)
 124         {
 125             f(std::forward<G1>(geom1), std::forward<decltype(g2)>(g2));
 126         }, std::forward<G2>(geom2));
 127     }
 128 };
 129
 130 template <typename Geometry1, typename Geometry2>
 131 struct visit_two<Geometry1, Geometry2, dynamic_geometry_tag, dynamic_geometry_tag>
 132 {
 133     template <typename F, typename G1, typename G2>
 134     static void apply(F && f, G1 && geom1, G2 && geom2)
 135     {
 136         traits::visit
 137             <
 138                 util::remove_cref_t<G1>, util::remove_cref_t<G2>
 139             >::apply([&](auto && g1, auto && g2)
 140             {
 141                 f(std::forward<decltype(g1)>(g1), std::forward<decltype(g2)>(g2));
 142             }, std::forward<G1>(geom1), std::forward<G2>(geom2));
 143     }
 144 };
 145
 146
 147 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
 148 struct visit_breadth_first
 149 {
 150     template <typename F, typename G>
 151     static bool apply(F f, G && g)
 152     {
 153         return f(std::forward<G>(g));
 154     }
 155 };
 156
 157 template <typename Geometry>
 158 struct visit_breadth_first<Geometry, void>
 159 {
 160     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
 161         "Not implemented for this Geometry type.",
 162         Geometry);
 163 };
 164
 165 template <typename Geometry>
 166 struct visit_breadth_first<Geometry, dynamic_geometry_tag>
 167 {
 168     template <typename Geom, typename F>
 169     static bool apply(F function, Geom && geom)
 170     {
 171         bool result = true;
 172         traits::visit<util::remove_cref_t<Geom>>::apply([&](auto && g)
 173         {
 174             result = visit_breadth_first
 175                 <
 176                     std::remove_reference_t<decltype(g)>
 177                 >::apply(function,
 178                          std::forward<decltype(g)>(g));
 179         }, std::forward<Geom>(geom));
 180         return result;
 181     }
 182 };
 183
 184 } // namespace dispatch
 185 #endif // DOXYGEN_NO_DISPATCH
 186
 187
 188 #ifndef DOXYGEN_NO_DETAIL
 189 namespace detail
 190 {
 191
 192 template <bool PassIterator = false>
 193 struct visit_breadth_first_impl
 194 {
 195     template <typename F, typename Geom>
 196     static bool apply(F function, Geom && geom)
 197     {
 198         using iter_t = std::conditional_t
 199             <
 200                 std::is_rvalue_reference<decltype(geom)>::value,
 201                 std::move_iterator<typename boost::range_iterator<Geom>::type>,
 202                 typename boost::range_iterator<Geom>::type
 203             >;
 204
 205         std::deque<iter_t> queue;
 206
 207         iter_t it = iter_t{ boost::begin(geom) };
 208         iter_t end = iter_t{ boost::end(geom) };
 209         for(;;)
 210         {
 211             for (; it != end; ++it)
 212             {
 213                 bool result = true;
 214                 traits::iter_visit<util::remove_cref_t<Geom>>::apply([&](auto && g)
 215                 {
 216                     result = visit_breadth_first_impl::visit_or_enqueue<PassIterator>(
 217                                     function, std::forward<decltype(g)>(g), queue, it);
 218                 }, it);
 219
 220                 if (! result)
 221                 {
 222                     return false;
 223                 }
 224             }
 225
 226             if (queue.empty())
 227             {
 228                 break;
 229             }
 230
 231             // Alternatively store a pointer to GeometryCollection
 232             // so this call can be avoided.
 233             traits::iter_visit<util::remove_cref_t<Geom>>::apply([&](auto && g)
 234             {
 235                 visit_breadth_first_impl::set_iterators(std::forward<decltype(g)>(g), it, end);
 236             }, queue.front());
 237             queue.pop_front();
 238         }
 239
 240         return true;
 241     }
 242
 243 private:
 244     template
 245     <
 246         bool PassIter, typename F, typename Geom, typename Iterator,
 247         std::enable_if_t<util::is_geometry_collection<Geom>::value, int> = 0
 248     >
 249     static bool visit_or_enqueue(F &, Geom &&, std::deque<Iterator> & queue, Iterator iter)
 250     {
 251         queue.push_back(iter);
 252         return true;
 253     }
 254     template
 255     <
 256         bool PassIter, typename F, typename Geom, typename Iterator,
 257         std::enable_if_t<! util::is_geometry_collection<Geom>::value && ! PassIter, int> = 0
 258     >
 259     static bool visit_or_enqueue(F & f, Geom && g, std::deque<Iterator> & , Iterator)
 260     {
 261         return f(std::forward<Geom>(g));
 262     }
 263     template
 264     <
 265         bool PassIter, typename F, typename Geom, typename Iterator,
 266         std::enable_if_t<! util::is_geometry_collection<Geom>::value && PassIter, int> = 0
 267     >
 268     static bool visit_or_enqueue(F & f, Geom && g, std::deque<Iterator> & , Iterator iter)
 269     {
 270         return f(std::forward<Geom>(g), iter);
 271     }
 272
 273     template
 274     <
 275         typename Geom, typename Iterator,
 276         std::enable_if_t<util::is_geometry_collection<Geom>::value, int> = 0
 277     >
 278     static void set_iterators(Geom && g, Iterator & first, Iterator & last)
 279     {
 280         first = Iterator{ boost::begin(g) };
 281         last = Iterator{ boost::end(g) };
 282     }
 283     template
 284     <
 285         typename Geom, typename Iterator,
 286         std::enable_if_t<! util::is_geometry_collection<Geom>::value, int> = 0
 287     >
 288     static void set_iterators(Geom &&, Iterator &, Iterator &)
 289     {}
 290 };
 291
 292 } // namespace detail
 293 #endif // DOXYGEN_NO_DETAIL
 294
 295
 296 #ifndef DOXYGEN_NO_DISPATCH
 297 namespace dispatch
 298 {
 299
 300 // NOTE: This specialization works partially like std::visit and partially like
 301 //   std::ranges::for_each. If the argument is rvalue reference then the elements
 302 //   are passed into the function as rvalue references as well. This is consistent
 303 //   with std::visit but different than std::ranges::for_each. It's done this way
 304 //   because visit_breadth_first is also specialized for static and dynamic geometries
 305 //   and references for them has to be propagated like that. If this is not
 306 //   desireable then the support for other kinds of geometries should be dropped and
 307 //   this algorithm should work only for geometry collection. Or forwarding of rvalue
 308 //   references should simply be dropped entirely.
 309 //   This is not a problem right now because only non-rvalue references are passed
 310 //   but in the future there might be some issues. Consider e.g. passing a temporary
 311 //   mutable proxy range as geometry collection. In such case the elements would be
 312 //   passed as rvalue references which would be incorrect.
 313 template <typename Geometry>
 314 struct visit_breadth_first<Geometry, geometry_collection_tag>
 315     : detail::visit_breadth_first_impl<>
 316 {};
 317
 318
 319 } // namespace dispatch
 320 #endif // DOXYGEN_NO_DISPATCH
 321
 322
 323 #ifndef DOXYGEN_NO_DETAIL
 324 namespace detail
 325 {
 326
 327 template <typename UnaryFunction, typename Geometry>
 328 inline void visit(UnaryFunction && function, Geometry && geometry)
 329 {
 330     dispatch::visit_one
 331         <
 332             std::remove_reference_t<Geometry>
 333         >::apply(std::forward<UnaryFunction>(function), std::forward<Geometry>(geometry));
 334 }
 335
 336
 337 template <typename UnaryFunction, typename Geometry1, typename Geometry2>
 338 inline void visit(UnaryFunction && function, Geometry1 && geometry1, Geometry2 && geometry2)
 339 {
 340     dispatch::visit_two
 341         <
 342             std::remove_reference_t<Geometry1>,
 343             std::remove_reference_t<Geometry2>
 344         >::apply(std::forward<UnaryFunction>(function),
 345                  std::forward<Geometry1>(geometry1),
 346                  std::forward<Geometry2>(geometry2));
 347 }
 348
 349
 350 template <typename UnaryFunction, typename Geometry>
 351 inline void visit_breadth_first(UnaryFunction function, Geometry && geometry)
 352 {
 353     dispatch::visit_breadth_first
 354         <
 355             std::remove_reference_t<Geometry>
 356         >::apply(function, std::forward<Geometry>(geometry));
 357 }
 358
 359 } // namespace detail
 360 #endif // DOXYGEN_NO_DETAIL
 361
 362 }} // namespace boost::geometry
 363
 364 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_VISIT_HPP