1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
5
6 // This file was modified by Oracle on 2013-2019.
7 // Modifications copyright (c) 2013-2019 Oracle and/or its affiliates.
8
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
14
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_RESULT_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_RESULT_HPP
17
18 #include <cstddef>
19 #include <cstring>
20
21 #include <boost/mpl/assert.hpp>
22 #include <boost/mpl/at.hpp>
23 #include <boost/mpl/begin.hpp>
24 #include <boost/mpl/deref.hpp>
25 #include <boost/mpl/end.hpp>
26 #include <boost/mpl/is_sequence.hpp>
27 #include <boost/mpl/next.hpp>
28 #include <boost/mpl/size.hpp>
29 #include <boost/static_assert.hpp>
30 #include <boost/throw_exception.hpp>
31 #include <boost/tuple/tuple.hpp>
32 #include <boost/type_traits/integral_constant.hpp>
33
34 #include <boost/geometry/core/assert.hpp>
35 #include <boost/geometry/core/coordinate_dimension.hpp>
36 #include <boost/geometry/core/exception.hpp>
37 #include <boost/geometry/util/condition.hpp>
38
39 namespace boost { namespace geometry {
40
41 #ifndef DOXYGEN_NO_DETAIL
42 namespace detail { namespace relate {
43
44 enum field { interior = 0, boundary = 1, exterior = 2 };
45
46 // TODO: IF THE RESULT IS UPDATED WITH THE MAX POSSIBLE VALUE FOR SOME PAIR OF GEOEMTRIES
47 // THE VALUE ALREADY STORED MUSN'T BE CHECKED
48 // update() calls chould be replaced with set() in those cases
49 // but for safety reasons (STATIC_ASSERT) we should check if parameter D is valid and set() doesn't do that
50 // so some additional function could be added, e.g. set_dim()
51
52 // --------------- MATRIX ----------------
53
54 // matrix
55
56 template <std::size_t Height, std::size_t Width = Height>
57 class matrix
58 {
59 public:
60 typedef char value_type;
61 typedef std::size_t size_type;
62 typedef const char * const_iterator;
63 typedef const_iterator iterator;
64
65 static const std::size_t static_width = Width;
66 static const std::size_t static_height = Height;
67 static const std::size_t static_size = Width * Height;
68
matrix()69 inline matrix()
70 {
71 ::memset(m_array, 'F', static_size);
72 }
73
74 template <field F1, field F2>
get() const75 inline char get() const
76 {
77 BOOST_STATIC_ASSERT(F1 < Height && F2 < Width);
78 static const std::size_t index = F1 * Width + F2;
79 BOOST_STATIC_ASSERT(index < static_size);
80 return m_array[index];
81 }
82
83 template <field F1, field F2, char V>
set()84 inline void set()
85 {
86 BOOST_STATIC_ASSERT(F1 < Height && F2 < Width);
87 static const std::size_t index = F1 * Width + F2;
88 BOOST_STATIC_ASSERT(index < static_size);
89 m_array[index] = V;
90 }
91
operator [](std::size_t index) const92 inline char operator[](std::size_t index) const
93 {
94 BOOST_GEOMETRY_ASSERT(index < static_size);
95 return m_array[index];
96 }
97
begin() const98 inline const_iterator begin() const
99 {
100 return m_array;
101 }
102
end() const103 inline const_iterator end() const
104 {
105 return m_array + static_size;
106 }
107
size()108 inline static std::size_t size()
109 {
110 return static_size;
111 }
112
data() const113 inline const char * data() const
114 {
115 return m_array;
116 }
117
str() const118 inline std::string str() const
119 {
120 return std::string(m_array, static_size);
121 }
122
123 private:
124 char m_array[static_size];
125 };
126
127 // matrix_handler
128
129 template <typename Matrix>
130 class matrix_handler
131 {
132 public:
133 typedef Matrix result_type;
134
135 static const bool interrupt = false;
136
matrix_handler()137 matrix_handler()
138 {}
139
result() const140 result_type const& result() const
141 {
142 return m_matrix;
143 }
144
matrix() const145 result_type const& matrix() const
146 {
147 return m_matrix;
148 }
149
matrix()150 result_type & matrix()
151 {
152 return m_matrix;
153 }
154
155 template <field F1, field F2, char D>
may_update() const156 inline bool may_update() const
157 {
158 BOOST_STATIC_ASSERT('0' <= D && D <= '9');
159
160 char const c = m_matrix.template get<F1, F2>();
161 return D > c || c > '9';
162 }
163
164 template <field F1, field F2, char V>
set()165 inline void set()
166 {
167 static const bool in_bounds = F1 < Matrix::static_height
168 && F2 < Matrix::static_width;
169 typedef boost::integral_constant<bool, in_bounds> in_bounds_t;
170 set_dispatch<F1, F2, V>(in_bounds_t());
171 }
172
173 template <field F1, field F2, char D>
update()174 inline void update()
175 {
176 static const bool in_bounds = F1 < Matrix::static_height
177 && F2 < Matrix::static_width;
178 typedef boost::integral_constant<bool, in_bounds> in_bounds_t;
179 update_dispatch<F1, F2, D>(in_bounds_t());
180 }
181
182 private:
183 template <field F1, field F2, char V>
set_dispatch(integral_constant<bool,true>)184 inline void set_dispatch(integral_constant<bool, true>)
185 {
186 static const std::size_t index = F1 * Matrix::static_width + F2;
187 BOOST_STATIC_ASSERT(index < Matrix::static_size);
188 BOOST_STATIC_ASSERT(('0' <= V && V <= '9') || V == 'T' || V == 'F');
189 m_matrix.template set<F1, F2, V>();
190 }
191 template <field F1, field F2, char V>
set_dispatch(integral_constant<bool,false>)192 inline void set_dispatch(integral_constant<bool, false>)
193 {}
194
195 template <field F1, field F2, char D>
update_dispatch(integral_constant<bool,true>)196 inline void update_dispatch(integral_constant<bool, true>)
197 {
198 static const std::size_t index = F1 * Matrix::static_width + F2;
199 BOOST_STATIC_ASSERT(index < Matrix::static_size);
200 BOOST_STATIC_ASSERT('0' <= D && D <= '9');
201 char const c = m_matrix.template get<F1, F2>();
202 if ( D > c || c > '9')
203 m_matrix.template set<F1, F2, D>();
204 }
205 template <field F1, field F2, char D>
update_dispatch(integral_constant<bool,false>)206 inline void update_dispatch(integral_constant<bool, false>)
207 {}
208
209 Matrix m_matrix;
210 };
211
212 // --------------- RUN-TIME MASK ----------------
213
214 // run-time mask
215
216 template <std::size_t Height, std::size_t Width = Height>
217 class mask
218 {
219 public:
220 static const std::size_t static_width = Width;
221 static const std::size_t static_height = Height;
222 static const std::size_t static_size = Width * Height;
223
mask(const char * s)224 inline mask(const char * s)
225 {
226 char * it = m_array;
227 char * const last = m_array + static_size;
228 for ( ; it != last && *s != '\0' ; ++it, ++s )
229 {
230 char c = *s;
231 check_char(c);
232 *it = c;
233 }
234 if ( it != last )
235 {
236 ::memset(it, '*', last - it);
237 }
238 }
239
mask(const char * s,std::size_t count)240 inline mask(const char * s, std::size_t count)
241 {
242 if ( count > static_size )
243 {
244 count = static_size;
245 }
246 if ( count > 0 )
247 {
248 std::for_each(s, s + count, check_char);
249 ::memcpy(m_array, s, count);
250 }
251 if ( count < static_size )
252 {
253 ::memset(m_array + count, '*', static_size - count);
254 }
255 }
256
257 template <field F1, field F2>
get() const258 inline char get() const
259 {
260 BOOST_STATIC_ASSERT(F1 < Height && F2 < Width);
261 static const std::size_t index = F1 * Width + F2;
262 BOOST_STATIC_ASSERT(index < static_size);
263 return m_array[index];
264 }
265
266 private:
check_char(char c)267 static inline void check_char(char c)
268 {
269 bool const is_valid = c == '*' || c == 'T' || c == 'F'
270 || ( c >= '0' && c <= '9' );
271 if ( !is_valid )
272 {
273 BOOST_THROW_EXCEPTION(geometry::invalid_input_exception());
274 }
275 }
276
277 char m_array[static_size];
278 };
279
280 // interrupt()
281
282 template <typename Mask, bool InterruptEnabled>
283 struct interrupt_dispatch
284 {
285 template <field F1, field F2, char V>
applyboost::geometry::detail::relate::interrupt_dispatch286 static inline bool apply(Mask const&)
287 {
288 return false;
289 }
290 };
291
292 template <typename Mask>
293 struct interrupt_dispatch<Mask, true>
294 {
295 template <field F1, field F2, char V>
applyboost::geometry::detail::relate::interrupt_dispatch296 static inline bool apply(Mask const& mask)
297 {
298 char m = mask.template get<F1, F2>();
299 return check_element<V>(m);
300 }
301
302 template <char V>
check_elementboost::geometry::detail::relate::interrupt_dispatch303 static inline bool check_element(char m)
304 {
305 if ( BOOST_GEOMETRY_CONDITION(V >= '0' && V <= '9') )
306 {
307 return m == 'F' || ( m < V && m >= '0' && m <= '9' );
308 }
309 else if ( BOOST_GEOMETRY_CONDITION(V == 'T') )
310 {
311 return m == 'F';
312 }
313 return false;
314 }
315 };
316
317 template <typename Masks, int I = 0, int N = boost::tuples::length<Masks>::value>
318 struct interrupt_dispatch_tuple
319 {
320 template <field F1, field F2, char V>
applyboost::geometry::detail::relate::interrupt_dispatch_tuple321 static inline bool apply(Masks const& masks)
322 {
323 typedef typename boost::tuples::element<I, Masks>::type mask_type;
324 mask_type const& mask = boost::get<I>(masks);
325 return interrupt_dispatch<mask_type, true>::template apply<F1, F2, V>(mask)
326 && interrupt_dispatch_tuple<Masks, I+1>::template apply<F1, F2, V>(masks);
327 }
328 };
329
330 template <typename Masks, int N>
331 struct interrupt_dispatch_tuple<Masks, N, N>
332 {
333 template <field F1, field F2, char V>
applyboost::geometry::detail::relate::interrupt_dispatch_tuple334 static inline bool apply(Masks const& )
335 {
336 return true;
337 }
338 };
339
340 //template <typename T0, typename T1, typename T2, typename T3, typename T4,
341 // typename T5, typename T6, typename T7, typename T8, typename T9>
342 //struct interrupt_dispatch<boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>, true>
343 //{
344 // typedef boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> mask_type;
345
346 // template <field F1, field F2, char V>
347 // static inline bool apply(mask_type const& mask)
348 // {
349 // return interrupt_dispatch_tuple<mask_type>::template apply<F1, F2, V>(mask);
350 // }
351 //};
352
353 template <typename Head, typename Tail>
354 struct interrupt_dispatch<boost::tuples::cons<Head, Tail>, true>
355 {
356 typedef boost::tuples::cons<Head, Tail> mask_type;
357
358 template <field F1, field F2, char V>
applyboost::geometry::detail::relate::interrupt_dispatch359 static inline bool apply(mask_type const& mask)
360 {
361 return interrupt_dispatch_tuple<mask_type>::template apply<F1, F2, V>(mask);
362 }
363 };
364
365 template <field F1, field F2, char V, bool InterruptEnabled, typename Mask>
interrupt(Mask const & mask)366 inline bool interrupt(Mask const& mask)
367 {
368 return interrupt_dispatch<Mask, InterruptEnabled>
369 ::template apply<F1, F2, V>(mask);
370 }
371
372 // may_update()
373
374 template <typename Mask>
375 struct may_update_dispatch
376 {
377 template <field F1, field F2, char D, typename Matrix>
applyboost::geometry::detail::relate::may_update_dispatch378 static inline bool apply(Mask const& mask, Matrix const& matrix)
379 {
380 BOOST_STATIC_ASSERT('0' <= D && D <= '9');
381
382 char const m = mask.template get<F1, F2>();
383
384 if ( m == 'F' )
385 {
386 return true;
387 }
388 else if ( m == 'T' )
389 {
390 char const c = matrix.template get<F1, F2>();
391 return c == 'F'; // if it's T or between 0 and 9, the result will be the same
392 }
393 else if ( m >= '0' && m <= '9' )
394 {
395 char const c = matrix.template get<F1, F2>();
396 return D > c || c > '9';
397 }
398
399 return false;
400 }
401 };
402
403 template <typename Masks, int I = 0, int N = boost::tuples::length<Masks>::value>
404 struct may_update_dispatch_tuple
405 {
406 template <field F1, field F2, char D, typename Matrix>
applyboost::geometry::detail::relate::may_update_dispatch_tuple407 static inline bool apply(Masks const& masks, Matrix const& matrix)
408 {
409 typedef typename boost::tuples::element<I, Masks>::type mask_type;
410 mask_type const& mask = boost::get<I>(masks);
411 return may_update_dispatch<mask_type>::template apply<F1, F2, D>(mask, matrix)
412 || may_update_dispatch_tuple<Masks, I+1>::template apply<F1, F2, D>(masks, matrix);
413 }
414 };
415
416 template <typename Masks, int N>
417 struct may_update_dispatch_tuple<Masks, N, N>
418 {
419 template <field F1, field F2, char D, typename Matrix>
applyboost::geometry::detail::relate::may_update_dispatch_tuple420 static inline bool apply(Masks const& , Matrix const& )
421 {
422 return false;
423 }
424 };
425
426 //template <typename T0, typename T1, typename T2, typename T3, typename T4,
427 // typename T5, typename T6, typename T7, typename T8, typename T9>
428 //struct may_update_dispatch< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
429 //{
430 // typedef boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> mask_type;
431
432 // template <field F1, field F2, char D, typename Matrix>
433 // static inline bool apply(mask_type const& mask, Matrix const& matrix)
434 // {
435 // return may_update_dispatch_tuple<mask_type>::template apply<F1, F2, D>(mask, matrix);
436 // }
437 //};
438
439 template <typename Head, typename Tail>
440 struct may_update_dispatch< boost::tuples::cons<Head, Tail> >
441 {
442 typedef boost::tuples::cons<Head, Tail> mask_type;
443
444 template <field F1, field F2, char D, typename Matrix>
applyboost::geometry::detail::relate::may_update_dispatch445 static inline bool apply(mask_type const& mask, Matrix const& matrix)
446 {
447 return may_update_dispatch_tuple<mask_type>::template apply<F1, F2, D>(mask, matrix);
448 }
449 };
450
451 template <field F1, field F2, char D, typename Mask, typename Matrix>
may_update(Mask const & mask,Matrix const & matrix)452 inline bool may_update(Mask const& mask, Matrix const& matrix)
453 {
454 return may_update_dispatch<Mask>
455 ::template apply<F1, F2, D>(mask, matrix);
456 }
457
458 // check_matrix()
459
460 template <typename Mask>
461 struct check_dispatch
462 {
463 template <typename Matrix>
applyboost::geometry::detail::relate::check_dispatch464 static inline bool apply(Mask const& mask, Matrix const& matrix)
465 {
466 return per_one<interior, interior>(mask, matrix)
467 && per_one<interior, boundary>(mask, matrix)
468 && per_one<interior, exterior>(mask, matrix)
469 && per_one<boundary, interior>(mask, matrix)
470 && per_one<boundary, boundary>(mask, matrix)
471 && per_one<boundary, exterior>(mask, matrix)
472 && per_one<exterior, interior>(mask, matrix)
473 && per_one<exterior, boundary>(mask, matrix)
474 && per_one<exterior, exterior>(mask, matrix);
475 }
476
477 template <field F1, field F2, typename Matrix>
per_oneboost::geometry::detail::relate::check_dispatch478 static inline bool per_one(Mask const& mask, Matrix const& matrix)
479 {
480 const char mask_el = mask.template get<F1, F2>();
481 const char el = matrix.template get<F1, F2>();
482
483 if ( mask_el == 'F' )
484 {
485 return el == 'F';
486 }
487 else if ( mask_el == 'T' )
488 {
489 return el == 'T' || ( el >= '0' && el <= '9' );
490 }
491 else if ( mask_el >= '0' && mask_el <= '9' )
492 {
493 return el == mask_el;
494 }
495
496 return true;
497 }
498 };
499
500 template <typename Masks, int I = 0, int N = boost::tuples::length<Masks>::value>
501 struct check_dispatch_tuple
502 {
503 template <typename Matrix>
applyboost::geometry::detail::relate::check_dispatch_tuple504 static inline bool apply(Masks const& masks, Matrix const& matrix)
505 {
506 typedef typename boost::tuples::element<I, Masks>::type mask_type;
507 mask_type const& mask = boost::get<I>(masks);
508 return check_dispatch<mask_type>::apply(mask, matrix)
509 || check_dispatch_tuple<Masks, I+1>::apply(masks, matrix);
510 }
511 };
512
513 template <typename Masks, int N>
514 struct check_dispatch_tuple<Masks, N, N>
515 {
516 template <typename Matrix>
applyboost::geometry::detail::relate::check_dispatch_tuple517 static inline bool apply(Masks const&, Matrix const&)
518 {
519 return false;
520 }
521 };
522
523 //template <typename T0, typename T1, typename T2, typename T3, typename T4,
524 // typename T5, typename T6, typename T7, typename T8, typename T9>
525 //struct check_dispatch< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
526 //{
527 // typedef boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> mask_type;
528
529 // template <typename Matrix>
530 // static inline bool apply(mask_type const& mask, Matrix const& matrix)
531 // {
532 // return check_dispatch_tuple<mask_type>::apply(mask, matrix);
533 // }
534 //};
535
536 template <typename Head, typename Tail>
537 struct check_dispatch< boost::tuples::cons<Head, Tail> >
538 {
539 typedef boost::tuples::cons<Head, Tail> mask_type;
540
541 template <typename Matrix>
applyboost::geometry::detail::relate::check_dispatch542 static inline bool apply(mask_type const& mask, Matrix const& matrix)
543 {
544 return check_dispatch_tuple<mask_type>::apply(mask, matrix);
545 }
546 };
547
548 template <typename Mask, typename Matrix>
check_matrix(Mask const & mask,Matrix const & matrix)549 inline bool check_matrix(Mask const& mask, Matrix const& matrix)
550 {
551 return check_dispatch<Mask>::apply(mask, matrix);
552 }
553
554 // matrix_width
555
556 template <typename MatrixOrMask>
557 struct matrix_width
558 {
559 static const std::size_t value = MatrixOrMask::static_width;
560 };
561
562 template <typename Tuple,
563 int I = 0,
564 int N = boost::tuples::length<Tuple>::value>
565 struct matrix_width_tuple
566 {
567 static const std::size_t
568 current = matrix_width<typename boost::tuples::element<I, Tuple>::type>::value;
569 static const std::size_t
570 next = matrix_width_tuple<Tuple, I+1>::value;
571
572 static const std::size_t
573 value = current > next ? current : next;
574 };
575
576 template <typename Tuple, int N>
577 struct matrix_width_tuple<Tuple, N, N>
578 {
579 static const std::size_t value = 0;
580 };
581
582 template <typename Head, typename Tail>
583 struct matrix_width< boost::tuples::cons<Head, Tail> >
584 {
585 static const std::size_t
586 value = matrix_width_tuple< boost::tuples::cons<Head, Tail> >::value;
587 };
588
589 // mask_handler
590
591 template <typename Mask, bool Interrupt>
592 class mask_handler
593 : private matrix_handler
594 <
595 relate::matrix<matrix_width<Mask>::value>
596 >
597 {
598 typedef matrix_handler
599 <
600 relate::matrix<matrix_width<Mask>::value>
601 > base_t;
602
603 public:
604 typedef bool result_type;
605
606 bool interrupt;
607
mask_handler(Mask const & m)608 inline explicit mask_handler(Mask const& m)
609 : interrupt(false)
610 , m_mask(m)
611 {}
612
result() const613 result_type result() const
614 {
615 return !interrupt
616 && check_matrix(m_mask, base_t::matrix());
617 }
618
619 template <field F1, field F2, char D>
may_update() const620 inline bool may_update() const
621 {
622 return detail::relate::may_update<F1, F2, D>(
623 m_mask, base_t::matrix()
624 );
625 }
626
627 template <field F1, field F2, char V>
set()628 inline void set()
629 {
630 if ( relate::interrupt<F1, F2, V, Interrupt>(m_mask) )
631 {
632 interrupt = true;
633 }
634 else
635 {
636 base_t::template set<F1, F2, V>();
637 }
638 }
639
640 template <field F1, field F2, char V>
update()641 inline void update()
642 {
643 if ( relate::interrupt<F1, F2, V, Interrupt>(m_mask) )
644 {
645 interrupt = true;
646 }
647 else
648 {
649 base_t::template update<F1, F2, V>();
650 }
651 }
652
653 private:
654 Mask const& m_mask;
655 };
656
657 // --------------- FALSE MASK ----------------
658
659 struct false_mask {};
660
661 // --------------- COMPILE-TIME MASK ----------------
662
663 // static_check_characters
664 template
665 <
666 typename Seq,
667 typename First = typename boost::mpl::begin<Seq>::type,
668 typename Last = typename boost::mpl::end<Seq>::type
669 >
670 struct static_check_characters
671 : static_check_characters
672 <
673 Seq,
674 typename boost::mpl::next<First>::type
675 >
676 {
677 typedef typename boost::mpl::deref<First>::type type;
678 static const char value = type::value;
679 static const bool is_valid = (value >= '0' && value <= '9')
680 || value == 'T' || value == 'F' || value == '*';
681 BOOST_MPL_ASSERT_MSG((is_valid),
682 INVALID_STATIC_MASK_CHARACTER,
683 (type));
684 };
685
686 template <typename Seq, typename Last>
687 struct static_check_characters<Seq, Last, Last>
688 {};
689
690 // static_mask
691
692 template
693 <
694 typename Seq,
695 std::size_t Height,
696 std::size_t Width = Height
697 >
698 struct static_mask
699 {
700 static const std::size_t static_width = Width;
701 static const std::size_t static_height = Height;
702 static const std::size_t static_size = Width * Height;
703
704 BOOST_STATIC_ASSERT(
705 std::size_t(boost::mpl::size<Seq>::type::value) == static_size);
706
707 template <detail::relate::field F1, detail::relate::field F2>
708 struct static_get
709 {
710 BOOST_STATIC_ASSERT(std::size_t(F1) < static_height);
711 BOOST_STATIC_ASSERT(std::size_t(F2) < static_width);
712
713 static const char value
714 = boost::mpl::at_c<Seq, F1 * static_width + F2>::type::value;
715 };
716
717 private:
718 // check static_mask characters
719 enum { mask_check = sizeof(static_check_characters<Seq>) };
720 };
721
722 // static_should_handle_element
723
724 template <typename StaticMask, field F1, field F2, bool IsSequence>
725 struct static_should_handle_element_dispatch
726 {
727 static const char mask_el = StaticMask::template static_get<F1, F2>::value;
728 static const bool value = mask_el == 'F'
729 || mask_el == 'T'
730 || ( mask_el >= '0' && mask_el <= '9' );
731 };
732
733 template <typename First, typename Last, field F1, field F2>
734 struct static_should_handle_element_sequence
735 {
736 typedef typename boost::mpl::deref<First>::type StaticMask;
737
738 static const bool value
739 = static_should_handle_element_dispatch
740 <
741 StaticMask,
742 F1, F2,
743 boost::mpl::is_sequence<StaticMask>::value
744 >::value
745 || static_should_handle_element_sequence
746 <
747 typename boost::mpl::next<First>::type,
748 Last,
749 F1, F2
750 >::value;
751 };
752
753 template <typename Last, field F1, field F2>
754 struct static_should_handle_element_sequence<Last, Last, F1, F2>
755 {
756 static const bool value = false;
757 };
758
759 template <typename StaticMask, field F1, field F2>
760 struct static_should_handle_element_dispatch<StaticMask, F1, F2, true>
761 {
762 static const bool value
763 = static_should_handle_element_sequence
764 <
765 typename boost::mpl::begin<StaticMask>::type,
766 typename boost::mpl::end<StaticMask>::type,
767 F1, F2
768 >::value;
769 };
770
771 template <typename StaticMask, field F1, field F2>
772 struct static_should_handle_element
773 {
774 static const bool value
775 = static_should_handle_element_dispatch
776 <
777 StaticMask,
778 F1, F2,
779 boost::mpl::is_sequence<StaticMask>::value
780 >::value;
781 };
782
783 // static_interrupt
784
785 template <typename StaticMask, char V, field F1, field F2, bool InterruptEnabled, bool IsSequence>
786 struct static_interrupt_dispatch
787 {
788 static const bool value = false;
789 };
790
791 template <typename StaticMask, char V, field F1, field F2, bool IsSequence>
792 struct static_interrupt_dispatch<StaticMask, V, F1, F2, true, IsSequence>
793 {
794 static const char mask_el = StaticMask::template static_get<F1, F2>::value;
795
796 static const bool value
797 = ( V >= '0' && V <= '9' ) ?
798 ( mask_el == 'F' || ( mask_el < V && mask_el >= '0' && mask_el <= '9' ) ) :
799 ( ( V == 'T' ) ? mask_el == 'F' : false );
800 };
801
802 template <typename First, typename Last, char V, field F1, field F2>
803 struct static_interrupt_sequence
804 {
805 typedef typename boost::mpl::deref<First>::type StaticMask;
806
807 static const bool value
808 = static_interrupt_dispatch
809 <
810 StaticMask,
811 V, F1, F2,
812 true,
813 boost::mpl::is_sequence<StaticMask>::value
814 >::value
815 && static_interrupt_sequence
816 <
817 typename boost::mpl::next<First>::type,
818 Last,
819 V, F1, F2
820 >::value;
821 };
822
823 template <typename Last, char V, field F1, field F2>
824 struct static_interrupt_sequence<Last, Last, V, F1, F2>
825 {
826 static const bool value = true;
827 };
828
829 template <typename StaticMask, char V, field F1, field F2>
830 struct static_interrupt_dispatch<StaticMask, V, F1, F2, true, true>
831 {
832 static const bool value
833 = static_interrupt_sequence
834 <
835 typename boost::mpl::begin<StaticMask>::type,
836 typename boost::mpl::end<StaticMask>::type,
837 V, F1, F2
838 >::value;
839 };
840
841 template <typename StaticMask, char V, field F1, field F2, bool EnableInterrupt>
842 struct static_interrupt
843 {
844 static const bool value
845 = static_interrupt_dispatch
846 <
847 StaticMask,
848 V, F1, F2,
849 EnableInterrupt,
850 boost::mpl::is_sequence<StaticMask>::value
851 >::value;
852 };
853
854 // static_may_update
855
856 template <typename StaticMask, char D, field F1, field F2, bool IsSequence>
857 struct static_may_update_dispatch
858 {
859 static const char mask_el = StaticMask::template static_get<F1, F2>::value;
860 static const int version
861 = mask_el == 'F' ? 0
862 : mask_el == 'T' ? 1
863 : mask_el >= '0' && mask_el <= '9' ? 2
864 : 3;
865
866 template <typename Matrix>
applyboost::geometry::detail::relate::static_may_update_dispatch867 static inline bool apply(Matrix const& matrix)
868 {
869 return apply_dispatch(matrix, integral_constant<int, version>());
870 }
871
872 // mask_el == 'F'
873 template <typename Matrix>
apply_dispatchboost::geometry::detail::relate::static_may_update_dispatch874 static inline bool apply_dispatch(Matrix const& , integral_constant<int, 0>)
875 {
876 return true;
877 }
878 // mask_el == 'T'
879 template <typename Matrix>
apply_dispatchboost::geometry::detail::relate::static_may_update_dispatch880 static inline bool apply_dispatch(Matrix const& matrix, integral_constant<int, 1>)
881 {
882 char const c = matrix.template get<F1, F2>();
883 return c == 'F'; // if it's T or between 0 and 9, the result will be the same
884 }
885 // mask_el >= '0' && mask_el <= '9'
886 template <typename Matrix>
apply_dispatchboost::geometry::detail::relate::static_may_update_dispatch887 static inline bool apply_dispatch(Matrix const& matrix, integral_constant<int, 2>)
888 {
889 char const c = matrix.template get<F1, F2>();
890 return D > c || c > '9';
891 }
892 // else
893 template <typename Matrix>
apply_dispatchboost::geometry::detail::relate::static_may_update_dispatch894 static inline bool apply_dispatch(Matrix const&, integral_constant<int, 3>)
895 {
896 return false;
897 }
898 };
899
900 template <typename First, typename Last, char D, field F1, field F2>
901 struct static_may_update_sequence
902 {
903 typedef typename boost::mpl::deref<First>::type StaticMask;
904
905 template <typename Matrix>
applyboost::geometry::detail::relate::static_may_update_sequence906 static inline bool apply(Matrix const& matrix)
907 {
908 return static_may_update_dispatch
909 <
910 StaticMask,
911 D, F1, F2,
912 boost::mpl::is_sequence<StaticMask>::value
913 >::apply(matrix)
914 || static_may_update_sequence
915 <
916 typename boost::mpl::next<First>::type,
917 Last,
918 D, F1, F2
919 >::apply(matrix);
920 }
921 };
922
923 template <typename Last, char D, field F1, field F2>
924 struct static_may_update_sequence<Last, Last, D, F1, F2>
925 {
926 template <typename Matrix>
applyboost::geometry::detail::relate::static_may_update_sequence927 static inline bool apply(Matrix const& /*matrix*/)
928 {
929 return false;
930 }
931 };
932
933 template <typename StaticMask, char D, field F1, field F2>
934 struct static_may_update_dispatch<StaticMask, D, F1, F2, true>
935 {
936 template <typename Matrix>
applyboost::geometry::detail::relate::static_may_update_dispatch937 static inline bool apply(Matrix const& matrix)
938 {
939 return static_may_update_sequence
940 <
941 typename boost::mpl::begin<StaticMask>::type,
942 typename boost::mpl::end<StaticMask>::type,
943 D, F1, F2
944 >::apply(matrix);
945 }
946 };
947
948 template <typename StaticMask, char D, field F1, field F2>
949 struct static_may_update
950 {
951 template <typename Matrix>
applyboost::geometry::detail::relate::static_may_update952 static inline bool apply(Matrix const& matrix)
953 {
954 return static_may_update_dispatch
955 <
956 StaticMask,
957 D, F1, F2,
958 boost::mpl::is_sequence<StaticMask>::value
959 >::apply(matrix);
960 }
961 };
962
963 // static_check_matrix
964
965 template <typename StaticMask, bool IsSequence>
966 struct static_check_dispatch
967 {
968 template <typename Matrix>
applyboost::geometry::detail::relate::static_check_dispatch969 static inline bool apply(Matrix const& matrix)
970 {
971 return per_one<interior, interior>::apply(matrix)
972 && per_one<interior, boundary>::apply(matrix)
973 && per_one<interior, exterior>::apply(matrix)
974 && per_one<boundary, interior>::apply(matrix)
975 && per_one<boundary, boundary>::apply(matrix)
976 && per_one<boundary, exterior>::apply(matrix)
977 && per_one<exterior, interior>::apply(matrix)
978 && per_one<exterior, boundary>::apply(matrix)
979 && per_one<exterior, exterior>::apply(matrix);
980 }
981
982 template <field F1, field F2>
983 struct per_one
984 {
985 static const char mask_el = StaticMask::template static_get<F1, F2>::value;
986 static const int version
987 = mask_el == 'F' ? 0
988 : mask_el == 'T' ? 1
989 : mask_el >= '0' && mask_el <= '9' ? 2
990 : 3;
991
992 template <typename Matrix>
applyboost::geometry::detail::relate::static_check_dispatch::per_one993 static inline bool apply(Matrix const& matrix)
994 {
995 const char el = matrix.template get<F1, F2>();
996 return apply_dispatch(el, integral_constant<int, version>());
997 }
998
999 // mask_el == 'F'
apply_dispatchboost::geometry::detail::relate::static_check_dispatch::per_one1000 static inline bool apply_dispatch(char el, integral_constant<int, 0>)
1001 {
1002 return el == 'F';
1003 }
1004 // mask_el == 'T'
apply_dispatchboost::geometry::detail::relate::static_check_dispatch::per_one1005 static inline bool apply_dispatch(char el, integral_constant<int, 1>)
1006 {
1007 return el == 'T' || ( el >= '0' && el <= '9' );
1008 }
1009 // mask_el >= '0' && mask_el <= '9'
apply_dispatchboost::geometry::detail::relate::static_check_dispatch::per_one1010 static inline bool apply_dispatch(char el, integral_constant<int, 2>)
1011 {
1012 return el == mask_el;
1013 }
1014 // else
apply_dispatchboost::geometry::detail::relate::static_check_dispatch::per_one1015 static inline bool apply_dispatch(char /*el*/, integral_constant<int, 3>)
1016 {
1017 return true;
1018 }
1019 };
1020 };
1021
1022 template <typename First, typename Last>
1023 struct static_check_sequence
1024 {
1025 typedef typename boost::mpl::deref<First>::type StaticMask;
1026
1027 template <typename Matrix>
applyboost::geometry::detail::relate::static_check_sequence1028 static inline bool apply(Matrix const& matrix)
1029 {
1030 return static_check_dispatch
1031 <
1032 StaticMask,
1033 boost::mpl::is_sequence<StaticMask>::value
1034 >::apply(matrix)
1035 || static_check_sequence
1036 <
1037 typename boost::mpl::next<First>::type,
1038 Last
1039 >::apply(matrix);
1040 }
1041 };
1042
1043 template <typename Last>
1044 struct static_check_sequence<Last, Last>
1045 {
1046 template <typename Matrix>
applyboost::geometry::detail::relate::static_check_sequence1047 static inline bool apply(Matrix const& /*matrix*/)
1048 {
1049 return false;
1050 }
1051 };
1052
1053 template <typename StaticMask>
1054 struct static_check_dispatch<StaticMask, true>
1055 {
1056 template <typename Matrix>
applyboost::geometry::detail::relate::static_check_dispatch1057 static inline bool apply(Matrix const& matrix)
1058 {
1059 return static_check_sequence
1060 <
1061 typename boost::mpl::begin<StaticMask>::type,
1062 typename boost::mpl::end<StaticMask>::type
1063 >::apply(matrix);
1064 }
1065 };
1066
1067 template <typename StaticMask>
1068 struct static_check_matrix
1069 {
1070 template <typename Matrix>
applyboost::geometry::detail::relate::static_check_matrix1071 static inline bool apply(Matrix const& matrix)
1072 {
1073 return static_check_dispatch
1074 <
1075 StaticMask,
1076 boost::mpl::is_sequence<StaticMask>::value
1077 >::apply(matrix);
1078 }
1079 };
1080
1081 // static_mask_handler
1082
1083 template <typename StaticMask, bool Interrupt>
1084 class static_mask_handler
1085 : private matrix_handler< matrix<3> >
1086 {
1087 typedef matrix_handler< relate::matrix<3> > base_type;
1088
1089 public:
1090 typedef bool result_type;
1091
1092 bool interrupt;
1093
static_mask_handler()1094 inline static_mask_handler()
1095 : interrupt(false)
1096 {}
1097
static_mask_handler(StaticMask const &)1098 inline explicit static_mask_handler(StaticMask const& /*dummy*/)
1099 : interrupt(false)
1100 {}
1101
result() const1102 result_type result() const
1103 {
1104 return (!Interrupt || !interrupt)
1105 && static_check_matrix<StaticMask>::apply(base_type::matrix());
1106 }
1107
1108 template <field F1, field F2, char D>
may_update() const1109 inline bool may_update() const
1110 {
1111 return static_may_update<StaticMask, D, F1, F2>::
1112 apply(base_type::matrix());
1113 }
1114
1115 template <field F1, field F2>
expects()1116 static inline bool expects()
1117 {
1118 return static_should_handle_element<StaticMask, F1, F2>::value;
1119 }
1120
1121 template <field F1, field F2, char V>
set()1122 inline void set()
1123 {
1124 static const bool interrupt_c = static_interrupt<StaticMask, V, F1, F2, Interrupt>::value;
1125 static const bool should_handle = static_should_handle_element<StaticMask, F1, F2>::value;
1126 static const int version = interrupt_c ? 0
1127 : should_handle ? 1
1128 : 2;
1129
1130 set_dispatch<F1, F2, V>(integral_constant<int, version>());
1131 }
1132
1133 template <field F1, field F2, char V>
update()1134 inline void update()
1135 {
1136 static const bool interrupt_c = static_interrupt<StaticMask, V, F1, F2, Interrupt>::value;
1137 static const bool should_handle = static_should_handle_element<StaticMask, F1, F2>::value;
1138 static const int version = interrupt_c ? 0
1139 : should_handle ? 1
1140 : 2;
1141
1142 update_dispatch<F1, F2, V>(integral_constant<int, version>());
1143 }
1144
1145 private:
1146 // Interrupt && interrupt
1147 template <field F1, field F2, char V>
set_dispatch(integral_constant<int,0>)1148 inline void set_dispatch(integral_constant<int, 0>)
1149 {
1150 interrupt = true;
1151 }
1152 // else should_handle
1153 template <field F1, field F2, char V>
set_dispatch(integral_constant<int,1>)1154 inline void set_dispatch(integral_constant<int, 1>)
1155 {
1156 base_type::template set<F1, F2, V>();
1157 }
1158 // else
1159 template <field F1, field F2, char V>
set_dispatch(integral_constant<int,2>)1160 inline void set_dispatch(integral_constant<int, 2>)
1161 {}
1162
1163 // Interrupt && interrupt
1164 template <field F1, field F2, char V>
update_dispatch(integral_constant<int,0>)1165 inline void update_dispatch(integral_constant<int, 0>)
1166 {
1167 interrupt = true;
1168 }
1169 // else should_handle
1170 template <field F1, field F2, char V>
update_dispatch(integral_constant<int,1>)1171 inline void update_dispatch(integral_constant<int, 1>)
1172 {
1173 base_type::template update<F1, F2, V>();
1174 }
1175 // else
1176 template <field F1, field F2, char V>
update_dispatch(integral_constant<int,2>)1177 inline void update_dispatch(integral_constant<int, 2>)
1178 {}
1179 };
1180
1181 // --------------- UTIL FUNCTIONS ----------------
1182
1183 // set
1184
1185 template <field F1, field F2, char V, typename Result>
set(Result & res)1186 inline void set(Result & res)
1187 {
1188 res.template set<F1, F2, V>();
1189 }
1190
1191 template <field F1, field F2, char V, bool Transpose>
1192 struct set_dispatch
1193 {
1194 template <typename Result>
applyboost::geometry::detail::relate::set_dispatch1195 static inline void apply(Result & res)
1196 {
1197 res.template set<F1, F2, V>();
1198 }
1199 };
1200
1201 template <field F1, field F2, char V>
1202 struct set_dispatch<F1, F2, V, true>
1203 {
1204 template <typename Result>
applyboost::geometry::detail::relate::set_dispatch1205 static inline void apply(Result & res)
1206 {
1207 res.template set<F2, F1, V>();
1208 }
1209 };
1210
1211 template <field F1, field F2, char V, bool Transpose, typename Result>
set(Result & res)1212 inline void set(Result & res)
1213 {
1214 set_dispatch<F1, F2, V, Transpose>::apply(res);
1215 }
1216
1217 // update
1218
1219 template <field F1, field F2, char D, typename Result>
update(Result & res)1220 inline void update(Result & res)
1221 {
1222 res.template update<F1, F2, D>();
1223 }
1224
1225 template <field F1, field F2, char D, bool Transpose>
1226 struct update_result_dispatch
1227 {
1228 template <typename Result>
applyboost::geometry::detail::relate::update_result_dispatch1229 static inline void apply(Result & res)
1230 {
1231 update<F1, F2, D>(res);
1232 }
1233 };
1234
1235 template <field F1, field F2, char D>
1236 struct update_result_dispatch<F1, F2, D, true>
1237 {
1238 template <typename Result>
applyboost::geometry::detail::relate::update_result_dispatch1239 static inline void apply(Result & res)
1240 {
1241 update<F2, F1, D>(res);
1242 }
1243 };
1244
1245 template <field F1, field F2, char D, bool Transpose, typename Result>
update(Result & res)1246 inline void update(Result & res)
1247 {
1248 update_result_dispatch<F1, F2, D, Transpose>::apply(res);
1249 }
1250
1251 // may_update
1252
1253 template <field F1, field F2, char D, typename Result>
may_update(Result const & res)1254 inline bool may_update(Result const& res)
1255 {
1256 return res.template may_update<F1, F2, D>();
1257 }
1258
1259 template <field F1, field F2, char D, bool Transpose>
1260 struct may_update_result_dispatch
1261 {
1262 template <typename Result>
applyboost::geometry::detail::relate::may_update_result_dispatch1263 static inline bool apply(Result const& res)
1264 {
1265 return may_update<F1, F2, D>(res);
1266 }
1267 };
1268
1269 template <field F1, field F2, char D>
1270 struct may_update_result_dispatch<F1, F2, D, true>
1271 {
1272 template <typename Result>
applyboost::geometry::detail::relate::may_update_result_dispatch1273 static inline bool apply(Result const& res)
1274 {
1275 return may_update<F2, F1, D>(res);
1276 }
1277 };
1278
1279 template <field F1, field F2, char D, bool Transpose, typename Result>
may_update(Result const & res)1280 inline bool may_update(Result const& res)
1281 {
1282 return may_update_result_dispatch<F1, F2, D, Transpose>::apply(res);
1283 }
1284
1285 // result_dimension
1286
1287 template <typename Geometry>
1288 struct result_dimension
1289 {
1290 BOOST_STATIC_ASSERT(geometry::dimension<Geometry>::value >= 0);
1291 static const char value
1292 = ( geometry::dimension<Geometry>::value <= 9 ) ?
1293 ( '0' + geometry::dimension<Geometry>::value ) :
1294 'T';
1295 };
1296
1297 }} // namespace detail::relate
1298 #endif // DOXYGEN_NO_DETAIL
1299
1300 }} // namespace boost::geometry
1301
1302 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_RESULT_HPP
1303