// Boost.Geometry // Copyright (c) 2021, Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // Licensed under the Boost Software License version 1.0. // http://www.boost.org/users/license.html #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_VISIT_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_VISIT_HPP #include <deque> #include <iterator> #include <utility> #include <boost/range/begin.hpp> #include <boost/range/end.hpp> #include <boost/geometry/core/static_assert.hpp> #include <boost/geometry/core/tag.hpp> #include <boost/geometry/core/tags.hpp> #include <boost/geometry/core/visit.hpp> #include <boost/geometry/util/type_traits.hpp> namespace boost { namespace geometry { #ifndef DOXYGEN_NO_DISPATCH namespace dispatch { template <typename Geometry, typename Tag = typename tag<Geometry>::type> struct visit_one { template <typename F, typename G> static void apply(F && f, G && g) { f(std::forward<G>(g)); } }; template <typename Geometry> struct visit_one<Geometry, void> { BOOST_GEOMETRY_STATIC_ASSERT_FALSE( "Not implemented for this Geometry type.", Geometry); }; template <typename Geometry> struct visit_one<Geometry, dynamic_geometry_tag> { template <typename F, typename Geom> static void apply(F && function, Geom && geom) { traits::visit < util::remove_cref_t<Geom> >::apply(std::forward<F>(function), std::forward<Geom>(geom)); } }; template < typename Geometry1, typename Geometry2, typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type > struct visit_two { template <typename F, typename G1, typename G2> static void apply(F && f, G1 && geom1, G2 && geom2) { f(std::forward<G1>(geom1), std::forward<G2>(geom2)); } }; template <typename Geometry1, typename Geometry2, typename Tag2> struct visit_two<Geometry1, Geometry2, void, Tag2> { BOOST_GEOMETRY_STATIC_ASSERT_FALSE( "Not implemented for this Geometry1 type.", Geometry1); }; template <typename Geometry1, typename Geometry2, typename Tag1> struct visit_two<Geometry1, Geometry2, Tag1, void> { BOOST_GEOMETRY_STATIC_ASSERT_FALSE( "Not implemented for this Geometry2 type.", Geometry2); }; template <typename Geometry1, typename Geometry2> struct visit_two<Geometry1, Geometry2, void, void> { BOOST_GEOMETRY_STATIC_ASSERT_FALSE( "Not implemented for these types.", Geometry1, Geometry2); }; template <typename Geometry1, typename Geometry2, typename Tag2> struct visit_two<Geometry1, Geometry2, dynamic_geometry_tag, Tag2> { template <typename F, typename G1, typename G2> static void apply(F && f, G1 && geom1, G2 && geom2) { traits::visit<util::remove_cref_t<G1>>::apply([&](auto && g1) { f(std::forward<decltype(g1)>(g1), std::forward<G2>(geom2)); }, std::forward<G1>(geom1)); } }; template <typename Geometry1, typename Geometry2, typename Tag1> struct visit_two<Geometry1, Geometry2, Tag1, dynamic_geometry_tag> { template <typename F, typename G1, typename G2> static void apply(F && f, G1 && geom1, G2 && geom2) { traits::visit<util::remove_cref_t<G2>>::apply([&](auto && g2) { f(std::forward<G1>(geom1), std::forward<decltype(g2)>(g2)); }, std::forward<G2>(geom2)); } }; template <typename Geometry1, typename Geometry2> struct visit_two<Geometry1, Geometry2, dynamic_geometry_tag, dynamic_geometry_tag> { template <typename F, typename G1, typename G2> static void apply(F && f, G1 && geom1, G2 && geom2) { traits::visit < util::remove_cref_t<G1>, util::remove_cref_t<G2> >::apply([&](auto && g1, auto && g2) { f(std::forward<decltype(g1)>(g1), std::forward<decltype(g2)>(g2)); }, std::forward<G1>(geom1), std::forward<G2>(geom2)); } }; template <typename Geometry, typename Tag = typename tag<Geometry>::type> struct visit_breadth_first { template <typename F, typename G> static bool apply(F f, G && g) { return f(std::forward<G>(g)); } }; template <typename Geometry> struct visit_breadth_first<Geometry, void> { BOOST_GEOMETRY_STATIC_ASSERT_FALSE( "Not implemented for this Geometry type.", Geometry); }; template <typename Geometry> struct visit_breadth_first<Geometry, dynamic_geometry_tag> { template <typename Geom, typename F> static bool apply(F function, Geom && geom) { bool result = true; traits::visit<util::remove_cref_t<Geom>>::apply([&](auto && g) { result = visit_breadth_first < std::remove_reference_t<decltype(g)> >::apply(function, std::forward<decltype(g)>(g)); }, std::forward<Geom>(geom)); return result; } }; } // namespace dispatch #endif // DOXYGEN_NO_DISPATCH #ifndef DOXYGEN_NO_DETAIL namespace detail { template <bool PassIterator = false> struct visit_breadth_first_impl { template <typename F, typename Geom> static bool apply(F function, Geom && geom) { using iter_t = std::conditional_t < std::is_rvalue_reference<decltype(geom)>::value, std::move_iterator<typename boost::range_iterator<Geom>::type>, typename boost::range_iterator<Geom>::type >; std::deque<iter_t> queue; iter_t it = iter_t{ boost::begin(geom) }; iter_t end = iter_t{ boost::end(geom) }; for(;;) { for (; it != end; ++it) { bool result = true; traits::iter_visit<util::remove_cref_t<Geom>>::apply([&](auto && g) { result = visit_breadth_first_impl::visit_or_enqueue<PassIterator>( function, std::forward<decltype(g)>(g), queue, it); }, it); if (! result) { return false; } } if (queue.empty()) { break; } // Alternatively store a pointer to GeometryCollection // so this call can be avoided. traits::iter_visit<util::remove_cref_t<Geom>>::apply([&](auto && g) { visit_breadth_first_impl::set_iterators(std::forward<decltype(g)>(g), it, end); }, queue.front()); queue.pop_front(); } return true; } private: template < bool PassIter, typename F, typename Geom, typename Iterator, std::enable_if_t<util::is_geometry_collection<Geom>::value, int> = 0 > static bool visit_or_enqueue(F &, Geom &&, std::deque<Iterator> & queue, Iterator iter) { queue.push_back(iter); return true; } template < bool PassIter, typename F, typename Geom, typename Iterator, std::enable_if_t<! util::is_geometry_collection<Geom>::value && ! PassIter, int> = 0 > static bool visit_or_enqueue(F & f, Geom && g, std::deque<Iterator> & , Iterator) { return f(std::forward<Geom>(g)); } template < bool PassIter, typename F, typename Geom, typename Iterator, std::enable_if_t<! util::is_geometry_collection<Geom>::value && PassIter, int> = 0 > static bool visit_or_enqueue(F & f, Geom && g, std::deque<Iterator> & , Iterator iter) { return f(std::forward<Geom>(g), iter); } template < typename Geom, typename Iterator, std::enable_if_t<util::is_geometry_collection<Geom>::value, int> = 0 > static void set_iterators(Geom && g, Iterator & first, Iterator & last) { first = Iterator{ boost::begin(g) }; last = Iterator{ boost::end(g) }; } template < typename Geom, typename Iterator, std::enable_if_t<! util::is_geometry_collection<Geom>::value, int> = 0 > static void set_iterators(Geom &&, Iterator &, Iterator &) {} }; } // namespace detail #endif // DOXYGEN_NO_DETAIL #ifndef DOXYGEN_NO_DISPATCH namespace dispatch { // NOTE: This specialization works partially like std::visit and partially like // std::ranges::for_each. If the argument is rvalue reference then the elements // are passed into the function as rvalue references as well. This is consistent // with std::visit but different than std::ranges::for_each. It's done this way // because visit_breadth_first is also specialized for static and dynamic geometries // and references for them has to be propagated like that. If this is not // desireable then the support for other kinds of geometries should be dropped and // this algorithm should work only for geometry collection. Or forwarding of rvalue // references should simply be dropped entirely. // This is not a problem right now because only non-rvalue references are passed // but in the future there might be some issues. Consider e.g. passing a temporary // mutable proxy range as geometry collection. In such case the elements would be // passed as rvalue references which would be incorrect. template <typename Geometry> struct visit_breadth_first<Geometry, geometry_collection_tag> : detail::visit_breadth_first_impl<> {}; } // namespace dispatch #endif // DOXYGEN_NO_DISPATCH #ifndef DOXYGEN_NO_DETAIL namespace detail { template <typename UnaryFunction, typename Geometry> inline void visit(UnaryFunction && function, Geometry && geometry) { dispatch::visit_one < std::remove_reference_t<Geometry> >::apply(std::forward<UnaryFunction>(function), std::forward<Geometry>(geometry)); } template <typename UnaryFunction, typename Geometry1, typename Geometry2> inline void visit(UnaryFunction && function, Geometry1 && geometry1, Geometry2 && geometry2) { dispatch::visit_two < std::remove_reference_t<Geometry1>, std::remove_reference_t<Geometry2> >::apply(std::forward<UnaryFunction>(function), std::forward<Geometry1>(geometry1), std::forward<Geometry2>(geometry2)); } template <typename UnaryFunction, typename Geometry> inline void visit_breadth_first(UnaryFunction function, Geometry && geometry) { dispatch::visit_breadth_first < std::remove_reference_t<Geometry> >::apply(function, std::forward<Geometry>(geometry)); } } // namespace detail #endif // DOXYGEN_NO_DETAIL }} // namespace boost::geometry #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_VISIT_HPP