detail/boundary_view/implementation.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2015-2020 Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0006 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0007
0008 // Licensed under the Boost Software License version 1.0.
0009 // http://www.boost.org/users/license.html
0010
0011 #ifndef BOOST_GEOMETRY_VIEWS_DETAIL_BOUNDARY_VIEW_IMPLEMENTATION_HPP
0012 #define BOOST_GEOMETRY_VIEWS_DETAIL_BOUNDARY_VIEW_IMPLEMENTATION_HPP
0013
0014 #include <cstddef>
0015 #include <algorithm>
0016 #include <iterator>
0017 #include <memory>
0018 #include <new>
0019 #include <type_traits>
0020 #include <utility>
0021 #include <vector>
0022
0023 #include <boost/core/addressof.hpp>
0024 #include <boost/iterator/iterator_facade.hpp>
0025 #include <boost/iterator/iterator_categories.hpp>
0026 #include <boost/range/size.hpp>
0027
0028 #include <boost/geometry/algorithms/num_interior_rings.hpp>
0029 #include <boost/geometry/core/assert.hpp>
0030 #include <boost/geometry/core/closure.hpp>
0031 #include <boost/geometry/core/exterior_ring.hpp>
0032 #include <boost/geometry/core/interior_rings.hpp>
0033 #include <boost/geometry/core/ring_type.hpp>
0034 #include <boost/geometry/core/static_assert.hpp>
0035 #include <boost/geometry/core/tags.hpp>
0036 #include <boost/geometry/iterators/flatten_iterator.hpp>
0037 #include <boost/geometry/util/range.hpp>
0038 #include <boost/geometry/views/closeable_view.hpp>
0039 #include <boost/geometry/views/detail/boundary_view/interface.hpp>
0040
0041
0042 namespace boost { namespace geometry
0043 {
0044
0045
0046 #ifndef DOXYGEN_NO_DETAIL
0047 namespace detail { namespace boundary_views
0048 {
0049
0050
0051 template
0052 <
0053     typename Polygon,
0054     typename Value = ring_type_t<Polygon>,
0055     typename Reference = ring_return_type_t<Polygon>,
0056     typename Difference = typename boost::range_difference
0057         <
0058             std::remove_reference_t<interior_return_type_t<Polygon>>
0059         >::type
0060 >
0061 class polygon_rings_iterator
0062     : public boost::iterator_facade
0063         <
0064             polygon_rings_iterator<Polygon, Value, Reference, Difference>,
0065             Value,
0066             boost::random_access_traversal_tag,
0067             Reference,
0068             Difference
0069         >
0070 {
0071     using size_type = typename boost::range_size
0072         <
0073             std::remove_reference_t<interior_return_type_t<Polygon>>
0074         >::type;
0075
0076 public:
0077     // default constructor
0078     polygon_rings_iterator()
0079         : m_polygon(NULL)
0080         , m_index(0)
0081     {}
0082
0083     // for begin
0084     polygon_rings_iterator(Polygon& polygon)
0085         : m_polygon(boost::addressof(polygon))
0086         , m_index(0)
0087     {}
0088
0089     // for end
0090     polygon_rings_iterator(Polygon& polygon, bool)
0091         : m_polygon(boost::addressof(polygon))
0092         , m_index(static_cast<size_type>(num_rings(polygon)))
0093     {}
0094
0095     template
0096     <
0097         typename OtherPolygon,
0098         typename OtherValue,
0099         typename OtherReference,
0100         typename OtherDifference
0101     >
0102     polygon_rings_iterator(polygon_rings_iterator
0103                            <
0104                                OtherPolygon,
0105                                OtherValue,
0106                                OtherReference,
0107                                OtherDifference
0108                            > const& other)
0109         : m_polygon(other.m_polygon)
0110         , m_index(other.m_index)
0111     {
0112         static const bool is_convertible
0113             = std::is_convertible<OtherPolygon, Polygon>::value;
0114
0115         BOOST_GEOMETRY_STATIC_ASSERT((is_convertible),
0116             "OtherPolygon has to be convertible to Polygon.",
0117             OtherPolygon, Polygon);
0118     }
0119
0120 private:
0121     friend class boost::iterator_core_access;
0122
0123     template
0124     <
0125         typename OtherPolygon,
0126         typename OtherValue,
0127         typename OtherReference,
0128         typename OtherDifference
0129     >
0130     friend class polygon_rings_iterator;
0131
0132
0133     static inline std::size_t num_rings(Polygon const& polygon)
0134     {
0135         return geometry::num_interior_rings(polygon) + 1;
0136     }
0137
0138     inline Reference dereference() const
0139     {
0140         if (m_index == 0)
0141         {
0142             return exterior_ring(*m_polygon);
0143         }
0144         return range::at(interior_rings(*m_polygon), m_index - 1);
0145     }
0146
0147     template
0148     <
0149         typename OtherPolygon,
0150         typename OtherValue,
0151         typename OtherReference,
0152         typename OtherDifference
0153     >
0154     inline bool equal(polygon_rings_iterator
0155                       <
0156                           OtherPolygon,
0157                           OtherValue,
0158                           OtherReference,
0159                           OtherDifference
0160                       > const& other) const
0161     {
0162         BOOST_GEOMETRY_ASSERT(m_polygon == other.m_polygon);
0163         return m_index == other.m_index;
0164     }
0165
0166     inline void increment()
0167     {
0168         ++m_index;
0169     }
0170
0171     inline void decrement()
0172     {
0173         --m_index;
0174     }
0175
0176     template
0177     <
0178         typename OtherPolygon,
0179         typename OtherValue,
0180         typename OtherReference,
0181         typename OtherDifference
0182     >
0183     inline Difference distance_to(polygon_rings_iterator
0184                                   <
0185                                       OtherPolygon,
0186                                       OtherValue,
0187                                       OtherReference,
0188                                       OtherDifference
0189                                   > const& other) const
0190     {
0191         return static_cast<Difference>(other.m_index)
0192             - static_cast<Difference>(m_index);
0193     }
0194
0195     inline void advance(Difference n)
0196     {
0197         m_index += n;
0198     }
0199
0200 private:
0201     Polygon* m_polygon;
0202     size_type m_index;
0203 };
0204
0205
0206 template <typename Ring>
0207 class ring_boundary : closeable_view<Ring, closure<Ring>::value>::type
0208 {
0209 private:
0210     typedef typename closeable_view<Ring, closure<Ring>::value>::type base_type;
0211
0212 public:
0213     typedef typename base_type::iterator iterator;
0214     typedef typename base_type::const_iterator const_iterator;
0215
0216     typedef linestring_tag tag_type;
0217
0218     explicit ring_boundary(Ring& ring)
0219         : base_type(ring) {}
0220
0221     iterator begin() { return base_type::begin(); }
0222     iterator end() { return base_type::end(); }
0223     const_iterator begin() const { return base_type::begin(); }
0224     const_iterator end() const { return base_type::end(); }
0225 };
0226
0227
0228 template <typename Geometry, typename Tag = tag_t<Geometry>>
0229 struct num_rings
0230 {};
0231
0232 template <typename Polygon>
0233 struct num_rings<Polygon, polygon_tag>
0234 {
0235     static inline std::size_t apply(Polygon const& polygon)
0236     {
0237         return geometry::num_interior_rings(polygon) + 1;
0238     }
0239 };
0240
0241 template <typename MultiPolygon>
0242 struct num_rings<MultiPolygon, multi_polygon_tag>
0243 {
0244     static inline std::size_t apply(MultiPolygon const& multipolygon)
0245     {
0246         return geometry::num_interior_rings(multipolygon)
0247             + static_cast<std::size_t>(boost::size(multipolygon));
0248     }
0249 };
0250
0251
0252 template <typename Geometry, typename Tag = tag_t<Geometry>>
0253 struct views_container_initializer
0254 {};
0255
0256 template <typename Polygon>
0257 struct views_container_initializer<Polygon, polygon_tag>
0258 {
0259     template <typename BoundaryView>
0260     static inline void apply(Polygon const& polygon, BoundaryView* views)
0261     {
0262         typedef polygon_rings_iterator<Polygon> rings_iterator_type;
0263
0264         std::uninitialized_copy(rings_iterator_type(polygon),
0265                                 rings_iterator_type(polygon, true),
0266                                 views);
0267     }
0268 };
0269
0270 template <typename MultiPolygon>
0271 class views_container_initializer<MultiPolygon, multi_polygon_tag>
0272 {
0273     typedef std::conditional_t
0274         <
0275             std::is_const<MultiPolygon>::value,
0276             typename boost::range_value<MultiPolygon>::type const,
0277             typename boost::range_value<MultiPolygon>::type
0278         > polygon_type;
0279
0280     typedef polygon_rings_iterator<polygon_type> inner_iterator_type;
0281
0282     struct polygon_rings_begin
0283     {
0284         static inline inner_iterator_type apply(polygon_type& polygon)
0285         {
0286             return inner_iterator_type(polygon);
0287         }
0288     };
0289
0290     struct polygon_rings_end
0291     {
0292         static inline inner_iterator_type apply(polygon_type& polygon)
0293         {
0294             return inner_iterator_type(polygon, true);
0295         }
0296     };
0297
0298     typedef flatten_iterator
0299         <
0300             typename boost::range_iterator<MultiPolygon>::type,
0301             inner_iterator_type,
0302             typename std::iterator_traits<inner_iterator_type>::value_type,
0303             polygon_rings_begin,
0304             polygon_rings_end,
0305             typename std::iterator_traits<inner_iterator_type>::reference
0306         > rings_iterator_type;
0307
0308 public:
0309     template <typename BoundaryView>
0310     static inline void apply(MultiPolygon const& multipolygon,
0311                              BoundaryView* views)
0312     {
0313         rings_iterator_type first(boost::begin(multipolygon),
0314                                   boost::end(multipolygon));
0315         rings_iterator_type last(boost::end(multipolygon));
0316
0317         std::uninitialized_copy(first, last, views);
0318     }
0319 };
0320
0321
0322 template <typename Areal>
0323 class areal_boundary
0324 {
0325     typedef boundary_view<ring_type_t<Areal>> boundary_view_type;
0326     typedef views_container_initializer<Areal> exception_safe_initializer;
0327
0328     template <typename T>
0329     struct automatic_deallocator
0330     {
0331         automatic_deallocator(T* ptr) : m_ptr(ptr) {}
0332
0333         ~automatic_deallocator()
0334         {
0335             operator delete(m_ptr);
0336         }
0337
0338         inline void release() { m_ptr = NULL; }
0339
0340         T* m_ptr;
0341     };
0342
0343     inline void initialize_views(Areal const& areal)
0344     {
0345         // initialize number of rings
0346         std::size_t n_rings = num_rings<Areal>::apply(areal);
0347
0348         if (n_rings == 0)
0349         {
0350             return;
0351         }
0352
0353         // allocate dynamic memory
0354         boundary_view_type* views_ptr = static_cast
0355             <
0356                 boundary_view_type*
0357             >(operator new(sizeof(boundary_view_type) * n_rings));
0358
0359         // initialize; if exceptions are thrown by constructors
0360         // they are handled automatically by automatic_deallocator
0361         automatic_deallocator<boundary_view_type> deallocator(views_ptr);
0362         exception_safe_initializer::apply(areal, views_ptr);
0363         deallocator.release();
0364
0365         // now initialize member variables safely
0366         m_views = views_ptr;
0367         m_num_rings = n_rings;
0368     }
0369
0370     // disallow copies and/or assignments
0371     areal_boundary(areal_boundary const&);
0372     areal_boundary& operator=(areal_boundary const&);
0373
0374 public:
0375     typedef boundary_view_type* iterator;
0376     typedef boundary_view_type const* const_iterator;
0377
0378     typedef multi_linestring_tag tag_type;
0379
0380     explicit areal_boundary(Areal& areal)
0381         : m_views(NULL)
0382         , m_num_rings(0)
0383     {
0384         initialize_views(areal);
0385     }
0386
0387     ~areal_boundary()
0388     {
0389         boundary_view_type* last = m_views + m_num_rings;
0390         for (boundary_view_type* it = m_views; it != last; ++it)
0391         {
0392             it->~boundary_view_type();
0393         }
0394         operator delete(m_views);
0395     }
0396
0397     inline iterator begin() { return m_views; }
0398     inline iterator end() { return m_views + m_num_rings; }
0399     inline const_iterator begin() const { return m_views; }
0400     inline const_iterator end() const { return m_views + m_num_rings; }
0401
0402 private:
0403     boundary_view_type* m_views;
0404     std::size_t m_num_rings;
0405 };
0406
0407
0408 }} // namespace detail::boundary_view
0409 #endif // DOXYGEN_NO_DETAIL
0410
0411
0412 #ifndef DOXYGEN_NO_DISPATCH
0413 namespace detail_dispatch
0414 {
0415
0416
0417 template <typename Ring>
0418 struct boundary_view<Ring, ring_tag>
0419     : detail::boundary_views::ring_boundary<Ring>
0420 {
0421     explicit boundary_view(Ring& ring)
0422         : detail::boundary_views::ring_boundary<Ring>(ring)
0423     {}
0424 };
0425
0426 template <typename Polygon>
0427 struct boundary_view<Polygon, polygon_tag>
0428     : detail::boundary_views::areal_boundary<Polygon>
0429 {
0430     explicit boundary_view(Polygon& polygon)
0431         : detail::boundary_views::areal_boundary<Polygon>(polygon)
0432     {}
0433 };
0434
0435 template <typename MultiPolygon>
0436 struct boundary_view<MultiPolygon, multi_polygon_tag>
0437     : detail::boundary_views::areal_boundary<MultiPolygon>
0438 {
0439     explicit boundary_view(MultiPolygon& multipolygon)
0440         : detail::boundary_views::areal_boundary
0441             <
0442                 MultiPolygon
0443             >(multipolygon)
0444     {}
0445 };
0446
0447
0448 } // namespace detail_dispatch
0449 #endif // DOXYGEN_NO_DISPATCH
0450
0451
0452 }} // namespace boost::geometry
0453
0454 #endif // BOOST_GEOMETRY_VIEWS_DETAIL_BOUNDARY_VIEW_IMPLEMENTATION_HPP