ceph/src/boost/libs/geometry/include/boost/geometry/views/detail/boundary_view/implementation.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2015, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Menelaos Karavelas, 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_VIEWS_DETAIL_BOUNDARY_VIEW_IMPLEMENTATION_HPP
  11 #define BOOST_GEOMETRY_VIEWS_DETAIL_BOUNDARY_VIEW_IMPLEMENTATION_HPP
  12
  13 #include <cstddef>
  14 #include <algorithm>
  15 #include <iterator>
  16 #include <memory>
  17 #include <new>
  18 #include <utility>
  19 #include <vector>
  20
  21 #include <boost/core/addressof.hpp>
  22 #include <boost/iterator.hpp>
  23 #include <boost/iterator/iterator_facade.hpp>
  24 #include <boost/iterator/iterator_categories.hpp>
  25 #include <boost/mpl/assert.hpp>
  26 #include <boost/mpl/if.hpp>
  27 #include <boost/range.hpp>
  28 #include <boost/type_traits/is_const.hpp>
  29 #include <boost/type_traits/is_convertible.hpp>
  30 #include <boost/type_traits/remove_reference.hpp>
  31
  32 #include <boost/geometry/core/assert.hpp>
  33 #include <boost/geometry/core/closure.hpp>
  34 #include <boost/geometry/core/exterior_ring.hpp>
  35 #include <boost/geometry/core/interior_rings.hpp>
  36 #include <boost/geometry/core/ring_type.hpp>
  37 #include <boost/geometry/core/tags.hpp>
  38
  39 #include <boost/geometry/iterators/flatten_iterator.hpp>
  40
  41 #include <boost/geometry/util/range.hpp>
  42
  43 #include <boost/geometry/views/closeable_view.hpp>
  44
  45 #include <boost/geometry/algorithms/num_interior_rings.hpp>
  46
  47
  48 namespace boost { namespace geometry
  49 {
  50
  51
  52 #ifndef DOXYGEN_NO_DETAIL
  53 namespace detail { namespace boundary_views
  54 {
  55
  56
  57 template
  58 <
  59     typename Polygon,
  60     typename Value = typename ring_type<Polygon>::type,
  61     typename Reference = typename ring_return_type<Polygon>::type,
  62     typename Difference = typename boost::range_difference
  63         <
  64             typename boost::remove_reference
  65                 <
  66                     typename interior_return_type<Polygon>::type
  67                 >::type
  68         >::type
  69 >
  70 class polygon_rings_iterator
  71     : public boost::iterator_facade
  72         <
  73             polygon_rings_iterator<Polygon, Value, Reference, Difference>,
  74             Value,
  75             boost::random_access_traversal_tag,
  76             Reference,
  77             Difference
  78         >
  79 {
  80     typedef typename boost::range_size
  81         <
  82             typename boost::remove_reference
  83                 <
  84                     typename interior_return_type<Polygon>::type
  85                 >::type
  86         >::type size_type;
  87
  88 public:
  89     // default constructor
  90     polygon_rings_iterator()
  91         : m_polygon(NULL)
  92         , m_index(0)
  93     {}
  94
  95     // for begin
  96     polygon_rings_iterator(Polygon& polygon)
  97         : m_polygon(boost::addressof(polygon))
  98         , m_index(0)
  99     {}
 100
 101     // for end
 102     polygon_rings_iterator(Polygon& polygon, bool)
 103         : m_polygon(boost::addressof(polygon))
 104         , m_index(static_cast<size_type>(num_rings(polygon)))
 105     {}
 106
 107     template
 108     <
 109         typename OtherPolygon,
 110         typename OtherValue,
 111         typename OtherReference,
 112         typename OtherDifference
 113     >
 114     polygon_rings_iterator(polygon_rings_iterator
 115                            <
 116                                OtherPolygon,
 117                                OtherValue,
 118                                OtherReference,
 119                                OtherDifference
 120                            > const& other)
 121         : m_polygon(other.m_polygon)
 122         , m_index(other.m_index)
 123     {
 124         static const bool is_convertible
 125             = boost::is_convertible<OtherPolygon, Polygon>::value;
 126
 127         BOOST_MPL_ASSERT_MSG((is_convertible),
 128                              NOT_CONVERTIBLE,
 129                              (types<OtherPolygon>));
 130     }
 131
 132 private:
 133     friend class boost::iterator_core_access;
 134
 135     template
 136     <
 137         typename OtherPolygon,
 138         typename OtherValue,
 139         typename OtherReference,
 140         typename OtherDifference
 141     >
 142     friend class polygon_rings_iterator;
 143
 144
 145     static inline std::size_t num_rings(Polygon const& polygon)
 146     {
 147         return geometry::num_interior_rings(polygon) + 1;
 148     }
 149
 150     inline Reference dereference() const
 151     {
 152         if (m_index == 0)
 153         {
 154             return exterior_ring(*m_polygon);
 155         }
 156         return range::at(interior_rings(*m_polygon), m_index - 1);
 157     }
 158
 159     template
 160     <
 161         typename OtherPolygon,
 162         typename OtherValue,
 163         typename OtherReference,
 164         typename OtherDifference
 165     >
 166     inline bool equal(polygon_rings_iterator
 167                       <
 168                           OtherPolygon,
 169                           OtherValue,
 170                           OtherReference,
 171                           OtherDifference
 172                       > const& other) const
 173     {
 174         BOOST_GEOMETRY_ASSERT(m_polygon == other.m_polygon);
 175         return m_index == other.m_index;
 176     }
 177
 178     inline void increment()
 179     {
 180         ++m_index;
 181     }
 182
 183     inline void decrement()
 184     {
 185         --m_index;
 186     }
 187
 188     template
 189     <
 190         typename OtherPolygon,
 191         typename OtherValue,
 192         typename OtherReference,
 193         typename OtherDifference
 194     >
 195     inline Difference distance_to(polygon_rings_iterator
 196                                   <
 197                                       OtherPolygon,
 198                                       OtherValue,
 199                                       OtherReference,
 200                                       OtherDifference
 201                                   > const& other) const
 202     {
 203         return static_cast<Difference>(other.m_index)
 204             - static_cast<Difference>(m_index);
 205     }
 206
 207     inline void advance(Difference n)
 208     {
 209         m_index += n;
 210     }
 211
 212 private:
 213     Polygon* m_polygon;
 214     size_type m_index;
 215 };
 216
 217
 218 template <typename Ring>
 219 class ring_boundary : closeable_view<Ring, closure<Ring>::value>::type
 220 {
 221 private:
 222     typedef typename closeable_view<Ring, closure<Ring>::value>::type base_type;
 223
 224 public:
 225     typedef typename base_type::iterator iterator;
 226     typedef typename base_type::const_iterator const_iterator;
 227
 228     typedef linestring_tag tag_type;
 229
 230     explicit ring_boundary(Ring& ring)
 231         : base_type(ring) {}
 232
 233     iterator begin() { return base_type::begin(); }
 234     iterator end() { return base_type::end(); }
 235     const_iterator begin() const { return base_type::begin(); }
 236     const_iterator end() const { return base_type::end(); }
 237 };
 238
 239
 240 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
 241 struct num_rings
 242 {};
 243
 244 template <typename Polygon>
 245 struct num_rings<Polygon, polygon_tag>
 246 {
 247     static inline std::size_t apply(Polygon const& polygon)
 248     {
 249         return geometry::num_interior_rings(polygon) + 1;
 250     }
 251 };
 252
 253 template <typename MultiPolygon>
 254 struct num_rings<MultiPolygon, multi_polygon_tag>
 255 {
 256     static inline std::size_t apply(MultiPolygon const& multipolygon)
 257     {
 258         return geometry::num_interior_rings(multipolygon)
 259             + static_cast<std::size_t>(boost::size(multipolygon));
 260     }
 261 };
 262
 263
 264 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
 265 struct views_container_initializer
 266 {};
 267
 268 template <typename Polygon>
 269 struct views_container_initializer<Polygon, polygon_tag>
 270 {
 271     template <typename BoundaryView>
 272     static inline void apply(Polygon const& polygon, BoundaryView* views)
 273     {
 274         typedef polygon_rings_iterator<Polygon> rings_iterator_type;
 275
 276         std::uninitialized_copy(rings_iterator_type(polygon),
 277                                 rings_iterator_type(polygon, true),
 278                                 views);
 279     }
 280 };
 281
 282 template <typename MultiPolygon>
 283 class views_container_initializer<MultiPolygon, multi_polygon_tag>
 284 {
 285     typedef typename boost::mpl::if_
 286         <
 287             boost::is_const<MultiPolygon>,
 288             typename boost::range_value<MultiPolygon>::type const,
 289             typename boost::range_value<MultiPolygon>::type
 290         >::type polygon_type;
 291
 292     typedef polygon_rings_iterator<polygon_type> inner_iterator_type;
 293
 294     struct polygon_rings_begin
 295     {
 296         static inline inner_iterator_type apply(polygon_type& polygon)
 297         {
 298             return inner_iterator_type(polygon);
 299         }
 300     };
 301
 302     struct polygon_rings_end
 303     {
 304         static inline inner_iterator_type apply(polygon_type& polygon)
 305         {
 306             return inner_iterator_type(polygon, true);
 307         }
 308     };
 309
 310     typedef flatten_iterator
 311         <
 312             typename boost::range_iterator<MultiPolygon>::type,
 313             inner_iterator_type,
 314             typename std::iterator_traits<inner_iterator_type>::value_type,
 315             polygon_rings_begin,
 316             polygon_rings_end,
 317             typename std::iterator_traits<inner_iterator_type>::reference
 318         > rings_iterator_type;
 319
 320 public:
 321     template <typename BoundaryView>
 322     static inline void apply(MultiPolygon const& multipolygon,
 323                              BoundaryView* views)
 324     {
 325         rings_iterator_type first(boost::begin(multipolygon),
 326                                   boost::end(multipolygon));
 327         rings_iterator_type last(boost::end(multipolygon));
 328
 329         std::uninitialized_copy(first, last, views);
 330     }
 331 };
 332
 333
 334 template <typename Areal>
 335 class areal_boundary
 336 {
 337     typedef boundary_view<typename ring_type<Areal>::type> boundary_view_type;
 338     typedef views_container_initializer<Areal> exception_safe_initializer;
 339
 340     template <typename T>
 341     struct automatic_deallocator
 342     {
 343         automatic_deallocator(T* ptr) : m_ptr(ptr) {}
 344
 345         ~automatic_deallocator()
 346         {
 347             operator delete(m_ptr);
 348         }
 349
 350         inline void release() { m_ptr = NULL; }
 351
 352         T* m_ptr;
 353     };
 354
 355     inline void initialize_views(Areal const& areal)
 356     {
 357         // initialize number of rings
 358         std::size_t n_rings = num_rings<Areal>::apply(areal);
 359
 360         if (n_rings == 0)
 361         {
 362             return;
 363         }
 364
 365         // allocate dynamic memory
 366         boundary_view_type* views_ptr = static_cast
 367             <
 368                 boundary_view_type*
 369             >(operator new(sizeof(boundary_view_type) * n_rings));
 370
 371         // initialize; if exceptions are thrown by constructors
 372         // they are handled automatically by automatic_deallocator
 373         automatic_deallocator<boundary_view_type> deallocator(views_ptr);
 374         exception_safe_initializer::apply(areal, views_ptr);
 375         deallocator.release();
 376
 377         // now initialize member variables safely
 378         m_views = views_ptr;
 379         m_num_rings = n_rings;
 380     }
 381
 382     // disallow copies and/or assignments
 383     areal_boundary(areal_boundary const&);
 384     areal_boundary& operator=(areal_boundary const&);
 385
 386 public:
 387     typedef boundary_view_type* iterator;
 388     typedef boundary_view_type const* const_iterator;
 389
 390     typedef multi_linestring_tag tag_type;
 391
 392     explicit areal_boundary(Areal& areal)
 393         : m_views(NULL)
 394         , m_num_rings(0)
 395     {
 396         initialize_views(areal);
 397     }
 398
 399     ~areal_boundary()
 400     {
 401         boundary_view_type* last = m_views + m_num_rings;
 402         for (boundary_view_type* it = m_views; it != last; ++it)
 403         {
 404             it->~boundary_view_type();
 405         }
 406         operator delete(m_views);
 407     }
 408
 409     inline iterator begin() { return m_views; }
 410     inline iterator end() { return m_views + m_num_rings; }
 411     inline const_iterator begin() const { return m_views; }
 412     inline const_iterator end() const { return m_views + m_num_rings; }
 413
 414 private:
 415     boundary_view_type* m_views;
 416     std::size_t m_num_rings;
 417 };
 418
 419
 420 }} // namespace detail::boundary_view
 421 #endif // DOXYGEN_NO_DETAIL
 422
 423
 424 #ifndef DOXYGEN_NO_DISPATCH
 425 namespace detail_dispatch
 426 {
 427
 428
 429 template <typename Ring>
 430 struct boundary_view<Ring, ring_tag>
 431     : detail::boundary_views::ring_boundary<Ring>
 432 {
 433     explicit boundary_view(Ring& ring)
 434         : detail::boundary_views::ring_boundary<Ring>(ring)
 435     {}
 436 };
 437
 438 template <typename Polygon>
 439 struct boundary_view<Polygon, polygon_tag>
 440     : detail::boundary_views::areal_boundary<Polygon>
 441 {
 442     explicit boundary_view(Polygon& polygon)
 443         : detail::boundary_views::areal_boundary<Polygon>(polygon)
 444     {}
 445 };
 446
 447 template <typename MultiPolygon>
 448 struct boundary_view<MultiPolygon, multi_polygon_tag>
 449     : detail::boundary_views::areal_boundary<MultiPolygon>
 450 {
 451     explicit boundary_view(MultiPolygon& multipolygon)
 452         : detail::boundary_views::areal_boundary
 453             <
 454                 MultiPolygon
 455             >(multipolygon)
 456     {}
 457 };
 458
 459
 460 } // namespace detail_dispatch
 461 #endif // DOXYGEN_NO_DISPATCH
 462
 463
 464 }} // namespace boost::geometry
 465
 466 #endif // BOOST_GEOMETRY_VIEWS_DETAIL_BOUNDARY_VIEW_IMPLEMENTATION_HPP