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