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
polygon_rings_iterator()90     polygon_rings_iterator()
91         : m_polygon(NULL)
92         , m_index(0)
93     {}
94 
95     // for begin
polygon_rings_iterator(Polygon & polygon)96     polygon_rings_iterator(Polygon& polygon)
97         : m_polygon(boost::addressof(polygon))
98         , m_index(0)
99     {}
100 
101     // for end
polygon_rings_iterator(Polygon & polygon,bool)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     >
polygon_rings_iterator(polygon_rings_iterator<OtherPolygon,OtherValue,OtherReference,OtherDifference> const & other)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 
num_rings(Polygon const & polygon)145     static inline std::size_t num_rings(Polygon const& polygon)
146     {
147         return geometry::num_interior_rings(polygon) + 1;
148     }
149 
dereference() const150     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     >
equal(polygon_rings_iterator<OtherPolygon,OtherValue,OtherReference,OtherDifference> const & other) const166     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 
increment()178     inline void increment()
179     {
180         ++m_index;
181     }
182 
decrement()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     >
distance_to(polygon_rings_iterator<OtherPolygon,OtherValue,OtherReference,OtherDifference> const & other) const195     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 
advance(Difference n)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 
ring_boundary(Ring & ring)230     explicit ring_boundary(Ring& ring)
231         : base_type(ring) {}
232 
begin()233     iterator begin() { return base_type::begin(); }
end()234     iterator end() { return base_type::end(); }
begin() const235     const_iterator begin() const { return base_type::begin(); }
end() const236     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 {
applyboost::geometry::detail::boundary_views::num_rings247     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 {
applyboost::geometry::detail::boundary_views::num_rings256     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>
applyboost::geometry::detail::boundary_views::views_container_initializer272     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     {
applyboost::geometry::detail::boundary_views::views_container_initializer::polygon_rings_begin296         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     {
applyboost::geometry::detail::boundary_views::views_container_initializer::polygon_rings_end304         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>
apply(MultiPolygon const & multipolygon,BoundaryView * views)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     {
automatic_deallocatorboost::geometry::detail::boundary_views::areal_boundary::automatic_deallocator343         automatic_deallocator(T* ptr) : m_ptr(ptr) {}
344 
~automatic_deallocatorboost::geometry::detail::boundary_views::areal_boundary::automatic_deallocator345         ~automatic_deallocator()
346         {
347             operator delete(m_ptr);
348         }
349 
releaseboost::geometry::detail::boundary_views::areal_boundary::automatic_deallocator350         inline void release() { m_ptr = NULL; }
351 
352         T* m_ptr;
353     };
354 
initialize_views(Areal const & areal)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 
areal_boundary(Areal & areal)392     explicit areal_boundary(Areal& areal)
393         : m_views(NULL)
394         , m_num_rings(0)
395     {
396         initialize_views(areal);
397     }
398 
~areal_boundary()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 
begin()409     inline iterator begin() { return m_views; }
end()410     inline iterator end() { return m_views + m_num_rings; }
begin() const411     inline const_iterator begin() const { return m_views; }
end() const412     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 {
boundary_viewboost::geometry::detail_dispatch::boundary_view433     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 {
boundary_viewboost::geometry::detail_dispatch::boundary_view442     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 {
boundary_viewboost::geometry::detail_dispatch::boundary_view451     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
467