algorithms/detail/visit.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2021, Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0006
0007 // Licensed under the Boost Software License version 1.0.
0008 // http://www.boost.org/users/license.html
0009
0010 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_VISIT_HPP
0011 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_VISIT_HPP
0012
0013 #include <deque>
0014 #include <iterator>
0015 #include <utility>
0016
0017 #include <boost/range/begin.hpp>
0018 #include <boost/range/end.hpp>
0019
0020 #include <boost/geometry/core/static_assert.hpp>
0021 #include <boost/geometry/core/tag.hpp>
0022 #include <boost/geometry/core/tags.hpp>
0023 #include <boost/geometry/core/visit.hpp>
0024 #include <boost/geometry/util/type_traits.hpp>
0025
0026 namespace boost { namespace geometry
0027 {
0028
0029 #ifndef DOXYGEN_NO_DISPATCH
0030 namespace dispatch
0031 {
0032
0033 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
0034 struct visit_one
0035 {
0036     template <typename F, typename G>
0037     static void apply(F && f, G && g)
0038     {
0039         f(std::forward<G>(g));
0040     }
0041 };
0042
0043 template <typename Geometry>
0044 struct visit_one<Geometry, void>
0045 {
0046     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0047         "Not implemented for this Geometry type.",
0048         Geometry);
0049 };
0050
0051 template <typename Geometry>
0052 struct visit_one<Geometry, dynamic_geometry_tag>
0053 {
0054     template <typename F, typename Geom>
0055     static void apply(F && function, Geom && geom)
0056     {
0057         traits::visit
0058             <
0059                 util::remove_cref_t<Geom>
0060             >::apply(std::forward<F>(function), std::forward<Geom>(geom));
0061     }
0062 };
0063
0064
0065 template
0066 <
0067     typename Geometry1, typename Geometry2,
0068     typename Tag1 = typename tag<Geometry1>::type,
0069     typename Tag2 = typename tag<Geometry2>::type
0070 >
0071 struct visit_two
0072 {
0073     template <typename F, typename G1, typename G2>
0074     static void apply(F && f, G1 && geom1, G2 && geom2)
0075     {
0076         f(std::forward<G1>(geom1), std::forward<G2>(geom2));
0077     }
0078 };
0079
0080 template <typename Geometry1, typename Geometry2, typename Tag2>
0081 struct visit_two<Geometry1, Geometry2, void, Tag2>
0082 {
0083     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0084         "Not implemented for this Geometry1 type.",
0085         Geometry1);
0086 };
0087
0088 template <typename Geometry1, typename Geometry2, typename Tag1>
0089 struct visit_two<Geometry1, Geometry2, Tag1, void>
0090 {
0091     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0092         "Not implemented for this Geometry2 type.",
0093         Geometry2);
0094 };
0095
0096 template <typename Geometry1, typename Geometry2>
0097 struct visit_two<Geometry1, Geometry2, void, void>
0098 {
0099     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0100         "Not implemented for these types.",
0101         Geometry1, Geometry2);
0102 };
0103
0104 template <typename Geometry1, typename Geometry2, typename Tag2>
0105 struct visit_two<Geometry1, Geometry2, dynamic_geometry_tag, Tag2>
0106 {
0107     template <typename F, typename G1, typename G2>
0108     static void apply(F && f, G1 && geom1, G2 && geom2)
0109     {
0110         traits::visit<util::remove_cref_t<G1>>::apply([&](auto && g1)
0111         {
0112             f(std::forward<decltype(g1)>(g1), std::forward<G2>(geom2));
0113         }, std::forward<G1>(geom1));
0114     }
0115 };
0116
0117 template <typename Geometry1, typename Geometry2, typename Tag1>
0118 struct visit_two<Geometry1, Geometry2, Tag1, dynamic_geometry_tag>
0119 {
0120     template <typename F, typename G1, typename G2>
0121     static void apply(F && f, G1 && geom1, G2 && geom2)
0122     {
0123         traits::visit<util::remove_cref_t<G2>>::apply([&](auto && g2)
0124         {
0125             f(std::forward<G1>(geom1), std::forward<decltype(g2)>(g2));
0126         }, std::forward<G2>(geom2));
0127     }
0128 };
0129
0130 template <typename Geometry1, typename Geometry2>
0131 struct visit_two<Geometry1, Geometry2, dynamic_geometry_tag, dynamic_geometry_tag>
0132 {
0133     template <typename F, typename G1, typename G2>
0134     static void apply(F && f, G1 && geom1, G2 && geom2)
0135     {
0136         traits::visit
0137             <
0138                 util::remove_cref_t<G1>, util::remove_cref_t<G2>
0139             >::apply([&](auto && g1, auto && g2)
0140             {
0141                 f(std::forward<decltype(g1)>(g1), std::forward<decltype(g2)>(g2));
0142             }, std::forward<G1>(geom1), std::forward<G2>(geom2));
0143     }
0144 };
0145
0146
0147 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
0148 struct visit_breadth_first
0149 {
0150     template <typename F, typename G>
0151     static bool apply(F f, G && g)
0152     {
0153         return f(std::forward<G>(g));
0154     }
0155 };
0156
0157 template <typename Geometry>
0158 struct visit_breadth_first<Geometry, void>
0159 {
0160     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0161         "Not implemented for this Geometry type.",
0162         Geometry);
0163 };
0164
0165 template <typename Geometry>
0166 struct visit_breadth_first<Geometry, dynamic_geometry_tag>
0167 {
0168     template <typename Geom, typename F>
0169     static bool apply(F function, Geom && geom)
0170     {
0171         bool result = true;
0172         traits::visit<util::remove_cref_t<Geom>>::apply([&](auto && g)
0173         {
0174             result = visit_breadth_first
0175                 <
0176                     std::remove_reference_t<decltype(g)>
0177                 >::apply(function,
0178                          std::forward<decltype(g)>(g));
0179         }, std::forward<Geom>(geom));
0180         return result;
0181     }
0182 };
0183
0184 } // namespace dispatch
0185 #endif // DOXYGEN_NO_DISPATCH
0186
0187
0188 #ifndef DOXYGEN_NO_DETAIL
0189 namespace detail
0190 {
0191
0192 template <bool PassIterator = false>
0193 struct visit_breadth_first_impl
0194 {
0195     template <typename F, typename Geom>
0196     static bool apply(F function, Geom && geom)
0197     {
0198         using iter_t = std::conditional_t
0199             <
0200                 std::is_rvalue_reference<decltype(geom)>::value,
0201                 std::move_iterator<typename boost::range_iterator<Geom>::type>,
0202                 typename boost::range_iterator<Geom>::type
0203             >;
0204
0205         std::deque<iter_t> queue;
0206
0207         iter_t it = iter_t{ boost::begin(geom) };
0208         iter_t end = iter_t{ boost::end(geom) };
0209         for(;;)
0210         {
0211             for (; it != end; ++it)
0212             {
0213                 bool result = true;
0214                 traits::iter_visit<util::remove_cref_t<Geom>>::apply([&](auto && g)
0215                 {
0216                     result = visit_breadth_first_impl::visit_or_enqueue<PassIterator>(
0217                                     function, std::forward<decltype(g)>(g), queue, it);
0218                 }, it);
0219
0220                 if (! result)
0221                 {
0222                     return false;
0223                 }
0224             }
0225
0226             if (queue.empty())
0227             {
0228                 break;
0229             }
0230
0231             // Alternatively store a pointer to GeometryCollection
0232             // so this call can be avoided.
0233             traits::iter_visit<util::remove_cref_t<Geom>>::apply([&](auto && g)
0234             {
0235                 visit_breadth_first_impl::set_iterators(std::forward<decltype(g)>(g), it, end);
0236             }, queue.front());
0237             queue.pop_front();
0238         }
0239
0240         return true;
0241     }
0242
0243 private:
0244     template
0245     <
0246         bool PassIter, typename F, typename Geom, typename Iterator,
0247         std::enable_if_t<util::is_geometry_collection<Geom>::value, int> = 0
0248     >
0249     static bool visit_or_enqueue(F &, Geom &&, std::deque<Iterator> & queue, Iterator iter)
0250     {
0251         queue.push_back(iter);
0252         return true;
0253     }
0254     template
0255     <
0256         bool PassIter, typename F, typename Geom, typename Iterator,
0257         std::enable_if_t<! util::is_geometry_collection<Geom>::value && ! PassIter, int> = 0
0258     >
0259     static bool visit_or_enqueue(F & f, Geom && g, std::deque<Iterator> & , Iterator)
0260     {
0261         return f(std::forward<Geom>(g));
0262     }
0263     template
0264     <
0265         bool PassIter, typename F, typename Geom, typename Iterator,
0266         std::enable_if_t<! util::is_geometry_collection<Geom>::value && PassIter, int> = 0
0267     >
0268     static bool visit_or_enqueue(F & f, Geom && g, std::deque<Iterator> & , Iterator iter)
0269     {
0270         return f(std::forward<Geom>(g), iter);
0271     }
0272
0273     template
0274     <
0275         typename Geom, typename Iterator,
0276         std::enable_if_t<util::is_geometry_collection<Geom>::value, int> = 0
0277     >
0278     static void set_iterators(Geom && g, Iterator & first, Iterator & last)
0279     {
0280         first = Iterator{ boost::begin(g) };
0281         last = Iterator{ boost::end(g) };
0282     }
0283     template
0284     <
0285         typename Geom, typename Iterator,
0286         std::enable_if_t<! util::is_geometry_collection<Geom>::value, int> = 0
0287     >
0288     static void set_iterators(Geom &&, Iterator &, Iterator &)
0289     {}
0290 };
0291
0292 } // namespace detail
0293 #endif // DOXYGEN_NO_DETAIL
0294
0295
0296 #ifndef DOXYGEN_NO_DISPATCH
0297 namespace dispatch
0298 {
0299
0300 // NOTE: This specialization works partially like std::visit and partially like
0301 //   std::ranges::for_each. If the argument is rvalue reference then the elements
0302 //   are passed into the function as rvalue references as well. This is consistent
0303 //   with std::visit but different than std::ranges::for_each. It's done this way
0304 //   because visit_breadth_first is also specialized for static and dynamic geometries
0305 //   and references for them has to be propagated like that. If this is not
0306 //   desireable then the support for other kinds of geometries should be dropped and
0307 //   this algorithm should work only for geometry collection. Or forwarding of rvalue
0308 //   references should simply be dropped entirely.
0309 //   This is not a problem right now because only non-rvalue references are passed
0310 //   but in the future there might be some issues. Consider e.g. passing a temporary
0311 //   mutable proxy range as geometry collection. In such case the elements would be
0312 //   passed as rvalue references which would be incorrect.
0313 template <typename Geometry>
0314 struct visit_breadth_first<Geometry, geometry_collection_tag>
0315     : detail::visit_breadth_first_impl<>
0316 {};
0317
0318
0319 } // namespace dispatch
0320 #endif // DOXYGEN_NO_DISPATCH
0321
0322
0323 #ifndef DOXYGEN_NO_DETAIL
0324 namespace detail
0325 {
0326
0327 template <typename UnaryFunction, typename Geometry>
0328 inline void visit(UnaryFunction && function, Geometry && geometry)
0329 {
0330     dispatch::visit_one
0331         <
0332             std::remove_reference_t<Geometry>
0333         >::apply(std::forward<UnaryFunction>(function), std::forward<Geometry>(geometry));
0334 }
0335
0336
0337 template <typename UnaryFunction, typename Geometry1, typename Geometry2>
0338 inline void visit(UnaryFunction && function, Geometry1 && geometry1, Geometry2 && geometry2)
0339 {
0340     dispatch::visit_two
0341         <
0342             std::remove_reference_t<Geometry1>,
0343             std::remove_reference_t<Geometry2>
0344         >::apply(std::forward<UnaryFunction>(function),
0345                  std::forward<Geometry1>(geometry1),
0346                  std::forward<Geometry2>(geometry2));
0347 }
0348
0349
0350 template <typename UnaryFunction, typename Geometry>
0351 inline void visit_breadth_first(UnaryFunction function, Geometry && geometry)
0352 {
0353     dispatch::visit_breadth_first
0354         <
0355             std::remove_reference_t<Geometry>
0356         >::apply(function, std::forward<Geometry>(geometry));
0357 }
0358
0359 } // namespace detail
0360 #endif // DOXYGEN_NO_DETAIL
0361
0362 }} // namespace boost::geometry
0363
0364 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_VISIT_HPP