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